PROBLEM LINK:Author: AmirReza PoorAkhavan 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. for $i=1$, basic knowledge of the probability theory gives us: for $i>1$, we have: we can rewrite the above formula as: 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.
This question is marked "community wiki".
asked 28 Dec '18, 22:13

@dp1priyesh3_3, since I can't post a comment on your post, I'll add it here. 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. Let's label some stuff first! It always helps in solving problems. 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}$.
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. Sidenote: 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! answered 01 Jan, 10:13

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 ? answered 31 Dec '18, 22:20

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