Google Code Jam Archive — Farewell Round B problems

Let $$$X_a$$$ and $$$X_b$$$ be the indices of the stacks chosen by Alice and Bob respectively. As per the definition in the question, $$$\mathbf{L_a} \le X_a \le \mathbf{R_a}$$$ and $$$\mathbf{L_b} \le X_b \le \mathbf{R_b} $$$.

The key observation to note here is that, while collecting pancakes, Alice and Bob cannot cross over any stack claimed by the other person at any point. Specifically, if $$$X_a \gt X_b$$$, then Bob cannot collect pancakes from any stacks with indices $$$\gt X_a$$$ and vice versa. This leads to the observation that only the pancake stacks in between Alice and Bob's initial choices are being contested for. All pancake stacks are guaranteed to be claimed by the person that started closer to them. Thus, the optimal strategy for either player would be to first start claiming stacks between $$$X_a$$$ and $$$X_b$$$, then start claiming the other stacks, leaving each player with a contiguous range of stacks which is either a prefix or suffix of the overall line of stacks.

Test Set 1

The constraint $$$\mathbf{N} \le 100$$$ allows a naive solution based on the observations above, which is to try out all valid combinations of $$$X_a$$$ and $$$X_b$$$, and simulate the optimal strategy described.

The optimal strategy would be for Alice and Bob to first start moving towards each other's initial positions, claiming stacks along the way. Once all stacks between $$$X_a$$$ and $$$X_b$$$ have been claimed, each player would claim all the stacks closer to them. The final answer would thus be the maximum number of pancakes collected by Alice in any such simulation.

Since there are $$$O(\mathbf{N}^2)$$$ combinations of $$$X_a$$$ and $$$X_b$$$, and simulating the strategy for any such $$$X_a$$$ and $$$X_b$$$ would take at most $$$\mathbf{N}$$$ steps, the overall time complexity of this approach is $$$O(\mathbf{N}^3)$$$.

Test Set 2

Another observation to be made is that once $$$X_a$$$ is chosen, Bob will always try to set $$$X_b$$$ as close to $$$X_a$$$ as possible, to minimize the number of additional pancakes Alice can get by choosing stacks between $$$X_a$$$ and $$$X_b$$$. This leads to three scenarios:

1. $$$X_a \le \mathbf{L_b}$$$: In this case, Bob can only choose $$$X_b$$$ to the right of $$$X_a$$$. This will result in Bob choosing $$$X_b = \mathbf{L_b}$$$ (or $$$X_b = \mathbf{L_b} + 1$$$ if $$$X_a = \mathbf{L_b} $$$). Then, once Alice and Bob start claiming stacks between $$$X_a$$$ and $$$X_b$$$, Alice will end up claiming all the stacks from $$$X_a$$$ to $$$\lfloor \frac{X_a + X_b}{2} \rfloor$$$. Finally, Alice would claim the stacks from $$$1$$$ to $$$X_a - 1$$$, leaving her with all the stacks from $$$1$$$ to $$$\lfloor \frac{X_a + X_b}{2} \rfloor$$$.
2. $$$X_a \ge \mathbf{R_b}$$$: Mirror image of Case 1.
3. $$$\mathbf{L_b} \lt X_a \lt \mathbf{R_b}$$$: Here, Bob can choose a position immediately adjacent to $$$X_a$$$ (either $$$X_a - 1$$$ or $$$X_a + 1$$$). This leaves no stacks between Alice and Bob's initial positions, so both players would just claim all the stacks closer to them without crossing the other player. Bob would choose between $$$X_a - 1$$$ or $$$X_a + 1$$$ with the goal of minimizing the number of panackes Alice collects, so the final number of pancakes collected by Alice would be $$$\min($$$ sum of pancakes in stacks from $$$1$$$ to $$$X_a$$$, sum of pancakes in stacks from $$$X_a$$$ to $$$\mathbf{N})$$$.

Using these cases, for a given $$$X_a$$$, we can exactly predict the contiguous range of stacks that Alice will claim, assuming optimal play, in $$$O(1)$$$. Given a range, calculating the sum of pancakes in that range can be done in constant time if we precompute prefix sums. The precomputation can be done in $$$O(\mathbf{N})$$$ time. Finally, if we do the constant time computation for each possible $$$X_a$$$ and take the maximum, we find the answer in $$$O(\mathbf{N})$$$ time overall.

