Google Code Jam Archive — Farewell Round D problems

Test Set 1

A brute-force solution would be to calculate and sum the distances between every pair of stations, then divide by the total number of pairs. The total number of stations is $$$\mathbf{W} + \mathbf{E}$$$, which means that there are $$$N = \frac{(\mathbf{W} + \mathbf{E}) \times (\mathbf{W} + \mathbf{E} - 1)}{2}$$$ total pairs of stations. Calculating the distance between any given pair takes $$$O(\mathbf{W} + \mathbf{E})$$$ time, so this solution has a time complexity of $$$O((\mathbf{W} + \mathbf{E})^3)$$$, which is too slow.

First notice that the western stations make a tree, because there is exactly one path between any two stations. This also applies to the eastern stations. Let us define the western tree as $$$T_W$$$, the eastern tree as $$$T_E$$$, and the tree created by connecting the two trees as $$$T_{W+E}$$$.

Instead of calculating the distances between every pair of stations, we can instead compute how many paths go through each edge, which we call the "contribution" of each edge, in $$$T_{W+E}$$$. The total sum of all distances between pairs of nodes is equal to the total sum of edge contributions. We just have to sum up these contributions and divide by $$$N$$$ to get the average distance for the given case.

To compute an edge's contribution, we need two depth-first-search (DFS) traversals. First, choose an arbitrary root $$$r$$$ in $$$T_{W+E}$$$. For the first traversal, for each node $$$n$$$ starting from $$$r$$$, compute and store the size of the subtree $$$S_n$$$ under $$$n$$$. This can be calculated recursively by $$$S_n = 1 + \sum_i S_i$$$, where the sum is over all children $$$i$$$ of $$$n$$$. Fig.1 has an example shown below.

Then, traverse the tree a second time to compute each edge's contribution. The key insight here is that for an edge between nodes $$$n$$$ and $$$p$$$, where $$$n$$$ is the child of $$$p$$$, the edge's contribution is equal to $$$S_n \times (\mathbf{W} + \mathbf{E} - S_n)$$$. Thus, the second traversal goes through all the edges in $$$T_{W+E}$$$ and calculates their contributions using the stored subtree sizes from the first traversal. This is demonstrated below in Fig.2.

Afterwards, summing up the edge contributions and dividing by $$$N$$$ yields the answer. Since the two traversals take $$$O(\mathbf{W} + \mathbf{E})$$$ each, and we need to redo the traversals for each of the $$$\mathbf{C}$$$ cases, the total time complexity is $$$O((\mathbf{W} + \mathbf{E}) \times \mathbf{C})$$$. This is sufficient for Test Set 1, but not for Test Set 2.

Test Set 2

The key insight for Test Set 2 is that the total path sum of the $$$N$$$ pairs can be computed from the formula $$$\mathbf{E} \times P^W_{\mathbf{A_k}} + \mathbf{W} \times P^E_{\mathbf{B_k}} + \mathbf{W} \times \mathbf{E} + Q^W + Q^E$$$, where $$$P^W_n$$$ is the path sum from node $$$n$$$ to all other nodes in $$$T_W$$$, $$$Q^W$$$ is the total path sum within $$$T_W$$$, and likewise for $$$P^E_n$$$ and $$$Q^E$$$. If these values are precomputed already, then whenever we are given a connection $$$(\mathbf{A_k}, \mathbf{B_k})$$$, we can return the average distance in a constant time operation using the formula above. Before deriving this formula, let us first find out how to precompute $$$Q^W, Q^E$$$, and $$$P^W_n, P^E_n$$$ for each node $$$n$$$ efficiently first. This can be accomplished with two DFS traversals for both $$$T_W$$$ and $$$T_E$$$ individually.

Let us look at $$$T_W$$$ for convenience. For the first DFS, starting from an arbitrary root $$$r$$$, calculate at each node $$$n$$$:

1. The size of the subtree rooted by $$$n$$$, defined as $$$S^W_n$$$. This can be calculated recursively by $$$S^W_n = 1 + \sum_i S^W_i$$$, where the sum is over all children $$$i$$$ of $$$n$$$.
2. The path sum from $$$n$$$ to all its descendants, defined as $$$D^W_n$$$. This can be computed recursively by $$$D^W_n = \sum_{i} D^W_i + (S_n-1)$$$, where the sum is over all children $$$i$$$ of $$$n$$$.

