You are not logged in. Please login at www.codechef.com to post your questions!

×

how to solve BUCKETS of december lunchtime 2018 question ?

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

asked 30 Dec '18, 00:35

adityaseth1011's gravatar image

3★adityaseth1011
32
accept rate: 0%

edited 30 Dec '18, 00:36


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 - https://www.codechef.com/viewsolution/22129576

link

answered 30 Dec '18, 00:47

masterox's gravatar image

3★masterox
623
accept rate: 0%

edited 30 Dec '18, 00:49

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

link

answered 30 Dec '18, 00:55

lets_see's gravatar image

4★lets_see
1
accept rate: 0%

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

answered 30 Dec '18, 13:12

codesniper99's gravatar image

3★codesniper99
1186
accept rate: 7%

Can Anyone point out the mistake with this solution.

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

link

answered 30 Dec '18, 16:15

prakhar897's gravatar image

4★prakhar897
1
accept rate: 0%

link

answered 30 Dec '18, 16:39

vatsal1998's gravatar image

5★vatsal1998
214
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×550

question asked: 30 Dec '18, 00:35

question was seen: 482 times

last updated: 31 Dec '18, 23:16