~\mathcal O(V^2)~ Solution

Here is a quadratic solution that uses dynamic programming in a naive way.

We first pre-compute the minimum number of pushes needed to move any robot from one grid to another. We can solve this as an all-pair shortest path problem on a directed, unweighted, graph ~G = (V, E)~, where every vertex is a grid and an edge ~(u, v)~ exists if a single push would move the robot from ~u~ to ~v~. Denote ~c(u, v)~ as the minimum number of pushes to send a robot from ~u~ to ~v~. ~c(u, v) = \infty~ if it is not possible to reach ~v~ from ~u~. This step can be computed in ~\mathcal O(VE)~ time. In the graph we constructed, each vertex has at most four outgoing edges (one for each direction). Therefore, ~E = \mathcal O(V)~ and this step takes ~\mathcal O(V^2)~ time.

Note that we only need to keep track of grid locations that are reachable by the robots. In the worst case, ~V~ is ~\mathcal O(W \times H)~ but in practice, if the number of occlusions is small, ~V \ll W \times H~.

We then compute the following: Given two compatible robots at grids ~u~ and ~v~, how many pushes are needed if they are to merge in location ~w~? The number of pushes is the sum of the minimum cost from ~u~ to ~w~ and ~v~ to ~w~. The order we push the robots does not matter.

Next, we need to determine the order of merging. The order can be modelled as a binary tree with the individual robots as leaf nodes and composite robots as intermediate nodes. The solution is thus to find, among all possible binary trees of ~N~ nodes, the tree that requires the fewest number of pushes. The solution can be achieved with dynamic programming.

Let ~d(i, j, u)~ be the minimum number of pushes it takes to merge robots ~i~ to ~j~, with the final merge taking place at grid ~u~. The final answer to the task ROBOTS is ~\min_{u \in V} d(1, N, u)~.

Let ~p(i, j, u)~ be the minimum number of pushes it takes to merge robots ~i~ to ~j~ in some grid AND move it to grid ~u~. In other words,

$$\displaystyle p(i, j, u) = \min_{v \in V} d(i, j, v)+c(v, u)$$

Here is the dynamic programming solution. First, we consider the base case, and initialize ~p(i, i, u)~ to ~c(v, u)~ if robot ~i~ is located at grid ~v~ initially.

For the recursive case, we have

$$\displaystyle d(i, j, u) = \min_{i \le k \le j} p(i, k, u) + p(k+1, j, u)$$

for ~j > i~.

Translating the equations above directly, we have our first solution, presented in Algorithm 1. The algorithm runs in ~\mathcal O(V^2)~ time, with Line 19 and computation of ~c(*, *)~ being the bottleneck. Note that since ~N \le 9~, we treat the factor ~N~ in the running time as a constant.

(too lazy to copy Algorithm 1)

~\mathcal O(V \log V)~ Solution

To improve the running time, we need to find a faster way to compute ~p(*, *, *)~ and avoid computing ~c(*, *)~. The key insight is that if ~p(i, j, v)~ has not been determined, and ~v~ is reachable from some grid location ~u~ in one push (i.e., ~(u, v) \in E~), then ~p(i, j, v) = \min_{u \mid (u,v) \in E} p(i, j, u)+1~. Further, we know that if ~i~ and ~j~ merge at ~u~, then ~p(i, j, u) = d(i, j, u)~.

For ease of exposition, we abuse the notation of ~p(i, j, v)~ to represent "minimum-so-far" in the following explanation and pseudocode, instead of the minimum.

The improved algorithm to compute ~p(*, *, *)~ is similar to that of Dijkstra's algorithm. We say that we relax a vertex ~v~ if we set ~p(i, j, v)~ to ~p(i, j, u)+1~ when ~p(i, j, v) > p(i, j, u)+1~ and ~(u, v) \in E~. We maintain a priority queue containing the "front" of vertices we are exploring, initialized with vertices corresponding to the merged locations. The main loop expands the front and keeps relaxing vertices until there are no more vertices to relax. When this happens, we know that each of the ~p(i, j, v)~ already contains its minimum value.

Note that this algorithm to compute ~p(i, j, v)~ no longer makes use of ~c(u, v)~. It turns out that we do not require ~c(u, v)~ during initialization as well, as ~p(i, i, u)~ can be initialized by repeatedly relaxing the vertices. The removal of ~c(u, v)~ removes the bottleneck ~\mathcal O(V^2)~ from the algorithm.

The pseudocode for this improved algorithm is shown in Algorithm 2. Note that the looping condition at Line 11 has changed to accommodate the calculation of ~p(i, i, u)~.

In the worst case, each vertex is inserted into the queue once for each incoming neighbor. Thus, there are ~\mathcal O(E)~ insertions, each taking ~\mathcal O(\log V)~ time using a binary heap implementation of a priority queue. Since ~E = \mathcal O(V)~, the running time for this version of the algorithm takes ~\mathcal O(V \log V)~ time.

~\mathcal O(V)~ Solution

We now present the final solution, relying on the observations that: (O1) the value of ~p(*, *, *)~ is bounded and is an integer, and (O2) we always insert an item with a key larger than the current minimum in Line 29.

Let's begin by bounding the value of ~p(*, *, *)~. We will present a very loose bound here for simplicity. For any two robots ~i~ and ~j~ to merge, in the worst case, they must (collectively) visit every reachable grid (each requiring one push). After merging, the composite robot may be pushed to each of the reachable grid again, before reaching ~u~. This simple analysis gives an upper bound for ~p(i, j, u)~ for any ~i, j~, and ~u~, as ~2V~.

Since the key value of the priority queue is an integer and is bounded, we can implement the priority queue as (i) an array of lists ~L_1, L_2, \dots~, where ~L_x~ stores a list of grid locations ~u~ such that ~p(i, j, u) = x~, and (ii) a value ~min~, such that ~L_{min}~ is the non-empty list with the smallest index.

The ~insert(k,v)~ operation (Lines 20 and 29) simply appends an item ~v~ to the end of the list ~L_k~ and updates ~min~ if necessary. This operation takes ~\mathcal O(1)~ time. The ~getMin()~ operation (Line 25) simply returns an item from the list ~L_{min}~ and scans for the next higher ~min~ if ~L_{min}~ becomes empty. Observation O2 implies that it suffices to make a single pass through the list (i.e., ~min~ always increases inside the while loop starting at Line 24). Summing up the cost of every ~getMin()~ operation, the running time is ~\mathcal O(V)~. Therefore, with this implementation of the priority queue, the total running time for the algorithm is reduced to ~\mathcal O(V)~.

(too lazy to copy Algorithm 2)

Credits

Task statement and ~\mathcal O(V^2)~ solution by Wei Tsang Ooi. ~\mathcal O(V \log V)~ solution by Harta Wijaya. ~\mathcal O(V)~ solution by Raymond Kang and Harta Wijaya.