how to solve BUCKETS of december lunchtime 2018 question ?

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

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.

Solution - CodeChef: Practical coding for everyone

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 : CodeChef: Practical coding for everyone

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;
}

Can Anyone point out the mistake with this solution.

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

My solution-- CodeChef: Practical coding for everyone