This first traversal calculates the number of subtrees and subtree path sums below $$$n$$$. However, $$$D^W_n$$$ is not the full sum of all paths from $$$n$$$ to other nodes in $$$T_W$$$ because we only counted paths travelling downwards from $$$n$$$. For every node, we also need to compute path sums that go above and through its parent. This is done via a second DFS. In this traversal, given a node $$$n$$$ and its parent $$$p$$$, the actual path sum $$$P^W_n$$$ is computed as follows:

$$$P^W_n = D^W_n + (\mathbf{W} - S^W_n) + (P^W_p - (D^W_n + S^W_n))$$$

Essentially, we add onto $$$D^W_n$$$ two values:

1. $$$(\mathbf{W} - S^W_n)$$$, the contribution of the edge connecting $$$n$$$ to $$$p$$$
2. $$$P^W_p - (D^W_n + S^W_n)$$$, the path sums starting from $$$p$$$ that do not go through $$$n$$$.

For the root $$$r$$$ of $$$T_W$$$, $$$P^W_r = D^W_r$$$, as shown below in Fig.4.

With $$$P^W_n$$$ computed for all nodes $$$n$$$ in $$$T_W$$$ and again $$$P^E_n$$$ computed for all nodes in $$$T_E$$$, we can calculate the average distance for each case in constant time. Now let us derive the formula mentioned earlier. Suppose we are given a connection between $$$\mathbf{A_k}$$$ from the west, and $$$\mathbf{B_k}$$$from the east. We first note that the total path sum can be computed as:

$$$\sum_{i \in T_W} \sum_{j \in T_E} d_{i,j} + Q^W + Q^E$$$

where $$$d_{i,j}$$$ is the distance between nodes $$$i$$$ and $$$j$$$. Here, $$$Q^W$$$ is the sum of all paths in $$$T_W$$$, and $$$Q^E$$$ is the sum of all paths in $$$T_E$$$. We can already calculate them just by summing the $$$P_n$$$s on each side.

$$$Q^W = \frac{\sum_{n \in T_W} P^W_n}{2}, Q^E = \frac{\sum_{n \in T_E} P^E_n}{2}$$$

The first sum about $$$d_{i,j}$$$ is trickier, but we can separate it into three terms that incorporate $$$\mathbf{A_k}$$$ and $$$\mathbf{B_k}$$$:

$$$\sum_{i \in T_W} \sum_{j \in T_E} (d_{i,\mathbf{A_k}} + d_{j,\mathbf{B_k}} + 1)$$$.

All the terms now allow us to simplify the double summation to single summations. The above equation is equivalent to:

$$$\mathbf{E} \times \sum_{i \in T_W} d_{i,\mathbf{A_k}} + \mathbf{W} \times \sum_{j \in T_E} d_{j,\mathbf{B_k}} + \mathbf{W} \times \mathbf{E}$$$.

Because we precomputed all the path sums, $$$\sum_{i \in T_W} d_{i,\mathbf{A_k}}$$$ is equal to $$$P^W_{\mathbf{A_k}}$$$, and $$$\sum_{j \in T_E} d_{j,\mathbf{B_k}}$$$ is equal to $$$P^E_{\mathbf{B_k}}$$$. Thus, the total path distances between the two trees is

$$$\mathbf{E} \times P^W_{\mathbf{A_k}} + \mathbf{W} \times P^E_{\mathbf{B_k}} + \mathbf{W} \times \mathbf{E} + Q^W + Q^E$$$.

Divide that by $$$N$$$ to get the average distance for each query. Each traversal for $$$T_W$$$ and $$$T_E$$$ is $$$O(\mathbf{W})$$$ and $$$O(\mathbf{E})$$$ respectively, which makes the overall complexity $$$O(\mathbf{W} + \mathbf{E} + \mathbf{C})$$$ for $$$\mathbf{C}$$$ cases.

Test Set 1

The problem asks us to answer queries on two strings $$$\mathbf{A}$$$ and $$$\mathbf{B}$$$. In each query, we are given an $$$\mathbf{A}$$$-prefix and a $$$\mathbf{B}$$$-suffix. We are asked to find the longest prefix of the $$$\mathbf{B}$$$-suffix that is a substring of the $$$\mathbf{A}$$$-prefix.

