November CookOff Contest Problem Editorials

RECIPE (written by David Stolp aka PieGuy)

The problem here is divide all numbers by some constant so that the divisions have no remainder. We produce the smallest result by dividing by a number that is as large as possible, that is the greatest common divisor. The greatest common divisor can be computed efficiently by Euclid's algorithm, but in this case it was fast enough to simply check all numbers from 1 to 1000 for divisibility.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

LIFE (written by David Stolp aka PieGuy)

First solution: If we choose an arbitrary assignment for any two adjacent cells of the original state, then the entire rest of the state can be determined from the current state. For example, if we choose values for original[0] and original[1], then current[1] is defined as original[0]^original[1]^original[2] (where '^' is exclusive or), thus original[2]=original[0]^original[1]^current[1]. Repeating the process allows us to determine all cells of the original state. Depending on the initial assignment, this may or may not yield a valid solution. There are only 4 initial assignments to try, and we simply count the number that yield valid solutions.

Second solution: Consider the state of the game as the binary representation of an N-bit integer. Let A represent the original state of the game, and B the current state. Then the simulation step simply implies that B=F(A), where F(A)=(A<<<1)^A^(A>>>1), '<<<' is left rotation (not left shift), and '>>>' is right rotation. Now consider these cases:

• If N is divisible by 3, then F(011011...011011)=000...000, hence the solution cannot be unique (becase F(X^Y)=F(X)^F(Y), there will either be 0 solutions, or 4 solutions). Denote G(B)=(B<<<1)^(B<<<2)=A^(A<<<3). Now G(B)^(G(B)<<<3)^(G(B)<<<6)^...^(G(B)<<<(N-3)) should equal 0. If this is the case, then there are multiple solutions. Otherwise there is no solution.
• If N has a remainder of 1 when divided by 3, then F(110110...1101101)=1000...000, hence there is always a unique solution, given by B^(B<<<1)^(B<<<3)^(B<<<4)^(B<<<5)^...^(B<<<(N-3))^(B<<<(N-1)).
• If N has a remainder of 2 when divided by 3, then F(101101...10110110)=1000...000, again implying a unique solution, given by B^(B<<<2)^(B<<<3)^(B<<<5)^(B<<<6)^...^(B<<<(N-2))^(B<<<(N-1)).

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

SOCIAL (written by David Stolp aka PieGuy)

The chef chooses a random derangement of the chairs as the follow-ups. If we focus our attention on a single guest, that guest will be back in their original seat after R ringings if and only if the cycle they belong to has a length that divides R. Thus, for each divisor D of R not exceeding N, we count the number of derangements where a specific element (say, the first one) belongs to a cycle of length D, then divide by the total number of derangements. This will give us the probability of a single guest being back in his/her original seat. To get the expected number of guests, simply multiply by the total number of guests. The total number of derangements where the first element belongs to a cycle of length D is the total number of possible cycles ((N-1)!/(N-D)!), times the number of derangements on (N-D) elements. The number of derangements is calculated by the recurrence derange[0]=1, derange[1]=0, derange[i]=(i-1)*(derange[i-1]+derange[i-2]).

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

COOKOFF (written by David Stolp aka PieGuy)

Assume, without loss of generality, that C₁≤C₂ (otherwise swap them). There are 2 cases to consider.

If there are more than M available problems with difficulty ratings between C₁ and C₂, inclusive, then all problems with a difficulty rating less than C₁ or greater than C₂ can be ignored. Now, we can decide, given a maximum difficulty gap G, if it's possible to select M problems such that the difficutly gap does not exceed G in O(N) time (assuming the difficulty ratings have been sorted ahead of time). To accomplish this, we use a greedy method where we select P₁ as the problem with the highest difficulty rating not exceeding C₁+G, then P_ias the problem with the highest difficulty rating not exceeding P_i-1+G for 1<i≤M. If P_M≥C₂, then there is a solution. The minimum value of G can be found using binary search.

If there are at most M available problems with difficulty ratings between C₁ and C₂, then we choose all of them. The remaining problems are chosen greedily, always choosing the problem that produces the smallest difficulty gap between itself and the nearest already chosen problem.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

KNIGHTS (written by David Stolp aka PieGuy)

If we construct a graph where each vertex corresponds to a square of the chessboard, and an edge connects two squares if they cannot both hold knights. Our task is then to find the size of the maximum independent set of this graph. Note that if we color the squares of the chessboard black and white, a knight on a black square can only attack white squares, and a knight on a white square can only attack black squares. Thus, the graph is bipartite. Now, by König's theorem, The size of the maximum independent set is the total number of vertices minus the size of the maximum matching. The maximum matching can easily be found in O(VE) using an augmenting paths algorithm, where V is the number of vertices and E is the number of edges. However, in this case E is O(V), so the solution can be found in O(V²).

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution