February 2012 Contest Problem Editorials

Problem Tester for the contest was Anton Lunyov.

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

SMVSEVIL (written by David Stolp)

Since Smart Chef must provide a route that can solve the maze regardless of which maze Evil Chef constructs, we can imagine that Evil Chef constructs all of the mazes and places a robot in each. Then Smart Chef needs to provide a sequence of moves that will lead all of the robots to their respective exits.

The simplest way to do this is one maze at a time. Pick any maze, and construct a sequence a sequence of moves that will move the robot in that maze to its exit. Have all of the other robots execute these moves as well. Then repeat until all robots are at their exits. Moving a single robot to its exit can be accomplished with a depth-first-search.

The winning solution used beam search. As a heuristic, it uses the sum of the minimum number of moves it would take each robot individually to reach its exit. It looks ahead 10 moves to try to find the state with the lowest heuristic. However, it doesn't actually try all possible sequences of length 10, as this would exceed one million sequences. Instead, it limits the search to the best 160 sequences at each depth. Once it's looked ahead 10 moves, it executes the first move of whichever sequence resulted in the lowest heuristic. However, it is possible for this algorithm to get stuck in loop where it alternates between 2 states. To prevent this, the solution hashes each position, and makes sure it never visits the same state twice. It also improves speed by precalculating a table in order to move a single robot 3 times with a single array lookup.

At this time I suspect the problem to be NP-complete, but do not have a proof. However, the variant of the problem where each maze is allowed to have up to 3 exits is NP-complete, via reduction from 3-SAT.

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

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

BBSYSTEM (written by Hiroto Sekido)

Basic Observations: Let f(N, k) be the number of the integers no more than N which have exactly k divisors. For each k, f(N, k) balls can be put into f(N, k) boxes freely. The number of these patterns is f(N, k)! (factorial number). Therefore the answer is (g(N)-1) mod M, where g(N) = f(N, 1)! * f(N, 2)! * ..., and M = 500009. Note that subtracting of one corresponds to the fact that initial state is not valid.

Some Tricks: By the definition, if N has k divisors, f(N, k) - f(N-1, k) = 1, otherwise f(N, k) - f(N-1, k) = 0. Therefore, we obtain g(N) = g(N-1) * f(N, k), where k is the number of the divisors of N. And, we can check the fact that g(N_MAX) mod M = 0, where N_MAX = 2229283, since f(N_MAX, 8) = M. Thus, g(k) mod M = 0 for k ≥ N_MAX.

To wrap up, now, our task is calculating the number of the divisors of N, for N < N_MAX. The following is a pseudo code.

div[k] := the number of the divisors of k (this part is considered in the following)
sum[k] := 0

res[0] := 1
for(k = 1; k < NMAX; k++)
  sum[div[k]] := sum[div[k]] + 1
  res[k] := res[k-1] * sum[div[k]] mod M

foreach N in test cases
  if N ≥ NMAX, print -1 mod M
  else print res[N] - 1 mod M

First Approach: For each integer, calculate the number of the divisors of the integer independently. However, this approach is terrible slow. This approach should get Time Limit Exceeded.

Second Approach: This approach is, for each integer i, to increment the number of the divisors of the integers multiple of i. This approach run in O(N_MAX log N_MAX) time, but this approach is a bit slow for this problem. (This approach can get Accepted for the first version of this problem. However, the tester suggested this problem should be solved more faster!)

div[k] := 0
for(i = 1; i < NMAX; i++)
  for(j = i; j < NMAX; j += i)
    div[j] := div[j] + 1

Modified Second Approach: The fact "if k is a divisor of N, then N/k is also a divisor of N" can make Second Approach about twice faster. This approach can be Accepted if some optimizations are used, but this approach may get Time Limit Exceeded if implemented naively. For example, use unsigned char or short arrays instead of int arrays for optimizations.

