February CookOff Contest Problem Editorials

The Tester for the February Cook-off was David Stolp (aka ~pieguy)
--------------------------------------------------------------------------------------------------------------

SEQUENCE (written by Zac Friggstad)
Such "gradual" sequences are similar to the well-known Gray codes. Here is one way (of many) to generate the Gray code x[0], x[1], ..., x[2^n-1] starting with x[0] = 0. To get the value of x[i], if i is odd then x[i] is simply x[i-1] with the least significant bit flipped. Otherwise, let j be such that the j'th bit of x[i-1] is 1 and all bits of x[i-1] that are less significant than the j'th bit are 0. Then x[i] is obtained from x[i-1] by flipping the bit at position j+1. This can be done with clever bitwise operations.

Now, if a and b differ in more than one bit then we may simply output the Gray code. Otherwise, if a and b differ in only one bit then there is no solution for n = 1 or n = 2. Finally, I claim that there is always a solution for n >= 3 if a and b differ in precisely one bit.

We begin by finding a gradual sequence where 0 is not consecutive to a XOR b (XOR means bitwise XOR of binary numbers). To do this, start with the Gray code as mentioned above (or any other gradual sequence you can generate). If 0 and a XOR b are not consecutive, then we are done. Otherwise, since n >= 3 there is some bit 0 <= k < n such that 2^k is not consecutive to 0 in the gradual sequence. Now, let c[i] be the bit that changes between x[i] and x[i+1] and note that the x[i] can be recovered from the sequence of c[i] if we assume x[0] = 0. Let 2^j = a XOR b. Modify the sequence c[i] by changing c[i] = k values to c[i] = j and c[i] = j values to c[i] = k. This will generate a new gradual sequence y[i] that starts with y[i] = 0. However, by construction we will not have 0 and a XOR b adjacent in y[i]. Finally, the gradual sequence of values y[i] XOR a will not have a and b consecutive.

You can view the solutions here:
Problem Setter Solution
Problem Tester Solution
--------------------------------------------------------------------------------------------------------------

ATOMS (written by Zac Friggstad)
First, say that two items x and y are "related" if there is no subset S_i with one of x,y in S_i but not the other. That is, x and y may appear together in an atom. Clearly x is related to itself and if x and y are related then so is y and x. Finally, if x is related to y and y is related to z, then x is related to z. Thus, we can partition the items into subsets A_1, ..., A_k so that any two items in the same subset are related and no two items in different subsets are related. These subsets A_1, ..., A_k is a partition of the items into atoms. I claim this is optimal. If there was a feasible solution using fewer than k atoms, then there must be some subset among these atoms that contains items from different A_i subsets which is a contradiction.

There are a number of ways we can proceed from here. The most straightforward is to build a graph whose nodes are items such that two items are adjacent if they are related. Then the problem boils down to counting the number of connected components of this graph. The straightforward way of building the graph is good enough. For each of the O(n^2) pairs of items we check them against the m subsets to determine if they are related. Then we use a linear-time (so at most O(n^2)) search of the graph to determine the number of connected components for a total running time of O(n^2m). Of course, seasoned veterans will see many shortcuts to this approach such as using bitwise operations (m <= 30 encourages this) or the union find data structure to shorten running time and/or coding time. In fact, the graph doesn't need to be explicitly built. The input limits were kept low to encourage multiple approaches.

You can view the solutions here:
Problem Setter Solution
Problem Tester Solution
--------------------------------------------------------------------------------------------------------------

COMM3 (written by Zac Friggstad)
Try all 3 pairs of transceivers to see which ones can communicate directly. If at least 2 pairs can communicate directly then at least one transceiver can communicate directly with the other two so the answer is 'yes'. Otherwise, if at most 1 pair can communicate directly then the answer is 'no'. To determine if two transceivers located at (x1,y1) and (x2,y2) we simply check that (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) <= r*r. This is the same as checking that the distance between them is r, but we can avoid floating point computations this way. Note that the input numbers are small enough to ensure that the above expression only involves signed 32 bit integers.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

--------------------------------------------------------------------------------------------------------------

ENERGY (written by Zac Friggstad)
Let G[t] be the bipartite graph at time t with boys on one side and girls on the other where only the boys and girls who are present at time t occur. There is an edge in G[t] between each couple who is willing to dance with each other at time t. Let M[t] denote the size of the maximum matching in G[t]. Say t' is the next event where a person either enters or exits. I claim that |M[t'] - M[t]| <= 1. If a person entered then assume, for the sake of contradiction, that M[t'] >= M[t] + 2. Then all but at most one edge in this matching in G[t'] involves this new person and after possibly removing such an edge we get a matching of size greater than M[t] in G[t]. If a person exited then at most one matching is destroyed.

So, given a maximum matching in G[t] we can get a maximum matching in G[t'] in the following way. If a person entered at t', then simply see if there is an alternating path in G[t'] with respect to the matching in G[t]. If so, then the matching increased and if not then the matching size is the same. If a person left at t', then discard the matched edge they were involved in (if any) from the maximum matching and then see if there is an alternating in path in G[t'] with respect to this modified matching. In fact, if the person was not matched when they left then we don't have to bother with finding an alternating path.

Overall, we initialize the graph to be empty and sort the events where a person enters or exits in increasing order of time. Then we process these events one after the other and look for a single alternating path each time. For each interval between events, we add the length of this interval to the time spent with the corresponding maximum matching size. The number of events is O(B+G) and the time it takes to update the matching is linear in the size of the graph, which is O(BG) in the worst case but much better on intervals when few people are dancing. The overall running time is O((B+G)BG).

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution

--------------------------------------------------------------------------------------------------------------

CROWNS (written by Zac Friggstad)
Try all ordered pairs of points p,q as the first and last points in the crown (the endpoints of the "base" of the crown). Translate the points so p is at the origin and then rotate so q is on the positive x axis. Now, discard all points with non-positive y coordinate, x coordinates at most 0 or at least the x coordinate of q (after rotating, of course). Finally, among these points keep only the one with minimum y coordinate among all points that share the same x coordinate. Sort these remaining points by their x coordinate.

For each point r (including the endpoints p,q), let U[r] be the maximum area of a crown that involves point r where the point after r is above r and let D[r] be the maximum area of a crown that involves point r where the point after r is below r. The largest area of a crown involving base points p,q is then U[p]. The base case is D[q] = infeasible and U[q] = 0, the idea being that the point before q in a crown must decrease to q. From an arbitrary point r, we compute D[r] by trying all points s whose x coordinate is greater than r and such that there is no other point lying below the line formed by the line r-s. The value of D[r] is the maximum of U[s] + (s.x-r.x)*(r.y+s.y)/2 over all such points s. U[r] is computed similarly. We can calculate D[r] in linear time given that the coordinates are sorted according to x coordinate by keeping track of the least slope of a line between r and a point seen so far in our sweep. Then we can determine, in constant time, whether a given point s has a point under the line r-s or not. In fact, it's not too hard to see that both U[r] and D[r] can be computed in a single sweep. The running time is O(n^4) since there are O(n^2) pairs of points to try, O(n) values D[r] and U[r] to compute, and computing each such value takes O(n) time.

One final note is that there is always a solution given that no three points are collinear. To see this, note that we can triangulate the set of points. Any triangle is a feasible crown by selecting the longest side to be a base.

You can view the solutions here:

Problem Setter Solution

Problem Tester Solution