August CookOff Contest Problem Editorials

1) CLEANUP (written by Zac Friggstad)

No real tricks here. An easy approach is to create a boolean array b[] of size n where item b[i] is true if and only if i does not appear in the input list. Make two passes through the array, each time keeping track of the number of "true" items seen so far. When an entry i is hit such that b[i] is true, output i if and only if the number of true items seen so far is odd/even depending on whether it is the first/second pass.

2) ARRANGE (written by Zac Friggstad)

The straightforward approach of writing a function that simply reverses the bits of an index to get the new index suffices (recalling that indices with fewer bits than k are padded with leading zeros). The complexity of this algorithm is O(n log n) where n = 2^k is the length of the string. While this was fast enough for the contest, an O(n) algorithm can be devised using a slighly more clever approach.

Let a[] be the original string and b[] be the scrambled string we are to compute. Consider a recursive function scramble(x,n,d,i) that will correctly place every character in the substring of a[] of length n starting at index x in its correct place in b[]. Here, d and i are auxiliary variables that will be used to index a location in b[] at the base of the recursion. The base of the recursion is when n == 1 in which case a[x] is assigned to b[d]. Otherwise, if n > 1 then just recursively call serve(x,n/2,d,i*2) followed by serve(x+n/2,n/2,d+i,i*2). Initially call serve(0,n,0,1) to begin the recursion. One can see that at a particular recursive call at depth j in the recursion, the function is basically taking the j'th most significant digit of l and placing it at the k-j'th bit of d which, in effect, is reversing the digits.

While the depth of the recursion is O(log n), one sees that only 1 call to the function is at depth 1, 2 are at depth 2, 4 are at depth 3, 8 are at depth 4, etc. Summing over all recursive calls, we see the total number of times serve() is called throughout the recursion is only O(n).

For interest's sake, reversing the bits of a binary number is not just some contrived problem that resides solely in algorithms competitions. It is a fundamental subroutine used in some implementations of the Fast Fourier Transform which is, perhaps, one of the most important algorithms in computing science with applications in digital signal processing and fast integer multiplication.

3) TOOLS (written by Zac Friggstad)

Exhaustively enumerating all possible ways of visiting the tools and chefs will time out. With clever pruning, it might be possible to get such an approach accepted, but there is a simpler way to guarantee acceptance. It is an easy modification of the O(n^2*2^n) dynamic programming approach to the Hamiltonian cycle problem. Let S be a subset of the tools and cooks. Let d[S,k] denote the minimum distance required to visit all locations not in S starting from location k while observing the "carry at most 2 tools at a time" rule. Of course, S should be such that if a cook c is in S, then their requested tool t is also in S (call this property *).

Given such a pair (S,k), we can easily determine how many tools the Chef is holding at location k after visiting locations in S. To compute d[S,k], we recursively try to compute d[S+z,z] for each location z not in S as long as S+z still has property * and doesn't leave the Chef holding more than 2 tools.

Then, d[S,k] is simply the minimum over d[S+z,z] + dist(z,k) over all valid z in S. The number of states is at most n*3^n since each cook-tool pair has 3 states (neither visited, tool visited, or tool and cook visited) and for a fixed S and a fixed cook-tool pair, at most one of the cook or tool may appear as the location k in a valid pair (S,k).

4) MUFFINS (written by Zac Friggstad)

The problem is simply to find a large independent set in a large graph. The standard backtracking method will probably time out on this instance. It might be possible to optimize this approach to get it accepted, but the time spent getting this to work may eat up much of the 2.5 hours of the contest.

Recall that if I is an independent set of a graph G(V,E), then V-I is a vertex cover: a collection of nodes such that at least one endpoint of each edge is in the collection. So, the problem was essentially to determine if there is a vertex cover of size k <= 15 (recall n-g <= 15 in the problem description).

There is actually a simple algorithm for deciding if there is a vertex cover of size k that runs in time O(m*2^k) where m is the number of edges. For a fixed constant k, this is linear time! Note that the standard algorithm "enumerate over subsets of V of size k" takes at least Omega(n^k) time (when n is the number of nodes) which is certainly not linear time for k > 1. Consider the following recursive routine that tries to cover the edges with j nodes (initially called with j = k).

