Get Time
statistics_w  Match Editorial
SRM 256
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 Problems

GridGenerator discuss it
Used as: Division Two - Level One:
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.

MagicCube discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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];
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 discuss it
Used as: Division Two - Level Three:
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

            for(int i = 0; i<N; i++){
                    used[i] = true;
                    assigned[cur] = i+1;
                    used[i] = false;

CliqueCount discuss it
Used as: Division One - Level Two:
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 220 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;
    return ret;

ImageRepeat discuss it
Used as: Division One - Level Three:
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.

By lbackstrom
TopCoder Member