Match Editorial

In Division 2, astaroth took top honors, narrowly edging out jachor, and palo in third. Each of the top three solved all three problems correctly. cbudin, who finished in fourth was the last correct entry for the hard problem, although his easy fell to system tests.

A special congratulations goes to palo, as the highest scoring newbie.

In Division 1, three top ranking coders took the top three slots, with SnapDragon winning by a commanding margin. Yarin and Eryx took second and third. ivan_metelsky, in fourth, was the fourth of the coders who successfully solved the hard problem.

The Problems

Value	250
Submission Rate	159 / 198 (80.30%)
Success Rate	81 / 159 (50.94%)
High Score	csd98412 for 243.89 points (4 mins 31 secs)
Average Score	178.69 (for 81 correct submissions)

This problem only deals with a string of at most 50 characters, so brute force searching for a solution is not difficult. The trick is to start with the largest possible substring, and work your way down to a smaller one, returning the result you find first. For each possible size substring, start at the left and try to find a repeat. Once you find a repeat, since you started with the largest first, and started at the left, you know you've got the proper result.

public String longestRepeat(String sourceText) {
   for (int i = sourceText.length() / 2; i > 0; i--)
      for (int j = 0; j < sourceText.length() - i; j++)
         if (sourceText.indexOf(sourceText.substring(j, j + i), j + i) > 0)
            return sourceText.substring(j, j + i);
   return "";
}

Value	500
Submission Rate	158 / 198 (79.80%)
Success Rate	130 / 158 (82.28%)
High Score	isv for 486.85 points (4 mins 41 secs)
Average Score	388.29 (for 130 correct submissions)

Value	250
Submission Rate	170 / 171 (99.42%)
Success Rate	164 / 170 (96.47%)
High Score	lars for 248.94 points (1 mins 51 secs)
Average Score	231.65 (for 164 correct submissions)

There are several ways to go about this problem, all of which can work. Essentially, you must first identify which categories of items need to be bagged. Then, count the number of items in each category. Then, for each category, determine how many bags are needed for the items of that category. Add up the number of bags, and you have a result.

One fast way to code the counting of the items in each category is to use a hashtable (of which some variety is available in every language) where the category is the key, and the number of items is the value. Then, at the end, loop through all the entries in the hashtable.

Another interesting approach is to first sort the list of item types, and then work through that list, keeping a count of how many of the "current" item types there are. When you reach an item of a new type, you can count the number of bags needed for the previous item type, and set your current item type to the new type. When you reach the end of the list, you add the last number of bags, and you're done.

Value	1000
Submission Rate	12 / 198 (6.06%)
Success Rate	4 / 12 (33.33%)
High Score	astaroth for 441.44 points (47 mins 8 secs)
Average Score	421.15 (for 4 correct submissions)

This problem perplexed a lot of coders, and even 2/3 of those who did manage to submit a solution would ultimately see it fall in the challenge phase or system testing.

At first glance, it's very tempting to look at a given set of dice and try to identify what hands are "almost made". For instance, {2, 3, 4, 6, 6} is almost a small straight, if only one of the 6's were a 1 or 5 instead. But, attempting to code this kind of logic fails, since there's also a possibility of this hand becoming a large straight, on that chance that both of the 6's re-roll favorably.

So, how do we tackle the problem at hand? Well, first we need a sound mechanism to score a given set of five dice values. This isn't terribly hard, and it's much easier when you first sort the values.

Now, consider that the values appearing on the five dice can be any one of 6^5 = 7776 possible configurations (note that {1,2,3,4,5} and {5,4,3,2,1} are different in this perspective). Now, when considering which dice to re-roll, we can represent our selection by a 5-digit binary number, where each digit indicates whether the corresponding die is re-rolled. That's 32 different re-roll configurations. So, this means brute force is efficient enough to work.

For each of the 32 possibilities of re-rolls, we simply check all possible outcomes of re-rolling the remaining dice, and from that we can calculate the probability of each hand, and hence the expected outcome. We then return the best of the 32 possible expected outcomes.

Value	500
Submission Rate	135 / 171 (78.95%)
Success Rate	72 / 135 (53.33%)
High Score	SnapDragon for 448.10 points (9 mins 54 secs)
Average Score	286.07 (for 72 correct submissions)

Depending on your preference, this problem is either a classic breadth-first search, or a flood fill of sorts. However, the existence of multi-lane roads in the town requires that some additional considerations be made when coding a solution.