bool cover(G,j)

if G has no edges then return true
else if j == 0 then return false
else let e = (u,v) be an edge
return cover(G-{u},j-1) OR cover(G-{v},j-1)

where G-{x} means remove vertex x and all of its incident edges from G. The depth of the recursion is k+1 and each call makes at most two recursive calls. It can be implemented so that only O(m) work is done each time the function is called (disregarding the work done in recursive calls). Thus, the total work is O(2^k*m). Of course, it really won't take this long in practice if implemented properly as O(m) was a coarse upper bound on the amount of work done at each step.

Now let's argue correctness. If there is no such vertex cover then clearly the algorithm fails to find one. Otherwise, consider a vertex cover C of size <= k. When the algorithm is trying to cover an uncovered edge, consider the recursive call that correctly guessed the node x in C that covered e (if both endpoints of e are in C, then any will do). Then C-{x} is clearly a feasible vertex cover of G-{v} of size <= k-1. Unroll this argument to the base case of C being empty. Then G has no edges in this case so the recursive algorithm will find a vertex cover.

5) FUNCTION (written by Zac Friggstad)

The problem is asking you to orient a subset of the edges in an undirected graph so each node has out-degree exactly 1. This should be done while maximizing the total value of the edges that were oriented. Now, a set of edges F can be oriented so each node has out-degree exactly 1 if and only if every connected component in the graph using only edges in F has exactly one cycle. Necessity is easy to see (consider the set of edges that were oriented and "undirect" them to see this) and sufficiency follows by orienting the edges on the cycle to create a directed cycle and orienting all other edges toward this cycle (it's like a tree with a cycle for the root instead of a single node). So, the problem really boils down to finding the highest total value subset of edges such that each connected component using these edges has a unique cycle.

This can be solved with a greedy algorithm that is similar to Kruskal's maximum spanning tree algorithm. Initialize a set of edges F to empty and consider the edges in decreasing order of value. When considering an edge e, add e to F if and only if it does not create a connected component in F having more than one cycle. Sorting takes O(M log M) time and the remaining part of the algorithm can be done using the union find data structure while keeping track of one additional bit of information at each component that indicates if the component already has a cycle or not. Thus, the entire algorithm takes O(M log M) time (assuming, of course M >= N, but there cannot be a solution otherwise).

Now, one can prove that the collection of subsets of edges where each subset has at most one cycle per connected component forms a matroid commonly called the "bicircular matroid". This immediately implies correctness of the above algorithm if you are familiar with such concepts. However, I'll argue correctness in a more down-to-earth fashion (which is similar to proving it is a matroid). Sort the edges e_1, ..., e_M in non-increasing order of value. If there is no solution then the greedy algorithm clearly can't find one. Now, assume there is a solution and let K be an optimum solution. Let F be the collection of edges used in our greedy algorithm (which we still haven't even proven form a valid solution). Consider the least index i such that e_i is in exactly one of K or F (i.e. the least index the greedy solution F disagrees with the optimum solution K). It must be that e_i is in F but not K since we greedily take any edge we see (if possible).

Now, adding e_i to K does one of two things. It either increases the number of cycles in a connected component in K or it bridges two connected components in K, each of which already has one cycle. Consider the latter case (the arguments for the former case are analagous). Let A and B denote these cycles and let C denote the path (including e_i) connecting these cycles. Now, there is some edge in A,B, or C that is not in F since F does not have any component with two cycles (by construction). Say this edge is e_j. Notice that j > i since i is the least index where F and K disagree on e_i. Consider the set of edges K + {e_i} - {e_j}. Regardless of whether e_j is in A,B or C, this new set is a feasible solution (it either destroys one of the cycles A or B or it separates them again). It's cost hasn't increased since j > i. Therefore, we arrive at a new optimum solution that agrees with our greedy solution F on the first >= i edges. Continue this process to see that there is an optimum solution that agrees with our greedy solution so F must be a) feasible and b) optimum.