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.

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

Hope this will help you and others as well

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 + p0*F(x,y,z) + p1*F(x-1,y,z) + p2*F(x+1,y-1,z) + p3*F(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 + p1*F(x-1,y,z) + p2*F(x+1,y-1,z) + p3*F(x,y+1,z-1)

simplifies to:

F(x,y,z) = (p1*F(x-1,y,z) + p2*F(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.

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.

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.

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

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 ??