A naive algorithm might try every single prefix of the $$$\mathbf{B}$$$-suffix and do a substring search in the $$$\mathbf{A}$$$-prefix. Assuming a fast string-searching algorithm, this gives us an $$$O(\mathbf{Q}M(N+M))$$$ algorithm where $$$\mathbf{Q}$$$ is the number of queries, $$$N$$$ is the length of $$$\mathbf{A}$$$, and $$$M$$$ is the length of $$$\mathbf{B}$$$. This is too slow to pass the first test set.

This approach can be sped up. One approach is to use the Z-function. The $$$i$$$-th entry of the Z-function is denoted by $$$Z_i$$$ is the longest match between a string and the suffix of that string starting at index $$$i$$$. We can precompute the Z-function for the concatenation of $$$\mathbf{A}$$$ onto the end of each $$$\mathbf{B}$$$-suffix. This requires $$$O(NM)$$$ time. When answering a query, we find the Z-function table corresponding to the $$$\mathbf{B}$$$-suffix in that query. Then, we can iterate through each index corresponding to the $$$\mathbf{A}$$$-prefix to find the longest match. Overall, this gives an $$$O(\mathbf{Q}N + NM)$$$ algorithm, which is fast enough for Test Set 1. Other techniques including Knuth-Morris-Pratt or suffix trees/arrays can be used too.

Test Set 2

A faster approach is needed for the larger second test set. We can start with some observations. Consider a single query. The longest match in the $$$\mathbf{A}$$$-prefix must be fully contained in the prefix. Imagine we had an algorithm that could quickly find the longest match but that match is allowed to go outside the $$$\mathbf{A}$$$-prefix. Specifically, the match only needs to start in the $$$\mathbf{A}$$$-prefix, but might go outside of the prefix later on. Call this a relaxed query. This may seem arbitrary, but we will see later that relaxed queries can be answered efficiently using well-known techniques.

Assume we have a fast algorithm for answering relaxed queries. Can we now solve the problem efficiently? Assume we want to check if the longest match is at least $$$k$$$ characters long. We know that any match must start in the $$$\mathbf{A}$$$-prefix with the last $$$k-1$$$ characters removed, so we can solve it using a relaxed query. Also, observe that if there is a match that is at least $$$k$$$ characters, it implies there is a match of at least $$$k-1$$$ characters. This means we can binary search on $$$k$$$. This allows us to answer a query in $$$O(R \log M)$$$ time, where $$$R$$$ is the time required to answer a relaxed query.

Now we need to find an efficient algorithm for anwering relaxed queries. One way to do this involves two data structures. A suffix array with its longest common prefix table, and a persistent binary search tree.

Consider the suffix array of $$$\mathbf{A}$$$ concated with $$$\mathbf{B}$$$. We will need some properties of the suffix array and the longest common prefixes between pairs of suffixes. We can find the suffix array position of any $$$\mathbf{B}$$$-suffix by keeping a lookup table into the suffix array. Let us say that that position is $$$b$$$. The longest common prefix between suffix $$$b$$$ and suffixes $$$b+1, b+2, \dots$$$ will decrease monotonically. The same is true for $$$b-1, b-2, \dots$$$. To answer a relaxed query, we need to find the longest common prefix between $$$b$$$ and any suffix beginning in the $$$\mathbf{A}$$$-prefix. Using the previously mentioned property, we will therefore need to find the first index less than $$$b$$$ that corresponds to a suffix starting in the $$$\mathbf{A}$$$-prefix, as well as the first index greater than $$$b$$$ also corresponding to a suffix starting in the $$$\mathbf{A}$$$-prefix.

We can find these two entries by sweeping over the suffixes of $$$\mathbf{A}$$$ and constructing a persistent binary search tree $$$T$$$. We can sweep over $$$\mathbf{A}$$$ in increasing order of indexes. The corresponding suffix array location can be found and added to $$$T$$$. The end result will be N different versions of $$$T$$$, each corresponding to the set of suffixes for each $$$\mathbf{A}$$$-prefix. When answering a relaxed query, we can look up the version of $$$T$$$ corresponding to the $$$\mathbf{A}$$$-prefix, and do a tree traversal to find the first elements immediately before and after the $$$\mathbf{B}$$$-suffix. Note that the query value will be the suffix array location of the $$$\mathbf{B}$$$-suffix.