Reachable Numbers on a Wheel

Let us first define the concept of "reachable numbers" on a wheel. These are the set of numbers that can be displayed on a wheel by rotating it in increments of $$$\mathbf{D}$$$, starting from the initial number on the wheel as given in the input.

Example: Let us take $$$\mathbf{N} = 6$$$ and $$$\mathbf{D} = 4$$$, and we start from the number $$$1$$$ on the wheel. Then the reachable numbers are:

$$$1 + 4 = \textbf{5}$$$

$$$5 + 4 = 9 \Rightarrow 9 - 6 = \textbf{3}$$$

$$$3 + 4 = 7 \Rightarrow 7 - 6 = \textbf{1}$$$

Which brings us back to the beginning. Thus, our set of reachable numbers is {$$$1, 3, 5$$$}. Note here that we subtract $$$6$$$ from numbers $$$\gt 6$$$ because of the circular sequence of numbers on the wheel.

Test Set 1

We can try all combinations of reachable values on the wheels, check for each combination if it forms a palindrome and if it does, calculate the minimum number of operations required to form that combination.

Each wheel can have a maximum of $$$\mathbf{N}$$$ reachable values. For $$$\mathbf{W}$$$ wheels, the number of possible combinations that can be shown on the security key will be of the order of $$$\mathbf{N}^{\mathbf{W}}$$$. A combination can be generated by generating the possible values for each wheel. For a given index $$$i$$$, we can start with $$$\mathbf{X}_i$$$, then incrementing the values in steps of $$$\mathbf{D}$$$. If the value overflows beyond $$$\mathbf{N}$$$, we circle back around to $$$1$$$ by subtracting $$$\mathbf{N}$$$, which then brings us to a value lying in $$$[1 \cdots \mathbf{N}]$$$. When we get to a value that we have previously encountered, we then have the complete set of values reachable for that index. In this way, we can generate all combinations by iterating through all possible reachable values for each index.

For each index, the set of reachable positions can be generated in $$$O(\mathbf{N})$$$, and for $$$\mathbf{W}$$$ wheels, we can do this in $$$O(\mathbf{N} \times \mathbf{W})$$$. Then, we can generate all combinations in $$$O(\mathbf{N}^{\mathbf{W}})$$$.

For a particular combination $$$A$$$, we can check if it is a palindrome by simply iterating over the array and verifying that $$$A_i = A_{\mathbf{W} - i + 1}$$$ for all $$$i = 1$$$ to $$$\frac{W}{2}$$$ in $$$O(\mathbf{W})$$$.

If $$$A$$$ is verified to be a palindrome, we can find the minimum cost of achieving the combination by summing over the minimum cost of converting each $$$\mathbf{X}_i$$$ to $$$A_i$$$. For each $$$i$$$, we can perform a process similar to the combination generation process by starting with $$$\mathbf{X}_i$$$ and simulating successive forward operations (that is keep adding $$$\mathbf{D}$$$) or by simulating successive backward operations (that is keep subtracting $$$\mathbf{D}$$$) till we reach $$$A_i$$$. We take the minimum of the number of forward or backward operations as the minimum number of operations it will take to achieve the conversion. For each index $$$i$$$, we can hence find out the cost in $$$O(\mathbf{N})$$$. Therefore, the cost for all $$$\mathbf{W}$$$ wheels can be calculated in $$$O(\mathbf{N} \times \mathbf{W})$$$ time.

Thus, the overall time complexity: $$$O(\mathbf{N}^{\mathbf{W}} \times \mathbf{W} \times \mathbf{N})$$$

Test Set 2

The above brute force of generating all possible combinations approach is not feasible to pass test set 2 constraints. Instead for each pair $$$(\mathbf{X}_i, \mathbf{X}_{\mathbf{W} - i + 1})$$$ in the array $$$\mathbf{X}$$$ (for all $$$i = 1$$$ to $$$\frac{\mathbf{W}}{2}$$$) that need to be equalized to make the array a palindrome, we calculate the minimum number of operations that can do so.

