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.
Hope this will help you and others as well :slight_smile:

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

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 :slight_smile:
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.

24 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)

I am talking about this statment.

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.

2 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.
also can you please tell
what about wasted attempts we made . we need to count that too as our answer is always going to be > total no of shusis . isnt it ??