Editorial for Art Academy V: Ruin


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: 4fecta

For this problem, let's define the terms "active" and "resting". The active person is the one who caught the most recent painting, and the resting person is the one who did not. For convenience, let us also define a function dist(i, j), which returns the Manhattan distance between the ith and jth painting. At the ith painting, we know that the active person caught the i - 1th painting (by definition). Therefore, the only variables are the position of the current painting and the position of the resting person. We can now use dynamic programming to solve this problem. The state is dp[i][j], which represents the minimum cost to catch the first i paintings where the resting person most recently caught the jth painting. For each dp[i][j], there are two transitions:

  1. The active person catches the current painting. This gives dp[i][j] = \min(dp[i][j], dp[i - 1][j] + dist(i - 1, i)).

  2. The resting person catches the current painting (and becomes the active person), and the active person becomes the resting person. This gives the transition dp[i][i - 1] = \min(dp[i][i - 1], dp[i - 1][j] + dist(j, i)) since we know that the active person, who is now resting, last caught the i - 1th painting.

Our final answer is \min\limits_{0 \le j \le N - 1} dp[N][j].

Note that whether hewmatt10 or his aide is active does not matter except for the first time they catch a painting, since that is the only time their position differs (at the same index). This can be handled in multiple ways, and will be left as an exercise to the reader to test if they understand the solution.

Time Complexity: \mathcal O(N^2)


Comments

There are no comments at the moment.