
Match Editorial 
2003 TopCoder Collegiate Challenge
Regional FinalsWednesday, March 12, 2003
Summary
This round of the Collegiate Championship was clearly a notch more difficult than all previous rounds.
bstanescu, the only competitor to sucessfully complete the hard problem, received the highest score
for the round. Along with the the challenging hard, coders were faced with an incredibly tricky medium
problem. The 550 caught many competitors by surprise with its unusual style. The easy problem,
a relatively simple dynamic programming exercise, would have been a medium had it been a normal SRM.
If this round is any indication of the future, competitors will need to be in top form to score above
1000 in the upcoming rounds.
The Problems
ChessMetric
Used as: Division 1  Level 1:
Value 
250 
Submission Rate 
47 / 50 (94.00%) 
Success Rate 
42 / 47 (89.36%) 
High Score 
Yarin for 240.21 points 
The most popular way to solve this problem uses dynamic programming. First, set up a
2dimensional array that represents the board. Each element of the array will signify
how many ways there are of reaching a given square. In other words, after the ith iteration
of our loop, a particular element in the array will represent how many ways there are of reaching
the corresponding square in i moves. To initialize the array, all elements should be 0 except the
start square which should be 1. We then loop over the number of moves, using the array from the
previous iteration to produce the array for the next iteration.
TileMatch
Used as: Division 1  Level 2:
Value 
550 
Submission Rate 
26 / 50 (52.00%) 
Success Rate 
14 / 26 (53.85%) 
High Score 
dgarthur for 378.71 points 
At first glance, it may appear that a brute force solution trying combinations of removals would be
the way to solve this problem, but the size of the inputs makes such a method infeasible.
Instead of blindly trying removals, we can directly calculate which colored tiles are causing
problems. By looping over the border of the given tile, we can check, for each square on an edge,
what squares it can come into contact with. For each of the noncorner squares, this involves
checking 12 possible adjacencies that can occur given any rotation of the tile. For corner squares
we must also check 12 possible adjacencies at each of the corners. If we ever find a colored square
that does not have a colored adjacent square we must uncolor that square. We return the total number
of squares that need be uncolored.
Optimizer
Used as: Division 1  Level 3:
Value 
1000 
Submission Rate 
5 / 50 (10.00%) 
Success Rate 
1 / 5 (20.00%) 
High Score 
bstanescu for 428.07 points 
This question, although more straightforward than the medium, requires more code to complete.
Given the grammar of the problem language, we construct a recursive descent parser that will
produce a parse tree of the input. This basically involves building a function for each production
in the grammar. Some tricks are: 1) arranging the grammar such that multiplication has higher precedence
than addition, 2) removing left recursion from the grammar (productions of the form ( N > N... ).
The grammar in this problem is easy enough that these two steps are almost automatic. Once the parser
has built a tree, we can traverse it producing the required optimizations. The easiest transformations
are the identity and annihilation properties: multiply by 1, add 0, multiply by 0. If we find any of
these in the grammar we can simply cut off tree branches. Another easy transformation changes subtrees
of the form "(Number)" to a leaf "Number". In other words, performs the unparenthesizing of numbers.
The most complicated transformation requires the isolation of subtrees that consist of multiplications.
Such subtrees can be replaced by a simpler subtree resulting from applying all associativity rules.
A similar transformation can be performed on subtrees consisting of additions and variable multiplications. Repetitive use of these transformations in a bottom up manner will give us the optimized tree. A final count of the number of multiplies and adds contained in the tree will produce the answer.
By
brett1479
TopCoder Member