PROBLEM LINK:Author: Sidhant Bansal PROBLEMYou 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 ycoordinates. You want to find expected number of paths from $(1, \frac{K}{2})$ to $(N, \frac{K}{2})$. PREREQUISITESUsing Matrix Exponentiation to solve linear recurrences. EXPLANATIONAn $O(N^{2}K)$ solutionFirst 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 xcoordinate would have the obstacle. There are $O(n)$ choices for the obstacle. For each xcoordinate, 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 formFor 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: $$ \begin{bmatrix} dp[i][1] \\ dp[i][2] \\ \vdots \\ dp[i][K] \end{bmatrix} $$ 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: $$ \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 \dots & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \dots & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \dots & 0 & 0 \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0 & 0 & 0 & 0 & 0 & 0 \dots & 1 & 1\\ \end{bmatrix} $$ 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:
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.
This question is marked "community wiki".
asked 28 Dec '17, 14:45

It can be done in O(K.N + N.(ba)) time also, no? The states for different obstacle locations don't need to be calculated, a single state suffices. Any point (x,y) can only be on a unique path to obstaclegap at (z,h) if yh<=(zx),i.e. if atmost all downright or all upright movements reach the gap point. this means the gap point's path count is unaffected by any points where yh>(zx), which is to say that for any point(z,h), even if the points that aren't on a path to it are "expanded" it is safe as these points can never "reach and affect" gap point. What I'm getting at is, you only need to calculate the matrix once, which takes O(N.K) time. Then O(N(ba)) time is taken to calculate the number of paths through each obstacle and add them up. So we get O(N.K + N(ba)).
link
This answer is marked "community wiki".
answered 19 Feb, 18:29
