Match Editorial

The most notable aspect of this round was the Level 2 problem, which was solved by only four coders. This lead to a lot of successful challenges by coders such as John Dethridge. The The Level 1 and Level 3 problems had very high success rates among those that submitted the problems, but only 14 coders managed to submit a possible solution for the Level 3 problem.

The Problems

Value	250
Submission Rate	84 / 102 (82.35%)
Success Rate	78 / 84 (92.86%)
High Score	lars for 232.90 points

Implementation

This problem can be solved by iterating over all pairs of outcomes. For each pair of outcomes A and B, one of the following will be true: A may be suboptimal to B; B may be suboptimal to A; or neither may be suboptimal to the other. In the first two cases, we can eliminate one of the outcomes as a candidate for being a Pareto optimum.

We can do this with two nested loops. The outer loop iterates over all outcomes. The inner loop also iterates over all outcomes. If the outer outcome is not suboptimal to any of the inner outcomes, we know that it is a Pareto optimum and increase a counter. We return this counter after iterating over all pairs in this fashion.

Value	500
Submission Rate	59 / 102 (57.84%)
Success Rate	4 / 59 (6.78%)
High Score	haha for 406.84 points

Implementation

Very few people were able to get this problem, yet the solution is almost embarrassingly simple. The first step should be to compare the number of foreground pixels to the number of background pixels. We will get very bogus results if there are more foreground pixels than background pixels, and it is this sort of test case that broke a great many submissions. The simple fix is to simply invert the colors if there are more foreground pixels than background pixels. This can be as simple as n <?= w * h - n in C++.

There are three possible ways to optimally layout the pixels. The first is to fill rows in the image with the foreground color, until there are not enough pixels left to fill a row (in which case you fill as much of the row as possible, aligned to the left). The second is to fill columns in the exact same fashion. The third is to fill in a rectangle that shares two sides with adjacent borders of the image (i.e., a corner).

For each of the first two methods, there is only one optimal count. The number of boundaries will be the width (height) of the image, plus an additional boundary if we have an incompletely filled row (column). For the third method, we need to iterate through all possible rectangle sizes. For each rectangle, the number of boundaries will be at least the height of the rectangle plus its width. This is true even for rectangles that cannot be completely filled. Only rectangles where every column (row) except for one is filled will be optimal, and in such cases the boundary count works out the same as for the fully filled rectangle; for each pixel that is removed, two previously unexposed boundaries become exposed, while two previously exposed boundaries become internal to the background.

So to solve the problem, we compute the number of boundaries that we would get if we fill in each of the first two fashions, and remember only the minimum. Then we iterate through every possible rectangle size that would fit in the image and be large enough to hold the number of pixels we need, and remember the minimum between our previous minimum and the sum of the dimensions of the rectangle. After all this we return the minimum value.

Value	1000
Submission Rate	14 / 102 (13.72%)
Success Rate	12 / 14 (85.71%)
High Score	John Dethridge for 837.02 points

Implementation

We start out with a 2048-element boolean array (initialized all to false) to indicate whether any particular angle is protected. Next we need to define a function that translates an angle name (e.g. "NENE") to an index into this array.

One way to do this is to precompute all the mappings between angle names and indices. To do this we will define a function that takes an angle name, its index, the index of its nearest neighbors of the same name length, and recursively generates the indices for all angles that have that name as a suffix in their own names. We would call this function four times at the top level, once for each cardinal direction. For instance, to generate all angle names that end with "N", we will start with name = "N", id = 512, prev = 0, and next = 1024. In the definition of this function, we simply determine the two characters that we can add to the beginning of the angle name to make new valid angles and recurse on these new angles. The two characters can be determined by looking at the index. Indices in the range 1-511 can be modified by either N (an increase in angle) or E (a decrease). Indices in the range 513-1023 are modified by either W (increase) or N (decrease). Indices in the range 1025-1535 are modified by either S (increase) or W (decrease). And indices in the range 1537-2047 are modified by either E (increase) or S (decrease). The indices of 0, 512, 1024, and 1536 -- corresponding to the four cardinal directions -- have their own modifiers, which are easy to determine. We will need a two-way mapping for returning the angle name when we're done.

Once we've generated a mapping of angle name to index, the rest of the problem is easy. For each wall description, we iterate from the index of the first angle to the index of the second angle (being careful to wrap around properly when necessary) and mark the angles covered by this range as protected (both endpoints being included). Once we have done this for all walls, we then find the smallest index that is unprotected, and then return the name associated with that index.