Match Editorial

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 Problems

Value	250
Submission Rate	348 / 377 (92.31%)
Success Rate	342 / 348 (98.28%)
High Score	antiw for 249.35 points (1 mins 27 secs)
Average Score	208.45 (for 342 correct submissions)

With the grid as small as it was, you just needed to follow the instructions. Initialize a 2-D 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.

Value	550
Submission Rate	149 / 375 (39.73%)
Success Rate	121 / 149 (81.21%)
High Score	embe for 527.05 points (5 mins 58 secs)
Average Score	334.00 (for 121 correct submissions)

Value	250
Submission Rate	232 / 256 (90.62%)
Success Rate	207 / 232 (89.22%)
High Score	lovro for 246.05 points (3 mins 36 secs)
Average Score	202.83 (for 207 correct submissions)

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];
    }
}

Value	950
Submission Rate	83 / 377 (22.02%)
Success Rate	75 / 83 (90.36%)
High Score	antiw for 940.99 points (2 mins 47 secs)
Average Score	639.13 (for 75 correct submissions)

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*(N-1)/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;
                }
            }
        }
    }

Value	450
Submission Rate	146 / 256 (57.03%)
Success Rate	107 / 146 (73.29%)
High Score	marek.cygan for 425.37 points (6 mins 54 secs)
Average Score	296.27 (for 107 correct submissions)

With at most 20 vertices, we can consider each of the 2²⁰ 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;

Value	1000
Submission Rate	108 / 256 (42.19%)
Success Rate	42 / 108 (38.89%)
High Score	ivan_metelsky for 834.84 points (13 mins 11 secs)
Average Score	606.01 (for 42 correct submissions)

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.

Lets say you want to find the size of the largest repeated square subimage that starts at position (i,j) of imageA and (i',j') of imageB. If the size of this is k, that means that there is a repeated square subimage of at least size k-1 starting at position (i+1,j+1) of imageA and position (i'+1,j'+1) of imageB. Similarly, there are repeated square subimages at (i,j+1) and (i',j'+1), as well as (i+1,j) and (i'+1,j'). In other words, the three squares of size k-1 that are in the square of size k and don't include the corner at (i,j) and (i',j') are also repeated.

From this observation, we can work the other way. If there are repeated squares of size k-1 at (i+1,j) and (i'+1,j'), (i,j+1) and (i',j'+1), and (i+1,j+1) and (i'+1,j'+1), and imageA[i][j] == imageB[i'][j'], then there must be a repeated square of size k between (i,j) and (i',j'). Hence we can use dynamic programming to find the size of the largest repeated square subimage for each quadruple: (i,j,i',j'). The return is just the maximum over all quadruples. See warmingup's code for a clean, concise implementation of this (bmerry's implementation is actually a bit simpler, but it has a fatal copy paste error in it).

There are a lot of other ways to solve this problem, and since the naive approach is not that far beyond the limits of what is possible in 2 seconds, many simple optimizations and prunings could make a variant of the naive solution run in time.