December CookOff Contest Problem Editorials

COMMUTE (written by Zac Friggstad)

Nothing really special here. Let t_i be the earliest time we can arrive at station i with the base case t_0 = 0. Then given t_i we can easily compute t_{i+1} by waiting from time t_i until the next train departs from station i, and then adding the travel time to this departure time to get t_{i+1}.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

PAIRING (written by Zac Friggstad)

A greedy strategy works here. Consider the pairs in the reverse of the order they appear. When considering a given pair, we greedily take it if neither of the chefs were in a used pair earlier. To see why this is optimum, suppose an optimum solution had a higher total value than our greedy solution. Let i be the greatest index where our solution disagrees with the optimum. Based on our greedy selection strategy, it must be that we took the i'th pair whereas the optimum doesn't include the i'th pair. But then we can improve the cost of the optimum solution by deleting all pairs j with j < i and adding pair i. This is an improvement because of the exponentially increasing values of the pairs: 2^1 + 2^2 + ... + 2^{i-1} is strictly smaller than 2^i. This contradicts optimality of the considered solution.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

PREPARE (written by Zac Friggstad)

Perhaps the simplest approach is to use binary search problem coupled with a dynamic programming subroutine. Given a value T, we can determine if it is possible to prepare all dishes in time T. All dishes that can be prepared by the other cooks in time at most T will be delegated to them. For the remaining dishes, we run a subset-sum style algorithm to determine if the Chef and his assistant can prepare them in time T. This can be done by building a table d[] where d[k] is true if and only if there is some subset of dishes of total preparation time k. We only have to build this table up to time T. Let the total preparation time (by the Chef and his assitant) of the remaining dishes be S. Then the remaining dishes can be prepared in time T if and only if some k with k <= T and S-k <= T has d[k] being true. That is, the Chef can prepare some dishes in time k and his assistant can prepare the remaining in time S-k.

There is a direct dynamic programming approach that avoids binary search which avoids the O(log n) overhead of the binary search method (as long as some sorting is done before hand), but it's simplest to describe this approach and it was fast enough for the problem.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

PUZZLES (written by Zac Friggstad)

This is the standard 3SAT problem where each clause depends on precisely three different variables and each variable appears in at most 3 clauses. Such instances can be solved efficiently. Form a bipartite graph with a node for each clause on one side and a node for each variable on the other. For each clause C, add an edge from the node for C to each of the three nodes corresponding to variables that appear in C. I claim there is a matching in this graph that involves each clause node. Before arguing this, we see that we can then satisfy the instance by assigning, to each matched variable, the value that will satisfy the clause it is matched to. Variables that are unmatched can be assigned anything.

Recall that Hall's matching theorem states that a bipartite graph with bipartitions X and Y has a matching involving every node in X if and only if each subset X' of X has at least |X'| neighbors in Y. This is true in our case. Consider a subset C' of clauses. The number of edges with one endpoint in C' is precisely 3|C'|. On the other hand, let V' be the subset of variables that are adjacent to some clause node in C'. Since each variable appears in at most 3 clauses, then the number of edges with one endpoint in V' is at most 3|V'|. We counted the same set of edges in two different ways which shows |C'| <= |V'|, so by Hall's theorem there is a matching involving every clause node.

Rajiv, this months tester, has a nice alternative linear-time solution. It solves the slightly more general problem when each group can contain a repeated number, but the total times a number appears is still at most three (e.g. it can appear in at most two groups if it is used twice in some group). It does not generalize as neatly to instances where each group has at least K distinct numbers and each number appears in at most K groups when K is some given number whereas the matching approach does. I'll sketch the details. Consider a number Z:

i) If Z appears with the same sign in all groups, then assign it the value that will satisfy all of these groups

ii) If Z appears in two different groups with opposite sign, then place it on a "dependency stack" which will be implicitly described in the following. Remove these two groups and form a new group that is the union of the original groups (without Z). This new group will contain at least three numbers. Now, if the resulting instance is solved then using the same assignment will satisfy at least one of the two original groups. Now, fix Z to have the value that will satisfy the other group.

iv) A similar, but messier, rule is used if Z appears in three groups with both Z and -Z appearing in at least one of these groups. I'll leave the details as an exercise.

A careful implementation of these ideas leads to a linear-time solution.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

SEEDS (written by Zac Friggstad)

Let x_0, x_1, ..., x_{d-1} be the seed values we are trying to discover. It is easy to see by induction that every value x_i is a linear combination of these seeds. Furthermore, we can use the usual fast matrix multiplication trick to discover the coefficients in this linear combination (I'll explain this below if you haven't seen it). So, for each of the x_i given in the input we have a linear equation with unknowns being the seed values. Once we determine all of these equations, it is a simple matter of solving this linear system with Gaussian elimination to determine if there are none, one, or many solutions for the seed values.

The matrix multiplication trick I'm alluding to is the following. For i >= 0, let z_i denote the column vector (x_{i+d-1}, x_{i+d-2}, ..., x_{i+1}, x_i)^T. The main idea is that there is a matrix A such that A z_i = z_{i+1} for every i >= 0. The first row of A consists of the a_{d-1}, ..., a_0 values given in the input and of the remaining rows, the j'th such row has all zeros except for a single 1 in column j-1 (try this on a few simple recurrences like the Fibonacci series). Then multiplying z_i by A "shifts" the entries down and the top entry becomes x_{i+d} by the recurrence. By induction on k >= 0, we have that A^k z_0 = z_k where z_0 is the column vector of the seed values we are trying to discover. The neat thing is that we can compute A^k in O(log k) matrix multiplications by using fast exponentiation. Just remember to keep all intermediate results reduced modulo 2. The coefficients of the linear combination of the seeds that yield x_i are then found on the bottom row of the matrix A^i.

This easily generalizes to the case when we are trying to discover the seeds when the recurrence is taken modulo p for some arbitrary prime p. However, it would involve implementing modular inversion and I thought there was enough to do for this problem in short contest already :)

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution