cyfra wins Room 1
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
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 N1 and N2 elements, and are given by the numbers num1...num1[N1] and num2...num2[N2]. 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 besti[n1,n2] the best time to deliver all letters up to n1 on side one and up to n2 on side two, with the last letter being delivered on side i (so that we are in front of house number numi[ni]), we can express this best time recursively. The relation for best1 is:
best1[n1,n2] = min (best1[n1-1,n2] + distance(n1-1,n1), best2[n1-1,n2] + distance(n2,n1) + crosstime).
The intuition behind this recursion should be clear. A similar equation with some ones and twos interchanged holds for best2. 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 best1[N1,N2], best2[N1,N2], the minimum of the following expressions (with n2 being the free parameter)
best1[N1,n2] + crosstime + distance(N1,N2) + distance(N2,n2+1)
or the similar expression for best2. The minimal one is the final answer.
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.
About TopCoder |
Press Room |
Contact Us |
Competitions | Cockpit
|Copyright TopCoder, Inc. 2001-|