 # how to solve BUCKETS of december lunchtime 2018 question ?

#1

Can someone tell me how to solve Choosing from Buckets problem ?

#2

Chosing a ball from bucket have two outcomes -

1. ball has color i
2. ball does not have color i

For first bucket -
Probability that ball has ith color = (No of balls with ith color) / Total balls

for consecutive bucket k -

Case1 - The ball added to bucket k had color i

Probability that new ball taken out of bucket k has ith color = Probability that ball with ith color came out of previous bucket * (1 + count of balls with color i in kth bucket)/ (1 + Total balls in bucket k)

Case2 - The ball added to bucket k did not had color i

Probability that new ball taken out of bucket k has ith color
= (1 - Probability that ball with ith color came out of previous bucket) * (count of balls with color i in kth bucket)/ (1 + Total balls in bucket k)

Total probability = Case1 + case 2

Calculate this for each color for each bucket.

#3

Calculate probability for each color(1 to k) by looping from 1 to n and using simple formula prob*=(prob[i-1](colorcnt+1))/(totalcnt+1) + ((1-prob[i-1])(colorcnt))/(totalcnt+1).

Reason : with probability[i-1] we will get this color from previous lot, and color count in this lot will increase by 1 and with 1-probability[i-1] we will get different color from previous lot and color count in this lot will remain the same whereas total count will increase by 1 in both cases. (For the start prob is simply colorcnt_in_1/total_cnt_of_1 )

For better reference of the above text see this solution : https://www.codechef.com/viewsolution/22121098

#4

see my solution. written in most easy way to understand. solve(x,y) is probability for xth ball color to come out in yth bucket.

``````#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#define ll long long int
#define li long int
using namespace std;

typedef vector<long long int> vi;
typedef pair<ll, ll> pi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define EB emplace_back
#define REP(i, x, y) for(long long int i=x ; i<y ; i++)
#define F first
#define PB push_back
#define S second
#define MP make_pair
#define MT make_tuple
#define INF 9999999
#define MOD 1000000007
ll n=1000,k=1000;
vi sum(n,0);
ll a;

double solve(ll ball_color, ll bucket){

if(bucket==1)
{
double prob= (double)a[ball_color-1]/(double)sum;
return prob;
}
else{

double prob_added = (((double)a[bucket-1][ball_color-1]+1)/((double)sum[bucket-1] +1)) * solve(ball_color,bucket-1);
double prob_not_added =(((double)a[bucket-1][ball_color-1])/((double)sum[bucket-1] +1))*(1-solve(ball_color,bucket-1)) ;

return prob_added+prob_not_added;

}
}

int main()
{
ios::sync_with_stdio(0);

cin>>n>>k;

cout<<setprecision(12)<<fixed;

REP(i,0,n)
{
REP(j,0,k)
{
cin>>a*[j];
sum*+=a*[j];

}

}

REP(i,0,k)
{

cout<< solve(i+1,n) <<" ";
}

return 0;
}``````

#5

Can Anyone point out the mistake with this solution.

https://www.codechef.com/viewsolution/22135717

#6

My solution-- https://www.codechef.com/viewsolution/22135834