# 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 *t*_{ij} of the prefix. If the maximal time is greater than *t*_{0} it is better to copy this task, getting the total time needed be *S* - *max*(0, *M* - *t*_{0}). Now compare this value to *t* to check whether it is possible to write down that many tasks for this variant.

## B. Centipede

First sort all notes based on the number of left legs. Then iterate over this array. If the centipede has *l*_{i} 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 *l*_{i}, 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 *r*_{j} ≤ *n* - *l*_{i}. 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 2^{h} - 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 *dfs*2(0) passing the longest path *up*[*v*] to a vertex *v* through its parent. To find it when running *dfs*2(*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*(*min*_{i}) >*sum*(*v*_{i}) — the answer is «NO»; - If
*sum*(*max*_{i}) <*sum*(*v*_{i}) — the answer is «NO»; - Pour
*min*_{i}·*p*_{i}/ 100 of*c*_{i}to each container; - For each reagent
*i*sort containers that have*c*_{j}=*i*by increasing*p*_{j}and pour the rest of reagent*i*to them; - Pour (
*max*_{j}-*min*_{j})·*p*_{j}/ 100 of reagent*c*_{j}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*min*_{j}of liquid - If it is still not enough, we can now move liquid
*c*_{j}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 *a*_{i}. In any other case the answer exists. First let us create any array that satisfies *a*_{1}·*x*_{1} + *a*_{2}·*x*_{2} + ... + *a*_{n}·*x*_{n} = *d*, but not necessarily other conditions. To do this divide all *a*_{i} and *d* to *gcd*(*a*_{1}, ..., *a*_{n}). If *n* = 1, then *x*_{1} = *d* / *a*_{1}. In other cases find the corresponding values for any prefix [1, *p*] such values *x*_{i, p} that *a*_{1} *x*_{1, p} + ... + *a*_{p} *x*_{p, p} = *gcd*(*a*_{1}, ..., *a*_{p}). Use induction. Set *x*_{1, 1} = 1. If we have *x*_{i, p} and want to find *x*_{i, p + 1}. Use extended Euclid algorithm to find *s* and *t*: *s*·*gcd*(*a*_{1}, ..., *a*_{p}) + *t*·*a*_{p + 1} = *gcd*(*gcd*(*a*_{1}, ..., *a*_{p}), *a*_{p + 1}) = *gcd*(*a*_{1}, ..., *a*_{p + 1}). Then for *i* ≤ *p* *x*_{i, p + 1} = *s*·*x*_{i, p} and *x*_{p + 1, p + 1} = *t*. Getting *x*_{i, n}, find *x*_{i} = *d* / *gcd*(*a*_{1}, ..., *a*_{n})·*x*_{i, n} = *d*·*x*_{i, n}. This solution takes *O*(*n*^{2}), and doesn't finish in time limit. To decrease the time complexity, first find subset of *a*_{i} that has gcd equal to 1. Iterate over *a*_{i} and add the current *a*_{i} 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 *x*_{i} = 0.

Now the algorithm is fast, but the conditions for *x*_{i} are not satisfied: they can exceed 10^{6} by their absolute value and there can be zeroes. Now let us normalize the values. First let us decrease *x*_{i} to not exceed 10^{6}. To do this make *x*_{i} non-negative, and less then *a*_{1} for all *i* > 1. This can be done by the following operation: subtract *ka*_{i} from *x*_{1} and add *ka*_{1} to *x*_{i} where *k* = (*x*_{i} mod *a*_{1} - *x*_{i}) / *a*_{1}. Note that the results of this operation can be stored in 64-bit integers, because *x*_{1} cannot exceed |*d* - *a*_{2} *x*_{2} - ... - *a*_{n} *x*_{n}| < 10^{6}·10^{6}·10^{5}. Now consider *x*_{i} starting from the second one, and for each one do the following: subtract *a*_{1} from *x*_{i} and add *a*_{i} to *x*_{1}. Note that there exists *i*, such that after applying the operation to *x*_{1}, ..., *x*_{i} we have 0 ≥ *x*_{1} ≥ - 10^{6}. Now we have |*x*_{i}| ≤ 10^{6}, 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 *x*_{i} = *a*_{j} and *x*_{j} = - *a*_{i}. We probably have one index *p* left such that *x*_{p} = 0. Consider several cases:

- If there exists
*x*_{j}such that it is not equal to*a*_{p}by its absolute value, then apply the following operation: subtract*sign*(*x*_{j})*a*_{p}from*x*_{j}and add*sign*(*x*_{j})*a*_{j}to*x*_{p}. - If there is no such
*x*_{j}, but*a*_{p}≤ 5·10^{5}, for any*x*_{j}we can apply the following operation: add*sign*(*x*_{j})*a*_{p}to*x*_{j}and subtract*sign*(*x*_{j})*a*_{p}from*x*_{p}. - Finally if none of the above is true there must be
*a*_{q}, such that*a*_{q}≠*a*_{p}. Now do the following: subtract*sign*(*x*_{j})*a*_{p}from*x*_{q}and add*sign*(*x*_{j})*a*_{q}to*x*_{p}. Now*x*_{q}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.

## More news

- 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