How to solve this problem?

help
1
2

I recommend you Errichto’s YouTube channel. He explained this problem here.

3

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.

4

Tozan Southparks explains it here.

5

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 : Submission #9551520 - Educational DP Contest
Let me know if you find something is not clear.

39 Likes
6

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

7

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.

8

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

I am talking about this statment.

9

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
10

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
11

Thanks a lot

12

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
13

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

14

Please can u explain why we add this 1 with each step?
Why we need to put the current move while we are expecting it?
Sorry but it’s not clear for me :frowning:

15

One more question please.
why we add the p0f(x,y,z) one time?
isn’t it p0f(x,y,z) + p0^2f(x,y,z) + p^3f(x,y,z) … +p^infinity * f(x,y,z)?