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)~