Thursday 27 October 2016

Spoj IEEEBGAM

Logic:

Problem is not written very well so many people didn't get that simple problem's problem. ;)
So basically problem is that you have N boxes , N White and N black Balls and you need to put all 2N balls in boxes where after putting them all boxes contains at least one ball and you need to find an arrangement where if you pick a box and a ball probability should be maximum for that ball's color is white.
Whenever you think about probability problems just remember that
Px = satisfied samples / Total Samples  ::where Px mean probability of x occur in Total samples
Now here we can see that if one factor is constant and other are change eg. satisfied samples increase or Total samples decreased then our probability will increase.
So Suppose we pick an arrangement where in N - 1 boxes we put 1 white ball  now we have 1 white ball and N black balls put them in last box and find probability of this arrangement
 = 1/1 + 1/1 + 1/1 + ... + N - 1 times + 1/(N + 1)
 = N / (N + 1)
and we can see that this is maximum probability in any arrangement we can get.
if you still in confuse try some examples and try to convince yourself(Most important part in Coding world :) )


Below Code you can see also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
int N;
scanf("%d", &N);
double wh = N;
double ans = wh / (wh + 1);
printf("%.8f\n", ans);
}
    return 0;
}



Happy Coding :)

4 comments:

  1. n-1 + 1/n+1 = n^2/n+1? Right?

    ReplyDelete
  2. by Baye's theorem , probability of selecting each box would also be multiplied with each one of them that is 1/N has to be multiplied.

    ReplyDelete
    Replies
    1. We are not applying baye's theorem over complete set, we are greedily thinking which arrangement is good and then we are finding what is total probability of that solution.

      Delete