Whatever approach is used, the problem simply breaks down to checking which of the four adjacent squares can be walked. For regular '.' locations, you simply move. For '-' locations you only move on to them if you're coming vertically, and vice-versa for '|' locations. Also, once you step onto a road, you continue moving in exactly the same direction until stepping off the road, or coming to an obstruction that prevents you from continuing.

A 50x50 array of integers, where each value represents the fewest number of crossings required to reach a given point, suffices for keeping track of results using a flood fill approach. Of course, you must be careful to bail out once you reach a location that you have already reached in fewer crossings. In the case where the flood fill never reaches the 'H' square, return -1, otherwise return the value corresponding to the square that contains the 'H'.

Value	1000
Submission Rate	10 / 171 (5.85%)
Success Rate	4 / 10 (40.00%)
High Score	Eryx for 635.27 points (24 mins 44 secs)
Average Score	557.78 (for 4 correct submissions)

With four successful solutions out of only 10 submissions, it's clear this problem was not obvious. The first few examples are intended to show a few very simple cases involving only two players. As implied by the examples, such a scenario is indeed solvable algebraically without too much effort. But, hopefully the latter examples made it obvious that a pure mathematical approach was no longer feasible once a third player was added.

At a glance, this appears to be a typical iterative probability problem, in which the task is simply, for each round of play, to calculate the winning percentage from each possible state (which is then accumulated into a single result value), and the probability of going to a different state in the next round of play. Then, repeat for the next round, and so on for however many loops are necessary to get enough precision in the result.

In the case of two players, there are only two states, where either you are king, or your opponent is king. In general, with n players, there are n! states to consider. After realizing this, it's obvious why the constraints are what they are. Each state is simply the ordering of the players in line (with the king being at the front of the line).

From any given state, one of several things can happen. The king can lose the throne immediately, the king can lose the throne after successfully scoring a point against one or more opponents, or the king can successfully score a point against all opponents, and win the game. In general, with n players, each state has one of n possible results.

So, for each state, we determine which other states we can get to, and the probability of each. Then, once we have that, we iterate from one round to the next, accumulating the winning probability for the first player. An interesting note about this is that, because of the king having the 2-to-1 advantage in play, the probabilities converge rather quickly, and a few hundred loops is more than sufficient to maximize the precision of the double data type.

I've saved for last what is one of the bigger difficulties in working out this problem. How does one efficiently represent the state space? A simple bitmask won't work, since 3 bits times 7 players = 21 bits, in which most values would equate to an invalid permutation (where a person appeared more than once, for instance), and would be far too inefficient to process over hundreds of loops.

One reasonable method involves building some kind of lookup table (indeed, it's possible to do this using some of the various types of collections provided by the standard libraries of your favorite language). This way, each ordering of players can be mapped to an index.

A more elegant, purely mathematical method, is to make use of a technique known as permutation mapping. The basic theory is that any permutation of n elements can be indexed with an integer from 0 to n-1. The way to do this is to take the first element, a1 of the permutatation, and determine its ordinal position among the other elements of the permutation. For a permutation of integers from 0 to n-1, this is just the value of a1. Then, multiple that ordinal value by (n-1)! and add that to the permutation index of the remaining subset of elements. Reversing the process is not difficult when it is known that the original permutation contained integers 0 through n-1.

Example methods (in Java) for determining the index of a permutation (of integers 0 through n-1), and determining the original permutation given the index and the number of elements:

int[] indexToPerm(int j, int d) {
   if (d == 1)
      return new int[]{0};
   int f = 1;
   for (int i = 2; i < d; i++)
      f *= i;      
   int[] r = new int[d];
   r[0] = j / f;
   int[] t = indexToPerm(j % f, d - 1);
   for (int i = 0; i < t.length; i++)
      if (t[i] >= r[0]) t[i]++;
   System.arraycopy(t, 0, r, 1, t.length);
   return r;
}

int permToIndex(int[] p) {
   if (p.length == 2)
      return p[0];
   int f = 1;
   for (int i = 1; i < p.length; i++)
      f *= i;
   int[] r = new int[p.length - 1];
   System.arraycopy(p, 1, r, 0, p.length - 1);
   for (int i = 0; i < r.length; i++)
      if (r[i] > p[0]) r[i]--;
   return f * p[0] + permToIndex(r);
}