Tuesday, December 7, 2004 Match summary 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 ProblemsTextCompressorUsed as: Division Two  Level One:
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 ""; }GroceryBagger Used as: Division Two  Level Two: Used as: Division One  Level One:
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. YahtzeeRollUsed as: Division Two  Level Three:
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 reroll 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 reroll, we can represent our selection by a 5digit binary number, where each digit indicates whether the corresponding die is rerolled. That's 32 different reroll configurations. So, this means brute force is efficient enough to work. For each of the 32 possibilities of rerolls, we simply check all possible outcomes of rerolling 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. WalkingHomeUsed as: Division One  Level Two:
Depending on your preference, this problem is either a classic breadthfirst search, or a flood fill of sorts. However, the existence of multilane 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 viceversa 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'. KingOfTheCourtUsed as: Division One  Level Three:
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 2to1 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 n1. 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 n1, this is just the value of a1. Then, multiple that ordinal value by (n1)! 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 n1. Example methods (in Java) for determining the index of a permutation (of integers 0 through n1), 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); } 