This leads to an algorithm whose complexity is $$$O((N+M) \log (N+M))$$$ to build the suffix array and persistent binary search trees. Then, we require $$$O(\mathbf{Q} \log(M) \log(N))$$$ to answer all of the queries. This is sufficient to pass Test Set 2.

Since there are at most 26 interesting finishes, we can find a list of interesting starts that are drivable to each of the interesting finishes separately. We can solve this in a more generic way: For a given interesting finish cell location, determine whether each of the other cells in the grid is drivable to the interesting finish cell or not.

Our goal is to build a graph from the given grid, where each cell is seen as a node, and for each pair of adjacent cells $$$(c_a, c_b)$$$, add a directed edge from $$$c_a$$$ to $$$c_b$$$ if there exist a strategy to force the car move from $$$c_a$$$ to $$$c_b$$$ safely. Note that the edges between two cells are not necessary to be bidirectional.

Take Sample Case #1's interesting finish $$$B$$$ as example, the blue arrow edges are added for each pair of cells if there exist a strategy to force the car go along the direction safely. From observation, we can see that $$$a, b, c$$$ are all drivable to the interesting finish $$$B$$$. Also note that there is not an edge from $$$B$$$ to its south side neighbor. This is because there is a hazard in its north side so it is not safe to make the "north/south" command when the car is on the cell $$$B$$$.

Determining an edge between two cells is not as simple as avoiding hazards, because in addition to the hazards, there will also be some empty cells that are not drivable to the interesting finish, which we will need to avoid. Below we show how to build a graph for a fixed interesting finish, and once the graph is built, how to determine which nodes (cell) are drivable to the interesting finish.

We can first temporarily put edges between each pair of adjacent cells, as the car has possibilities to move between them. Then whenever we identify a move is unsafe, i.e., some edges are found as we are unable to force the car to go along their directions safely, then we remove those edges.

Specifically the steps are, we first build an edge from each of the empty cells to its four neighboring cells if it is not a wall. Then after running a BFS/DFS from the interesting finish with edges reversed, we can discover the nodes that are never drivable to the interesting finish (i.e., there does not exist a path from that node to the interesting finish). These nodes are now seen as "non-winning" nodes.

Take Sample Case #4 for example. The red cells are hazards and the gray cells are walls. Let us build an edge from each of the empty cells to its four neighboring cells if it is not a wall.

For simplicity, let us use $$$(r, c)$$$ to refer the cell at the $$$r$$$-th row and the $$$c$$$-column in 0 index. Running a BFS or a DFS from the interesting finish $$$F$$$, we can see that cells $$$(0, 1)$$$, $$$(0, 5)$$$, $$$(0, 6)$$$, $$$(1, 3)$$$, $$$(1, 6)$$$ cannot reach the interesting finish $$$F$$$, thus they are non-winning cells. Non-winning cells are as bad as hazards, thus we mark them red.

Having these non-winning nodes identified, we must remove some edges from the graph. Precisely, if a node has a non-winning node at its west side, then we must remove the edges to its west neighbor and also the edge to its east neighbor. Likewise for the north and south edges.

Remove all the edges according to the non-winning nodes we found in the last step.

Since some edges are removed, it will result in getting more non-winning nodes. We can run a BFS/DFS again on the current graph to find out those non-winning nodes. We iteratively repeat these two steps to identify non-winning nodes and remove edges, until there is no more non-winning nodes to be identified. Then this final graph is what we wanted to build, and all the cells on the final winning positions are the cells drivable to the interesting finish.

After removing the edges, $$$(0, 0)$$$, $$$(0, 2)$$$, $$$(1, 0)$$$, $$$(1, 1)$$$ and $$$(1, 2)$$$ become non-winning nodes.

Remove all the edges that are possible to lead to non-winning nodes

Finally, cell $$$(0, 3)$$$ is found as non-winning too. After this step, there is no more edge to be removed, and no more node to be marked as non-winning. Thus this is the final graph we are looking for, and $$$(0, 4)$$$ is the cell drivable to the interesting finish $$$F$$$.

Since in each iteration, there are at least one new non-winning node identified, and there are at most $$$O(\mathbf{R}\times\mathbf{C})$$$ nodes in the graph, thus we have at most $$$O(\mathbf{R}\times\mathbf{C})$$$ iterations. And in each iteration, a $$$O(\mathbf{R}\times\mathbf{C})$$$ BFS/DFS is run. Thus the time complexity of this solution is $$$O((\mathbf{R}\times\mathbf{C})^2)$$$. This must be done separately for each interesting finish, hence the total time complexity for finding all the drivable pairs is $$$O((\mathbf{R}\times\mathbf{C})^2\times num\_of\_finishes)$$$

