BUCKETS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi

PREREQUISITES:

DP, Probabilities

QUICK EXPLANATION:

We’re going to use Dynamic Programming. Define p[i][j] = the probability that the ball we pick from the i^{th} bucket is of color j. If we can quickly fill this dp array, the answer will obviously be p[N][j] for each color j.

EXPLANATION:

Let’s use Dynamic Programming. Define p[i][j] as the probability that the ball we pick from the i^{th} bucket is of color j. Also, let’s define sm[i] as the total number of balls in the i^{th} bucket at the beginning. Note that at the i^{th} step, the number of balls in the i^{th} bucket is sm[i]+1 if i > 1 and sm[i] otherwise.
The above explanations lead to a solution to calculate p[i][j] that is as follows:

for i=1, basic knowledge of the probability theory gives us:
p[1][j] = \frac{a[1][j]}{sm[1]}

for i>1, we have:
p[i][j] = (\sum_{w=1, w!=j}^{K} p[i-1][w] \times \frac{a[i][j]}{sm[i]+1}) + p[i-1][j] \times \frac{a[i][j]+1}{sm[i]+1}

we can rewrite the above formula as:
p[i][j] = (\frac{a[i][j]}{sm[i]+1} \times \sum_{w=1, w!=j}^{K} p[i-1][w]) + p[i-1][j] \times \frac{a[i][j]+1}{sm[i]+1}
which based on the additivity axiom is equal to:
p[i][j] = (\frac{a[i][j]}{sm[i]+1} \times (1 - p[i-1][j])) + p[i-1][j] \times \frac{a[i][j]+1}{sm[i]+1}
which can easily be calculated in O(N \times K).

Refer to the editorialist’s code to see the described solution. Note that the code contains some small tricks to make the implementation easier.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here

Editorialist’s solution can be found here.

2

ohh… seems scary after looking at DP tag… though I solved it XD

3

I didn’t understand the question. Was he picking just one ball from bucket i and moving to i+1 OR was he picking all the balls from bucket i and then moving to i+1 ?

4

@dp1priyesh3_3, since I can’t post a comment on your post, I’ll add it here.

It essentially a step-wise process, in step i, you choose a ball from bucket i and then go ahead and place the ball in bucket i + 1. In step i + 1, you pick a ball from bucket i + 1 (this ball can be the one we added in step i too) and place it in bucket i + 2 and so on…

There’s a far simpler solution though I’m not sure if it counts as DP or not. It probably does, but can’t say.

So, essentially we have to compute the average of probability in all possible cases which is the same as calculating the probability in the average case.

So, what would be the average case?

Let’s label some stuff first! It always helps in solving problems.

Let B_i refer to bucket i, a_{i, j} be the number of balls of colour j in B_i and S_i = \sum_{j=1}^k a_{i, j} be the total number of balls in the B_i.

Well, so after step i - 1 what will the distribution of B_i look like? There will clearly be S_{i - 1} possible cases, since we are picking up a ball from B_{i - 1}.

In a_{i - 1, j} of the cases the value of a_{i, j} is increased by 1 and value of a_{i, r} (r \neq j) remains the same.

So, the distribution of color j in the average case will simply be

a_{i, j} + \frac{a_{i - 1, j}}{S_i}.

Now, simply loop this from i = 2 to n. The pseudo-code is:


    <b>for</b> i = 1 to n <b>do</b>
        S[i] := 0
        <b>for</b> j = 1 to k <b>do</b>
            S[i] → S[i] + a[i][j]
    <b>for</b> i = 2 to n <b>do</b>
        <b>for</b> j = 1 to k <b>do</b>
            a[i][j] → a[i][j] + a[i - 1][j]/S[i - 1]
        S[i] → S[i] + 1
    <b>for</b> j = 1 to k <b>do</b>
        print a[n][j]/S[n]

Also, notice the line S_i \to S_i + 1, don’t forget to increment S_i by 1 because we just added a ball.

Here’s my implementation in C++ which is what I submitted during the contest.

Don’t forget that a_{i, j} has to be floating-point. :stuck_out_tongue:

Side-note: If you are looking for a rigorous proof of the average case shenanigans, search for Expected Value and Linearity of Expectation.
Such an obvious statement gives many unexpected results.

Happy New Year!

1 Like