I need help with a problem from Codersbit 2019 held on 1st September.
There are 4 persons W X Y Z and there is one ball. Each person can pass the ball to any one of the rest 3. Initially the ball is with W. What is the probability that after A number of passes the ball will land back at person W. If the probability is p/q the answer should be (p ^ q-1) mod (10^9 + 7).
0<= A <= 10^5
I believe that the value of p = 3 * (A-1) and q = 3 ^ A but was getting WA. What should be the correct approach to this?
You could use dp for these kind of problems. The number of chances that Person X has after A passes can be calculated from the state A-1 passes. Initialise a A x 4 dp array. dp[0][W] = 1. Since after 0 passes the ball remains with W. Then you could calculate the probability after 1st pass as,
dp[1][W] = dp[0][X] + dp[0][Y] + dp[0][Z]
dp[1][X] = dp[0][W] + dp[0][Y] + dp[0][Z]
dp[1][Y] = dp[0][X] + dp[0][W] + dp[0][Z]
dp[1][Y] = dp[0][X] + dp[0][Y] + dp[0][W]
Repeat these for all passes upto A. dp[A][W] is your answer.