div[k] := 0
for(i = 1; i*i < NMAX; i++)
  div[i*i] := div[i*i] + 1
  for(j = i*i+i; j < NMAX; j += i)
    div[j] := div[j] + 2

Third Approach: Let the factorization of k be 2^p[2] * 3^p[3] * 5^p[5] * ..., then the number of the divisors of k is (p[2]+1) * (p[3]+1) * .... This approach also can be Accepted if some optimizations are used, but sometimes get Time Limit Exceeded.

div[k] := 1
rest[k] := k

foreach prime number p such that p*p < NMAX
  for(i = p; i < NMAX; i += p)
    power := 0
    while(p divides rest[i])
      power := power + 1
      rest[i] := rest[i] / p
    div[k] := div[k] * (power + 1)

foreach k such that rest[k] > 1
  div[k] := div[k] * 2

Fourth Approach (Model Solution): Let m[k] be the minimum prime divisor of k, and let the factorization of k be m[k]^deg[k] * .... Then the following recursion formula is hold:
Let i be k / m[k], then
If m[i] = m[k], then deg[k] = deg[i] + 1, and div[k] = div[i] * (deg [k]+1) / (deg[i]+1),
otherwise, deg[k] = 1, and div[k] = div[i] * 2.
This recursion formula can be proved by using the fact that the number of the divisors is (p[2]+1) * (p[3]+1) * .... This approach run in about 1.5 sec if implemented naively in C/C++. Here, the following naive way is enough for calculating m[k].

m[k] := k

foreach prime number p such that p*p < NMAX
  for(i = p; i < NMAX; i += p)
    if m[k] > p, then m[k] = p

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

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

FINDSEQ (written by Imran Sunny)

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

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

MAXCOUNT (written by Nikhil Garg)

This was supposed to be a problem that anyone who knows basic programming could solve and I'm glad that it's satisfied our expectations.

For the given constraints there were two easy approaches that one could use to solve this problem:

• Approach 1:
  The number of elements in the array bounded just by 100. For each element check how many other elements are equal to this one and hence find out what is the corresponding count. This would take time O(N²). Since N <= 100 here this solution would fit easily into the time limit.

• Approach 2:
  The range of elements is small - all elements are between 1 and 10000. One could create a frequency map for the array. I.e. create an array FREQ of size 10000 such that FREQ[x] gives the number of times the number x appears in the array. Initially all values in FREQ are zeros. When you start reading input and say you read a number x, you should add 1 to FREQ[x]. It takes O(N) time to build this array after initialization. When all input values have been scanned, one could make iteration at the FREQ array to find the smallest element with the largest count.

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

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

WCOUNT (written by Nikhil Garg)

The original version I had proposed had much tighter constraints though tester suggested bringing the constraints down so that various easier approached could be used. Here are four different solutions that the current constraints would allow. But before that lets understand the solution. Essentially problem asks you to find number of permutations of some alphabets when they might repeat. The formula for this is : N!/ (a1! * a2! * ... * ak!) if there are a1 letter of first type, a2 of second type and so on. Further this has to be computed modulo 10⁹ + 7 which we denote as MOD everywhere below. The main difficulty lies in computing. So the simplest solution is to compute N! and divide it by a1! , a2!, ..., ak!. The mistake is when you compute N! you've probably overflown the 32bit and even 64bit integer type. Here are the four different correct approaches each of which we tested to run in time :

• Approach 1 : Big Integers
  If you know how to use BigIntegers in Java or have written a BigInteger library in language of your choice, or you use python, you sail easy. Do all intermediate calculations in big integers so that there is no overflow and finally take the modulo. Heavy machinery, easy enough. See the corresponding tester solution to see how to implement this approach using only (BigInt *= Small) and (BigInt /= Small).
• Approach 2 : Modular Inverses
  If you don’t know about modular inverse, read more here. Solution is give away from here : the formula is (N! * inv(a1!) * inv(a2!) * ... * inv(ak!) ) % MOD where inv(a) denotes multiplicative inverse of a with respect to MOD. Here you use the fact that MOD is a prime number and hence all modular inverses would exist. The intended solution to original constraints was to precompute all factorials and factorial inverses, however here precomputation is also not necessary.

