October 2011 Cook-off Problem Editorials

Problem Setter for the contest was Anton Lunyov.
Problem Tester for the contest was David Stolp.

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

GENARSEQ: Generalized Arithmetic Progression Free Sequence

Finding x[k] at each step directly by definition is very slow. Let's do the following. After we find some x[k] let's mark all numbers greater than x[k] that definitely can't be the future elements of this sequence. What are these numbers? Clearly that all numbers of the form a * x[i] - b * x[j] where 1 <= i, j <= k can't be the elements of this sequence. But all other numbers possibly can belong to this sequence until we find the next element. The element x[k] bring us the following numbers that was not marked earlier: a * x[k] - b * x[i] for 1 <=i <=k and a * x[i] - b * x[k] for 1 <=i < k. So we need to mark only these 2 * k - 1 numbers at k^th step. The finding of x[k] now becomes easy. We just need to iterate through all numbers greater than x[k - 1] until we find not marked number. This number is equal to x[k].

Some additional hints. Don't forget to mark a - b before finding x[2]. Take some bound for numbers that will be marked. We don't need to mark numbers greater than x[n]. Of course we don’t know it. But we can estimate it. Since at each step we mark at most 2 * k - 1 new numbers it follows that x[k+1] <= x[k] + 2 * k - 1. And hence x[n] <= 1 + 1 + 3 + 5 + ... + (2 * n - 3) = (n - 1)² + 1. Thus we can mark only numbers that is not greater than (n - 1)² + 1. In fact you don't need all this stuff and simply can mark all numbers using array with one million elements. Thus we obtain algorithm with complexity O(n²).

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

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

LAMQUGAM: Lame Queen Game

If we find some losing position (x₀, y₀) then all points on the same row and column will be winning and all points on its diagonal for which x have the same residue as x₀ modulo d will be winning. Call this residue winning for this diagonal. Hence in each row and each column we have exactly one losing position. So we will have at most N losing positions in the square 1 <= x <= N, 1 <= y <= N. In order to find them efficiently let store for each diagonal all residues that is not already winning and also maintain the first not winning diagonal (where at least one not winning residue is left) and the first not winning row. Then at each step we will find the new losing position simply iterating from maximal of first not winning row and first not winning diagonal until we find the free point. By direct running of this approach it can be shown that for N <= 200000 and d <= 20 it performs at most 8 * N operations for inner iterating. It is clear that all other stuff is linear here.
Now we talk about how to answer the queries. Each query is equivalent to 4 queries for rectangles with one of the corner in (0,0). Let's sort all queries by x. In binary indexed tree (BIT) we maintain for each y the number of losing positions that has this y and x <= xcur where xcur is the x of the current query. Then answer to the query (xcur, ycur) is the sum of first ycur elements of out BIT and can be found in O(log N) time. Before processing queries with x = xcur we need to add losing position with x = xcur to our BIT. And this also can be done in O(log N) time.
Thus we obtain an algorithm with complexity O(N log N).

Problem tester has noted an interesting fact about this game. If (x, y) is the losing position and x > y then there are no losing positions (a, b) such that x > a > b > y + d. This fact allows us to answer the query in O(d) time if we precalculate the number of losing positions in squares 1 <= x <= n, 1 <= y <= n for all n. See its solution as a reference for this approach.

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

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

NONPALIN: First Non-Palindrome