Test Set 1

For a given gold placement, we can consider what the markings would look like if they were all known. For example, if two consecutive gold nuggets are 3 kilometers apart, the expected pattern of markings would be o<>o. If they are 6 kilometers apart, the expected pattern would be o<<=>>o, and if they are 1 kilometer apart, it would be simply oo.

Because each of the expected patterns only depends on the positions of the two gold nuggets to the left and right, our solution can involve repeatedly adding a new gold nugget to the east and checking that all of the markings between the new gold nugget and the previous gold nugget match the expected pattern. We can make this algorithm efficient with dynamic programming by defining $$$dp(i)$$$ as the number of gold placements for the first $$$i$$$ kilometers that have a gold nugget at the $$$i$$$-th kilometer.

$$$dp(i)$$$ is calculated as the sum of $$$dp(j)$$$ for all $$$(j < i)$$$ where the markings between kilometer $$$j$$$ and $$$i$$$ are valid, plus $$$1$$$ if $$$i$$$ can be the first gold nugget on the road. We can check if the markings are valid by iterating over all positions between $$$j$$$ and $$$i$$$ and checking if each one is either (.) or the expected marking of (<), (=), or (>). Also, the positions $$$j$$$ and $$$i$$$ themselves must have a (.) or (o).

We also need to specially handle the parts of the road to the west of the first gold nugget and to the east of the last gold nugget. All markings to the west of the first gold nugget must be (.) or (>). Similarly, our final answer will be the sum of $$$dp(i)$$$ for all $$$i$$$ where all markings to the east are (.) or (<).

In the solution above, we calculate the value of each $$$dp(i)$$$ by iterating over all positions for the previous nugget and checking if the markings in between are valid. This is $$$O(n^2)$$$, where $$$n$$$ is the length of $$$\mathbf{S}$$$. Applying this to each element of the dynamic programming table leads to a final time complexity of $$$O(n^3)$$$.

Test Set 2

We will solve Test Set 2 by speeding up the calculation of each $$$dp(i)$$$. Let's use $$$\mathbf{S}_x$$$ to denote the marking at position $$$x$$$, with $$$\mathbf{S}_0$$$ being the first marking. Also, let's use $$$p$$$ to denote the position of the last known (<, =, >, or o) marking before $$$i$$$, or $$$-1$$$ if there is no known marking before $$$i$$$. This means that $$$\mathbf{S}_j$$$ is (.) for all ($$$p < j < i$$$). We need to find all positions $$$j$$$ that are valid and part of our summation for $$$dp(i)$$$. We can make the following observations:

1. All positions ($$$p < j < i$$$) are valid since there are only (.)s in this range.
2. If $$$\mathbf{S}_p$$$ is (o), then its position $$$j = p$$$ is valid.
3. If $$$\mathbf{S}_p$$$ is (<), then it can be part of the left half of the pattern between two gold nuggets. The range of valid positions extends to the left of $$$p$$$ as long as the markings are (.) or (<) and the center of the pattern has not passed $$$p$$$. More precisely, let $$$q$$$ be the largest position less than $$$p$$$ where $$$\mathbf{S}_q$$$ is (=), (>), or (o), or $$$-1$$$ if there is no such position, and let $$$r$$$ be the leftmost position for the gold nugget that keeps the center of the pattern to the right of $$$p$$$. In this case, $$$r = p - (i - (p + 1)) = 2p - i + 1$$$. Then all positions ($$$max(q, r - 1) < j < p$$$) where $$$\mathbf{S}_j$$$ is (.) are valid. If $$$\mathbf{S}_q$$$ is (o), then $$$j = q$$$ can be valid as well as long as $$$q \ge r$$$.
4. If $$$\mathbf{S}_p$$$ is (=), then it can be the center of the pattern between two gold nuggets, as long as the markings that will end up on the left side of the pattern are (.) or (<). More precisely, let $$$q$$$ again be the largest position less than $$$p$$$ where $$$\mathbf{S}_q$$$ is (=), (>), or (o), or $$$-1$$$ if there is no such position. Let $$$r$$$ be the position of the gold nugget that will result in the center of the pattern being at $$$p$$$. In this case, $$$r = p - (i - p) = 2p - i$$$. Then $$$j = r$$$ is valid as long as $$$r > q$$$, or if $$$\mathbf{S}_q$$$ is (o) and $$$r = q$$$.
5. If $$$\mathbf{S}_p$$$ is (>), then it can be part of the right half of the pattern between two gold nuggets. As such, the gold nugget cannot be anywhere to the left of $$$p$$$ that causes the center of the pattern to be to the right of $$$p$$$. More precisely, let $$$r$$$ be the rightmost position for the gold nugget with the center of the pattern to the left of $$$p$$$, so $$$r = p - 1 - (i - p) = 2p - i - 1$$$. Then ($$$r < j < p$$$) is not valid.

