Match Editorial

Usually the top ten is dominated by reds, but this time five yellows and a blue snuck in, leaving two targets and many other reds out in the cold. SnapDragon flirted with another top-ten list, the list of Highest Match Totals, finishing in a blazing 27 minutes. tomek finished 2 minutes and a hundred points behind. But then SnapDragon discovered an off-by-one bug in his Medium and had to resubmit, handing tomek the win.

In Division Two, several coders entered the Challenge Phase with 1300+ points, but none survived challenges and system tests. Among those lurking just behind the leaders, anikov rode a successful challenge to victory, with rookie jvpardon taking second, also using a challenge to pass veteran dhyanesh.

The Problems

Value	250
Submission Rate	141 / 158 (89.24%)
Success Rate	118 / 141 (83.69%)
High Score	DamnEcuadorian for 247.17 points (3 mins 3 secs)
Average Score	205.27 (for 118 correct submissions)

It's easy to find the best player using a loop like

  int bestPlayer = -1, bestScore = -1;
  for (int i = 0; i < fame.length; i++) {
    int score = min(fame[i], min(fortune[i], secrets[i]));
    if (score > bestScore) { 
      bestPlayer = i; 
      bestScore = score;
    }
  }
  return bestPlayer;

  int bestPlayer = -1, bestScore = -1;
  boolean tie = false;
  for (int i = 0; i < fame.length; i++) {
    int score = min(fame[i], min(fortune[i], secrets[i]));
    if (score > bestScore) { 
      bestPlayer = i; 
      bestScore = score;
      tie = false;
    }
    else if (score == bestScore) tie = true;
  }

  if (tie) return -1;
  else return bestPlayer;

A slightly easier approach, taken by bugloaf and egghead, is to reset bestPlayer to -1 when a tie is detected, as in

  int bestPlayer = -1, bestScore = -1;
  for (int i = 0; i < fame.length; i++) {
    int score = min(fame[i], min(fortune[i], secrets[i]));
    if (score > bestScore) { 
      bestPlayer = i; 
      bestScore = score;
    }
    else if (score == bestScore) bestPlayer = -1;
  }
  return bestPlayer;

Value	500
Submission Rate	114 / 158 (72.15%)
Success Rate	80 / 114 (70.18%)
High Score	czar for 480.45 points (5 mins 46 secs)
Average Score	343.91 (for 80 correct submissions)

This problem boils down to deciding if two sequences of letters are permutations of each other, once you've removed all the spaces and converted all lowercase letters to uppercase (or vice versa). One appoach is to walk through the letters of the first string. For each letter, search for an occurrence of that letter in the second string and delete it if found. If you can't find the letter, or if there are letters left over in the second string when you're done, then the strings were not anagrams.

A simpler approach, suggested by the title of the problem, is to sort both strings and test if the sorted strings are equal. See, for example, arun_zero's implementation of this test. This sorting trick is an instance of the general technique of checking if two objects are equivalent by converting both into some normal form and testing if they both have the same normal form. Using normal forms to turn an equivalence check into an equality check is a good idea whenever the notion of equivalence is even a little bit complicated.

Once you've converted the strings into normal form, you can compare them pairwise (see czar's or ronit_dragon's solutions) or check for duplicates by putting them into some kind of set (see Toivoa's solution).

Value	900
Submission Rate	33 / 158 (20.89%)
Success Rate	19 / 33 (57.58%)
High Score	JavaLinZi for 669.55 points (18 mins 1 secs)
Average Score	526.20 (for 19 correct submissions)

Value	300
Submission Rate	148 / 173 (85.55%)
Success Rate	132 / 148 (89.19%)
High Score	Eryx for 298.27 points (2 mins 10 secs)
Average Score	220.16 (for 132 correct submissions)

