# How to solve this problem?

I recommend you Errichtoâ€™s YouTube channel. He explained this problem here.

I watched it, but did not understand much. Can you elaborate on how we selected the order of the three for loops for the probability part. I think I need to read up on expected values before understanding it further.

Tozan Southparks explains it here.

Here is my attempt to explain the solution in the best possible manner.

First : what really matters is the number of dishes with 0, 1, 2 and 3 sushis and not the order of the dishes.

Number of dishes with 0 sushis is easily determined by N - one - two - three, where one is the number of dishes with 1 sushi and N is the total number of dishes in the input.

Let F(x, y, z) be the expected moves needed for x dishes with 1 sushi, y with 2 and z with 3.

Now in the next move we can pick a dish with 1 sushi with a probability of x/N or p1. we can pick a dish with 2 sushi with a probability of y/N or p2. we can pick a dish with 3 sushi with a probability of z/N or p3. we can pick a dish with 0 sushi with a probability of (N - (x + y + z))/N or p0.

Now try to understand this :
F(x,y,z) = 1 + p0F(x,y,z) + p1F(x-1,y,z) + p2F(x+1,y-1,z) + p3F(x,y+1,z-1)

Here we add a 1 for the current move that we are making.
(Note : if you pick a dish with 3 sushi z decreases but y increases)

This equation now becomes :
(1 - p0) F(x,y,z) = 1 + p1F(x-1,y,z) + p2F(x+1,y-1,z) + p3*F(x,y+1,z-1)

simplifies to:
F(x,y,z) = (p1F(x-1,y,z) + p2F(x+1,y-1,z) + p3*F(x,y+1,z-1))/(1-p0)

This equation can be easily evaluated using dynamic programming
However try and simplify the equation to minimize the number of divisions for higher precision.

Implementation : https://atcoder.jp/contests/dp/submissions/9551520
Let me know if you find something is not clear.

39 Likes

Could you please explain why are we adding 1 in when we pick x y or z ,why other increases?

Because thatâ€™s the expected amount of steps needed to eat all of them next turn. That one move accounts for the turn of reaching the next turn.

(Note : if you pick a dish with 3 sushi z decreases but y increases)

If you eat a sushi from a dish has 3 sushis, then this plate now has 2 sushis. So there is one more plate that has 2 sushis.

3 Likes

Eating a sushi from a dish with 1 sushi makes it a dish with 0 sushi. If you pick a sushi from a dish with X sushi then there will be X-1 sushi left in the dish.

1 Like

Thanks a lot

Sir there is one blip it should be
F(x,y,z) = (1+(p1 F(x-1,y,z) + p2 F(x+1,y-1,z) + p3*F(x,y+1,z-1))/(1-p0)

Thanks for the explanation I finally managed to understand it

1 Like

how someone can think this way . you are genius.