Before I discuss other two approaches, lets look at the formula again : N!/ (a1! * a2! * ... * ak!). So numerator has product of N numbers from 1 to N. Denominator has product of 1 to ai for each i. We know that its an integer in the end. So its possible to 'cancel' each number in denominator with some number of numerator. Next two approaches try this only. Imagine you have an array A of size N containing numbers 1 to N initially. We'd try to cancel numbers from denominator and in process reduce some numbers in A. Finally we'd take the product of remaining numbers only.

• Approach 3 : Prime factorization of denominator
  As its given that all ai are no more 10, prime factorization of denominator contains only 2, 3, 5 and 7. We can count the exponent of each of the primes coming from ak! : simply loop from 1 to ak and add to exponent of 2, 3, 5 or 7 based on number. Add exponents from all ai. Now we know prime factorization of denominator. Loop over each number in A and reduce from it requisite number of powers or 2, 3, 5 or 7. Look at the setter's official solution for this approach.
• Approach 4 : Reduction using GCD
  Denominator looks like : (1 * 2 * ... * a1) * (1 * 2 * ... * a2) * ... * (1 * 2 * ... * ak). We know that each of these numbers can be cancelled from numerator. So lets pick a number from denominator and move over numerator and cancel the gcd from both. Eventually the number in denominator would become 1. Look at sample program here.
• Approach 5 : Reduction without GCD (WRONG!!!)
  As in the previous approach lets pick a number (say x) from denominator and move over numerator until we find the value A[i] that is divisible by x and reduce A[i] by x. This approach is wrong even if we try some smart schemes when finding what A[i] choose to cancel if it is not unique. The simplest test is 15!/6!/9!. Clearly it is advantageous to cancel 9! as it is so we left with the fraction 10*11*12*13*14*15/(1*2*3*4*5*6). And now look: the only number that can handle 4 and 6 is 12 but it can't be reduced by both 4 and 6. More complicated example is 50!/10!/10!/10!/10!/10!. It is a good exercise to prove that there is no way to cancel using this approach. And if the first example can be simply calculated in int this one is a hard nut for trying to add some hacks to this approach in order to get Accepted.

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

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

RSRECIPE (written by Sergey Kulik)

Let A[1], A[2], ..., A[N] be an array that we should restore. Consider the sequence of partial sums S[k]=A[1]+...+A[k], 0<=k<=N. In particular, S[0]=0. Clearly, conditions on array A[] mean that

Let's build a weighted graph on numbers 0, 1, ..., N, where for each triple (X_i, Y_i, Z_i) from the input we add edges from X_{i- 1} to Y_i with weight Z_i and from Y_i to X_i-1 with weight -Z_i. We consider this graph as not-oriented when talk about connectivity but weights of edges depends on direction. Then if in some connected component of this graph we set value S[v] for some vertex v, all other values of S[] in this component can be restored by simple DFS using equalities (*). Namely, if we are in some vertex v and the value S[v] is known then for each neighbor u of v the value S[u] must be equal to S[v]+e[u][v] where e[u][v] is the weight of the edge from u to v. So if it is not known we set S[u] to this value and run DFS for it. Otherwise if it is known but not equal to this value the recipe can't be restored. This leads to a simple algorithm for restoring array S[]. Then array A[] can be restored by formulas A[i]=S[i]-S[i-1], 1<=i<=N. The total complexity is O(N+M).

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

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

CYDB (written by Tomaž Hočevar)

What exactly does Chef's program compute? It iterates over all offsets i in string B. For each offset it tries all valid lengths j, checks whether first j characters of string A match with string B at current offset i and adds a corresponding score. String matching allows at most two errors on positions indicated by digits 1 in string C. Let's call string B the text and string A the pattern. Instead of trying increasing lengths j, we could find the longest match of the pattern with text at offset i and apply the formula for sum of squares. That won't be fast enough, but it's very useful for testing whether your faster algorithm is in fact correct.

