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

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

To calculate dp[u₁][v₁][u₂][v₂] we have to make correspondence between subtrees of u₁ in the first tree and u₂ in the second tree. Let us note that if e₁ is the child of u₁ not equal to v₁, subtree of e₁ contains fewer vertices then subtree of u₁. 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₁][u₁][e₂][u₂] gives us the maximal number we can get if we put correspondence between e₁ and e₂. So we can get the matrix a[e1][e2] which contains maximal values for each pair of adjacent vertices to u₁ and u₂, 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⁵).