Get Time
statistics_w  Match Editorial
SRM 204
Wednesday, July 21, 2004

Match summary

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

Medici discuss it
Used as: Division Two - Level One:
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;
but this doesn't account for the treatment of ties. We could maintain a boolean flag to indicate ties, as in
  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;
For example, dukeola and jvpardon took essentially this approach. AleaActaEst and czar used a counter instead of the boolean flag.

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;

Aaagmnrs discuss it
Used as: Division Two - Level Two:
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).

Apothecary discuss it
Used as: Division Two - Level Three:
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)
Used as: Division One - Level One:
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;
Ryan and marian had particularly clean implementations of this idea.

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}.

Sortitaire discuss it
Used as: Division One - Level Two:
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; 
The hard work is done by the canSolve function. Begin by sorting the cards in the partial stock. This will mean that the order in which we process cards from the stock will not be the same as the order in which they were dealt, but this is okay because we get to see all the cards ahead of time. Once we know where we want to put each card, we could go back and make all those moves in the correct order. The real game is much harder because you must decide what to do with each card before you get to draw the next card.

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++];
            prev = tab[i];
      for (; i < tab.length; i++) {
         if (tab[i] < prev) return false;
         prev = tab[i];
      return true;
jms137 and tomek gave nice implementations of this algorithm, tomek even including a semi-gratuitous binary search for the right number of turns.

WorldPeace discuss it
Used as: Division One - Level Three:
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
Designate the number of countries in each set as F, S, B, and L, respectively.

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.

By vorthys
TopCoder Member