tomek takes Room 1... but barelyby vorthys,
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.
CoinWeightAt first glance, this looks like a bogstandard 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[wd,vvalue(c)] then T[w,v] = trueThere 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. StackMachineAt its heart, this is a problem about SethiUllman 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 SethiUllman numbering, you need to know the shape of the expression tree, which you can reconstruct by parsing the input string. SethiUllman 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,cost1), // with swap (right then left) 1 + minSwaps(b,cost) + minSwaps(a,cost1) )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). TreeDrawingConceptually, 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. 
