JOIN
 Match Editorial
2004 TopCoder Open
Qualification Problem Set 1

September 7-8, 2004

Summary

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

NinePatch
Used as: Division One - Level One:
 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;
```
LogCabin
Used as: Division One - Level Three:
 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
```
Strip 7 is adjacent to strips 6, 4, and 3. Strip K is not adjacent to strip K-2, except for the special case of strip 3, which is adjacent to strips 2 and 1.
```     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;
}
}
```
Then the main function initializes the strip array, calls dfs(1), and returns most.

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;
```
refers to strips that do not exist when n <= 4. To avoid special cases for these values of n, it is useful to insert phantom strips, known as sentinels, in positions 0, -1, -2, and -3, initialized to some non-existent fabric number like 99. Then we are guaranteed that the current fabric will not equal the fabric in, say, strip n-4 when strip n-4 does not exist.

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].

By vorthys
TopCoder Member