Match Editorial

Tension builds as we get closer and closer to the finals. This round, the Regional Quarterfinals, proved to be one of the most interesting to date. After 15 minutes only a few competitors submitted the easy problem, a departure from the normal frantic pace. John Dethridge, the top ranked competitor, was seemingly unfazed by the problem set. He sped through all 3 problems winning the round by a margin. Quite amazingly he finished both the easy and the hard before second highest ranked coder Yarin submitted his first problem. As time passed many coders finished the treacherous easy and were able to complete the rest of the problems. Although slightly troubled by the easy problem, Reid finished off the rest of the set with ease propelling him to second place. Previous tournament champions jonmac and dmwright are both returning to top form winning their respective rooms.

The Problems

Value	300
Submission Rate	168 / 273 (61.54%)
Success Rate	100 / 168 (59.52%)
High Score	John Dethridge for 272.77 points

One popular way to solve this problem involves building an array of the entire champagne glass tower simulating the process second by second. At the beginning of each iteration pour 1 unit of champagne into the first glass. Then loop through the entire tower searching for spills. If a spill occurred, distribute its contents to the two glasses below it. An optimization on this method involves pouring all of the champagne into the first glass all at once, and processing the rest of the tower as before. Some other coders used recursive methods that similarly handled spillage and distribution of champagne. An easy way to deal with the required fractional amounts was to pick some arbitrarily large power of 2 and store all glass contents as fractions of that amount. 2^23 would have been more than sufficient for all of the possible tower sizes. At the end a call to a GCD function would reduce the fraction producing the correct results. This method avoids the use of any floating points values.

Value	500
Submission Rate	99 / 273 (36.26%)
Success Rate	66 / 99 (66.67%)
High Score	sjelkjd for 448.58 points

The problem requirements cleanly map to a pair of concepts in the field of graph theory. Splitting the marketed products equally to two consumer groups corresponds to the notion of bipartite or 2-colorable graphs. Once a graph is determined to be bipartite one must determine the number of distinct connected components in order to calculate the flexibility present in marketing schemes. 2-colorability is quickly verified using a depth first search that colors each adjacent vertex with a different color. If you ever try to color the same vertex twice with a different color each time, the graph is not bipartite and your method can return -1 immediately. To determine the number of components a depth first search will suffice again. A single call to the search on a particular vertex will identify all reachable vertices. Repeating this process until all vertices have been reached one way or another will produce the number of components. 2 raised to this number is the number of possible ways to market the products.

Value	1000
Submission Rate	39 / 273 (14.29%)
Success Rate	18 / 39 (46.15%)
High Score	John Dethridge for 888.44 points

This problem is related to a well known algorithm in formal language theory that determines which strings are derivable from a given grammar. The existence of this algorithm, called CKY after its inventors, proves that the membership problem for context-free languages is decidable. Using dynamic programming this algorithm determines which non-terminals (called Variable Characters in the problem) can produce fragments of the string, and then builds the entire string from these fragments. For example, lets say the string was "abba". The algorithm would first determine which 2 character substrings can be produced by the given rules and how they are produced, i.e. whether ab, bb, and ba can be derived and which non-terminals can produce them. Using that information it tries produce the 3 character substrings. This continues until it determines which non-terminals can produce the entire string.