BYTES14 - Editorial

Problem Description :
A man is " n " distance away from the home . He needs to reach his home given that he can either 2 or 3 places backwards with the probability " p " for jumping 2 steps backwards and " 1-p " for jumping 3 steps backwards .
Assuming each jump takes 2 sec find the expected time to reach his home .

Problem Type : Medium / DP + Probability

Explanation :

Lets construct a dp array .
dp[0]=0 , dp[1]=2, dp[2]=2 are the base conditions as each jump takes 2 sec.

No we run a loop fom 3 to n and for each state we have the following relation :
dp[i] = (dp[i-2]+2)p + (dp[i-3]+2)(1-p) as we can go 2 steps backward with probability p and 3 jumps backwards with probability 1-p .
Final answer will be dp[n].

Complexity : O(t*n) where " t " is the number of test cases .

Solution : https://ideone.com/UPBbQQ

Related Problems :

Practice : https://www.codechef.com/problems/BYTES14

Contest : https://www.codechef.com/BYTE2016/problems/BYTES14