Wednesday, August 9, 2006 Match summary
This match had 720 registrants – a little above average, but not as high as one would expect from a money SRM. One reason may have been the schedule, and another could be that the International Olympiad in Informatics takes place in the next week in Mexico and some competitors may be on the way there. The ProblemsRosePetalsUsed as: Division Two  Level One:
This task is straightforward with no tricky cases. We can just implement a loop over the dice values and add 2 petals to the total count if the value is 3 and 4 petals if the value is 5. This way we get the following solution:
public class RosePetals { public int getScore(int[] dice) { int total_petals = 0; for (int i = 0; i < dice.length; i++) { if (dice[i] == 3) total_petals += 2; if (dice[i] == 5) total_petals += 4; } return total_petals; } }DigitsSum Used as: Division Two  Level Two: Used as: Division One  Level One:
This was one of the simplest div 1 tasks of all time, as people solved it in less than a minute. To solve this problem we just code what the problem asks us to. First we need a function to get the sum of digits of a number, and then we need a loop to repeat this until the result is a digit. So here it goes: public class DigitsSum { int sumOfDigits(int n) { int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } } public int lastDigit(int n) { do { n = sumOfDigits(n); } while (n > 10); return n; } }We can get a shorter solution with the use of some math. Let's use the S(X) notation for the sum of digits of the number X. The following property will be useful: X % 9 = S(X) % 9 (we will prove this later). The result that we need to return is S(S(...S(X)...)), which is the first number smaller than 10. But if X % 9 = S(X) % 9 we have that X % 9 = S(S(...S(X)...)) % 9, so if our result is smaller than 9 then it is equal to X % 9. We are left with the case where X % 9 = 0. If X = 0 then the result is clearly 0. If X is different from 0, we can see that if X > 0 then S(X) > 0 so if X > 0 and X % 9 = 0 then the result in 9. This translates into the following code: public class DigitsSum { public int lastDigit1(int n) { if (n < 10) return n; if (n % 9 == 0) return 9; return n % 9; } }vorthys has a one liner based on this ideea. public class DigitsSum { public int lastDigit(int n) { return n==0 ? 0 : (int)((n+8L)%9+1); } }Kawigi has a nicer solution, which uses the behavior of % for negative numbers and is language dependent. public class DigitsSum { public int lastDigit(int n) { return (n1)%9 + 1; } } Some people who took this approach failed the case when n = 0 or when n was a multiple of 9. Let's prove the property used above: say X = a_{n}...a_{1}a_{0} is a number with digits a_{i} and an is the most significant digit, while a0 is the least significant digit. We can write a_{n}...a_{1}a_{0} = a_{n} * 10^{n} + ... + a_{i} * 10^{i} + ... + a_{1} * 10 + a_{0}. Used as: Division Two  Level Three:
This task is a variation of the classical Josephus problem, as the original problem had m = 2 and asked for the last kid eliminated. The task is an interesting one as it has many different solutions.
We think of the circle as a line of kids. We ignore the labels of the kids as we are interested only in the kid labeled k. At each step we keep a count of how many kids are left, of how many kids with labels in the set {1, 2, ... k  1} were eliminated (for this we use the indentifier beforeK), and we also keep the currentIndex, which is the spot where we will eliminate a kid at the current step. It is easy to see that if currentIndex < beforeK + 1. Then we will eliminate a kid with a label smaller than k. Now at each step we update n, beforeK if needed and currentIndex, when currentIndex = beforeK + 1 it means that we are about to delete the kid labeled with k. Here we have some code which does what we just said. public int kthKid(int n, int m, int k) { int curIndex = (m  1 + n) % n + 1; int beforeK = k  1; int nr = 1; while (curIndex != beforeK + 1) { if (curIndex < beforeK + 1) { beforeK; } nr++; n; curIndex = (curIndex  1 + m + n  1) % n + 1; } return nr; }This solution does O(n) steps. For another short solution that took this approach you can check vorthys's solution or vlad_D's solution, which has intuitive variable names. We get another linear time solution not by walking around the circle of kids but moving the circle itself around. First we start counting from the kid labeled 1, and then we need to eliminate the mth kid, and we start again counting from the next kid. We can relabel the circle of kids so that we start again to count for the kid labeled 1 and kids are labeled in a clockwise order, and keeping track at every step of the new label of the kid we are interested in. For example if n = 5, m = 2, and k = 3 at the first step we have the kids labeled: 1 2 3 4 5, when we have to eliminate 2 and get 1 3 4 5 and start counting from 3, by relabeling them we get 4 1 2 3 so the kid labeled 3, was relabeled with 1. Now we must eliminate 3 and start counting again from 4, so relabeling 4 1 2, we get 1 2 3, and the kid we are interested in, who before had the label 1 gets the label 2. Again we eliminate the 3rd kid and relabel, kid 2 gets the same label, then we eliminate 1, and the kid labeled 2 gets the label 1. So now we know that the kid labeled with 3 at the start of the game is eliminated at the 5th step. goldendf's solution implemented in C# is based on this idea. The solution can be easily adapted to finding the last eliminated kid, while the first idea explained above can't be used for that. In the first two solutions the problem was that we didn't have a efficient data structure that quickly found an element at a specified index (this was a problem for the linked list structure) or couldn't delete an element at a specified index fast enough (this was a problem for the vector structure). A data structure that does both operations quickly can be constructed. One idea would be to split the kids into buckets of size x each, so we would have a total of n/x buckets in total. If we want to find the pth kid in this data structure we can just go over the buckets and find the bucket that contains the pth kid, so knowing the number of kids in each bucket we can find the pth kid bucket in n/x steps, and then for finding the kid in the bucket we need at most x steps. So one eliminating step of our algorithm takes at most n/x + x steps, to minimize this formula we find that x = sqrt(n), so a operation will take O(sqrt(n)) time, thus the algorithm using this data structure will take O(n sqrt(n)) steps in total. chenll took this approach here. Another data structure that could have worked was a segment tree (explained by misofin the FloatingMedian solution) each node in the segment tree has an associated interval of numbers, and for that interval it keeps count of how many kids in that interval haven't yet been eliminated. Finding the pth kid not deleted yet will take O(log n) steps, and it's very similar to the binary search algorithm. For deleting a kid we need to decrease the count of active kids in all the nodes that have associated intervals which contain the current kid. This step is also O(log n). You can see a solution that works along these lines in whusnoopy's code. The time complexity of this solution is O(n log n). These two data structure solutions are a bit more complicated than the first two, but using any of them we get the step of the elimination for each kid not for just one specified kid. SillySudokuUsed as: Division One  Level Two:
This problem is based on the classical Sudoku puzzle. There is no known polymonial solution for the generalised Sudoku puzzle, so we cannot hope for a solution different from brute force. The original Sudoku puzzle has a table of 9x9 cells, and wikipedia says it has 6670903752021072936960 solution grids, which is why our problem asks about a much smaller table of 4x4 cells. We can suppose that for this table the number of solutions is a lot smaller; this is also suggested by example 4 which had just one cell different from , and the result of 72, which implies that the number of solutions for a empty table equals 4*72. int[][] table,r, c, sq; String[] b; String[][] sol = new String[288][]; int nr; public void count(int x, int y) { if (x == 4) nr++; else if (y == 4) count(x + 1, 0); else { if (b[x].charAt(y) != '') { int i = b[x].charAt(y)  '0'; if (r[x][i] == 0 && c[y][i] == 0 && sq[(x/2) * 2 + (y/2)][i] == 0) { r[x][i] = 1; c[y][i] = 1; sq[(x/2)*2 + (y/2)][i] = 1; table[x][y] = i; count(x, y + 1); r[x][i] = 0; c[y][i] = 0; sq[(x/2)*2 + (y/2)][i] = 0; } } else for (int i = 0; i < 4; i++) { if (r[x][i] == 0 && c[y][i] == 0 && sq[(x/2) * 2 + (y/2)][i] == 0) { r[x][i] = 1; c[y][i] = 1; sq[(x/2)*2 + (y/2)][i] = 1; table[x][y] = i; count(x, y + 1); r[x][i] = 0; c[y][i] = 0; sq[(x/2)*2 + (y/2)][i] = 0; } } } } public int countWays(String[] board) { table = new int[4][4]; r = new int[4][4]; c = new int[4][4]; sq = new int[4][4]; this.b = board; nr = 0;count(0, 0); return nr; }Some people failed the case where all the table was filled and the configuration was valid or invalid. ThreeMines Used as: Division One  Level Three:
This problem was a interesting combination of geometry and dynamic programming. misof's solution is one of the most clear solutions, as well as being the fastest submission. We can brute force in O(n^2) two lines which split the three rectangles in three different zones, and then for each zone we can find the largest square in with a naive solution that tries all rectangles in O(n^4) but we have to use the array B with partial sums. This is just what some people did and succeeded in passing system tests with a solution in O(n^6). We notice that for a more efficient solution we need the largest sum rectangles in zones of the type: [0..i]x[0..j], [0..i]x[j..m], [i..n]x[0..j], [i..n]x[j..m], [i..j]x[0..m] and [0..n]x[i..j]. We will just explain how to find the best rectangle in a zone of this type: [i..j]x[0..m] the left types can be solved similarly. To find the best rectangle in this zone we must first know the best rectangle in the [i+1..j]x[0..m] zone, and in the [i..j1]x[0..m] zone. Now we are left to find the best rectangle that has the upper row i and the lower row i. This can be solved in O(n) as we will explain next. We can think of this subproblem as one that works on finding a maximum sum contignuous subsequence in a linear array A because we have can think to A[k] as the sum of the elements in the rectangle i..j]x[k..k]. Now for finding the best sequence in A, we will use a array sum so that sum[p + 1] = A[p] + A[p  1] + ... + A[1], now to get the sum of A[p..q] we just compute sum[q + 1]  sum[p]. To get the best subsequence that ends in q, we have to find the smallest sum[p] so that sum[q + 1]  sum[p] is maximum. This idea translates to the folowing code: int[] sum = new int[A.length + 1] int best =  infinity; sum[0] = 0; for (int i = 0; i < A.length; i++) sum[i + 1] = A[i] + sum[i]; int mins = 0; for (int i = 0; i < A.length; i++) { if (best < sum[i + 1]  mins) best = sum[i + 1]  mins; if (mins > sum[i + 1]) mins = sum[i + 1]; } return best;We have O(n^2) regions in our algorithm and as we shown above each region can be solved in O(n), thus we have a O(n^3) time algorithm. 
