PROBLEM LINK:
Author: Rahim Mammadi
Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Matrix Exponentiation
PROBLEM:
You have a grid of N*M cells. There is a prince located at (0,0) and a princess located at (N-1,M-1). There are minions moving in the grid, each minion has a starting cell and a finishing cell (both must share either the same row or the same column). Each minion moves 1 cell per second towards the target (and when reaches the target returns to the start in the same way).
Each second, the prince can move from his cell to any cell within distance R_1 (Manhattan Distance). Prince cannot move outside the grid nor to a cell with a minion. At some point in time, among all the points that the prince can move to, he chooses one of them equiprobably. The princess moves the same style except that the distance threshold is R_2.
Given T, find the probability that the prince and princess are at the same cell after T steps. Note that they don’t see each other.
Please read this problem from the problem page as it’s more detailed there.
Constraints:
1 \leq N*M \leq 100
1 \leq T \leq 10^9
For each minion, the distance between its starting cell and finishing cell is at most 4.
EXPLANATION:
First of all, let’s assume that T is small enough and try to solve it with dynamic programming.
A very important observation is that the prince’s movement and the princess’s movement are independent. So our answer would be:
P_{prince}(C) denotes the probability that the prince reaches cell C after T seconds.
So let’s assume now that we are solving the problem for one character only as the other is just the same. We are gonna do that using dynamic programming.
What do we really care about in our DP/recursion space?
Clearly, we care about the time counter and the current cell. So a dynamic programming approach of the form dp[T][N][M] can solve this problem easily in complexity O(T*N^2*M^2). If T was small enough it would work.
Transitions in this DP approach are pretty straightforward. For each cell we can iterate through all cells of the grid and check which of them has an accepted distance. And since we know what would be the time counter at the next step we can check whether there’s a minion or not.
Now if you don’t know about matrix exponentiation and how to solve linear recurrences with it. You must read about it before you continue.
Tutorial on solving linear recurrences using matrices
Tutorial on solving DP problems with the above technique
Let’s assume there are no minions in the grid. The matrix of transitions is totally the same at every moment. So for each cell C we can find out which cells can we move to at the next step and set our cell’s C row values. If we can move to K cells, then for each cell we can move to the coefficient will be K^{-1} (Modulo 10^9+7) (read about modular inverse). Otherwise, it’s Zero.
Now if we raise the coefficients matrix to the power T we can figure out easily the probability to reach any cell inside the grid.
Now, how do the minions make our problem harder? That’s because for a fixed cell at a certain moment our next move depends on the minions positioning and it changes from a second to a second.
You can see that the system of minions’ positions has a period of 24 (Why?).
LCM(2*1,2*2,2*3,2*4) = 24 (LCM of all possible minions full trip values).
That means for any t1,t2, if and only if t1 mod 24 equals t2 mod 24 then every minion is in the same cell at both timestamps.
How does that contribute to the solution?
Let’s denote by Mat_i the transitions matrix at a certain moment i. So we know that Mat_i = Mat_{i \, + \, 24 \, * const}
Ans = StartingValMatrix * Mat_0 * Mat_1 * Mat_2 * Mat_3 .... * Mat_{T-1}
Since matrix multiplication is associative we can group each 24 consecutive matrix together.
Mat' = Mat_0 * Mat_1 * Mat_2 * ... * Mat_{23}
Let’s re-write the answer:
Ans = StartingValMatrix * {Mat'}^{T/24} * ( Mat_0 * Mat_1 * Mat_2 * ... *Mat_{T \, mod \, 24 \, -1})
Complexity: O(N^3 * M^3 * log T)
