|
Match Editorials |
Thursday, March 8, 2007
Match summary
Completing 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. Thirty-three of the 35 were able to do so.
The Problems
ItemizedList
Used 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.
Value 250 Submission Rate 34 / 35 (97.14%) Success Rate 32 / 34 (94.12%) High Score Curiouser for 248.19 points (2 mins 25 secs) Average Score 217.63 (for 32 correct submissions)
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).
Value 500 Submission Rate 25 / 35 (71.43%) Success Rate 13 / 25 (52.00%) High Score Burunduk3 for 458.12 points (8 mins 45 secs) Average Score 298.77 (for 13 correct submissions)
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 (a-b/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.
Value 1000 Submission Rate 6 / 35 (17.14%) Success Rate 2 / 6 (33.33%) High Score Burunduk3 for 535.21 points (33 mins 20 secs) Average Score 523.51 (for 2 correct submissions)
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 re-roll, this means there are no more than 25 = 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 re-rolling anything.)
Next, for each of these possible re-rollings, we need to calculate the expected score. Noting that this means the average score for each possible result of re-rolling, we can determine in the back of our minds that there are no more than 65 = 7776 possible results after re-rolling 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 re-rollings, 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 re-rolled, I keep the value fixed for each of the 6 iterations. Why do I do this? Simply put, it allows an easy apples-to-apples 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 re-rolling (some of which are identical, depending upon how many dice are fixed versus re-rolled). 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;
}