Before we move forward, we transpose the set of possible values for each wheel from $$$[1 \cdots \mathbf{N}]$$$ to $$$[0 \cdots \mathbf{N} - 1]$$$. This will allow us to visualize the circular nature of operations as modulo $$$N$$$. We do this by simply subtracting $$$1$$$ from all elements in $$$\mathbf{X}$$$.

With that, let us try to find the minimum operations to change $$$\mathbf{X}_i$$$ to $$$\mathbf{X}_{\mathbf{W} - i + 1}$$$. Say we rotate the $$$i$$$-th wheel in the positive direction and try to make it equal to $$$\mathbf{X}_j$$$. Let $$$x$$$ be the number of operations it takes to do so. With operations being circular in nature, we get:

$$$\mathbf{X}_i + \mathbf{D}x \equiv \mathbf{X}_j \pmod{\mathbf{N}}$$$

$$$\Rightarrow \mathbf{X}_i + \mathbf{D}x + \mathbf{N}y = \mathbf{X}_j$$$

$$$\Rightarrow \mathbf{D}x + \mathbf{N}y = \mathbf{X}_j - \mathbf{X}_i$$$

The above equation is Linear Diophantine Equation. The greatest common divisor (GCD) of two numbers $$$i$$$ and $$$j$$$ can be written as $$$GCD_{i,j}$$$.

From the Extended Euclidean Algorithm, an LDE (Linear Diophantine Equation) $$$ax + by = c$$$ has a solution only if $$$c$$$ divides $$$GCD_{a,b}$$$. Thus, the above equation $$$\mathbf{D}x + \mathbf{N}y = \mathbf{X}_j - \mathbf{X}_i$$$ will have a solution for $$$x$$$ and $$$y$$$ only if $$$\mathbf{X}_j - \mathbf{X}_i$$$ is divisible by $$$GCD_{\mathbf{D},\mathbf{N}}$$$. Thus, for any pair $$$(\mathbf{X}_i, \mathbf{X}_{\mathbf{W} - i + 1})$$$, if $$$\mathbf{X}_{\mathbf{W} - i + 1} - \mathbf{X}_i$$$ is not divisible by $$$GCD_{\mathbf{D}, \mathbf{N}}$$$ the answer is IMPOSSIBLE.

Otherwise, we can use the Extended Euclidean Algorithm to solve for one possible solution for $$$x$$$ and $$$y$$$ in $$$O(\log min(\mathbf{D}, \mathbf{N}))$$$. We need the minimal operations $$$x_{min}$$$, which is $$$(\mathbf{N} + x) \pmod{\mathbf{N}}$$$. This is because a general solution for $$$(x, y)$$$ will be of the form $$$(x + k \frac{\mathbf{N}}{GCD_{\mathbf{D},\mathbf{N}}}, y - k \frac{\mathbf{D}}{GCD_{\mathbf{D},\mathbf{N}}})$$$, where $$$k$$$ is an arbitrary integer. From the above general form, we can see that the minimum number of operations $$$x_{min}$$$ would be in the range $$$[0, \frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}} - 1]$$$ (if it is larger than that, we can simply subtract $$$\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}}$$$ from it to get a smaller value).

Hence, $$$x_{min} = x \pmod{\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}}}$$$. Since $$$x$$$ returned from the Extended Euclidean Algorithm can be negative, we add $$$\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}}$$$ and take modulo $$$\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}}$$$ again to get $$$x_{min} = (\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}} + x) \pmod{\frac{\mathbf{N}}{GCD_{\mathbf{D}, \mathbf{N}}}}$$$. Let us call this "forward direction $$$x_{min}$$$" as $$$x_{forward}$$$.

Similarly, we can find the minimum number of operations if we rotate $$$i$$$-th wheel in the backward direction. We get a similar equation in this case as well:

$$$\mathbf{X}_i - \mathbf{D}x \equiv \mathbf{X}_j \pmod{\mathbf{N}}$$$

$$$\Rightarrow \mathbf{X}_i - \mathbf{D}x + \mathbf{N}y = \mathbf{X}_j$$$

$$$\Rightarrow \mathbf{D}x - \mathbf{N}y = \mathbf{X}_i - \mathbf{X}_j$$$

