Editorial for TLE '17 Contest 2 P6 - Save Jody!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: d

In the first subtask, the intended solution is to use brute force. This can be done recursively.

Make sure that the previous locations are stored, because Fax cannot move to a previous location. Also, make sure that the answer is $0$ ~0~ if there are no ways to go to the end.

Time complexity: $\mathcal O(H^L)$ ~\mathcal O(H^L)~

In the second subtask, the intended solution is to use DP to calculate the number of paths. From any coordinate in the grid (except $x=L$ ~x=L~), there are $0$ ~0~, $1$ ~1~, $2$ ~2~, or $3$ ~3~ paths to advance to the right. After some preprocessing, it is possible to compute all of these paths in $\mathcal O(1)$ ~\mathcal O(1)~ time.

Try to do this preprocessing in $\mathcal O(HL)$ ~\mathcal O(HL)~ time, $\mathcal O(250H)$ ~\mathcal O(250H)~ time, or $\mathcal O(250H^2)$ ~\mathcal O(250H^2)~ time. Afterwards, do the DP in $\mathcal O(HL)$ ~\mathcal O(HL)~ time.

Make sure that an infinite loop does not occur if there are $H$ ~H~ pillars with the same $x$ ~x~ coordinate.

Time complexity: $\mathcal O(HL)$ ~\mathcal O(HL)~

In the third subtask, we will use matrices to help solve the task. For simplicity, define a column to be a part of the grid that is $H$ ~H~ blocks tall and $1$ ~1~ block wide. Also, number these columns from $0$ ~0~ to $L$ ~L~. Also, say that column $x$ ~x~ is computed if you know the number of ways to go to any particular block in column $x$ ~x~.

Define the matrix $M$ ~M~ to be an $H$ ~H~ by $H$ ~H~ matrix where $M[i][j]$ ~M[i][j]~ is the number of ways to move from $(x,i)$ ~(x,i)~ to $(x+1,j)$ ~(x+1,j)~ if column $x+1$ ~x+1~ is empty. In other words:

$\displaystyle M[i][j] = \begin{cases}1 & \text{if }|i-j| \le 1 \\ 0 & \text{if }|i-j| > 1\end{cases}$

Next, calculate $M, M^2, M^4, M^8, \dots$ ~M, M^2, M^4, M^8, \dots~ until the largest exponent is at least $L$ ~L~. Since matrix multiplication is $\mathcal O(H^3)$ ~\mathcal O(H^3)~ and we multiply $\mathcal O(\log L)$ ~\mathcal O(\log L)~ times, this step is $\mathcal O(H^3 \log L)$ ~\mathcal O(H^3 \log L)~.

Note that $M^k[i][j]$ ~M^k[i][j]~ is the number of ways to move from $(x,i)$ ~(x,i)~ to $(x+k,j)$ ~(x+k,j)~ if columns $x+1,\dots,x+k$ ~x+1,\dots,x+k~ are all empty. So if column $x$ ~x~ is computed, and columns $x+1,\dots,x+k$ ~x+1,\dots,x+k~ are empty, then you can use $M^k$ ~M^k~ to compute column $x+k$ ~x+k~. This can be done in $\mathcal O(H^2)$ ~\mathcal O(H^2)~ time.

Now we have finished the precomputation, and we want to get the actual answer. Suppose that column $x$ ~x~ is computed (initially, $x=0$ ~x=0~). You may get the answer by repeatedly applying these steps:

If the next column contains a pillar anywhere, then apply the idea used to solve subtask 2. It should take $\mathcal O(H)$ ~\mathcal O(H)~ time to compute column $x+1$ ~x+1~ (although $\mathcal O(H^2)$ ~\mathcal O(H^2)~ time is okay).
Otherwise, suppose that columns $x+1,\dots,x+k$ ~x+1,\dots,x+k~ are empty. You should select $\mathcal O(\log k)$ ~\mathcal O(\log k)~ matrices so that their exponents sum to $k$ ~k~. It should take $\mathcal O(H^2 \log k)$ ~\mathcal O(H^2 \log k)~ time to use these matrices to compute column $x+k$ ~x+k~.

In the worst case, both of these steps will happen around $250$ ~250~ times, and each $k$ ~k~ is approximately $L/250$ ~L/250~.

After column $L$ ~L~ has been computed, you can find the number of ways to reach column $L$ ~L~ by calculating a sum.

Time complexity: $\mathcal O(H^3 \log L + 250H^2 \log(L/250))$

Comments

There are no comments at the moment.