cyfra wins Room 1


Discuss this match
Wednesday, May 3, 2006
Introduction by lbackstrom

The TCO kicked off this morning in sunny Las Vegas. With more competitors from more countries and more spectators than ever before This year's TCO promises to be a thrilling event.

The round started with all but one of the competitors opening the easy problem. OpenGL was first to submit, but he found a flaw in his solution and eventually resubmitted. Petr submitted second, 13 points ahead of krijgertje. The easy proved difficulty for most though, and after 25 minutes, only half of the competitors had submitted it, but the other half were all still working hard on it. As the seconds ticked by, the easies rolled slowly in, and after 40 minutes all but 3 of the competitors had submitted it. Petr was the first to submit the second problem, with a little over 40 minutes left to go. krijgertje was next to submit the medium problem, but he had to resubmit, putting him over 2 challenges behind Petr, but giving him enough points to stay in second until the end. At the end of the coding phase, all but one of the competitors had submitted the easy problem, and 10 of the 16 competitors had submitted the medium. Petr had a comfortable lead, and seemed sure to advance as long as his two submissions held up. krijgertje, on the other hand, was less than one challenge ahead of cyfra and Egor in third and fourth places.

The challenge phase started off slow, with a couple of unsuccessful challenge in the first few minutes. With two minutes to go though, Petr successfully challenged krijgertje, expanding his lead. Shortly later, SnapDragon successfully challenged OpenGL, moving him into third place, with cyfra holding on in second.

System tests were not kind to the competitors and only cyfra had two submissions survive for the win. Petr's medium fell, but his fast easy problem was enough to get him into the finals (by 0.25 points). SnapDragon, bladerunner, Ying, and grotmol, the only other competitors with positive points, advance to the wildcard round.

ThirstyGroup

by lovro

Regardless of which glass we choose, the amount of water each glass gets doesn't change. We need to find the glass which will get us the most water in the end.

Simulating the entire party can take a billion time units, so we need to think of something better. Assume that we have an infinite supply of water available. Suppose we evaluate the situation at time index T. The problem statement describes the participants as greedy i.e. everyone attempts to gather as much water as possible. But this enables us to calculate the exact amount of water everyone got by time T and the overall water used. The exact formula for the i-th person is ceil(T / (capacities[i]+1)) * capacities[i], which can be written as (T+capacities[i]) / (capacities[i]+1) * capacities[i], when division truncates.

The next thing to note is that the total amount of water used is a nondecreasing function of T. This allows us to use binary search to find the last time index at which the amount of water used is no more than the amount of water available. Earlier we assumed that the supply of water was infinite and everyone could always fully refill their glass. This is not the case, but our binary search will calculate the last time index for which the assumption holds.

What's left is to distribute the remaining water. A bit of insight tells us that all the remaining water will be taken in an instant (otherwise, our binary search would have returned a later time index). But the only ones to get water will be those whose glasses are empty at time T, which the division remainder operator will happily tell us: the condition is T mod (capacities[i]+1) == 0. We now know how much water each glass gets and which one to choose

Postman

by Jan_Kuipers

The easy part is parsing the input and splitting it in two sets: the odd house numbers and the even ones. Let's say these two sets have N₁ and N₂ elements, and are given by the numbers num₁[1]...num₁[N₁] and num₂[1]...num₂[N₂]. We assume these two arrays to be sorted.

We start in front of house number 1 and have to walk our way to the increasing numbers. The first observation is that it never helps to deliver a letter to a house on one side of the road if there are still houses to deliver to on the same side with both smaller and larger numbers. So to start off with, we can deliver the letters on both sides in increasing order. Only in the end, delivering the last letter first and then walking back, can be useful.

This increasing order in which the letters can be delivered immediately smells like a dynamic programming approach, which indeed is the right way to solve it. If we call best_i[n₁,n₂] the best time to deliver all letters up to n₁ on side one and up to n₂ on side two, with the last letter being delivered on side i (so that we are in front of house number num_i[n_i]), we can express this best time recursively. The relation for best₁ is:

best₁[n₁,n₂] = min (best₁[n₁-1,n₂] + distance(n₁-1,n₁), best₂[n₁-1,n₂] + distance(n₂,n₁) + crosstime).

The intuition behind this recursion should be clear. A similar equation with some ones and twos interchanged holds for best₂. To obtain the final answer one subtlety arises as already mentioned: after delivering every letter on one side, it can be quicker to walk to the end of the other side, deliver there, and then walk back. The final answer therefore is either best₁[N₁,N₂], best₂[N₁,N₂], the minimum of the following expressions (with n₂ being the free parameter)

best₁[N₁,n₂] + crosstime + distance(N₁,N₂) + distance(N₂,n₂+1)

or the similar expression for best₂. The minimal one is the final answer.

SymmetricalTree

by Andrew_Lazarev

To solve the main problem let's solve the following subproblem. For two given nodes of the tree v1 and v2 let's find the best in terms of the problem common string representation B[v1, v2], i.e. such first lexicographically representation which is obtained for both nodes by removing the least number of child nodes. This can be done using dynamic programming. Let's introduce A1[v1, v2, s1, s2], where s1 is any subset of children of the node v1, s2 is any subset of children of the node v2, and A1 is the best common string representation of nodes v1 and v2, if it is allowed to take only children from s1 and s2 correspondingly. Let's define A[v1, v2, s1, s2] equal to A1[v1, v2, s1, s2] without leading '1' and last '0'. So, B[v1, v2] = '1' + A[v1, v2, all children of v1, all children of v2] + '0'. To find A[v1, v2, s1, s2] let's iterate the last child node i1 in s1 and i2 in s2. In this case A[v1, v2, s1, s2] = A[v1, v2, s1-i1, s2-i2] + B[i1, i2]. Now back to the main problem. For the root node let's iterate through all possible first c1 and last c2 children of the root in the result tree. In this case the answer will be B[c1, c2] + answer for the problem without nodes c1 and c2 + reversed B[c1, c2]. From all such answers choose the best. In such a way we reduced the dimension of the problem. If the root node has only one child left, the answer will be the answer for this node with '1' and '0' attached correspondingly. If the root node has two children we can try to delete one of them and get the previous case.