Observations 2, 3, and 4 all impose a limit on the lowest possible values for $$$j$$$, but observation 5 does not. This means that we can traverse backwards through $$$\mathbf{S}$$$ applying observation 5 for each (>) until we reach a (o), (<), (=), at which point the limits from observations 2, 3, and 4 take effect, or until we reach the start of the road.

We need to make one more observation about the number of contiguous ranges of positions for $$$j$$$ that are valid. Observation 5 causes the next range of valid positions to be double the distance from the current (>) to $$$i$$$. Let's suppose that the position of the last (>) is $$$l$$$ kilometers to the west of $$$i$$$. If we were trying to maximize the number of contiguous ranges of valid positions, we would place the next (>) at a position $$$2l + 2$$$ kilometers west of $$$i$$$ so that there is a valid range of length 1 at $$$2l + 1$$$ kilometers west. Similarly, we would place the following (>) at a position $$$2(2l + 2) + 2 = 4l + 6$$$ kilometers west of $$$i$$$. Continuing this logic and ignoring the constant term in the equation, we get that having $$$k$$$ ranges of valid positions requires $$$n > 2^kl$$$ kilometers. Therefore, $$$k < \log n - \log l$$$, which is $$$O(\log n)$$$ even if $$$l = 1$$$!

Our resulting algorithm will iterate over all ranges of valid positions for $$$j$$$ and calculate the sum of $$$dp(j)$$$ in that range. We can calculate this sum for a single range in $$$O(1)$$$ time complexity using a prefix sum array. This prefix sum array should be updated as we calculate each $$$dp(i)$$$. Our target overall time complexity will be $$$O(n \log n)$$$.

Implementation

To aid in the implementation of the observations above, we can precalculate the positions of the last marking for each kilometer on the road, for various combinations of marking types. In particular, we can precalculate the largest $$$j < i$$$ such that $$$\mathbf{S}_j$$$ is (>) for each possible $$$i$$$. This would be needed to calculate observation 5. We can also precalculate similar arrays for the last instance of (o), (<), or (=) to choose between observations 2, 3, and 4, and the last instance of (o), (=), or (>) for the calculation of observation 3 or 4.

Unfortunately, simply traversing through each (>) until we reach observation 2, 3, or 4 could be $$$O(n)$$$ if there are many (>)s. However, if $$$p$$$ is the position of the current (>), we know that there are no valid positions between $$$r = 2p - i - 1$$$ and $$$p$$$, so we can simply skip to the leftmost (>) in that range, as long as we don't skip past any (o), (<), or (=). We can precalculate an array with the next (>) for each position $$$i$$$ for this purpose. Even though we have not travelled our expected $$$2^k$$$ kilometers, we will reach that point in the next iteration anyway because there were no more (>)s before the one we chose.

Also note that, when calculating observation 3, we can use the sum of all values for $$$j$$$ in ($$$max(q, r - 1) < j < p$$$), even if some of the positions have a <, because those positions cannot have a gold nugget and the corresponding $$$dp$$$ value will be $$$0$$$.

Finally, note that the range of invalid positions in observation 5 between $$$r = 2p - i - 1$$$ and $$$p$$$ can cause an upper bound on the valid positions when applying observations 2, 3, or 4. An example of this is o.>.i, where the (o) cannot be a valid $$$j$$$ when calculating $$$dp(i)$$$.

Since none of these implementation details worsens the time complexity, our final algorithm is $$$O(n \log n)$$$

Alternative Implementation

TODO: Add explanation of alternative implementation idea if desired.

