Editorial for TLE '17 Contest 2 P6 - Save Jody!
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 if there are no ways to go to the end.
Time complexity:
In the second subtask, the intended solution is to use DP to calculate the number of paths. From any coordinate in the grid (except ), there are , , , or paths to advance to the right. After some preprocessing, it is possible to compute all of these paths in time.
Try to do this preprocessing in time, time, or time. Afterwards, do the DP in time.
Make sure that an infinite loop does not occur if there are pillars with the same coordinate.
Time complexity:
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 blocks tall and block wide. Also, number these columns from to . Also, say that column is computed if you know the number of ways to go to any particular block in column .
Define the matrix to be an by matrix where is the number of ways to move from to if column is empty. In other words:
Next, calculate until the largest exponent is at least . Since matrix multiplication is and we multiply times, this step is .
Note that is the number of ways to move from to if columns are all empty. So if column is computed, and columns are empty, then you can use to compute column . This can be done in time.
Now we have finished the precomputation, and we want to get the actual answer. Suppose that column is computed (initially, ). 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 time to compute column (although time is okay).
- Otherwise, suppose that columns are empty. You should select matrices so that their exponents sum to . It should take time to use these matrices to compute column .
In the worst case, both of these steps will happen around times, and each is approximately .
After column has been computed, you can find the number of ways to reach column by calculating a sum.
Time complexity:
Comments