# Russian Code Cup 2016 — 1st qualification Round — Short Editorial

## A. Binary String

First notice that there is no solution in one of the following two cases:

- Either |
*b*-*c*| > 1 - Or
*b*= 0,*c*= 0, and both*a*≠ 0 and*d*≠ 0

For other cases there are two steps in the solution. First, construct the minimal string that satisfies conditions for 01 and 10 pairs. After that add *a* - 1 zeroes after the first zero, and *d* - 1 ones after the first one.

## B. Train in a Tunnel

The solution is greedy.

First let's turn the light on in the first and in the last car. Then divide the train to one or more segments of continuous cars with light off. Сonsider one such segment. Iterate over cars and when you the sum of lengths of such cars would exceed *h* if we didn't turn the light on in the current car. Then turn the light in that car on, and continue from the next car.

## C. Beautiful Partition

Consider *a*[1], it is either in *M*_{1}, or in *M*_{2}. Since it doesn't matter, let it be in *M*_{1}. Then *a*[1] divides *gcd*(*M*_{1}), therefore *gcd*(*M*_{1}) — is the divisor of *a*[1].

Consider all divisors of *a*[1] (there are at most 1344 for numbers not exceeding 10^{9}). For each each divisor *d* all elements of the array that are divisible by *d*can be put to *M*_{1} (in this case *gcd*(*M*_{1}) would not be less then *d*, and the fewer elements are there in *M*_{2} — the greater *gcd*(*M*_{2}) is), all the other elements can be put to *M*_{2}. The answer can be relaxed with the value *min*(*gcd*(*M*_{1}), *gcd*(*M*_{2})). For the purpose of relaxation we can ignore that *M*_{2} is empty and consider *gcd* for an empty set be equal to infinity. If we put any element to *M*_{2} the value of *gcd*(*M*_{2}) will not be less then *d* in this case since all elements are divisible by *d*.

The time estimation is *O*(*sqrt*(*a*[1] + *d*(*a*[1])·*n*) where *d*(*a*[1]) ≤ 1344.

## D. Problem Preparation

First let us solve the problem if there are no changes in *t*_{i}. Let us generate new array *cnt*[*j*] equal to the count of *i* such that *t*_{i} = *j*. Also calculate the array of prefix sums for *cnt*. Then for each *k* we can find the time for each friend in *O*(*MAX* / *k*) where *MAX* is the maximal time needed for one problem. We just iterate over all *j* and find the number of problems that require exactly *j* minutes for each friend using prefix sums array. The sum for all valid *k* of *O*(*MAX* / *k*) is *O*(*MAXlogMAX*).

Now let us see what happens if we change the time needed for the problem from *t* to *t* + 1. Note that only values for *k* which are divisors of *t* change. Since the number of divisors is small, we can just iterate over all divisors and change the answer just for them.

Similar idea works when *t* changes to *t* - 1, the answer changes only for such *k* that are divisors of *t* - 1.

## E. Similar Subways

You have to find isomorphic connected subtrees of the two given trees with maximal number of vertices. Let us use dynamic programming to solve the problem.

Consider two directed edges (*u*_{1}, *v*_{1}) in the first tree and (*u*_{2}, *v*_{2}) in the second tree. Let the value dp[*u*_{1}][*v*_{1}][*u*_{2}][*v*_{2}] be equal to the maximal size of isomorphic subtrees, such that *u*_{1} is corresponding to *u*_{2} and vertices *v*_{1} and *v*_{2} are not included into the corresponding subtrees. Additionally, let us also calculate such value for *v*_{1} = - 1 or *v*_{2} = - 1, which means that any vertex from the first/second tree can be in a subtree. Then the answer to the problem is maximum over all *u*_{1}, *u*_{2} of the values dp[*u*_{1}][-1][*u*_{2}][-1].

To calculate dp[*u*_{1}][*v*_{1}][*u*_{2}][*v*_{2}] we have to make correspondence between subtrees of *u*_{1} in the first tree and *u*_{2} in the second tree. Let us note that if *e*_{1} is the child of *u*_{1} not equal to *v*_{1}, subtree of *e*_{1} contains fewer vertices then subtree of *u*_{1}. So if we find the values in increasing order of sizes of subtrees, we can use values for all child subtrees. The value dp[*e*_{1}][*u*_{1}][*e*_{2}][*u*_{2}] gives us the maximal number we can get if we put correspondence between *e*_{1} and *e*_{2}. So we can get the matrix *a*[*e*1][*e*2] which contains maximal values for each pair of adjacent vertices to *u*_{1} and *u*_{2}, correspondingly. Now we have to find the maximal weight matching in this matrix which can be done by mincost flow, or Hungarian algorithm.

The complexity is *O*(*n*^{5}).

## 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 — Elimination Round — Short Editorial 17.06.2016