November 2011 Cook-off Problem Editorials

Problem Setter for the contest was Gennady Korotkevich.
Problem Tester for the contest was Anton Lunyov.

----------------------------------------------------------

COLCHAIN : Colorful Chain

Consider a particular coloring. Let's call a pair of links good if they are of the same color and there are less than M other links between them, so that there exists a block of M+1 links containing this pair. It's easy to see that the coloring satisfies the restrictions if every block of M+1 consecutive links contains exactly one good pair. Even more, suppose we have fixed a set of good pairs and there is exactly one good pair in each block of size M+1. Then there are M! satisfying colorings having exactly such set of pairs. We can see it when we try to color the links from left to right -- the coloring becomes uniquely determined after we color the first M+1 links.

The problem is thus reduced to finding the number of satisfying sets of good pairs and multiplying this number by M!. Let's consider two arrays A and B of size K, where K is the number of good pairs. A_i and B_i are the indices of the chains of good pair i so that A_i < B_i. Let's also sort the pairs in increasing order of B_i. For any satisfying coloring the following conditions must be held:

• B₁ ≤ M+1 and (if K > 1) B₂ > M+1, as the first block should contain exactly one good pair;
• N-M ≤ A_K < B_K and (if K > 1) A_K-1 < N-M, as the last block should contain exactly one good pair;
• A_i+M+1 = B_i+1 for each 1 ≤ i < K -- block A_i..A_i+M contains one good pair (A_i B_i), and block A_i+1..A_i+M+1 should contain one good pair, for which the only candidate is (A_i+1 B_i+1); also, as A_i < B_i, this implies B_i+1-B_i ≤ M.

Now, let's look at these conditions carefully. Suppose we've fixed array B so that all the conditions above are satisfied. What is the number of ways to fill A? Notice that A_1..K-1 are determined uniquely using the third condition, and there are B_K-(N-M) ways to fill A_K by the second condition.

Let f[i] be the number of ways to fill array B so that the last value B_K = i (we don't consider the second condition now). By the first condition we get f[2] = f[3] = ... = f[M+1] = 1. Then, by the implication from the third condition we get f[i] = sum(f[i-M]..f[i-1]) for i > M+1. The answer now is sum(f[i]*(i-(N-M))) for i > N-M (multiplication comes from the number of ways to fill A_K). This description may be difficult to fully understand, so you're encouraged to try to figure out the exact details by yourself given the main idea.

The last thing to note is that we should calculate the values of f[] in O(N) time, as O(N²) is too much to pass the time limit. One of the ways is to maintain an auxiliary array s[] so that s[1] = 0 and s[i] = s[i-1]+f[i] for i > 1 (so s[i] is the sum of f[1]..f[i]). Then f[i] = s[i-1]-s[i-M-1], as it can be easily seen. Another way is to notice that f[M+2] = M and f[i] = 2*f[i-1]-f[i-M-1] for i > M+2. Of course, all calculations should be done modulo 10⁹+7.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

MVCOIN : Moving Coins

A simple greedy solution is possible. First, suppose we have a group of Q coins placed in subsequent cells. How many moves do we need to move this group one cell to the left? The answer is (Q-1)/K+1 (integer division is supposed) -- the sum of cells' indices must decrease by Q while we can only decrease it by K in one move, so that's the lower bound; moreover, if we move every K-th coin from the left and also the rightmost coin of the group, we'll make exactly (Q-1)/K+1 moves, so that's also the upper bound.

Now, consider the rightmost coin (on cell X) and the nearest coin to the left of it (on cell Y). Obviously, we'll have to move the rightmost coin to cell Y+1 at some moment of time. So why not to do it first? Next, consider the nearest coin to the left of the coin on cell Y (on cell Z). We'll have to move coins on cells Y and Y+1 to cells Z+1 and Z+2 at some moment of time, so again, why not to do it right now? Here we have two possibilities -- either move each coin independently or move them as a group in the sense described above -- and it's easy to see that moving the group is better. Now we have a group of three coins on cells Z, Z+1 and Z+2, so we can move these coins up to the next coin on the left -- and again, moving it as a whole group can't be worse than separating the coins into different groups and moving each of them independently.

So, the optimal strategy is to move from the rightmost coin left increasing the size of the group and moving it one cell left as a whole when needed. This solution is very easy to implement. Its complexity is O(N log N), so it works even when N is up to 100000 and there are 10⁹ cells. The constraints were deliberately set low to allow solutions with higher complexities, but probably the simplest O(N²) solution is harder to implement than the described one.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

SUBANAGR : Subanagrams

It's easy to check if a string is an anagram or a subsequence of some other string. Is it easy to check if a string is an anagram of some subsequence (a subanagram) of some other string? Yes, it is!

To see that, notice that if string A contains more letters 'a' than string B, then A can't be a subanagram of B. The same is the case for any other letter. If no such letters exist, it's obvious that A is a subanagram of B -- we may remove extra letters from B to get A's anagram.

When we're dealing with a set of strings, it's easy to see that each letter's quantity in the resulting string can't exceed the corresponding quantity in each string from the set. As we need the longest possible string, let's set each letter's quantity to be equal to the smallest of such quantities in the strings of the set. Lastly, as we need the lexicographically smallest string, output the resulting letters in alphabetical order as their order doesn't matter.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

GRAPLANE : Graph on a Plane

First, let's solve the following subproblem. Suppose we've already distributed the vertices of the graph among the quadrants. What is the smallest possible number of intersections then? Obviously, each edge connecting two vertices from differents quadrants produces at least one intersection. But notice that at least is actually at most -- we can place each vertex so that the absolute values of its X and Y coordinates are equal. This way every edge connecting the 1st and the 3rd (or the 2nd and the 4th) quadrants will pass through the origin, resulting in just one intersection for us. Of course, the graph won't look good any more, but recall that Caroline doesn't care about that :)

