Qualification Problem Set 1 September 78, 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 ProblemsNinePatchUsed as: Division One  Level One:
A WbyL 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:
In general, when you first add strip K, it is adjacent to strips K1, K3, and K4. For example, consider strip 7 in the following diagram. 7666 7325 7315 7445Strip 7 is adjacent to strips 6, 4, and 3. Strip K is not adjacent to strip K2, 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 depthfirst 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[n1]  f == strip[n3]  f == strip[n4) 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 (03) of the nth strip. Notice that the line if (f == strip[n1]  f == strip[n3]  f == strip[n4) 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 nonexistent fabric number like 99. Then we are guaranteed that the current fabric will not equal the fabric in, say, strip n4 when strip n4 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 nth strip is stored in, say, strip[n+4]. 
