Match Editorial

reid rode the fastest Easy and the fastest Medium to victory on a night where no one solved all three problems. Kudos to gepa for the lone successful solution to the Hard, but resubmissions on both his Easy and Hard dropped him to fifth.

At the conclusion of coding, only 22 coders had submitted more than one problem. All but a few of the rest were within a single challenge of the 24th-place cutoff for advancing, so tensions were especially high entering the challenge phase. However, only ambrose and AdrianKuegel made successful challenges. ambrose would have made the cut anyway, but for AdrianKuegel the challenge made the difference between advancing and not advancing. System tests were uneventful for the Easy and the Medium, with only a single Easy failing and no Mediums. The Hard was a different story, as all but one of the nine submissions failed.

The Problems

Value	250
Submission Rate	49 / 49 (100.00%)
Success Rate	46 / 49 (93.88%)
High Score	reid for 237.74 points (6 mins 31 secs)
Average Score	200.52 (for 46 correct submissions)

Many people simulated all the steps of the movement, but it was cleaner to calculate the answer directly. First, board B starts at table T0 = (B-1)/3+1. Between round 1 and round R, it moves to table T1 = T0 - (R-1), except that this value has to be wrapped to stay in the range 1 to N. Wrapping can be accomplished by a function

  Wrap(X) = (X-1) mod N + 1

This problem would be much cleaner and much less error prone if all the ranges started at 0 instead of 1, but the bridge community has yet to see the light when it comes to 0-based indexing.

Value	500
Submission Rate	16 / 49 (32.65%)
Success Rate	16 / 16 (100.00%)
High Score	reid for 323.32 points (23 mins 57 secs)
Average Score	280.37 (for 16 correct submissions)

This problem was harder than its 100% success rate might indicate. Most people seemed to realize right away that a greedy strategy was called for, but the trick was to come up with the right greedy strategy.

Some obvious strategies, like choosing the pair with the maximum energy difference or the pair with the minimum energy difference (greater than 1), don't work. The first is actually the quickest path to heat death. The second fails on an example like {1,2,3,6}. The minimum energy difference is between 1 and 3, but it is better to transfer energy from 6 to 3 in the first microsecond. Why? Because transferring energy from 3 to 1 would lead to the state {2,2,2,6} in the first microsecond, and from there to {2,2,3,5} in the second microsecond. In constrast, we can take three microseconds to reach state {2,2,3,5} by going from {1,2,3,6} to {1,2,4,5} to {1,3,3,5} to {2,2,3,5}.

This example suggests a greedy strategy that does work. First sort the list. Then, always choose a pair of adjacent locations with an energy difference of two or more, whenever such a pair exists. If there is more than one such pair, all of them will eventually yield the same result, so pick one arbitrarily. If there is no such pair of adjacent locations, then any pair of locations with an energy difference of exactly two will work. Again, pick one arbitrarily. For example, given {1,2,3,4,5}, you might pick 1&3 or 2&4 or 3&5. The process ends when the maximum energy level is within one unit of the minimum energy level.

One concise way to formulate this greedy strategy is to always pick the two feasible locations that are closest together in the array. See ambrose's solution for a nice implementation of this approach. A pleasant feature of this formulation is that updating the energy levels of the two locations always leaves the array sorted. Maintaining the order of the array is trivial when picking adjacent locations, but takes some care when choosing non-adjacent locations.

Choosing adjacent locations is not always better than choosing non-adjacent locations, but it is never worse. For example, if we start with {1,1,2,2,3,3,5}, then we can achieve the same optimal result by transferring energy either between 3 and 5, or between 1 and 3. This typically happens when we would have to choose the non-adjacent locations eventually anyway, even if we did pick the adjacent locations first.

Value	1000
Submission Rate	9 / 49 (18.37%)
Success Rate	1 / 9 (11.11%)
High Score	gepa for 339.82 points (47 mins 28 secs)
Average Score	339.82 (for 1 correct submission)

If the Medium was not as easy as its success rate suggests, this problem was not as Hard as its success rate suggests. Many more coders would have gotten it if they hadn't spent so much time trying different strategies in the Medium.

There are at most eight ways to order the suits in alternating colors, so we can just try them all. However, we must be able to recognize when a particular ordering is invalid because of a missing suit (called a void in bridge lingo). For example, the ordering Clubs-Diamonds-Spades-Hearts is invalid if we have a void in either Diamonds (because the two black suits would be adjacent) or Spades (because the two red suits would be adjacent). The general rule is that, if we have exactly one void and that void is in one of the two middle suits, then that particular ordering of suits will not work. If we have two or even three voids, then any ordering of suits will work.

Given a particular ordering of suits, we want to find the minimum number of cards we have to move to achieve that ordering. Or, looking at it in the other direction, we want to find the maximum number of cards we can leave in place to achieve the ordering. This turns out to be the famous Longest Increasing Subsequence problem, previously seen in a similar form in the Books problem from SRM 175. (In our case, it would more accurately be called the Longest Non-Decreasing Subsequence problem, but I'll stick to the traditional terminology.) For example, if we want to achieve the ordering Clubs-Diamonds-Spades-Hearts, then we look for the longest increasing subsequence, treating the suits as numeric values with Clubs < Diamonds < Spades < Hearts. If our cards were DCSCDHSSH (considering only the suits), then the longest increasing subsequence is -C-CD-SSH, where the dashes indicate the cards that have to be moved.

Longest Increasing Subsequence is one of the classic applications of dynamic programming. We maintain an array longest[N], where longest[i] is the length of the longest increasing subsequence ending with the card at index i. We can fill in this array as follows:

  for (int i = 0; i < N; i++) {
    longest[i] = 1;
    for (int j = i-1; j >= 0; j--) {
      // can we put card i after card j in an increasing subsequence?
      if (suit[j] <= suit[i])
        longest[i] = max(longest[i], 1 + longest[j])
    }
  }

  int best = 0;
  for (int i = 0; i < N; i++) best = max(best, longest[i]);
  return N - best;

So far, I've only talked about the suits of the cards, but what about their ranks? We have to make sure that no suit ends up in increasing or decreasing order by rank (not counting suits with only one or two cards). This is trivial for suits that start out unsorted, but for suits that start out in sorted order, we need to find the longest increasing subsequence that excludes at least one card in that suit. Then, when that card is moved, we can be careful to put it in a position that will make the suit unsorted (although we do not have to go so far as to actually find that position in this problem).

We can adapt the LIS algorithm above to handle this extra constraint. We extend the longest array to have dimensions longest[N][2][2][2][2]. The four binary dimensions represent whether or not we are required to exclude a card in each of the four suits: 1 means that we want the longest subsequence that definitely does exclude a card in that suit, and 0 means that we want the longest subsequence, regardless of whether or not it excludes a card in that suit. For example, longest[5][0][1][1][0] would be the length of the longest increasing subsequence ending at position 5 that is known to have excluded a diamond and a heart. It may or may not have excluded a club and/or a spade—the 0's means we don't care. Adding these ideas to the previous algorithm, we get:

  for (int i = 0; i < N; i++)
    for (int c = 0; c < 2; c++)         // clubs
      for (int d = 0; d < 2; d++)       // diamonds
        for (int h = 0; h < 2; h++)     // hearts
          for (int s = 0; s < 2; s++) { // spades
            int[] x = new int[]{ c, d, h, s};
            // Do we still need to exclude a card in each suit?

            int best = -999; // initialize to an impossible value
            for (int j = i-1; j >= 0; j--) {
              if (suit[j] <= suit[i])
                best = max(best, 1 + longest[j][x[0]][x[1]][x[2]][x[3]]);
              // Otherwise, we are excluding card j,
              // so no longer need to exclude this suit.
              x[ suit[j] ] = 0;
            }
            if (x[0]+x[1]+x[2]+x[3] == 0) // ok to have card i by itself
              best = max(best, 1);
            longest[i][c][d][h][s] = best;
          }

  int best = 0;
  int[] x = new int[]{ sorted(0), sorted(1), sorted(2), sorted(3) };
  for (int i = N-1; i >= 0; i--) {
    best = max(best, longest[i][x[0]][x[1]][x[2]][x[3]]);
    // Otherwise, we are excluding card i
    x[ suit[i] ] = 0;
  }
  return N - best;

On a personal note, I actually do arrange my bridge hands more or less like in this problem, but without making a deliberate effort to keep the individual suits unsorted—they usually end up that way on their own.