PROBLEM LINK:
Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar
DIFFICULTY:
Medium
PREREQUISITES:
Probability
PROBLEM:
A grid of height H * width W is provided with 2 moving characters, Superman and Batman. Superman starts at the top row and can move to any neighbouring cell with which his current cell shares an edge or a corner. Batman starts at the bottom row and can only move one cell left or right, or not at all. Superman tries to reach the cell Batman is on, whereas Batman tries to avoid Superman. Both play optimally. The goal is to find the expected number of moves in which Superman reaches Batman if they start at random positions.
EXPLANATION:
First we realize that for any given starting position, the number of moves can never be less than H-1, since Superman must get down to the bottom row. Now we must determine the behaviour of Superman and Batman. For Batman it is always optimal to keep moving in the direction away from Superman. Note that this can either be left or right. If he hits a wall he will choose to not move at all, since moving towards Superman only means he will be caught earlier. For Superman it is always optimal to keep moving diagonally downwards towards Batman. This sequence can end in 2 ways. If the bottom row is reached, then Superman can simply chase Batman along the row until he hits a wall and is forced to stop. In this situation, the number of moves required is >H-1. If a wall is reached, that means Batman is directly below him. Now even if Batman runs the other way, Superman can reach him optimally by moving diagonally down so that he is directly above Batman again. In this case the number of moves is exactly H-1.
We know that there are M*M unique starting positions, so we can easily come up with an M*M algorithm which analyzes each case in turn, sums up the number of moves over all M*M cases, and print the sum divided by M*M as the answer. This algorithm is O(M^2). Can we do better? Yes we can.
Consider a case where W$<=$H.
You’ll see that for any starting position, the number of moves required is H-1.
Let us focus on cases where W$>$H. Consider the starting position of Superman to be i, and that of Batman to be j.
Now if i$==j** or the difference between them is 1, then Superman catches up to Batman in H-1 moves. So let **j>i+1**. Now recall the optimal movement of Superman. He moves diagonally downwards until the bottom row or a wall is reached. If a wall is reached, then once again only **H-1** moves are required. This occurs when Superman is closer to a wall than he is to the bottom row. If the bottom row is reached, **H-1** moves have been covered already. Now Superman must chase Batman to the end of the row. If Superman starts at position **i**, he reaches the bottom row at position **i+(H-1)**, since he's moving diagonally. Now the additional steps required is till the end of the row, which is **W-(i+(H-1))** Thus the total steps required is **W-(i+(H-1))** + **H-1** which equals **W-i**. You'll notice that this is the case **for ALL j>i+1**. Similarly, if **j<i-1**, a similar procedure is followed. But we can eliminate the hassle of separately calculating this. Why? Because, by symmetry, chasing Batman right from position i requires the same number of steps as chasing Batman left from position **W-$i. Therefore while summing the total moves, we can simply multiply each value by 2. Thus our optimised algorithm becomes:
Pseudo Code 1:
sum = W * W * (H-1) //first add up H-1 moves for all cases
for i in 1 to W-H // we consider W-H cases because only in these cases Superman reaches the bottom row before he reaches a wall
sum = sum + 2*(W-i-1) * (W-i-(H-1)) // W-i-1 is the number of cases when j>i+1
// W-i is the number of moves, we must subtract H-1 from each move because they are already in sum
expectedValue = sum/(W * W)
print sum
Optimisation:
Can we do even better? Yes we can!
Let a = W$-1, b = W-(H-1), n = W-H
What our loop is doing is simply summing up 2(a-i)(b-i) for all i in 1 to n
which is = 2(ab + i^2 - (a+b)i) for all i in 1 to n
= 2(nab + (1^2+2^2+...+n^2) - (a+b) * (1+2+...+n))
= 2(nab + n(n+1)(2n+1)/6 - (a+b) * n * (n+1)/$2)
A final thing to keep in mind, for W$<$H cases the value of n becomes negative. In such a case simply skip the calculation.
There, we have it! An O(1) solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.