Tuesday, August 2, 2005 Match summary As SRM 256 started everyone was wondering the same thing: will the system crash because 256 won't fit in a single byte, or will the 666 registrants bring bad luck? However, like Y2K, the alarm proved to be mostly unfounded, and the match came off without a hitch. In division 1, a number of coders were able to polish off all three problems in less than half an hour. However, with so many submissions, there were lots of challenges to be had, and kalinov took advantage, moving up 200 points, and taking first by a wide margin. ivan_metelsky tried to get some, but in the end he netted 0 for the challenge phase, and had to settle for second, followed closely by marek.cygan, who had no challenges. In division 2, coders had similarly high scores, as embe beat out two new comes in second and third place: zig2 and Rounder. The ProblemsGridGeneratorUsed as: Division Two  Level One:
With the grid as small as it was, you just needed to follow the instructions. Initialize a 2D integer array with the appropriate initial values for the first row and column. Then, you can just iterate over all other rows and columns. Of course, you have to calculate all the values in row i before you calculate the values in row i+1, but the order of iteration that most coders naturally use takes care of that. MagicCubeUsed as: Division Two  Level Two: Used as: Division One  Level One:
In all, there are 27 rows, columns and pillars  9 of each. Each of them has constant values for two of its coordinates, and the third coordinate varies from 0 to 2, inclusive. So, a simple way to calculate the sums of all 27 is with two nested loops: ptr = 0; for(int i = 0; i<3; i++){ for(int j = 0; j<3; j++){ r[ptr++] = n[i][j][0]+n[i][j][1]+n[i][j][2]; r[ptr++] = n[i][0][j]+n[i][1][j]+n[i][2][j]; r[ptr++] = n[0][i][j]+n[1][i][j]+n[2][i][j]; } }That will give us all the sums, and we can easily find the difference between the minimum sum and the maximum sum. Next, we just need to consider swapping some pair of elements. This can be accomplished by just trying all pairs. However, it would take a lot of ugly loops to do it after the input has been converted to a 3D array. Instead, it is easier to swap elements in the input, a 1D array, and then convert it to 3D to compute the sums as above. GraphLabel Used as: Division Two  Level Three:
With at most 9 vertices, there are at most 9! = 362,880 different ways to assign the labels to the vertices. Once the labels are assigned, we need to find the differences between the adjacent vertices, which takes N*(N1)/2=36 operations. Multiplying 9!*9*8/2 gives you 13,063,680, which is well within the limits of what you can do in 2 seconds. Now, convinced that a simple brute force solution will not timeout, we just have to implement it. One of the simplest ways to do this is with a recursive function: void recurse(bool[] used, int[] assigned, int cur){ if(cur == N){ //I'm all done assigning check(assigned); }else{ for(int i = 0; i<N; i++){ if(!used[i]){ used[i] = true; assigned[cur] = i+1; recurse(used,assigned,cur+1); used[i] = false; } } } }CliqueCount Used as: Division One  Level Two:
With at most 20 vertices, we can consider each of the 2^{20} subsets of them, and check if each one is a maximal clique. There are a lot of different ways to do this, but my favorite one uses no additional memory and is very fast, as far as exponential algorithms go. For each subset, it examines all of the vertices. If a vertex is in the subset, but it doesn't connect to all of the other vertices in the subset, then the subset is not a clique (the first continue out condition below). If a vertex is not in the subset, but it connects to all of the vertices in the subset, then the subset is not maximal (the second continue out condition)) //code written by brett1479 int N = graph.length, ne[] = new int[N], ret = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (graph[i].charAt(j) == '1') ne[i] = 1<<j; out: for (int i = 0; i < (1<<N); i++) { for (int j = 0; j < N; j++) { if ((i & (1<<j)) != 0 && (i & ne[j]) != (i^(1<<j))) continue out; if ((i & (1<<j)) == 0 && (i & ne[j]) == i) continue out; } ret++; } return ret;ImageRepeat Used as: Division One  Level Three:
A naive solution to this problem would try all possible square sizes, and for
each size, it would compare all possible squares of that size between the two
images. This would take roughly 8 billion operations though, in the worst case,
and would not run nearly in time. As is often the case, you need to use dynamic
programming to make this problem run in time. 
