Match Editorial

This set was the only one not dominated by reds. In fact, only one red, Jan_Kuipers cracked the top five, finishing second. Yellow lujo took top honors, with a green and two blues rounding out the top five, all three rising to yellow in the process.

The Problems

Value	250
Submission Rate	188 / 200 (94.00%)
Success Rate	176 / 188 (93.62%)
High Score	omkarashish for 247.71 points (2 mins 11 secs)
Average Score	207.64 (for 176 correct submissions)

A W-by-L scrap has enough fabric for (W/2)*(L/2) squares, with both divisions rounding down if necessary. Add up the squares for all the scraps, and divide by 9 to get the number of blocks.

    int squares = 0;
    for (int i = 0; i < length.length; i++)
      squares += (width[i]/2)*(length[i]/2);
    return squares/9;

Value	1000
Submission Rate	69 / 200 (34.50%)
Success Rate	36 / 69 (52.17%)
High Score	lujo for 711.70 points (15 mins 53 secs)
Average Score	478.96 (for 36 correct submissions)

In general, when you first add strip K, it is adjacent to strips K-1, K-3, and K-4. For example, consider strip 7 in the following diagram.

    7666
    7325
    7315
    7445

     32
     31

With those constraints in mind, a recursive depth-first search that tries all possibilities runs in plenty of time. There was no need to do anything fancy like remembering the states that you've visited before. In each recursive call, simply try all four fabrics as the next strip, backtracking when a fabric would be adjacent to itself or when the fabric is shorter than the desired strip. During the search, keep track of the most strips that are ever used.

    int most = 0;
    void dfs(int n) {
       int desiredLength = (n+1)/2;
       for (int f = 0; f < 4; f++) {
          if (fabricLength[f] < desiredLength) continue;
          if (f == strip[n-1] || f == strip[n-3] || f == strip[n-4) continue;
          if (n == 3 && f == strip[1]) continue; // special case for strip 3

          fabricLength[i] -= desiredLength;
          strip[n] = f;
          most = max(most, n);
          dfs(n+1);
          fabricLength[i] += desiredLength;
       }
    }

In this code, strip is an array that keeps track of which fabric was used in each strip, where strip[n] contains the fabric number (0-3) of the n-th strip. Notice that the line

    if (f == strip[n-1] || f == strip[n-3] || f == strip[n-4) continue;

Of course, you are probably working in a language that does not support negative array indices. In that case, shift all the strips a few positions forward, so that the n-th strip is stored in, say, strip[n+4].