We solve for $$$x_{min}$$$ for this equation in a similar fashion using the Extended Euclidean Algorithm as the forward case. Let us call the $$$x_{min}$$$ we get this time as $$$x_{backward}$$$.

Thus, the overall minimum operations it takes to change $$$\mathbf{X}_i$$$ to $$$\mathbf{X}_j$$$ is $$$min(x_{forward}, x_{backward})$$$. We add together the minimum costs for all such pairs (that is for all $$$i = 1$$$ to $$$\mathbf{W}/2$$$) to get the minimum cost to make the array a palindrome.

The overall time complexity: $$$O(\mathbf{W} \times \log \log min(\mathbf{N}, \mathbf{D}))$$$.

For simplicty let us define a function $$$\text{minDiff(X)}$$$, which takes a list of numbers $$$X$$$ as input and returns the minimum absolute difference between any two elements in the list.

Test Set 1

Since $$$\mathbf{N}$$$ is very small, for each $$$i$$$ we can find all subsets of $$$\mathbf{A}$$$ containing $$$\mathbf{A_i}$$$ in $$$O(2^\mathbf{N})$$$ and then we can filter the subsets that have $$$\text{minDiff(subset)} \ge \mathbf{K}$$$ in $$$O(\mathbf{N}^2)$$$. We can find the size of such subsets in $$$O(\mathbf{N})$$$ and then we can find the maximum size of all such subsets while iterating through the subsets. So the total time complexity will be $$$O(\mathbf{N} \cdot 2^\mathbf{N} \cdot \mathbf{N}^2) = O(2^\mathbf{N} \cdot \mathbf{N}^3)$$$ which should work for Test Set 1.

Test Set 2

The previous algorithm would be too slow for Test Set 2, so we have to find another efficient solution.

Since the order of elements in the subset does not matter, let us sort the list $$$\mathbf{A}$$$ in increasing order and call it $$$B$$$. The output list $$$L$$$ for $$$B$$$ can be rearranged to find the output list of $$$\mathbf{A}$$$.

For simplicty, let us use the below definition on some key lists:
$$$E_i$$$ is the maximum length of some subsequence $$$s$$$ of $$$B$$$ such that $$$s$$$ ends with $$$B_i$$$ and $$$\text{minDiff(s)} \ge \mathbf{K}$$$.
$$$S_i$$$ is the maximum length of some subsequence $$$s$$$ of $$$B$$$ such that $$$s$$$ starts with $$$B_i$$$ and $$$\text{minDiff(s)} \ge \mathbf{K}$$$.

Now, $$$L_i$$$ can be written as $$$L_i = E_i + S_i - 1$$$ (since $$$B_i$$$ would be repeated). So we can derive $$$L$$$ by computing $$$E$$$ and $$$S$$$.

We can use dynamic programming to compute $$$E$$$ and $$$S$$$:
$$$E_i = E_{left_i} + 1$$$, where $$$\text{left}_i$$$ is the largest index less than $$$i$$$ such that $$$B_i - B_{left_i} \ge \mathbf{K}$$$.
$$$S_i = S_{right_i} + 1$$$, where $$$\text{right}_i$$$ is the smallest index greater than $$$i$$$ such that $$$B_{right_i} - B_i \ge \mathbf{K}$$$.

Binary Search

Now the problem reduces to compute the $$$\text{left}$$$ and $$$\text{right}$$$ lists efficiently. Since $$$B$$$ is sorted, by using binary search we can find $$$\text{left}_i$$$ and $$$\text{right}_i$$$ for each $$$i$$$ in $$$O(\log\mathbf{N})$$$. Once we know $$$\text{left}$$$ and $$$\text{right}$$$ lists then we can easily compute the $$$E$$$ and $$$S$$$ lists in $$$O(\mathbf{N})$$$, and then we can compute the $$$L$$$ list in $$$O(\mathbf{N})$$$. The total complexity will be $$$O(\mathbf{N}\log \mathbf{N} + \mathbf{N}\log\mathbf{N} + \mathbf{N} + \mathbf{N}) = O(\mathbf{N} \log \mathbf{N})$$$.

Sweeping Technique