The problem was designed around the Aho-Corasick algorithm for string searching. Explaining the algorithm is beyond the scope of this editorial so just look it up if you're not familiar with it (here's one of many presentations). A quick summary would be that it is a generalization of Knuth-Morris-Pratt algorithm so that it can simultaneously search for a set of patterns in linear time. Instead of computing a failure function, it builds a trie of pattern strings and computes failure links in that trie. The searching phase is very similar to KMP. The result of running the algorithm is that it determines for all positions i, what is the longest prefix of a pattern which ends at position i.

First expand the string A into a set of possible patterns. Instead of computing the result by starting positions of the pattern in text as in Chef's program, we can compute it by ending positions of the pattern. We can do this with a small modification of the Aho-Corasick algorithm. For every position in text, we get the length of the longest matching pattern prefix. To take into account the shorter ones, all we have to do is follow the failure links in the trie. Just precompute the scores of each such path along the failure links and you get an algorithm which is linear in the length of text and in the sum of pattern lengths.

Tester for this round came up with an alternative algorithm with complexity O(nb*log na). It is based on computing hashes of string prefixes and binary search. For each position i in string B, you can use binary search to find the longest prefix of A, which exactly matches with string B at offset i. All you have to do is repeat this three times to take care of allowed mismatches. A lot of effort went into preparing test cases, which would prevent such solutions with some additional optimizations from getting accepted. One such optimization would be to use the Z-algorithm for computing longest common prefixes of string A and all suffixes of B. If the entire string A matches or if the mismatch occurs at an invalid position, you can skip the other two steps of binary search with hashes and proceed to the next position i in string B. A side effect of this was that intended Aho-Corasick solutions had to be carefully implemented. For example, a sum of squares of first 1000 natural numbers fits in 32-bit integer type, so you should avoid modulo operations, which are rather slow. Some solutions still squeezed through but they were mostly more complicated than the intended solution. Low accuracy of submissions shows that our efforts were effective.

Problem Setter's solution.
Problem Tester's solution will be updated soon.

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

FLYDIST (written by Tomaž Hočevar)

Let x_i,j = D_i,j + d_i,j represents the distance of a direct flight between cities i and j after the modification (there are exactly M such variables). Here D_i,j is the original distance between cities i and j and d_i,j is the value that Chef will add to the distance. We will represent the shortest path between cities i and j by s_i,j. The problem is asking us to minimize sum of |d_i,j|. We can formulate this as a linear program (LP) :
for all i, j, k such that there is a direct flight between cities i and k
s_i,j <= (D_i,k + d_i,k) + s_k,j (conditions for shortest paths)
for all i, j such that there is a direct flight between cities i and j
(D_i,j + d_i,j) <= s_i,j (direct connection should be the shortest path)
minimize sum(|d_i,j|)

It is never optimal to reduce distances below 1 so we don't have to worry about the restriction that the distances should be positive. The standard method to get rid of absolute values |d_i,j| in a linear program is to represent the modification d_i,j as a difference of two positive variables d_i,j⁺ - d_i,j^-. The expression which we're trying to minimize changes to sum(d_i,j⁺ + d_i,j^-). We have a valid linear program but most linear programming algorithms require a valid initial solution and things become much more manageable if setting all variables to 0 gives this initial solution. Note that setting all flight distances to 0 gives a valid solution so we can shift the linear program by D_i,j in every dimension. This brings us to a linear program which can be solved by simplex algorithm. The problem with this solution is that it is hard to tell whether it will be fast enough or not until you actually try it out and is not trivial to code it. That's probably one of the reasons for the low number of attempted solutions.

