|
||||
|
||||
 |
 |
 |
||
|
||||
|
 |
 |
 |
|
|
Online Rounds | Room 1 | Room 2 | Room 3 | Wildcard | Finals | |
|
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.
CoinWeight
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.
StackMachine
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
else
// 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
else
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).
TreeDrawing
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.