Mohan and Magic Boots

The idea for this approach is to divide the problem into subproblems, calculate their answers individually and then merge them for the main problem.
 

Here in this problem, when we are at some point ‘X’ then we calculate the probability to reach point ‘N’ from point ‘X+2’, and then multiply the probability to reach ‘X+2’ (i.e. ‘P/100’) by it. Similarly, we calculate the probability to reach point ‘N’ from point ‘X+3’, and then multiply the probability to reach ‘X+3’ (i.e. ‘(100-P)/100’) by it, Then we add both these probabilities to find the probability to reach point ‘N’ from point ‘X’.
 

Thus the above idea, shows there are two sub-problems involved with every main problem. Thus it can be solved using a recursive algorithm that will return the probability to reach point ‘N’ from that point.

Algorithm:
 

// This function will return the probability to reach point ‘N’ from the index ‘i’.

Double getProbability(I, N, P)

• If ‘I>=N’
  • Return ‘(Double)(I==N)’.
• Initialize the variable ‘ANS’ with the value of ‘(P/100)*getProbability(I+2, N, P)’.
• Add ‘((100-P)/100)*getProbability(I+3, N, P)’ to ‘ANS’.
• Return ‘ANS’.

// The function will return if the magic boots should be worn by Mohan or not.

Int canWear(N, P, X)

• Initialize the variable ‘ANS’ with the value of ‘getProbability(0, N, P)’.
• Initialize the variable ‘minProbability’ with the value of ‘X/100’.
• If ‘ANS > minProbability’
  • Return ‘1’
• Return ‘0’.

The idea for this approach is based on dynamic programming. Let’s suppose we are at point ‘X’ then we either go to point ‘X+2’ with a probability of ‘P/100’ or we go to point ‘X+3’ with a probability of ‘(100-P)/100’ and the same thing happens for point ‘X+2’ and ‘X+3’. Hence it is clearly visible that the main problem can be solved by computing the probability of subproblems and merging them.
 

Now if we try out every possibility by a recursive algorithm without any optimization that would be O(2^N) algorithm. But if we observe there are many overlapping subproblems involved that don’t need to be re-calculated and hence can be memoized. 
 

For e.g. let’s suppose we are at position ‘X’, then we have to calculate answers to subproblems of positions ‘X+2’ and ‘X+3’,

Now, from point ‘X+2’, we have to calculate answers to subproblems of points ‘X+4’ and ‘X+5’.

And from point ‘X+3’, we have to calculate answers to subproblems of points ‘X+5’ and ‘X+6’.

So from this small sample, it is visible that the answer to the subproblem of point ‘X+5’ is calculated twice (i.e. once from point ‘X+2’ and once from point ‘X+3’), but the answer for that will remain the same hence we can memoize it and reduce the exponential time complexity to linear.

Thus we store the probability to reach point ‘N’ from ‘i’, where ‘i’ ∈ ‘[0, N]’. This can be done using memoization.
 

The base case for this algorithm is if we reach a point ‘i>N’ then we don’t need to take into account the probability to reach that point as it is ahead of point ‘N’, and in the case of ‘i=N’ we say the probability is ‘1’, as we are already on the point ‘N’.

Algorithm:

// This function will return the probability to reach point ‘N’ from the index ‘i’.

Double getProbability(i, N, P, DP)

• If ‘i>=N’
  • Return ‘(Double)(i==N)’.
• If ‘DP[i] != -1’
  • Return ‘DP[i]’.
• Initialize the variable ‘ANS’ with the value of ‘(P/100)*getProbability(i+2, N, P, DP)’.
• Add ‘((100-P)/100)*getProbability(i+3, N, P, DP)’ to ‘ANS’.
• Assign ‘DP[i]’ the value of ‘ANS’
• Return ‘DP[i]’.
   

// The function will return if the magic boots should be worn by Mohan or not.

Int canWear(N, P, X)

• Initialize a ‘DP’ array that can store real values of length ‘N+1’ with the initial value of ‘-1’.
• Initialize the variable ‘ANS’ with the value of ‘getProbability(0, N, P, DP)’.
• Initialize the variable ‘minProbability’ with the value of ‘X/100’.
• If ‘ANS > minProbability’
  • Return ‘1’
• Return ‘0’.

The idea for this approach is similar to the memoized DP version, but the only difference is we don’t need a ‘DP’ array of length ‘N+1’, and also ‘DP[i]’ will represent the probability to reach point ‘i’ from ‘0’.

If we observe properly there are only ‘2’ ways to reach some point ‘X’ i.e. either from ‘X-2’ with a probability of ‘P/100’ or from ‘X-3’ with a probability of ‘(100-P)/100’. Hence thus when we iteratively calculate the probability to reach some point ‘X’ we only need to maintain the value of points ‘X-1’, ‘X-2’, and ‘X-3’ (We need to maintain the value of ‘X-1’ because it will be used by point ‘X+1’ in next iteration).

The base case here will be ‘DP[0]’ = ‘1’, ‘DP[1]’ = ‘0’ and ‘DP[2]’ = ‘P/100’.

The transitions will be similar to the previous solution, i.e. 

‘DP[i]’ = ‘DP[i-2]*(P/100)’ + ‘DP[i-3]*((100-P)/100)’.
 

But to make the information useful for further points we remove the ‘i-3’ point and insert the value of point ‘i’ into the end of a list. This can be easily done using deque.
 

Algorithm:
 

// The function will return if the magic boots should be worn by Mohan or not.

Int canWear(N, P, X)

• Initialize a ‘DP’ array that can store real values of length ‘3’ with the initial value of ‘0’.
• Assign ‘DP[0]’ the value of ‘1’.
• Assign ‘DP[2]’ the value of ‘P/100’.
• If ‘N<=2’
  • Return ‘DP[N]’.
• Initialize the variable ‘currAns’ with the value ‘0’.
• Run a for loop from ‘3’ to ‘N’ with a variable named ‘i’.
  • Assign ‘currAns’ the value of ‘DP[1]*(P/100)’.
  • Add ‘DP[0]*((100-P)/100)’ to ‘currAns’.
  • Assign ‘DP[0]’ the value of ‘DP[1]’.
  • Assign ‘DP[1]’ the value of ‘DP[2]’.
  • Assign ‘DP[2]’ the value of ‘currAns’.
• Initialize the variable ‘minProbability’ with the value of ‘X/100’.
• If ‘DP[2] > minProbability’
  • Return ‘1’
• Return ‘0’.