PROBLEM LINK:
Author: Sidhant Bansal
Tester: Zi Song Yeoh
Editorialist: Animesh Fatehpuria
PROBLEM
You are playing flappy bird on a screen of width K and length N, where K \le 50 and N \le 10^9.
In one step you can move either right, up and right or down and right. There is an obstacle at exactly one
x coordinate between 2 and N - 1, where each x has equal probability. An obstacle allows passing only
through some contiguous range (a, b) of y-coordinates.
You want to find expected number of paths from (1, \frac{K}{2}) to (N, \frac{K}{2}).
PREREQUISITES
Using Matrix Exponentiation to solve linear recurrences.
EXPLANATION
An O(N^{2}K) solution
First we try to solve the problem with smaller constraints, say around N \le 1000 and K \le 50. For such constraints, we can iterate over which x-coordinate would have the obstacle. There are O(n) choices for the obstacle. For each x-coordinate, we can use dynamic programming with state dp[i][j] = \text{Total number of paths from } (1, \frac{K}{2}) \text{ to } (i, j). Clearly, this dynamic program has O(NK) states and computing each state takes O(1) since we just
look at the three neighbours of (i, j) i.e. (i - 1, j), (i - 1, j - 1), (i - 1, j + 1) and sum them up to compute dp[i][j]. The only place where the DP differs is when we reach the column with the obstacle. In this case, the cells blocked by the obstacle will have a DP value of zero.
Finally, we can add up all the dp[N][\frac{K}{2}] values that we get for each obstacle coordinate. Let’s call this value S. Then, the answer is \frac{S}{N - 2} since each coordinate between 2 and N - 1 is equiprobable. Thus, this solution is O(N) \times O(NK) = O(N^{2}K).
Representation in matrix form
For this part, we expect that you have some level of familiarity with using matrix exponentiation to optimize dynamic programming. What we’re looking for here is a transition matrix T. Consider the vector f[i] which is defined as follows:
Note that f[i] is a K \times 1 matrix. T should have the property that T \cdot f[i] = f[i + 1]. Thus, T is a K \times K matrix. If (i + 1)^{th} column doesn’t have an obstacle, then T looks as follows:
If the (i + 1)^{th} column does have an obstacle, then the matrix differs a little. Formally, let this matrix be S. Then, all the rows of S that are outside the range (a, b) are zero rows.
Let E^{*}[i] be the final vector that we get when the obstacle is at column i i.e. the f[n] vector when the obstacle
is at column i. Define E[i] = E^{*}[i][\frac{K}{2}]. Note that E[i] = E^{*}[i] \cdot v where v is a unit vector with a one at the \frac{K}{2}^{th} row.
Note that E[i] = T^{N - i} \cdot S \cdot T^{i - 1} \cdot v. The expected number of paths is given by \frac{1}{N - 2} \cdot \sum_{k = 2}^{N - 1} E[k]. So, the problem is essentially to compute this summation efficiently, since N itself can be as large as 10^9.
Optimization to O(K^3 \log^{2}N)
Let P[x] = \sum_{i = 1}^{x} T^{x - i} \cdot S \cdot T^{i - 1}. Note that P[x] is closely related to the answer when N = x, but it counts the first and the last columns (which cannot have obstacles). We must subtract that quantity. So, our desired summation would be (P[x] - (T^{x - 1} \cdot S + S \cdot T^{x - 1})) \cdot v.
Now, we note that P[x] can be computed in O(log^{2} x) matrix multiplications, due to the following properties:
- When x is even then P[x] = P[\frac{x}{2}] \cdot T^{\frac{x}{2}} + T^{\frac{x}{2}} \cdot P[\frac{x}{2}]
- When x is odd then P[x] = P[x - 1] \cdot T + T^{x - 1} \cdot S
Thus, we can use the fast binary exponentiation method to compute P[N] recursively. The recursion tree would have depth O(\log{N}) and each step would do about O(K^3 \log{N}) work, making the total complexity O(K^3 \log^{2}N).
Note that this can further be optimized to O(K^3 \log{N}), but that wasn’t required for this problem.