Thursday, March 8, 2007 Match summaryCompleting all three tasks in about 48 minutes, Burunduk3 secured the win by a margin of more than 100 points. At the end of the challenge phase, six coders had solved the hard problem but, by the end of system testing, RuslanSM was the only other to pass system tests on all three problems, earning himself a second place finish.In all, with 100 slots for advancement, and only 35 competitors, earning a positive score was all that was required to stay in the tournament. Thirtythree of the 35 were able to do so. The ProblemsItemizedListUsed as: Division One  Level One: Most coders using C++ used the STL map<string, int> here, iterated through the array, and then iterated through the completed map to generate the required output. This was easy enough. Another approach is to first sort the array, then iterate through the array, keeping count of each item as you go, and adding the previous item (and it's quantity) to the list whenever a new item is found. In Java: public String[] generateList (String[] items) { Arrays.sort(items); ArrayList ret = new ArrayList(); String cur = items[0]; int count = 1; for (int i = 1; i < items.length; i++) { if (cur.equals(items[i])) { count++; } else { ret.add(cur + "  " + count); cur = items[i]; count = 1; } } ret.add(cur + "  " + count); return (String[])ret.toArray(new String[0]); }FractionPoints Used as: Division One  Level Two: Careful reading of the problem statement, and implementing the definitions exactly as given, were the keys to solving this problem. Three basic pieces of functionality are needed: sorting the data, finding a median (being careful to handle appropriately when there are an even or odd number of elements), and extracting the lower and upper halves of a data set (again, paying attention to parity). Following how the the terminology was defined in the problem statement, a basic recursive solution seems pretty natural, and indeed works well here. However, an iterative approach is also possible. In general, we are looking for the "a/b" point in the data. If a/b = 1/2, then we take the median, and we're done. Otherwise, if 2a < b, then our desired point is in the lower half, and we need to find the a/(b/2) point of the lower half. If 2a > b, then we need the (ab/2)/(b/2) point from the upper half of the data. Having noticed this much, we can simply sort our data, and then keep track of the range of elements in which the target point exists, like this: public double findPoint(int[] data, int numerator, int denominator) { Arrays.sort(data); int beginPoint = 0; int endPoint = data.length  1; while (denominator > 2) { if (numerator < denominator / 2) { endPoint = (beginPoint + endPoint  1) / 2; } else { beginPoint = (beginPoint + endPoint + 2) / 2; numerator = denominator / 2; } denominator /= 2; } if ((endPoint  beginPoint) % 2 == 1) { int point1 = data[(beginPoint + endPoint) / 2]; int point2 = data[(beginPoint + endPoint + 1) / 2]; return 0.5 * (point1 + point2); } else { return data[(beginPoint + endPoint) / 2]; } }YahtzeeAdversary Used as: Division One  Level Three: Yahtzee is a pretty popular game, and typically the goal is to maximize one's score. However, the addition of an adversary (who has the goal of minimizing the first player's score) into the game changes things a bit. The variable scoring also means that the optimal stratey might change, depending on what formations are worth the most points. First, we need to think about how much effort is involved in determining what we want to know. Since there are five dice, and we're going to choose some subset of them to reroll, this means there are no more than 2^{5} = 32 choices that the second player can make. When we consider the restriction that at least two dice must be chosen, this number is actually only 26. (Problem writer's note: the restriction about having a minimum of two dice was not arbitrary, but was intended instead to prevent the majority of cases, where the existing dice showed no scoring formation, from having a trivial solution of not rerolling anything.) Next, for each of these possible rerollings, we need to calculate the expected score. Noting that this means the average score for each possible result of rerolling, we can determine in the back of our minds that there are no more than 6^{5} = 7776 possible results after rerolling the dice. So, hopefully it's obvious that 7776 * 26 = 202,176... and more importantly, that brute forcing this easily runs in time. Now, all that's left is to consider each of the 26 rerollings, and determine which one has the lowest expected score. In my example shown here, note that I calculate the expected score by iterating through 6 possible results for each of the five dice. For any of the dice that are not being rerolled, I keep the value fixed for each of the 6 iterations. Why do I do this? Simply put, it allows an easy applestoapples comparison between outcomes, without having to divide and compare floating point numbers. By doing it this way, I actually calculated the total score resulting from 7,776 results of rerolling (some of which are identical, depending upon how many dice are fixed versus rerolled). I can then directly compare these totals. Lastly, notice that I generate all of the possible results in lexicographic order already, so that I don't have to handle tiebreaking if another possible selection has the same expected result. int[] s; int[] d; public boolean has(int[] v, int x) { for (int i = 0; i < v.length; i++) if (v[i] == x) return true; return false; } public int scoreHand(int[] values) { int res = 0; Arrays.sort(values); // Check for Yahtzee if (values[0] == values[4]) res = Math.max(res, s[0]); // Check for Full House if (values[0] == values[1] && values[3] == values[4] && (values[1] == values[2]  values[2] == values[3])) res = Math.max(res, s[3]); // Check for large straight if (values[1]  values[0] == 1 && values[2]  values[1] == 1 && values[3]  values[2] == 1 && values[4]  values[3] == 1) res = Math.max(res, s[1]); // Check for small straight if (has(values, 3) && has(values, 4)) { if (has(values, 2) && (has(values, 1)  has(values, 5))) res = Math.max(res, s[2]); if (has(values, 5) && has(values, 6)) res = Math.max(res, s[2]); } return res; } public int getExpectedScore(int[] values) { int res = 0; int[] i = new int[5]; for (i[0] = 1; i[0] <= 6; i[0]++) for (i[1] = 1; i[1] <= 6; i[1]++) for (i[2] = 1; i[2] <= 6; i[2]++) for (i[3] = 1; i[3] <= 6; i[3]++) for (i[4] = 1; i[4] <= 6; i[4]++) res += scoreHand(new int[]{ has(values, 0) ? i[0] : d[0], has(values, 1) ? i[1] : d[1], has(values, 2) ? i[2] : d[2], has(values, 3) ? i[3] : d[3], has(values, 4) ? i[4] : d[4]}); return res; } public int[] reRollDice(int[] scores, int[] dice) { s = scores; d = dice; int bestExpected = 999999999; int[] best = new int[0]; int testScore; for (int a = 0; a <= 4; a++) for (int b = a + 1; b <= 4; b++) { testScore = getExpectedScore(new int[]{a, b}); if (testScore < bestExpected) { bestExpected = testScore; best = new int[]{a, b}; } for (int c = b + 1; c <= 4; c++) { testScore = getExpectedScore(new int[]{a, b, c}); if (testScore < bestExpected) { bestExpected = testScore; best = new int[]{a, b, c}; } for (int d = c + 1; d <= 4; d++) { testScore = getExpectedScore(new int[]{a, b, c, d}); if (testScore < bestExpected) { bestExpected = testScore; best = new int[]{a, b, c, d}; } for (int e = d + 1; e <= 4; e++) { testScore = getExpectedScore(new int[]{a, b, c, d, e}); if (testScore < bestExpected) { bestExpected = testScore; best = new int[]{a, b, c, d, e}; } } } } } return best; } 