It is clear that K(1)=0. Hence we will only consider L from 2 to N.
Assume that for some L substrings S[1, L] and S[2, L + 1] are palindromes. Then it is easy to see that for even L we must have S[i] = S[i - 1] (1 < i <= L + 1) and for odd L we must have S[i] = S[i - 2] (2 < i <= L + 1). For example, let S[1, 4] and S[2, 5] are palindromes. Then by definition of palindrome we have S[1] = S[4], S[2] = S[3], S[1] = S[5], S[2] = S[4]. From here it follows that all characters of S[1, 5] are equal.
Append some imaginary character to the end of S. Note that now K(L) always exists. But if for some L we obtain that K(L) = N - L + 2 then we should set K(L) = 0.
For d = 1, 2 denote by I[d] the first integer i > d such that s[i] != s[i - d]. For example, for the string "ccccodechef" we have I[1] = 5 and I[2] = 5, for the string "cococodechef" we have I[1] = 2 and I[2] = 7.
Let L be an even integer from 2 to N. If I[1] >= L then it is clear that first non-palindrome substring of length L is S[I[1] - L + 1, I[1]] (all previous substring are composed of equal characters but this one has last character that differs from the first). So in this case K(L) = I[1] - L + 1. Otherwise let's check whether the prefix S[1, L] is a palindrome. If it not then K(L) = 1. But if it is a palindrome than by considerations of the second paragraph and definition of I[1] we must have that S[2, L + 1] is not a palindrome. So we can set K(L) = 2 even without checking whether S[2, L + 1] is a palindrome.
Now let L be an odd integer from 2 to N. If I[2] >= L then it is clear that first non-palindrome substring of length L is S[I[2] - L + 1, I[2]] (all previous substring has the form "aba...aba" but this one has last character that differs from the first). So in this case K(L) = I[2] - L + 1. Otherwise let's check whether the prefix S[1, L] is a palindrome. If it not then K(L) = 1. But if it is a palindrome than by considerations of the second paragraph and definition of I[2] we must have that S[2, L + 1] is not a palindrome. So we can set K(L) = 2 even without checking whether S[2, L + 1] is a palindrome.
Thus we see that we should only be able to test prefixes of the string by palindrome test. This can easily be done using hashes. Just iterate over prefixes and update in O(1) time polynomial hash of prefix and its reverse. Another approach is to use Z-algorithm here. Append to S its reverse and denote this new string by T. Then prefix S[1, L] is a palindrome if and only if z[2*N - L + 1] = L where z[k] denotes the largest number i such that T[1, i] = T[k, k + i - 1]. Numbers z[1], z[2], ..., z[2 * N] can be calculated in O(N) time by Z-algorithm . You can read about it elsewhere.
Thus we obtain quite simple O(N) algorithm for solving the problem.

There is also another approach possible here. It uses Manacher algorithm for finding palindrome radii and then some greedy considerations allow us to solve the problem in O(N) time. See tester solution as a reference. Instead of Manacher algorithm you can use hashes and binary search to find palindrome radii in O(N log N) time.

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

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

PERMDIG: Permute Digits

The most obvious approach here is to iterate over all permutations of digits of A, calculate B' = C - A' where A' is a current permutation of A and check whether B' is a permutation of B. Interestingly that under assumptions of the problem (that is X * len <= 80) this approach is fast enough for large bases 10, 9, 8 and even 7. But for small bases it is very slow, especially for 2, 3 and 4. Thus we need another algorithm here.

At first consider the worst case for the first approach - the base 2. Assume for simplicity that A, B and C all have equal length and denote it by L. Denote digits of C by C₁, C₂, ..., C_L and its prefix of length k by C(k), that is C(k) = C₁C₂...C_k (see notation in the problem statement). Also denote by nA and nB the number of ones in binary representation of A and B respectively.

Let dp[d][k][na][nb] stands for the number of pairs of non-negative integers A' and B' such that

• A' and B' has exactly k digits in binary (possibly with leading zeros);
• A' has na ones in binary;
• B' has nb ones in binary;
• A' + B' + d = C(k).

It is easy to see that dp[0][0][0][0] = 1, dp[1][0][0][0] = 0 and the answer to the problem is dp[0][L][nA][nB].

Here for parameters d, k, na, nb the following inequalities hold

• 0 <= d <= 1;
• 0 <= k <= L;
• 0 <= na <= min(k, nA);
• 0 <= nb <= min(k, nB).

Now let's consider what transitions we have between states of this dp. Let x and y be the last digits of numbers A' and B'. Then equation A' + B' + d = C(k) is equivalent to the couple of relations

• x + y + d = 2 * d' + C_k where 0 <= d' <= 1;
• A'' + B'' + d' = C(k - 1),