For each testcase in this interactive problem, we are first given two integers $$$\mathbf{C}$$$ and $$$\mathbf{L}$$$. First we send the judge a design, $$$G$$$, that contains exactly $$$\mathbf{C}$$$ computers and $$$\mathbf{L}$$$ links, then the judge sends back another design $$$H$$$ which is almost identical to the previous design $$$G$$$, except that the IDs are randomly permuted. At the end, we are required to find out a ring on $$$H$$$.

However, it's difficult to efficiently find out a ring on an arbitrary design. It's actually equivalent to the Hamiltonian cycle problem , and currently there's no efficient solution for it yet.

Thankfully, we don't need to do that in this problem. We can construct $$$G$$$ in such a way that finding a ring of $$$H$$$ is easier. There are several heuristics to do so, such as:

• Make some computers distinguishable enough to find part of the bijection between $$$G$$$ and $$$H$$$
• Make some computers sort of equivalent, so permuting their IDs doesn't matter
• When $$$\mathbf{C}$$$, $$$\mathbf{L}$$$ meets some condition, construct some kinds of special designs whose ring could be efficiently found. For example, making use of Ore's theorem when $$$\mathbf{L}$$$ is sufficiently large.

We might need to combine these heuristics to build a complete strategy that applies to all possible $$$\mathbf{C}$$$, $$$\mathbf{L}$$$.

The IDs in $$$H$$$ are randomly permuted, which become meaningless to us. Afterward in this analysis, the ID of a computer refers to the one in $$$G$$$, that is, the ID before shuffled.

In the following approaches, we first add the links $$$(1, 2), (2, 3), ..., (\mathbf{C}-1, C), (\mathbf{C}, 1)$$$ to form a ring $$$R$$$. Then, we add the remaining links apart from $$$R$$$ to fulfill the link number limit $$$\mathbf{L}$$$.

Let's define the degree of computer $$$i$$$, or $$$deg(i)$$$, to be the number of neighbors of computer $$$i$$$. It is an important property of a computer in this problem, because it remains invariant after the ID permuted.

Test Set 1

In this test set, the number of links is at most $$$(C + 10)$$$. Apart from the ring $$$R$$$, there are at most $$$10$$$ links remaining.

When $$$\mathbf{C}$$$ is large enough ($$$>12$$$), we can put the extra links in such a way that allow us to efficiently find a ring in $$$H$$$. Otherwise, $$$\mathbf{C}$$$ is suffiently small ($$$\leq 12$$$) that we could find a ring in $$$H$$$ by brute-force. These two different approaches are explained in detail in the following sections.

$$$\mathbf{C} > 12$$$

We could add the links in the order $$$(1, 3), (1, 4), (1, 5), ...$$$. There are at most $$$10$$$ remaining links, so the last link we add is at most $$$(1, 12)$$$. In this case, $$$\mathbf{C}>12$$$, so all of these links $$$(1, 3), (1, 4), ..., (1, 12)$$$ are not in $$$R$$$.

All extra links are added on computer $$$1$$$, so computer $$$1$$$ has the greatest degree among all computers. This helps us to identify the computer $$$1$$$ in $$$H$$$.

Then, we ignore the computer $$$1$$$ and all the links on it. The rest part in $$$H$$$ are the links $$$(2, 3), (3, 4), ..., (\mathbf{C}-1, \mathbf{C})$$$. Combine these links with computer $$$1$$$, then the ring $$$R$$$ is reconstructed.

$$$\mathbf{C} \leq 12$$$

In this case, $$$\mathbf{C}$$$ is small enough for most of the brute-force approaches.

We can add the remaining $$$10$$$ links arbitrarily, and find a ring via plain backtracking, or the $$$O(\mathbf{C}^2\times 2^{\mathbf{C}})$$$-time algorithm for Hamiltonian cycle.

Test Set 2

We add the remaining links in the order
$$$(1, 2), $$$
$$$(1, 3), (2, 3), $$$
$$$(1, 4), (2, 4), (3, 4), $$$
...,
$$$(1, \mathbf{C}), (2, \mathbf{C}), (3, \mathbf{C}), ..., (\mathbf{C}-1, \mathbf{C})$$$
if it's not in the ring $$$R$$$ yet, until we put $$$\mathbf{L}$$$ links in total.

