Back to news

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 M1, or in M2. Since it doesn't matter, let it be in M1. Then a[1] divides gcd(M1), therefore gcd(M1) — is the divisor of a[1].

Consider all divisors of a[1] (there are at most 1344 for numbers not exceeding 109). For each each divisor d all elements of the array that are divisible by dcan be put to M1 (in this case gcd(M1) would not be less then d, and the fewer elements are there in M2 — the greater gcd(M2) is), all the other elements can be put to M2. The answer can be relaxed with the value min(gcd(M1), gcd(M2)). For the purpose of relaxation we can ignore that M2 is empty and consider gcd for an empty set be equal to infinity. If we put any element to M2 the value of gcd(M2) 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 ti. Let us generate new array cnt[j] equal to the count of i such that ti = 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 (u1, v1) in the first tree and (u2, v2) in the second tree. Let the value dp[u1][v1][u2][v2] be equal to the maximal size of isomorphic subtrees, such that u1 is corresponding to u2 and vertices v1 and v2 are not included into the corresponding subtrees. Additionally, let us also calculate such value for v1 =  - 1 or v2 =  - 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 u1, u2 of the values dp[u1][-1][u2][-1].

To calculate dp[u1][v1][u2][v2] we have to make correspondence between subtrees of u1 in the first tree and u2 in the second tree. Let us note that if e1 is the child of u1 not equal to v1, subtree of e1 contains fewer vertices then subtree of u1. So if we find the values in increasing order of sizes of subtrees, we can use values for all child subtrees. The value dp[e1][u1][e2][u2] gives us the maximal number we can get if we put correspondence between e1 and e2. So we can get the matrix a[e1][e2] which contains maximal values for each pair of adjacent vertices to u1 and u2, 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(n5).

More news

Log in

It.Mail.ru

Forgot password?

Registration

The instruction for password recovery
has been sent to your email