Editorial for Back From Summer '19 P2: Straying From God's Light


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

For the first subtask, we can do five-dimensional Breadth First Search (BFS). We can use dist[r][c][D][L][R] to be 1 if it is possible to move to posiiton (r, c) using exactly D down movements, L left movements, and R right movements, and 0 otherwise. The BFS is the classical BFS algorithm, except you should only check the down, left, and right directions, not up.

Time Complexity: \mathcal O(N^5)

For the second subtask, we need a faster algorithm.

Let us assume, for now, that there is always at least one valid path from position (1, 1) to (N, N). Note that since Marcus is not allowed to travel up, he can never increase the number of down movements. He must travel down exactly N-1 times, and thus D = N-1 in every case. Now, we need to find the number times Marcus moves left and right. Note that in the best case, Marcus moves exactly N-1 times right, which is a constant. If Marcus moves one unit left, he must move an extra unit right later on to account for the change in the column. Thus, if Marcus moves x units left, he must move exactly N-1+x units right. Observe that in the optimal solution, you should move left as little times as possible, as moving left increases both the L count and the R count. Also, note that the cost to a position depends solely on the number of right movements.

Thus, to find the optimal solution, we can perform a Breadth First Search (BFS). Let dist[r][c] represent the minimum number of movements in any direction (which is D + L + R). Since D = N-1, R = x, L = N-1+x, we can show that dist[r][c] = N-1 + x + N-1 + x. Rearranging this equation gives us x = \frac{dist[r][c]}{2} - (N-1), which in turn gives us the values we need: D, L, R.

In the case that there is no valid path, we can use another BFS to check if position (N, N) is visited while beginning at position (1, 1).

Time Complexity: \mathcal O(N^2)


Comments

There are no comments at the moment.