Let the row $$$(1, k), (2, k), ..., (k-1, k)$$$ be the row $$$k$$$. Note that the last link in each rows is aready in the ring $$$R$$$, and so do the first link in row $$$\mathbf{C}$$$. These links are only listed to clarify the order.

Let row $$$K$$$ be the last row that are completely added to $$$G$$$, then each pair of computers among $$$1..K$$$ is directly connected with a link.

A clique is a set of computers such that each pair of computers among them is directly connected with a link. In this case, computers $$$1..K$$$ form a clique of size $$$K$$$.

Let's handle the edge cases $$$K \leq 3$$$ and $$$K \geq \mathbf{C}-1$$$ separately first.

• When $$$K \leq 3$$$, $$$H$$$ is a ring with at most $$$2$$$ extra links. We can solve this case by the TS1 approach.
• When $$$K = \mathbf{C}-1$$$, we can identify computer $$$\mathbf{C}$$$ as the computer with minimum degree. We first pick two neighbors of computer $$$C$$$, say, computer $$$A$$$ and $$$B$$$, and there's a ring $$$A \rightarrow C \rightarrow B \rightarrow$$$ other computers $$$\rightarrow A$$$.
• When $$$K=\mathbf{C}$$$, $$$H$$$ itself is a clique, so each pair of computers is directly connected with a link. Any order of the $$$\mathbf{C}$$$ computers forms a ring.

Afterward in this analysis,, $$$3 \lt K \lt \mathbf{C} - 1$$$.

The simpler case

If no extra links from the next row $$$(K+1)$$$ were added to $$$G$$$, that is, the last link is $$$(K-2, K)$$$, then things are simpler.

Let's call computers $$$1..K$$$ the clique part, and computers $$$(K+1)..\mathbf{C}$$$ the ring part.

In $$$H$$$, we can classify the computers into the clique part and the ring part by their degrees.

In the ring part, the only links on the computers are the links in the ring $$$R$$$, so the degrees of them are all $$$2$$$. On the other hand, if the degree of a computer is greater than $$$2$$$, then it's in the clique part.

(Actually that's why we handled the case $$$K=3$$$ beforehand. When $$$K=3$$$, the degree of computer $$$2$$$ is also $$$2$$$, but it belongs to the clique part. This kind of confusion won't happen when $$$K>3$$$.)

Then, we can identify computer $$$1$$$ and computer $$$K$$$ from the clique part, since they are the only computers that connected with the ring part.

Though we can't tell which one is computer $$$1$$$ and which one is computer $$$K$$$, we can start from either of them, pass along the ring part to the other, pass through the rest of the clique part in any order, and go back to the starting computer.

The resulting ring is one of the following.

• $$$1$$$ $$$\rightarrow$$$ ring part $$$\rightarrow$$$ $$$K$$$ $$$\rightarrow$$$ clique part $$$\rightarrow$$$ $$$1$$$
• $$$K$$$ $$$\rightarrow$$$ ring part $$$\rightarrow$$$ $$$1$$$ $$$\rightarrow$$$ clique part $$$\rightarrow$$$ $$$K$$$

The more complicated case

Now let's handle the complicated case. Part but not all computers in the next row $$$(K+1)$$$ are added to $$$G$$$. Since the link $$$(K, K+1)$$$ is already in the ring $$$R$$$, the last added link cannot be $$$(K-1, K+1)$$$, otherwise the row $$$(K+1)$$$ is completely added.

In this case, we have the clique part $$$1..K$$$, the ring part $$$(K+2)..\mathbf{C}$$$, and a special computer $$$(K+1)$$$.

The degrees of the computers in the ring part are still all $$$2$$$, so we can identify the ring part in $$$H$$$.

Among the computers not in the ring part, computers $$$1$$$ and $$$(K+1)$$$ are the only computers that connect with the ring part.

Though we can't tell which one is computer $$$1$$$ and which one is $$$(K+1)$$$, the following difference helps us to distinguish the two.

• The non-ring part excluding computer $$$(K+1)$$$, which are the computers $$$1..K$$$, form a clique.
• The non-ring part excluding computer $$$1$$$, which are the computers $$$2..(K+1)$$$, cannot form a clique, because $$$(K-1, K+1)$$$ must not be added.

Now we are able to identify the clique part, the ring part, and the special computer $$$(K+1)$$$, so we can obtain a ring using the same approach as the previous case.