Instead of binary search, there is a more efficient algorithm if we observe the pattern of $$$\text{left}_i$$$ and $$$\text{right}_i$$$ values. The observation is: as $$$i$$$ increases, $$$\text{left}_i$$$ increases, and as $$$i$$$ decreases, $$$\text{right}_i$$$ decreases.

Now initialize a variable $$$x = 0$$$ and try to find $$$\text{left}_i$$$ while iterating through $$$i$$$. At the $$$i$$$-th iteration, keep incrementing $$$x$$$ by $$$1$$$ till you find $$$B_i - B_{x+1} \lt \mathbf{K}$$$ or $$$x = i-1$$$. Now $$$\text{left}_i = x$$$. At the end of the $$$i$$$-th step $$$x = \text{left}_i$$$.
As $$$x$$$ always increases, total increment step of $$$x$$$ can be at max length of list which is $$$\mathbf{N}$$$. So the amortized time complexity of finding the $$$\text{left}$$$ list is $$$O(\mathbf{N})$$$.
Similarly, $$$\text{right}$$$ list can found by iterating from right to left (from $$$\mathbf{N}$$$ to $$$1$$$), and initializing the $$$x$$$ with $$$\mathbf{N}$$$ and keep decrementing in $$$O(\mathbf{N})$$$.
Once we compute the $$$\text{left}$$$ and $$$\text{right}$$$ lists, we can compute $$$L$$$ list in $$$O(\mathbf{N})$$$. Total time complexity is $$$O(\mathbf{N}\log\mathbf{N} +\mathbf{N}) = O(\mathbf{N}\log\mathbf{N})$$$.

Test Set 1

We can represent the railroad network as an undirected graph by creating a node for each station, and then creating an edge for each pair of adjacent stations in each train line, that is, for every $$$1 \le i \le \mathbf{L}$$$, and for every $$$1 \le j \le \mathbf{K_i} - 1$$$, add an edge between nodes $$$\mathbf{S_{i,j}}$$$ and $$$\mathbf{S_{i,{j+1}}}$$$.

Let's define an undirected graph to be connected if, for every pair of vertices $$$x$$$ and $$$y$$$, there is a path between them. From that definition, we can say that a train line is essential if, by removing it, a connected graph stops being connected.

Given an undirected graph, to check if it's connected, it is enough to check if a single arbitrary vertex can reach all others. To prove it, let's assume that a vertex $$$v$$$ can reach all other vertices. Then, because the graph is undirected, all vertices can also reach vertex $$$v$$$. Therefore, for any pair of vertices $$$x$$$ and $$$y$$$, we can see that $$$x$$$ can reach $$$y$$$ because $$$x$$$ can reach $$$v$$$ and $$$v$$$ can reach $$$y$$$.

Now we can check if a train line is essential by building the graph without the edges that belong to that train line, and checking if the graph is not connected. If we do that for each train line, we will be able to solve Test Set 1.

Let's define $$$E$$$ as the number of edges of the entire graph, that is, $$$E = \mathbf{K_1} + \mathbf{K_2} + \dots + \mathbf{K_L}$$$. The time complexity to build the graph is $$$O(\mathbf{N} + E)$$$. The time complexity to check if the graph is connected is $$$O(\mathbf{N} + E)$$$. These two operations have to be performed for every train line, therefore the overall time complexity of the algorithm will be $$$O(\mathbf{L} \times (\mathbf{N} + E))$$$.

Test Set 2

The algorithm described for Test Set 1 is too slow for the limits of Test Set 2.

Now let's introduce the concept of articulation points (or cut vertices), which are vertices that, when removed (along with its adjacent edges), make a connected undirected graph not be connected anymore.

Let's explore a different way to represent the railroad network. We will first create $$$\mathbf{L}$$$ special nodes to represent each train line, and then add edges between each train line's special node and the stations that such train line goes through. In other words, for every $$$1 \le i \le \mathbf{L}$$$, let's create a special node $$$\mathbf{P_i}$$$, and for every $$$1 \le j \le \mathbf{K_i}$$$, add an edge between nodes $$$\mathbf{S_{i,j}}$$$ and $$$\mathbf{P_i}$$$.

For this graph representation, the action of shutting down a train line can be seen as removing its special node and all its adjacent edges. Now notice that if a train line's special node is an articulation point, that means that such train line is essential.

