You are not logged in. Please login at www.codechef.com to post your questions!

×

CODIE - Editorial

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[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:

$$ \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:

  • 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.

This question is marked "community wiki".

asked 28 Dec '17, 14:45

admin's gravatar image

0★admin ♦♦
17.6k347489517
accept rate: 36%

edited 09 Jan, 17:50

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,788
×180
×77
×70
×61
×5

question asked: 28 Dec '17, 14:45

question was seen: 183 times

last updated: 09 Jan, 17:50