Russian Code Cup 2016 — Elimination Round — Short Editorial
A. Important Test
For each variant consider all prefixes of tasks. It is optimal to copy the task that takes most time, so we keep track of maximal time and calculate the sum S of tij of the prefix. If the maximal time is greater than t0 it is better to copy this task, getting the total time needed be S - max(0, M - t0). Now compare this value to t to check whether it is possible to write down that many tasks for this variant.
First sort all notes based on the number of left legs. Then iterate over this array. If the centipede has li left legs, then first i notes can be correct, and other notes are definitely incorrect (we can ignore the fact that some notes have the same li, we will find the answer considering them).
Now we want to find out how many of the first i notes can be correct. Note with number j ≤ i can be correct if rj ≤ n - li. This problem is quite standard, we can solve it using, for example, Internal Tree.
C. Binary Tree
To minimize the number of days Basil needs, we need to minimize the height of the resulting tree. If the depth of the leaf in the resulting tree is h, Basil needs 2h - 1 - n days to create the required number of vertices.
Note that if the tree has a vertex of degree greater than 3, it is impossible to fulfill the task, because in a complete binary tree every vertex has at most 3 neighbors. Also note that the root vertex must have two sons.
So let us try all vertices with degree not greater than 2 and try it as a root. Choose vertex which results in the smallest tree height.
Finding the most distant vertex for each vertex in a tree is a well known trick. Choose vertex 0 as a root and run dfs(0). First find h[v] for each vertex — the length of the longest path down starting from v. Then run dfs2(0) passing the longest path up[v] to a vertex v through its parent. To find it when running dfs2(x) from y we choose maximum among up[y] + 1, and maximal value of h[z] + 2 for all children z of y except x.
D. Containers and Reagents
The solution proceeds in several rounds.
- If sum(mini) > sum(vi) — the answer is «NO»;
- If sum(maxi) < sum(vi) — the answer is «NO»;
- Pour mini·pi / 100 of ci to each container;
- For each reagent i sort containers that have cj = i by increasing pj and pour the rest of reagent i to them;
- Pour (maxj - minj)·pj / 100 of reagent cj to the container j;
- The rest of reagents can be put to containers arbitrarily;
- If after doing so there is still extra liquid the answer is «NO»;
- Some containers may still have not enough liquid.
- Consider such container i, first pour from other container reagents other than this container is marked by, not making it contain less then minj of liquid
- If it is still not enough, we can now move liquid cj from container j, it will not ruin percentage condition any more.
Now the resulting distribution of reagents satisfies all required conditions.
Final note: there could be precision troubles in this problem. Although there were no such tests, they are possible, Petr Mitrichev (congratulations on winning the round!) found such test after the contest. We understand that this is not good, and will try to avoid such problems in future.
E. Money Exchange
Let us first solve the following problem: find the minimal amount of money that cannot be paid by a set of coins. Let us first consider that we have no coins and the maximal amount we can pay is 0.
Let us describe the step when we have considered all coins with the value not exceeding X and we can pay any sum up to Y, inclusive. Let the total cost of coins with value greater than X, but not exceeding Y + 1, be sum. Then if sum = 0, we cannot represent Y + 1 with this set. In the other case we can move to the state where we have considered coins with the value not exceeding Y + 1, and we can pay any sum up to Y + sum, inclusive.
Now we see, that the value of the greatest considered coin grows as Fibonacci numbers, so the process terminates in at most O(log Answer) iterations.
So what we need to do now is to find the sum of numbers not exceeding X at a segment. This can be done using Interval Tree, the final complexity is O(m log n log Answer).
F. Elimination Round, Problem F
The answer is «NO» only if d is not divisible by the greatest common divisor of all ai. In any other case the answer exists. First let us create any array that satisfies a1·x1 + a2·x2 + ... + an·xn = d, but not necessarily other conditions. To do this divide all ai and d to gcd(a1, ..., an). If n = 1, then x1 = d / a1. In other cases find the corresponding values for any prefix [1, p] such values xi, p that a1 x1, p + ... + ap xp, p = gcd(a1, ..., ap). Use induction. Set x1, 1 = 1. If we have xi, p and want to find xi, p + 1. Use extended Euclid algorithm to find s and t: s·gcd(a1, ..., ap) + t·ap + 1 = gcd(gcd(a1, ..., ap), ap + 1) = gcd(a1, ..., ap + 1). Then for i ≤ p xi, p + 1 = s·xi, p and xp + 1, p + 1 = t. Getting xi, n, find xi = d / gcd(a1, ..., an)·xi, n = d·xi, n. This solution takes O(n2), and doesn't finish in time limit. To decrease the time complexity, first find subset of ai that has gcd equal to 1. Iterate over ai and add the current ai to the set if it decreases the number of different divisors. Such subset would contain at most 7 elements. Use the algorithm described above for this set, for other elements set xi = 0.
Now the algorithm is fast, but the conditions for xi are not satisfied: they can exceed 106 by their absolute value and there can be zeroes. Now let us normalize the values. First let us decrease xi to not exceed 106. To do this make xi non-negative, and less then a1 for all i > 1. This can be done by the following operation: subtract kai from x1 and add ka1 to xi where k = (xi mod a1 - xi) / a1. Note that the results of this operation can be stored in 64-bit integers, because x1 cannot exceed |d - a2 x2 - ... - an xn| < 106·106·105. Now consider xi starting from the second one, and for each one do the following: subtract a1 from xi and add ai to x1. Note that there exists i, such that after applying the operation to x1, ..., xi we have 0 ≥ x1 ≥ - 106. Now we have |xi| ≤ 106, so everything that is left is to get rid of zeroes. Let us pair all zeroes to each other, except probably one if the number of zeroes is odd. For each such pair (i, j) set xi = aj and xj = - ai. We probably have one index p left such that xp = 0. Consider several cases:
- If there exists xj such that it is not equal to ap by its absolute value, then apply the following operation: subtract sign(xj)ap from xj and add sign(xj)aj to xp.
- If there is no such xj, but ap ≤ 5·105, for any xj we can apply the following operation: add sign(xj)ap to xj and subtract sign(xj)ap from xp.
- Finally if none of the above is true there must be aq, such that aq ≠ ap. Now do the following: subtract sign(xj)ap from xq and add sign(xj)aq to xp. Now xq is zero. But if n > 2, it is the first case for q, if n = 2 it is the second case for q.
Finally note that we must make this normalization must be performed for each prefix in the algorithm described in the first paragraph, so that the intermediate results fit 64-bit type. See judges solution for more details.
- Solution of the final round of RCC2016 The final round of RCC2016 is over! We congratulate the winners! Here you can find solutions for the final tasks. 18.09.2016
- Russian Code Cup 2016 — 3rd qualification Round — Short Editorial 03.06.2016