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 if there are no ways to go to the end.

Time complexity: \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), there are 0, 1, 2, or 3 paths to advance to the right. After some preprocessing, it is possible to compute all of these paths in \mathcal O(1) time.

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

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

Time complexity: \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 blocks tall and 1 block wide. Also, number these columns from 0 to L. Also, say that column x is computed if you know the number of ways to go to any particular block in column x.

Define the matrix M to be an H by H matrix where M[i][j] is the number of ways to move from (x,i) to (x+1,j) if column 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 until the largest exponent is at least L. Since matrix multiplication is \mathcal O(H^3) and we multiply \mathcal O(\log L) times, this step is \mathcal O(H^3 \log L).

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

Now we have finished the precomputation, and we want to get the actual answer. Suppose that column x is computed (initially, 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) time to compute column x+1 (although \mathcal O(H^2) time is okay).
  • Otherwise, suppose that columns x+1,\dots,x+k are empty. You should select \mathcal O(\log k) matrices so that their exponents sum to k. It should take \mathcal O(H^2 \log k) time to use these matrices to compute column x+k.

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

After column L has been computed, you can find the number of ways to reach column 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.