PacNW Regional 2014 Solutions

Post date: Jan 4, 2015 9:53:58 AM

Problem B - Alchemy

The first challenge is reading the problem statement. Try it now before continuing ahead! Essentially, we have N circles that don't touch but may contain one another. They must each be activated once, in an order that maximizes the spell's energy. When a circle is activated, energy is added or subtracted to the total by every circle it contains. Conceptually, we can already simplify the problem by thinking of the circles as nodes in a forest (collection of trees, in this case rooted). Each circle's parent in the tree is the smallest circle containing it.

Now, activating a node can be described as turning it from colourless to red. All of the activated node's descendants are affected as follows: every red node i turns blue and adds Ai energy to the spell, while every blue node i turns red and adds Bi energy. Colourless descendants are unaffected. Analysing the total contribution from each such activation is complicated, as it depends heavily on past activations. We must view the problem from a different angle.

When a problem asks for a sum, a common trick is to rearrange its terms into an equivalent sum. (By linearity of expectation, this technique applies equally well when the sum is inside an expectation, so don't be scared of probabilities!) Looking at a fixed node, consider the total energy contribution owed to its colour changes throughout all activations. This value depends only on the number of ancestors that are activated later than this node. If all are activated before and none after, this node contributes 0; if one ancestor is activated after, it contributes Ai; two make it contribute Ai + Bi, three make 2Ai + Bi, etc. Furthermore, this optimization can be done locally, without caring for the relative ordering of any other activations. No matter how the ancestors are ordered amongst themselves, thus determining their own colour-change contributions, the present node can always be inserted between them so that any desired rank from 0 to depthi is achieved. We should choose a rank which maximizes energy.

This is easy enough to write as a very short program, but what if some nodes can be optimal for many different ranks? And how should we interleave different trees and subtrees, which are independent from one another? The problem specifically requests the lexicographically smallest optimal permutation, adding considerable complexity to the implementation. A common trick (thanks Paul for reminding me) is to build the permutation from the first element to the last, at each step taking the smallest possible choice for which a solution exists. Having chosen a node to activate, we can remove it and connect its parent to its subtrees, leaving a new forest and a smaller problem that matches the original specs; we call this a subproblem.

It would be inefficient to solve the subproblem from scratch. If each subproblem took O(N^2), the total runtime would be O(N^3). Fortunately, we can reuse information, updating the data in O(N) time after each activation. Suppose each node stores the set of optimal ranks, as described above. Recall the locality argument, which guarantees the existence of an optimal solution so long as each of these sets remains non-empty. Activating and collapsing a node implicitly adds one to the rank of each of its descendants, so the resulting subproblem should decrease by one each element in the descendants' sets, throwing out any negative numbers that arise. Thus, valid activations to perform at the current step are precisely those which contain zero in their rank sets and a non-zero value in each descendant's rank set. Ancestors of nodes that contain only zero can be marked by a simple multi-source BFS. Among all valid choices, we activate the node which came earliest in the input.

Careful use of basic data structures makes the updates very efficient. Deliberate design and planning can simplify the implementation somewhat; for instance, it's not necessary to code a general graph structure, nor to explicitly collapse activated nodes. The problem bounds were designed so that all results fit into 32 bits. Watch out: not all problem setters are so kind!

Problem G - Number Game

We have N tiles, numbered 1 to N, arranged in a row. Alice and Bob take turns, each taking any one tile which is smaller than its remaining neighbours. The player who takes the 1-tile wins. While an optimized O(N^4) solution was likely to pass under the given bounds, here I describe an O(N) solution. To learn the structure of a game, it's helpful to think along the lines of backward induction: we know the winning condition, and any earlier state wins iff there is a move to put the opponent into a losing state.

Let's assume the most complex case, where the 1-tile is not at either end of the row. Once one of the 1-tile's two neighbours is taken, both players will want to stall the game for as long as possible by taking other tiles, because taking the remaining neighbour would allow an opponent to take the 1-tile and win. Thus, we have two cases depending on which neighbour is taken first. For each case, we compute the total number of moves in the game by greedily taking any available tiles (except the neighbour which is taken last) until none are left, and adding 2 for the 1-tile and its remaining neighbour. This can be done in O(N) using DFS. From the parity of the number of moves, we immediately deduce which player wins in each case.

Now it only remains to determine which case actually occurs, in the event where each case would cause a different player to win. Each player will race to have its preferred neighbour of the 1-tile be taken first. To accomplish this, they have to take every tile going in the corresponding direction from the 1-tile, until the numbers on the tiles stop increasing. The length of this monotonic subsequence is the number of moves needed to take that neighbour. Of course, in the event of a tie, Alice wins as the first move was hers. The attached version takes O(N^2) as I replaced the DFS with simple repeated scans.

Problem J - Stamp Stamp

Thanks to UBC alumnus grandmaster Cedric Lin for the main solution idea! I came fairly close, only to diverge along a completely irrelevant train of thought. The solution is quite creative; however, in ICPC training, we distill creativity itself into an algorithmic problem solving process! Therefore, I will try to explain not only the solution, but also a possible train of thought leading to it. Seasoned programmers can rapidly assault any given problem by a multitude of approaches in parallel, typically based on algorithms and data structures from their vast toolkit, balancing breadth and depth among the different approaches and branching in a heuristic fashion; basically, imagine problem solving as an A* search in the mind.

Note the absence of constraints on which or how many of the pixels have ink, so inverting the image reveals the problem is equivalent to asking for the maximum-size stamp whose translated intersection results in the input image. While we will not make use of this, it is helpful to search for such dualities as they may transform the problem into a more familiar form.

The problem essentially asks us to decompose a given point set into the union of two identical but translated point sets (stamps). As a first attempt at separating out the two copies of the stamp, we might look at the topmost filled pixel, breaking ties by choosing the leftmost. In other words, choose the first pixel in lexicographic (row, column) order. Translation respects this order: A comes before B iff the translated image of A comes before that of B. Thus, the first point in this order must belong to a different copy of the stamp than the last (bottom-right) pixel. Furthermore, we can generalize this order.

To find the most general form for such an ordering, suppose we have a partial order on the rational points of the plane such that all translations respect it. Some thought reveals that there exists some vector such that, if we number points by the (signed) length of their projection along the vector, the numbers are consistent with the order. A full argument is unnecessary; it's enough to make the intuitive generalization of looking at extreme points along all possible directions. We get a total order if no pair of points have the same projection. The lexicographic order corresponds to projection along (1, epsilon) for a very small positive epsilon.

Notice that for any point set, its extreme points along projections are precisely the points on its convex hull. Now we start making certain observations, such as a generalization of what we had before: that opposite corners of the convex hull must belong to different stamps. Many such observations go nowhere. However, consider any extreme point in the direction perpendicular to the true translation vector between the two stamps. Not only is this point on the convex hull, but so is its translation! Furthermore, the grid structure ensures that the points are constrained inside an N by N square. Since convex hulls are minimum-perimeter bounding regions, its perimeter cannot exceed 4N. By simply trying every vector from a corner of the convex hull to points on the same edge of the hull, we need try only 4N candidates!

It remains to solve the problem in O(N^2) time for each candidate translation vector. We will scan the grid along any projection-based ordering, such as the lexicographic order. By negating the translation vector if necessary, we can assume without loss of generality that it jumps forward in this ordering. Every time we encounter a pixel of ink, we erase it as well as any consecutive ink pixels that can be obtained by repeatedly jumping along the translation vector until we see a clear pixel. If this chain has length L, the stamp must add ceil(L/2) pixels to its image. However, if L = 1, we must discard this translation vector as invalid.

An interesting consequence of this algorithm is that, unless the translation was zero, since ceil(L/2) <= 2L/3, the stamp will contain at most two thirds of the input image! In case you were wondering about my tangential train of thought, I noticed that naively trying N^2 possible translation vectors yields an O(N^4) algorithm. Furthermore, the above algorithm only needs to identify whether any length 1 chain exists and count the number of odd-length chains, adding that to half the total ink and halving the result. After briefly flirting with convex hulls, I gave up on them, hoping instead to find redundant computations so as to amortize the total cost of checking N^2 vectors to O(N^3).

Easy combinatorics exercise: how many possible images can the original, untranslated stamp have while still minimizing ink? What if we don't restrict ink?