
Match Editorial 
2003 TopCoder Collegiate Challenge
Round 1  InternationalSaturday, February 22, 2003
Summary
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
Pareto
Used as: Level 1
:
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.
Coherence
Used as: Level 2
:
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.
Wireless
Used as: Level 2
:
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 2048element 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 1511 can be modified by either N
(an increase in angle) or E (a decrease). Indices in the range 5131023 are modified by either W
(increase) or N (decrease). Indices in the range 10251535 are modified by either S (increase)
or W (decrease). And indices in the range 15372047 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 twoway
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.