A straightforward implementation of simplex algorithm is too slow so lets try to find some improvements. The first observation is that simplex tableau is very sparse, which means that you can skip a lot of updates at each iteration of the algorithm. Precomputing some greatest common divisors for the purpose of reducing fractions is a good idea because a lot of time is spent on arithmetic operations with rational numbers. Another trick used by some successful solutions was to run the simplex algorithm with floating point numbers and convert the result to a fraction just before outputting the solution. You can do this by iterating over small denominators until you find a fraction which is close enough to the floating point value.

So far we have only mentioned technical optimizations but there is also a more conceptual improvement thanks to our problem tester for this round. We can try to formulate this problem without shortest paths. The only condition that must be fulfilled is that for every simple cycle the length of each edge is no more than sum of other edges. But of course there is a very large number of such cycles. This way we can reduce the number of variables in the linear program, but the number of conditions would increase drastically. The next step was to observe that we need only those cycles for which the only edges between its vertices are the edges of this very cycle. Let's call these cycles "strongly simple". The required condition for all other cycles will be fulfilled automatically. It is hard to estimate the total sum S of lengths of all strongly simple cycles, which is equal to the number of inequalities in our LP problem. It seems that the largest value for S is achieved on the complete graph and equals to N*(N-1)*(N-2)/2. This LP formulation has approximately the same number of inequalities as our initial solution but only 2*M variables and is fast enough to solve all test cases we could come up with.

Problem Setter's solution.
Problem Tester's solution will be updated soon.

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

LUCKY1 (written by Vitaliy Herasymiv)

It is well-known that the sum of any range Sum[l; r] can be rewritten in form Sum[0; r]-Sum[0; l-1]. Let Sum4[i] is the total number of digits 4 in all numbers from 1 to i, inclusive, and Sum7[i] is the total number of digits 7 in all numbers from 1 to i, inclusive. We need to find the number of such pairs (l; r) that 1 <= l <= r <= N and Sum4[r]-Sum4[l-1] = Sum7[r]-Sum7[l-1]. Rewrite it in this way: Sum4[l-1]-Sum7[l-1] = Sum4[r]-Sum7[r]. We can iterate through all r from 1 to N, and for each r we need to know the number of correct l indexes. Let S = Sum4[r]-Sum7[r] for some current r. We need to find the number of such l (l <= r) that Sum4[l-1]-Sum7[l-1] = S. Since we are iterating r through all numbers from 1 to N, we can handle some array C[i], where C[i] is current number of such l that Sum4[l]-Sum7[l] = i. In each iteration of r, we add to the result number C[Sum4 [r]-Sum7[r]], and then increment C[Sum4[r]-Sum7[r]] by 1. In general this array can has negative indexes so if your programming language does not support arbitrary indexation you should make some tricks. But it can be proven that Sum4[r]-Sum7[r] is always non-negative so you can use usual array for this. Also it is useful to handle arrays Cnt4[i] and Cnt7[i] where Cnt4[i] is the number of fours of decimal representation of i and similar definition is for Cnt7[i]. Then Cnt4[i] can be calculated in O(1) time from Cnt4[i/10]. Thus the total complexity of such algorithm is O(N) for one query. But, you can precompute results for all numbers from 1 to 10⁵ and store them in some array. That gives O(1) complexity for each query.

And here is some example: test case for N = 10.

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

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

LUCKY5 (written by Vitaliy Herasymiv)

In this problem the only thing you should notice is that the only operation that you need to use is the changing of digits.

Indeed, adding leading digit operation worsens our situation - it gives nothing good.

On the other hand, incrementing number by 1 is equivalent to changing of last digit except the case when the last digit is 9. If N has k trailing nines and d < 9 is the next digit after nines then the block d 9 9 ... 9 9 will be changed to (d+1) 0 0 ... 0 0. So it is equivalent to changing of digit d and some useless changes from 9 to 0 that do not involve lucky digits. So we can use just one change of digit instead of this incrementing operation with the same effect in sense of lucky digits.

After noticing this, we see that the answer to the problem is simply the number of unlucky digits of N.

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

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