Now on to the problem. Instead of minimizing the number of edges connecting vertices from different quadrants, let's maximize the number of edges connecting vertices from the same quadrant (that's essentially the same; we'll call such edges inner). The only question remaining is the optimal distribution of vertices among the quadrants. Simply trying every possible distribution won't finish in time -- there are 192 972 780 different distributions into subsets of 4, 4, 5 and 5 vertices in the worst case of N = 18.

Let's iterate over all possible sets of N/2 vertices (recall that N is even) and find the best (with maximal number of inner edges) distribution of these vertices between two quadrants simply checking every possible distribution. For N = 18 we have 48 620 subsets of size 9 and 126 possible separations of 9 vertices into 4 and 5, giving a total of 6 126 120 combinations -- considerably less than 192 million. Then, let's iterate over all possible separations of the given N vertices into two subsets of size N/2. As for either subset we already know the best distribution between two quadrants, we can just add the numbers of inner edges for both subsets to get the number of inner edges in the best overall distribution.

This approach is of course faster than the trivial one, but it is still too slow if we count the number of inner edges improperly. The fastest way to do it is to use bitmasks. We can build a bitmask T_i for each vertex with set bits (that is, 1-bits) corresponding to the vertices connected with it. If we want now to find out how many edges connect vertex i with vertices of some fixed subset represented by bitmask B, we can just find the number of set bits in B & T_i, where & is bitwise AND operation. The number of set bits can be easily precalculated for each possible mask beforehand. Solutions using this approach were supposed to get accepted though they might have needed some optimization.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

BUYING : Buying Candies

Essentially, we're asked to find a subset S of the given N numbers containing exactly M numbers such that their sum is the smallest possible sum divisible by K. An easy O(NMK) dynamic programming solution, where the state is (how many numbers have been processed, how many numbers have been chosen, what is the current sum of chosen numbers modulo K) obviously exceeds the time limit.

Of course, we need some observations to proceed further. The first useful observation can be the following. Suppose the given numbers are separated into K bunches based on their value modulo K. Then, if we are going to include X numbers from a particular bunch into S, it's easy to see that we should include the smallest X of them.

The second useful observation is trivial. Let's include the smallest M numbers of the given N into S, and say their sum is Q. If Q is divisible by K, the answer is found! This doesn't seem to help much from the first sight, but actually it helps. Obviously, when Q is not divisible by K, we should remove several -- say, R -- numbers from S and include R other numbers into S. Intuition may tell that in the optimal solution the value of R is not very large since K is very small, and that's correct. Let's denote the largest possible value of R by W and show that W ≤ K(K-1). Suppose R > K(K-1). By pigeonhole principle, there will be at least one bunch (as described above) containing at least K removed numbers, and at least one bunch containing at least K added numbers. But if we hadn't removed those K removed numbers and hadn't added those K added numbers, the sum of numbers is S would have been smaller while still divisible by K, so a solution with R > K(K-1) can't be optimal.

Now a DP solution is possible, but instead of processing numbers one by one, we will process whole bunches. Let's assign each bunch a number called delta in [-W;+W] interval, with -C meaning that we remove C largest added numbers of this bunch from S, and +C meaning that we add C smallest unadded numbers of this bunch to S. Let's also define a function H(bunch,delta) meaning by how much the total sum changes when we "apply" delta to this bunch (this value is negative when delta is negative). As we should add exactly as many numbers as remove, the sum of all deltas should be equal to 0. Another condition is that the initial sum of numbers in S plus all the values of H(bunch,delta) should be the smallest possible such sum divisible by K. Note that H(bunch,delta) may be undefined if there are not enough numbers in the bunch.

The only remaining question is an optimal assignment of deltas to the bunches, and we'll use DP. The state of our DP will be (how many bunches have been processed, what is the current sum of all deltas, what is the current sum of chosen numbers modulo K), and the value of DP in this state is the smallest possible current sum of chosen numbers under these conditions. So, from state (i, j, p) we can move to (i+1, j+C, (p+H(i,C)) mod K) adding H(i,C) for every C between -W and +W. The initial state is (0, 0, the initial sum mod K), and the final state is (K, 0, 0). The complexity of this solution is O(N+K²W²), which is O(N+K⁶) when W = K(K-1).

In fact, it can be proved that W ≤ 2K-2. It comes from the proof that you can always choose K integers from any 2K-1 integers so that their sum is divisible by K (so, in context of our problem it means that we can find K such numbers among the removed ones, K such numbers among the added ones, and replace the added numbers with the removed numbers decreasing the sum and leaving the modulo value untouched). I'm not posting this proof here, but it does exist :) This was probably impossible to prove during the contest if you hadn't known the fact before, but it was possible to believe your intuition and convince yourself that the value of K(K-1) is still too large for W -- in fact, even 2K-2 is too large. The final complexity of the solution becomes O(N+K⁴).

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------