To find all articulation points of an undirected graph we can use this modified Depth First Search (DFS) algorithm.

The time complexity to build the graph is $$$O(\mathbf{N} + E)$$$. The time complexity to run the modified DFS algorithm is $$$O(\mathbf{N} + E)$$$. Therefore, the overall time complexity of the algorithm will be $$$O(\mathbf{N} + E)$$$.

For this problem, let's define $$$R_i$$$ as the number of railroad cars that the station $$$i$$$ has already received from other stations. At the beginning, $$$R_i = 0$$$ for all $$$i$$$. Then, each time we make a shipment from station $$$i$$$ to station $$$\mathbf{D_i}$$$, $$$R_{\mathbf{D_i}}$$$ increases by $$$\mathbf{C_i}$$$.

Test Set 1

The shipment order can be defined as a permutation of the network stations. In Test Set 1, the limits are small enough that we can try every possible order and output the smallest answer among all of them.

For a given order, we process the shipments one by one. For the station $$$i$$$, let $$$cost(i)$$$ be the number of additional railroad cars required to complete the shipment. Since we can reuse the received cars to reduce the answer, $$$cost(i) = \max(\mathbf{C_i} - R_i, 0)$$$. We can then add $$$cost(i)$$$ to the answer, and also increase $$$R_{\mathbf{D_i}}$$$ by $$$\mathbf{C_i}$$$.

The answer for a given shipment order can be calculated in $$$O(\mathbf{N})$$$ and there are $$$\mathbf{N}!$$$ different orders. Therefore, a test case can be solved in $$$O(\mathbf{N}! \times \mathbf{N})$$$.

Test Set 2

Let's create a weighted directed graph with $$$\mathbf{N}$$$ vertices (one for each station) and $$$\mathbf{N}$$$ edges (one for each shipment). In other words, for each vertex $$$i$$$ there will be exactly one outgoing edge, from $$$i$$$ to $$$\mathbf{D_i}$$$, with weight $$$\mathbf{C_i}$$$.

Note that for each edge $$$e$$$ from $$$u$$$ to $$$v$$$, if $$$e$$$ is not part of a cycle, then it is optimal to complete the shipment of $$$u$$$ before the shipment of $$$v$$$. The reasoning behind this is that $$$v$$$ can reuse railroad cars sent by $$$u$$$, possibly reducing the answer, while it is impossible to do the opposite: no car can ever travel from $$$v$$$ to $$$u$$$. Therefore, we can apply the following process:

1. Pick any vertex $$$u$$$ with no incoming edges
2. Increase the answer by $$$cost(u)$$$ and $$$R_{\mathbf{D_u}}$$$ by $$$\mathbf{C_u}$$$
3. Erase the vertex $$$u$$$ and its outgoing edge from the graph
4. Repeat while there are vertices with no incoming edges.

Now, since each remaining vertex has at least one incoming edge and exactly one outgoing edge, the graph is now a collection of disjoint simple cycles. Thus, we can add the cost of each cycle separately.

One way to calculate the cost of a cycle is to traverse it for each possible starting point, completing the shipments in order, and then use the smallest answer among all traversals. However, the time complexity of this is $$$O(\mathbf{N}^2)$$$, which is not enough to pass Test Set 2.

We can optimize this to a linear solution with the following observation: suppose that the starting vertex is $$$s$$$. The cost of $$$s$$$ is $$$cost(s) = \max(\mathbf{C_s} - R_s, 0)$$$. For any other vertex $$$u$$$ which is not the starting one, its cost is $$$cost\_in\_cycle(u) = \max(\mathbf{C_u} - R_u - \mathbf{C_{pred(u)}}, 0)$$$, where $$$pred(u)$$$ is the predecessor of $$$u$$$ in the cycle (i.e. $$$\mathbf{D_{pred(u)}} = u$$$). Note that this is independent of $$$s$$$, hence we can precalculate $$$sum\_of\_costs$$$ as the sum of $$$cost\_in\_cycle(u)$$$ for all vertices $$$u$$$ in the cycle and compute the cost for each starting vertex $$$s$$$ as $$$sum\_of\_costs - cost\_in\_cycle(s) + cost(s)$$$, in constant time.