Get Time

2004 TopCoder Collegiate Challenge

Algorithm Headline
  Tournament Overview Tab Algorithm Tab Component tab  
about advancers details
Online Rounds Room 1 Room 2 Room 3 Wildcard Finals

See more photos!

The field of battle

tomek takes Room 1... but barely

by vorthys,
TopCoder Member
Thursday, April 15, 2004
introduction by lbackstrom

All eyes were on Room 1, as top seeded tomek sought to represent and crush the competition. According to radeye's odds, tomek had about a 57% chance of winning this room. But, confident as ever, tomek said the night before that he estimated his probability of advancing at 95%. As the room started, all 8 competitors opened the easy problem. Ruberik, the only Java coder in the round, was first to submit, but he was quickly followed by 5 other coders in the next 6 minutes. bstanescu moved on to the hard problem, a strategy that paid off for him in the last TCO. All other competitors opened the 500 first. At the half way mark, everyone had submitted the easy problem, and only Polish competitors had submitted the medium, with tomek leading Eryx by 27 points.

After a little while, a few competitors gave up on the medium, and moved on to a brutal hard problem. lars was among them, but then had an epiphany and went back to submit the medium problem, placing him in third. About an hour into the coding phase, tomek psyched out the other competitors, submitting the hard problem, despite the fact that he had hardly tested it. The final submissions of the round came when AdrianKuegel submitted the medium, and then resubmitted it.

During the challenge phase, everyone searched through the problems, hoping to pick up an extra 50 points. But no one had the guts to challenge, and going into the system tests, tomek was in the lead with all three problems, while Eryx and lars were in second and third.

Surprising no one, tomek's hard problem failed, but his other two held up, and he advanced to the final round. Eryx and lars took second and third, and must compete again in the Wildcard Room later tonight. Good luck to all the competitors in the next rooms.


At first glance, this looks like a bog-standard knapsack problem, but the ranges on the weight of each coin mean you have to do a little bit more. Knapsack suggests dynamic programming, so if you take that approach, you'll build a table where T[w,v] is true if and only if it is possible to achieve a value v using coins with a combined weight of w. Then you just count the number of trues in the row for the given weight.

You can fill in the table using four nested loops:

  T[0,0] = true
  for each coin type c do
     for each weight d in minWeight(c) .. maxWeight(c) do
        for each weight w in d .. total weight do
           for each value v in value(c) .. max value do
              if T[w-d,v-value(c)] then
                 T[w,v] = true
There are many possible variations on these loops. For example, you can reorder the loops at will, as long as you keep the d loop inside the c loop. Each ordering of the loops suggests different possible optimizations, some of which get rid of the d loop entirely. However, the constraints were small enough that no optimizations were needed.


At its heart, this is a problem about Sethi-Ullman numbering, which is an algorithm commonly used in compilers to determine how many registers you need to evaluate an arithmetic expression. The number of registers used in a register machine is the same as the number of stack slots used in a stack machine (ignoring the inconvenient fact that most real machines have only a small number of registers).

To apply Sethi-Ullman numbering, you need to know the shape of the expression tree, which you can reconstruct by parsing the input string. Sethi-Ullman numbering calculates the cost of an expression e as follows.

   function minCost(e) is
      if e is a leaf then return 1
// e is a binary operator applied to a
// left argument and a right argument
         lcost = minCost(left argument of e)
         rcost = minCost(right argument of e)
// cost without swap (left then right)
         return min( max(lcost,1+rcost),
// cost with swap (right then left)
                     max(rcost,1+lcost) )
The minimum and the maximums in the return statement have the effect of returning the bigger of lcost and rcost, unless they are equal, in which case you return 1+lcost (or, equivalently, 1+rcost). In essence, you want to do the left side first if lcost is bigger and the right side first (ie, do a swap) if rcost is bigger. If the costs are the same, then it doesn't matter which one you do first.

Once you know the minimum cost of the expression, you can go back and compute the minimum number of swaps needed to achieve that cost. This can be expressed recursively as

   function minSwaps(e,cost) is
// can't achieve the given cost
      if cost == 0 then return ∞
// no swaps needed
      if e is a leaf then return 0
// e is a binary operator applied to a
// left argument and a right argument
         a = left argument of e
         b = right argument of e
// without swap (left then right)
         return min( minSwaps(a,cost) + minSwaps(b,cost-1),
// with swap (right then left)
                     1 + minSwaps(b,cost) + minSwaps(a,cost-1) )
However, this version of minSwaps is inefficient because it repeatedly calls itself on the same subexpressions with the same costs. Memoization can easily take care of this inefficiency, as can dynamic programming (albeit a little less simply).


Conceptually, this was probably the easiest problem of the round. Nothing fancy is needed—no DP!—just recursion and careful attention to detail. But conceptually easy does not necessarily mean easy to code in 75 minutes. There are a lot of details to get right, and a lot of steps along the way.

The crucial intuition is to realize that nothing that happens outside of a given subtree can affect the layout within that subtree. In other words, once a subtree is drawn, it might be moved around as a unit, but the individual components inside the subtree will never move around with respect to each other.

Therefore, to draw a tree, we recursively draw its subtrees, squeeze the subtrees as close together as we can, and center the label of the root over the children. At the very end, we pad all the rows with spaces as necessary to make the final drawing rectangular.

The key step is squeezing two subtrees together. Because nothing inside the subtrees can change, we only need to keep track of the left and right borders of each subtree. Then we position the subtrees so that the right border of the left subtree and the left border of the right subtree are separated by exactly one space in some row (and by one or more spaces in all the other rows).

A potentially tricky case arises when calculating the borders of a new tree. The left border of the combined tree is the left border of the left subtree, and the right border of the combined tree is the right border of the right subtree. However, when one of the subtrees is taller than the other one, we still need to fill in the missing border. For example, if the right subtree is taller than the left subtree, then the left border of the combined tree is the left border of the right subtree in those rows below the bottom of the left subtree.