This problem was amenable to brute force (see, for example, NeverMore's fourteen nested loops), but a more elegant solution arises by thinking about the relationships between the weights.

Consider, for example, the 1-grain weight. Notice that the other weights are multiples of 3, so any combination of the other weights will yield a net result that is a multiple of three. If your target weight is not a multiple of three, then the 1-grain weight must be involved. If the target weight mod 3 is 1, then the 1-grain weight goes in the opposite pan. If the target weight mod 3 is 2, then the 1-grain weight goes in the same pan as the object. If the target weight mod 3 is 0, then the 1-grain weight is not used at all, because combining the 1-grain weight with other weights could never yield a multiple of three.

Once you've placed the 1-grain weight, similar logic can be used to place each successive weight, as in

   answer = create a new vector or list;
   current_size = 1;
   while W > 0 do
      if W % 3 == 1 then
         W -= 1;
         add current_size to answer;  // place on opposite pan
      if W % 3 == 2 then
         W += 1;
         add -current_size to answer; // place on same pan
      W /= 3;
      current_size *= 3;
   sort(answer);

If you like weird number systems, another way of looking at this problem is that you are converting W into a base-3 number system where the allowable digits are {-1,0,1} instead of {0,1,2}.

Value	600
Submission Rate	40 / 173 (23.12%)
Success Rate	28 / 40 (70.00%)
High Score	tomek for 513.59 points (12 mins 4 secs)
Average Score	348.28 (for 28 correct submissions)

You could use memoization (SnapDragon) or dynamic programming (radeye) here, but a greedy approach works even better.

Basically, you test each possible number of turns to find the smallest one that yields a solution.

  for (int n = 0; n <= stock.length; n++) {
    int[] partialStock = ...copy first n elements of stock...
    if (canSolve(tableau, partialStock)) return n;
  }
  return -1; 

Now, which card should end up in the first position in the tableau? There are only two candidates, either the existing first card in the tableau or the first card in the sorted stock, of which we pick the smaller one in order to give maximum freedom in placing future cards. This is the greedy choice. It may be possible to win the game by picking a different card to go in the first position, either the bigger of the two or a different card from the stock, but in all such cases picking the indicated card would also lead to a win. For example, if we picked some larger card from the stock to go in the first position, then we must have discarded the smallest card from the stock, in which case we could just as easily have kept the smallest card and discarded the larger card instead. Similar arguments hold if we choose to keep the existing first card in the tableau when it is bigger than the smallest card in the stock, or if we choose to replace the first card in the tableau when it is actually smaller than the smallest card in the stock.

Once we've settled which card goes in the first position, we move on to the second position. Again there are two candidates, either the existing card in that position or the smallest remaining card in the stock, and again we pick the smaller of the two, with one exception. If the existing card in the second position is smaller than the card that we picked for the first position, then we cannot pick it. (This special case is not a concern for cards from the stock, because they will never be smaller than the card we picked for the previous position.)

We continue in this fashion until either we fill the tableau, in which case we have won the game, or we run out of stock, in which case we check if the rest of the tableau just happens to be sorted but if it's not, then know we cannot win.

In code, this algorithm could be written

   boolean canSolve(int[] tab, int[] stock) {
      sort(stock); // remember this is a portion of the real stock
      int prev = -1;
      int i = 0, j = 0;
      for (; i < tab.length && j < stock.length; i++) {
         if (stock[j] < tab[i] || tab[i] < prev)
            prev = stock[j++];
         else
            prev = tab[i];
      }
      for (; i < tab.length; i++) {
         if (tab[i] < prev) return false;
         prev = tab[i];
      }
      return true;
   }

Value	1000
Submission Rate	14 / 173 (8.09%)
Success Rate	8 / 14 (57.14%)
High Score	SnapDragon for 933.62 points (7 mins 41 secs)
Average Score	650.16 (for 8 correct submissions)

There are lots of different ways to approach this problem. Some are hard to think of but easy to code, others are easy to think of but hard to code.

SnapDragon had what was perhaps the easiest algorithm to explain. Suppose you wanted to determine whether it is possible to form M groups. He imagined a grid M columns wide by k rows high, where each column represents a group. Then, he tried to fill in the grid row by row. He filled in people from the first country starting in the top left corner, then people from the second country starting from where the first country ended, and so. If a given country had fewer than M people, he used them all; otherwise, he only used the first M people from that country. If he succeeded in filling the entire grid, then it was possible to form M groups. A binary search on different values of M finds the largest value of M that works.

Let sum be the sum of all the populations. Then the maximum number of groups that could possibly be formed is sum/k. SnapDragon's algorithm serves as a constructive proof for the following theorem: If the biggest country contains no more than sum/k people, then it is in fact possible to form sum/k groups. This theorem provides the base case for a simple recursive algorithm. If the biggest country contains more than sum/k groups, then you figure you will use one person from this country in every group and discard the rest. The number of groups is determined by how many groups of k-1 people can be formed from the remaining countries.

These two algorithms are trivial to code, but require a lot of insight up front. At the other extreme is an algorithm that requires little insight up front, but ends up being much harder to code. This algorithm is based on the idea that groups should be formed greedily. In other words, to form each group, we should take one person from each of the k countries that currently have the most people remaining. Of course, with the possibility of billions of groups, we cannot afford to form groups one at a time. So how can we form many groups at once?

Suppose that the k-th largest country is, say, 100 bigger than the (k+1)-st largest country. Then we can safely form 101 groups from the k largest countries. At that point, what was the (k+1)-st largest country replaces what was the k-th largest country in the top k. This technique lets us make a big jump at the very beginning of the algorithm, but, unfortunately, once the k-th largest country and the (k+1)-st largest country are within one of each other, we can never make such a large jump again. Instead, we are again limited to forming groups one or two at a time. And with possibly billions of groups still to form, we are little better off than before.

But with smarter handling of the k-th and (k+1)-st largest countries, we can extend this technique into something manageable. Divide the countries into four sets:

• the frontier: countries with the same size as the k-th largest country
• the subfrontier: countries one smaller than the k-th largest country
• the bigs: countries larger than those in the frontier
• the littles: countries smaller than those in the subfrontier

Now, when we form a single group of penpals, what happens? We take one person from each country in the bigs, and fill out the rest of the group from k-B countries in the frontier. This moves k-B countries from the frontier to the subfrontier. If there are still more countries in the frontier, then we check whether any countries in the bigs are now small enough to join the frontier. If the frontier is empty, then the subfrontier becomes the new frontier, and we check whether any countries in the littles are now big enough to join the now-empty subfrontier.

Let M be the least common mulitple of F+S and k-B. Then, if we form M/(k-B) groups, we will end up using each member of the frontier and subfrontier exactly M/(F+S) times. However, the composition of the frontier and subfrontier will not change at all; that is, they will contain exactly the same countries as before, assuming no countries from the bigs have joined the frontier and no countries from the littles have joined the subfrontier.

At each step, we want to take the largest multiple of M/(k-B) groups that we can without causing the smallest country in the bigs to join the frontier or the largest country in the littles to join the subfrontier. Let above be the gap between the sizes of the smallest country in the bigs and the countries in the frontier, and let below be the gap between the sizes of the largest country in the littles and the countries in the subfrontier. How quickly are these gaps closing? For every M/(k-B) groups we form, the below gap closes by M/(F+S) and the above gap closes by M/(k-B) - M/(F+S). Therefore, we can safely form Q groups, where Q is M/(k-B) times the minimum of below/(M/(F+S)) and above/(M/(k-B) - M/(F+S)). If Q is 0, then we merely form a single group, but we will not have to do this very many times until the frontier or the subfrontier has absorbed the member of the bigs or littles that was blocking further progress. Then we can again make potentially large jumps.

Many people appeared to be working on variations on this theme as time expired, but none successfully completed it.