Editorial for TLE '16 Contest 2 P4 - Harambe's Noble Quest


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.

Authors: ZQFMGB12, d

Subtask 1

We simply need to check if Harambe's path must intersect with the guard's sight. Either the single guard is covering the point (0,0) or the guard covers a horizontal range of [0,x_h] or a vertical range of [0,y_h].

Time complexity: \mathcal{O}(1)

Subtask 2

The size of the grid is small, and thus the number of guards is low. Therefore, we can generate all possible paths to the origin, and count the number of guards that need to be taken out.

Time complexity: \mathcal{O}\left(\dbinom{2k}{k} k^3\right) where k = \max(|x_h|,|y_h|).

Subtask 3

The number of guards is low. First, we should reflect all of the points across the x and/or y axis so that Harambe's original point contains non-negative coordinates. Let dp[i][j] be the minimum number of guards that need to be eliminated in order to reach (i,j). Clearly, dp[i][j] = \min(dp[i+1][j] + newGuards(i,j,i+1,j), dp[i][j+1] + newGuards(i,j,i,j+1)). The newGuards(x_1,y_1,x_2,y_2) method counts the number of guards present in (x_1,y_1) but not (x_2,y_2). The answer will be located at dp[0][0].

Time complexity: \mathcal{O}(T X_h Y_h)

Subtask 4

We need to optimize the solution for the previous subtask. Note that the only important event with any guard is when Harambe enters its range. Thus, we only need the top edge and the right edge of each guard's range (remember, the coordinate system is rotated so that Harambe's original point contains non-negative coordinates). We can use two separate arrays/grids to keep the count of top edges and right edges. Now, we can see that dp[i][j] = \min(dp[i+1][j] + top[i][j], dp[i][j+1] + right[i][j]).

Time complexity: \mathcal{O}(TL + X_h Y_h)


Comments

There are no comments at the moment.