Can someone tell me how to solve Choosing from Buckets problem ?
Chosing a ball from bucket have two outcomes -
- ball has color i
- 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.
2 Likes
Calculate probability for each color(1 to k) by looping from 1 to n and using simple formula prob[i]=(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[1] 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
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[1000][1000];
double solve(ll ball_color, ll bucket){
if(bucket==1)
{
double prob= (double)a[0][ball_color-1]/(double)sum[0];
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[i][j];
sum[i]+=a[i][j];
}
}
REP(i,0,k)
{
cout<< solve(i+1,n) <<" ";
}
return 0;
}