The most difficult part in solving this problem is modelling the situation into something more familiar. Although the implementation itself can be quite challenging, we will mainly go over the general logic and intuition behind the solution rather than specifics and implementation.

Subtask 1

In this subtask, there are only at most ~2~ searchers. As such, we can simply try sending each one first or second if there are ~2~ searchers (and for ~1~ there is only one option). Although this simple brute-force approach alone is simple, it is useful to examine the two cases that can arise in order to build intuition for the full solution.

Case 1: Perpendicular

If the ~2~ searchers intersect perpendicularly, then we can notice that either way the same number of cells are searched in the grid until the point of intersection, which we can see in the diagram below (where the dark blue cell shows the cell in which they intersect). The only difference comes from after the point of collision, where we have to consider which searcher ends up visiting more cells. This can help build intuition for the next subtask.

Case 2: Parallel

If the ~2~ searchers go in parallel directions, then we can notice that the order in which we send them does not affect the final answer, as shown in the diagram below. This idea will be useful for later subtasks.

As the grid size is large, we cannot directly simulate the process and instead must handle it through calculations, leading to an overall time complexity of ~\mathcal{O}(1)~.

Subtask 2

In this subtask, we need to extend the perpendicular (which will be referred to as a corner case) to account for multiple searchers. Consider a corner situation like the one shown below. We can use an idea from the perpendicular case in the first subtask, where regardless the order we send two searchers on distinct sides in the corner, the cells visited until the intersection remain the same, forming a box in this case. If we consider what happens when we send a searcher within this enclosed region, such as the one shown with their path in green, we can see that it splits it into ~2~ regions.

On one side, there will be searchers (or possibly none) that simply must go parallel to that searcher and will not interfere with anyone going perpendicular, as the green-pathed searcher closed off any potential intersection. As with the second case from the first subtask, we can see that it doesn't matter the order in which we send them, and so we can just directly send those searchers one by one.

The other side of the green line path is another, smaller corner case. This leads us to consider a dynamic programming approach, as sending any particular person results in a sub-problem corner case along with a gain of cells based on sending that searcher and all parallel searchers cut off on the other side.

More specifically, we can perform dynamic programming over an interval of searchers, as the corner sub-problem is some interval of searchers in clockwise order, with decreasing interval width as we send more searchers. In order to find the optimal next searcher to send, we can loop over all searchers within the current interval and consider sending each one as the next, and choose the best case out of those.

With this interval-based dynamic programming approach and a linear-time transition for looping next potential searchers, we get an overall time complexity of ~\mathcal{O}(N^3)~.

Subtask 3

In this subtask, we must now extend our second subtask approach beyond the corner case. When we send someone initially, they do not create a corner case, but rather they split the grid into ~2~ sections. We will consider just one side of two sections that the grid is split into. Note that the initial searcher could have gone horizontally or vertically across the grid, however the same logic will still apply. In the diagram below, we will assume the initial searcher created the blue path across. At this point, there's ~2~ options left (similar to the first subtask).

Case 1: Perpendicular

If the next searcher is sent perpendicular to the previous searcher, we can observe that this simply splits the grid into ~2~ corner-case regions. We can simply precompute the ~4~ corner cases using the same interval-based dynamic programming approach as the previous subtask and retrieve the value for this. This is shown on the left diagram.

Case 2: Parallel

If the next searcher is sent parallel to the previous searcher, we can see that this simply splits the region into another smaller region that's similar to the initial region. Similar to the previous subtask, one of the sides that this searcher splits the region into becomes closed off to any perpendicular searchers, and so they can be sent in any order. This is shown on the right diagram.

Notice that it doesn't matter if the parallel searcher start from the top or bottom side, as either way they make their way to the end. As with the previous subtask, we can perform a dynamic programming approach since we can see from case ~2~ that sending a parallel searcher simply creates a similar, smaller sub-problem of searchers. We don't need to do this part of the dynamic programming with intervals as the sub-problem is only based on a singular searcher bounding the next searchers.

We first precompute the ~4~ corner cases using the same dynamic programming approach as from the previous subtask. Then, run another ~1~-dimensional dynamic programming based on a side of the grid after a searcher is sent, which either breaks down into a sub-problem or ~2~ corner cases. We can loop over which searcher to send next, leading to a linear-time transition. Overall, this yields a time complexity of ~\mathcal{O}(N^3)~.

Subtask 4

To optimize to ~\mathcal{O}(N^2)~, we simply need to optimize the corner-case cases. As with interval-based dynamic programming, the time complexity is always at least quadratic time, and so the transition is all we can hope to optimize.

Consider sending a searcher that is not right at either of the bounds set by other searchers (bounds shown in blue, searcher being sent in green). In the diagram below, as previously discussed, anyone to the side of that searcher that is not on the corner side (shown in purple) can be sent in any order at any time, as they won't interfere with anyone perpendicular. Notice that because of this, we could have also sent the purple searchers on the left first beforehand. So instead of looping all next potential searchers, we can observe that if sending any searcher that is not right by the bounds of the region is most optimal, then that would have already been considered if we sent a searcher by the bounds, and so instead we only need to check the ~2~ searchers by the bound. In other words, sending the green searcher then the purple searchers will never be more optimal than just sending the left-most purple searcher first, and so we just need to check the left-most purple searcher or the searcher closest to the bottom blue-bounded path.

So instead of looping through each possible next searcher, we can only check the ~2~ searchers closest to the bounds, and so we reduce the transition of our dynamic programming from ~\mathcal{O}(N)~ to ~\mathcal{O}(1)~. Since both parts of our dynamic programming solution are done in quadratic time, the overall time complexity is ~\mathcal{O}(N^2)~.

As a small constant optimization, we can apply a similar logic to this subtask to the pre-corner horizontal/vertical searchers, where we only need to search the next parallel searcher along with the perpendicular searchers.