
Match Editorial 
2003 TopCoder Collegiate Challenge
Regional QuarterFinalsWednesday, February 26, 2003
Summary
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
Champagne
Used as: Division 1  Level 1:
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.
Marketing
Used as: Division 1  Level 2:
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 2colorable 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. 2colorability 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.
Macros
Used as: Division 1  Level 3:
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 contextfree languages is decidable. Using dynamic programming this algorithm
determines which nonterminals (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 nonterminals can produce them. Using that
information it tries produce the 3 character substrings. This continues until it determines which nonterminals
can produce the entire string.
By
brett1479
TopCoder Member