Thursday, March 6, 2008 Match summaryDivision 1 was won by ACRush who showed the best time on both the 500pointer and the 1000pointer. The second place went to marek.cygan, and the third was gained by Petr, thanks to his two successful challenges. andrewzta and krijgertje came in fourth and fifth, both regaining a rating of 3000+ and a target sign. Division 2 was won by Ripatti, who was closely followed by leohoyee and emotionalBlind. Along with gajcz and Blue.Mary, those are the only five contestants who were able to solve all three problems correctly. In Division 1, during both the challenge phase and the system tests, a lot of 500pointer and 1000pointer solutions failed the tests with maximal possible inputs (N=200000 for the medium, and N=10^{18} for the hard). Let this be a reminder for all of us to check our solutions on "max tests" every time. The ProblemsAverageCandyLifetimeUsed as: Division Two  Level One:
The average lifetime of the candies is the sum of their lifetimes divided by the number of the candies. The natural approach for this problem is to calculate these two values. In can be done by iterating over the given array eatenCandies just once. The following Java code is a correct solution for the problem: private final int[] months = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; public double getAverage(int[] eatenCandies) { int lifetime = 0; int sum = 0; int number = 0; for (int i = 0; i < 12; i++) { lifetime += months[i]; sum += eatenCandies[i] * lifetime; number += eatenCandies[i]; } return sum * 1.0 / number; }TwoStringMasks Used as: Division Two  Level Two: Used as: Division One  Level One:
First, suppose neither s1 nor s2 start with an asterisk. If they start with different letters, the correct answer is "impossible", because after any replacements the strings will still start with different letters. Otherwise, if they start with the same letter, we can remember that the answer must start with this letter and remove this letter from both strings. Similarly, we can consecutively remove letters from the endings of the strings, (and if we notice different letters on the endings, the answer is "impossible"). After doing so, we will have two strings, at least one of which starts with an asterisk (otherwise we could remove one more letter from the beginning), and at least one of which ends with an asterisk (otherwise we could remove one more letter from the ending). If one of the strings is an asterisk ("*"), than the answer is the other string with its asterisk removed (better to say, replaced with an empty string). Otherwise, we have one string starting with an asterisk (say, s2) and the other string ending with an asterisk (s1). Remove the asterisks from both strings. Now the answer is the shortest string that starts with s1 and ends with s2 (possibly, there is an overlapping of s1 and s2). The shortest string with a given prefix and a given suffix can be found using KnuthMorrisPratt Algorithm in linear time. However, constraints of this problem allowed to solve this subproblem using a slower algorithm. The easiest approach is to find the largest length of the overlapping part of s1 and s2. Just try all possible lengths from 0 to the length of s1 and check whether the corresponding number of last characters of s1 are equal to the corresponding first characters of s2. If they are equal then we can make this letters the overlapping part of s1 and s2. Obviously, the string with the largest overlapping part is the shortest string that starts with s1 and ends with s2. An implementation of this approach was coded by yuhch123. Also worthy of mentioning is a witty solution by maniek who used the Java builtin regular expressions. QuasiLatinSquaresUsed as: Division Two  Level Three:
Division 2 coders were asked to find the lexicographically smallest QuasiLatin square, a natural generalization of Latin square. However, the generalization wasn't really important, because the correct answer for any n and d looks like this:
Thus, the problem could be reduced to finding the lexicographically smallest Latin square of size d. However, this reduction wasn't necessary, because even the generalized problem can be solved in reasonable time using a simple backtracking algorithm. A pseudocode implementation of it is shown below. boolean search(i, j) { for (int v = 0; v < d; v++) { a[i][j] = v; Consider row i of matrix a Count p, the number of different digits in cells a[i][0] through a[i][j] We need to put dp more digits, and we only have nj1 cells If there is not enough cells for the digits continue; Consider column j of matrix a Count q, the number of different digits in cells a[0][j] through a[i][j] We need to put dq more digits, and we only have ni1 cells If there is not enough cells for the digits continue; if (i, j) is the last cell return true; if search(next cell after (i, j)) return true; } return false; } The nature of the lexicographically smallest Latin squared of size d strongly depends on d. When d is a power of two, the desired Latin square is not only symmetrical, but it also follows a wonderful pattern: On the other hand, for d=5, 7, 9, and 10 (and many larger values that weren't considered in the given problem), the answer is not symmetrical with respect to the main diagonal. RoundAboutCircleUsed as: Division One  Level Two:
Let's try to calculate the score of the player, when starting from all possible initial cells. Then the answer to the problem is the maximum of all N such values. Start emulating the process from initial cell number 1. The token will make some moves and finally reach a cell that was already visited before. Look at the piece of the path, from the first visitation of that cell to the second visitation. This is a loop. Calculate the length of this loop L (the number of the cells in it), and for each cell in the loop, store that the score when starting from this cell is L (indeed, if we start in this cell, the token will travel along the loop and reach the initial cell, thus giving score L). Now let's look at the cells of the considered path that come before the loop. What if we start from the cell right before the loop? The score in this case will be L+1. Starting from the previous cell leads to the score of L+2, and so on. Iterate over all the cells that come before the loop and calculate this scores. By now, we've gathered all the useful information about all the cells on the path starting from 1. But we need to process all the cells outside this path as well. Select any cell that doesn't belong to this path. Start emulating the process from this cell. We will reach one of the following situations:
In the first case, we should do the same procedure as we did above for the path starting from 1. In the second case, we reach a cell C processed before, so we already know the score when starting from cell C. Then the score for the cell before C is equal to the score for C plus 1. The score for the previous cell is the score for C plus 2 etc. Iterate over the entire path in backwards direction and calculate all the scores in this fashion. Repeat the above procedure for all cells that haven't been processed until there are no such cells left. Note that each cell is processed exactly once in the proposed algorithm, thus the overall working time is O(N). Coders should be aware that implementing this algorithm (or a similar one) in a recursive fashion can lead to stack overflow. It is good to know the default stack size of your language. It is also good to know how to avoid recursive functions in hazardous situations (roughly speaking, using your own stack). EquiDigitNumbersUsed as: Division One  Level Three:
First, since the number 999...9 is an equidigit number, the answer to the problem always has the same length as the input N. Let's denote this length m. Also for simplicity let's check whether N is already equitigit, and return N if it is. So now we need to find the smallest equidigit number of length m that is strictly greater than N. As this desired number is greater than N, let's denote p the position of the leftmost digit in which this number differs from N. Also, let's denote q the digit of this number in the position p. Iterate over all posible values of p and q. Having fixed p and q, the task is to find the smallest equidigit number satisfying the following conditions:
Now iterate over v from 1 to 10, that is the number of different digits in the desired equidigit number. When we have fixed m, v and several first digits of the desired number, the next digit can be found easily according to a greedy algorithm. Indeed, iterate over all possible values for the next digit, and select the smallest value, such that setting it into the current position doesn't make the number of different digits used exceed v and doesn't make the amount of each digit exceed m/v. 