where A'' is obtained from A' by erasing its last digit and similar is for B''.

If we fix x then y and d' determined uniquely from the first condition

• y = (C_k - d - x) mod 2;
• d' = (x + y + d) div 2.

Now consider the second condition A'' + B'' + d' = C(k - 1). It is very similar to the 4^th condition in definition of dp[d][k][na][nb]. Note that A'' have na' ones in binary where na' = na if x = 0 and na' = na - 1 if x = 1 and B'' have nb' ones in binary where nb' = nb if y = 0 and nb' = nb - 1 if y = 1. Hence we have transition from the state (d', k - 1, na', nb') to (d, k, na, nb) provided that parameters d', k - 1, na', nb' satisfy all needed inequalities. So by basic combinatorial principles dp[d][k][na][nb] is equal to the sum of dp[d'][k - 1][na'][nb'] over all valid states (d', k - 1, na', nb') from which we have a transition to (d, k, na, nb). Thus we obtain an algorithm with complexity O(L³) for finding the answer if base is equal to 2. Indeed, we find each dp[d][k][na][nb] in O(1) time as a sum of at most two previous values of dp (this is because transition is uniquely determined by x) and we have at most 2 * (L + 1) * (nA + 1) * (nB + 1) states in our dp in total. Since L <= 40 it is very fast.

Now consider the general case when base is arbitrary.
If A, B and C has different lengths then some quite careful analysis is needed. Let La be the length of A, Lb be the length of B and L be the length of C. Swapping if needed A and B we can always assume that La >= Lb .
If L < La then we simply can pad C with La - L leading zeros and set L = La.
If L > La then there is big chance that the answer is zero. It can be non-zero only in the case when L = La +1 and C starts with 1. In this case if base is equal to 2 we can simply delete this 1 from C, decrease L by 1 and set dp[0][0][0][0]=0 and dp[1][0][0][0]=1. In the general case of base after we discuss what is dp here the same trick with initialization of dp can be done.

Thus we can assume that L = La >= Lb. When base is arbitrary the state in dp will be more complicated than for base 2. Namely the state is the following triple (d, maska, maskb) where maska = (na[0], na[1], ..., na[X - 1]) and maskb = (nb[0], nb[1], ..., nb[X - 1]). Here na[j] is the number of digits j in representation of A' and similar is for B'. Also we must have La - na = Lb - nb where na = na[0] + na[1] + ... + na[X - 1] and similar for nb. All other assumptions on parameters are the same as for the case of base 2. The meaning of dp[d][maska][maskb] is similar to that for the case of base 2. The transitions between states can be obtained in similar manner. The total number of states is equal to 2 * totA * totB where totA = (nA[0] + 1) * (nA[1] + 1) * ... * (nA[X - 1] + 1) and similar is for totB. Under assumptions of the problem this number does not exceed 1296. We can code maska as a number of length X in positional numerical system where each digit has its own bounds, namely j^th digit is from 0 to nA[j]. Then dp[d][maska][maskb] can be stored in usual three-dimensional array.

Thus we have obtained an algorithm which is fast enough now.

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

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

TRAVELER: Chef Travel Routes

You just simply need to do what is asked in the problem statement. Any adequate way is possible. Even the following naive solution will pass. Let's store cities in simple array of strings and roads in array of triples (string, string, integer). You even don't need to sort these arrays. For each route check at first whether all cities are correct by simple search of each name in the list of cities, then check whether they all are different by pair-wise comparison of all cities in the route. Finally search each pair of consecutive cities in the route in the list of all roads and add its length to the answer if it was found. This algorithm has complexity O(T * K * L * (N + K + M)) where L = 20 is the bound for the length of names.
Now we discuss the optimal solution. Again let's store cities in simple array of strings but we sort them. Now for each road we find by binary search the indices of cities in this array and write its length in adjacent matrix. Then for each route we check correctness of the names again by binary search and use the boolean array of used cities in order to check whether they all are different. Finally we check the existence of the road by simple looking in the adjacent matrix. This solution has complexity O((N + M + T * K) * L * log N).
Feel the difference :)

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

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