Match Editorial

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

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 2-dimensional 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.

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 non-corner 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.

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.