CODIE - Editorial

acm17chn
chn17rol
codie
editorial
expected-value
matrix-expo
med-hard

#1

PROBLEM LINK:

Practice

Contest

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*[j] = ext{Total number of paths from } (1, \frac{K}{2}) ext{ 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*[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) imes 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* which is defined as follows:

\begin{bmatrix} dp*[1] \\ dp*[2] \\ \vdots \\ dp*[K] \end{bmatrix}

Note that f* is a K imes 1 matrix. T should have the property that T \cdot f* = f[i + 1]. Thus, T is a K imes 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^{*}* 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* = E^{*}*[\frac{K}{2}]. Note that E* = E^{*}* \cdot v where v is a unit vector with a one at the \frac{K}{2}^{th} row.

Note that E* = 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.


#2

It can be done in O(K.N + N.(b-a)) 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 obstacle-gap at (z,h) if |y-h|<=(z-x),i.e. if at-most all down-right or all up-right movements reach the gap point.
this means the gap point’s path count is unaffected by any points where |y-h|>(z-x), 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(b-a)) time is taken to calculate the number of paths through each obstacle and add them up.
So we get O(N.K + N(b-a)).