|
Match Editorial |
Tuesday, May 15, 2007
Match summary
In Division 2, coders faced a straightforward easy, an approachable but tricky medium, and a challenging hard problem. Only four coders successfully solved all three problems, placing them at the top of the pack. The win was claimed by newcomer hken_old, who vaulted into division 1 with the maximum possible rating after a single match. He was followed by luison9999, espr1t, and smichal.In Division 1, coders faced a simple but tricky easy, a fairly straightforward medium, and a deceptively ferocious hard. In the end, only tomek, PaulJefferys, and monsoon solved the hard (and in fact, all three problems) correctly. That, and a few challenges, easily gave them the top three slots.
In Division 2, the tricky set of cases on the medium problem, as well as issues with double precision, saw a lot of problems fall during the challenge phase. In Division 1, the slaughterhouse style challenge phase was even more cruel, with only 8 of the more than 100 hard submissions surviving until systests.
The Problems
DocumentSearch
Used as: Division Two - Level One:
The only thing to worry about here is not making a mistake as we implement the algorithm exactly as described in the problem statement. We first concatenate the string. Then, starting at position 0, moving forward one character at a time, we check each substring, and if the next several characters match the search string, we advance to the character immediately following the search string, and increment our result counter.
Value 250 Submission Rate 571 / 603 (94.69%) Success Rate 404 / 571 (70.75%) High Score Margarita for 248.89 points (1 mins 54 secs) Average Score 206.24 (for 404 correct submissions)
public int nonIntersecting(String[] doc, String search) {
String s = "";
for (int i = 0; i < doc.length; i++)
s += doc[i];
int i = 0;
int ret = 0;
while (i <= s.length() - search.length())
if (s.substring(i, i + search.length()).equals(search)) {
ret++;
i += search.length();
} else {
i++;
}
return ret;
}
RadarFinder
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 500 Submission Rate 457 / 603 (75.79%) Success Rate 41 / 457 (8.97%) High Score GeKa for 464.51 points (7 mins 58 secs) Average Score 290.89 (for 41 correct submissions)
This problem was good challenge bait, as there are several cases to consider. Not only are we are haunted by the typical problems that go along with using doubles, but we need to make sure we think about all possible configurations of the two circles represented by the radar measurements.
Value 250 Submission Rate 533 / 548 (97.26%) Success Rate 170 / 533 (31.89%) High Score Petr for 248.46 points (2 mins 14 secs) Average Score 192.75 (for 170 correct submissions)
Now, we can look first for the special case where there are an infinite number of possible points. Namely, the case where two of the circles have the same radius, centered at the same location.
With that special case out of the way, note that the only things we care about, to describe all other configurations, are the radii of the circles, and the distance between the centers. Beyond that, the exact locations are not relevant. Call these values r1, r2, and d. Assume r1 >= l2.
Now, we can have five basic cases (possibly more or less depending on exactly how one defines the different cases):
| Comparison Description | Configuration Description | Number of Points |
|---|---|---|
| d < r1 - r2 | One circle completely inside the other | 0 |
| d = r1 - r2 | Circles internally tangent | 1 |
| d > r1 - r2 and d < r1 + r2 |
Circles intersect | 2 |
| d = r1 + r2 | Circles externally tangent | 1 |
| d > r1 + r2 | Circles separate | 0 |
One last consideration, to avoid the issues with doubles, is to use only (64-bit) integers. We can easily calculate d2 using only integers. If we square both sides of each of the comparisons above, we then have some equivalent comparisons that use only integer arithmetic.
public int possibleLocations(int x1, int y1, int r1, int x2, int y2, int r2) {
long sr = (long)(r1 + r2) * (long)(r1 + r2);
long dr = (long)(r1 - r2) * (long)(r1 - r2);
long d = (long)(x2 - x1) * (long)(x2 - x1)
+ (long)(y2 - y1) * (long)(y2 - y1);
if (x1 == x2 && y1 == y2 && r1 == r2) return -1;
if (d < dr || d > sr) return 0;
if (d == sr || d == dr) return 1;
if (d > dr && d < sr) return 2;
// Never get to this line
return 3;
}
BoggleScore
Used as: Division Two - Level Three:
After understanding the problem here, we can make a few quick calculations that give us some idea about what type of solutions may or may not work. In particular, notice that when tracing out the path of a word we find, there are at least three ways to get from one character to the next (namely, if you're moving from a corner -- in other cases there are more than three ways). So, if you are trying to spell out a word with 50 characters, there are more than 350 ways to do it. Clearly, a brute force approach is doomed to failure, so we need to be a little more efficient.
Value 1000 Submission Rate 184 / 603 (30.51%) Success Rate 16 / 184 (8.70%) High Score hken for 872.51 points (11 mins 12 secs) Average Score 562.26 (for 16 correct submissions)
Since we don't care about the actual paths used to spell out a word, but rather only the number of ways to do so, this implies something about how we solve the problem. More specifically, we can ask the question, "How many ways can I spell a given word, such that it ends at a position (x,y)?" We can then answer this question by saying, if the character at that position is the right character, then it's the sum of the number of ways to spell all but the last character of the word from each of the adjacent positions. This is enough to build a Dynamic programming solution.
In the example solution below, I have actually built a 6x6 grid, with junk characters as the border (also known as sentinnel values), to avoid having to worry about boundary checking. Note also the frequent usage of the modulus operation, to avoid overflowing a 64-bit value.
public long bestScore(String[] grid, String[] words) {
long mod = 10000000000000L;
long total = 0;
char[][] letters = new char[6][6];
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
if (i == 0 || i == 5 || j == 0 || j == 5)
letters[i][j] = '.';
else
letters[i][j] = grid[i - 1].charAt(j - 1);
for (int k = 0; k < words.length; k++) {
long[][][] count = new long[6][6][words[k].length()];
char c = words[k].charAt(0);
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (letters[i][j] == c)
count[i][j][0] = 1;
for (int m = 1; m < words[k].length(); m++) {
c = words[k].charAt(m);
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if (letters[i][j] == c) {
for (int x = -1; x <= 1; x++)
for (int y = -1; y <= 1; y++)
if (x != 0 || y != 0)
count[i][j][m] += count[i + x][j + y][m - 1];
count[i][j][m] = count[i][j][m] % mod;
}
}
long t = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
t += count[i][j][words[k].length() - 1];
t = t % mod;
t *= words[k].length() * words[k].length();
t = t % mod;
total += t;
total = total % mod;
}
return total;
}
DiceGames
Used as: Division One - Level Two:
Many coders quickly saw the DP solution to this problem. When we think about what a formation means, it's nice to think of it as a "canonical form" where the values are in sorted order. Furthermore, when we think about ways to make a formation from the dice, we should assume that the lowest value of the formation came from the die with the fewest sides. Why is this? Consider the case where you have two dice, with four and six sides. Formations like (2, 3) and (1, 4) can be made in two different ways (either die could show either value), but formations like (4, 5) and (3, 6) can only be made in one way. Assuming that the lowest values appear on the dice with the fewest sides allows us to maximize the number of formations.
Value 500 Submission Rate 415 / 548 (75.73%) Success Rate 352 / 415 (84.82%) High Score JongMan for 495.34 points (2 mins 45 secs) Average Score 380.60 (for 352 correct submissions)
The most common approach to the problem goes something like this: How many formations can be made is the number of non-decreasing sequences that can be made from the dice. So, how do we get the number of such sequences? If we consider the possible values that end (or start) the sequence, then we know that the previous (or next) n-1 terms of the sequence must all be less than or equal to this value. This leads us to a fairly straightforward DP solution (shown below).
It is interesting to point out that, in the heat of a match, we often come up with other unique ways to solve problems. For instance, mohamedafattah offered up a slightly different way of breaking down the problem. Also starting with sorted dice, and noting that the maximum sum of the values shown on the dice is limited by the constraints of the problem, his code asks the question, how many ways can I make the first several dice sum up to a given value? Implicitly, it accomplishes the same thing as the previously explained approach, but it takes a slightly different thought process to get there.
public long countFormations(int[] sides) {
Arrays.sort(sides);
long[][] ret = new long[sides.length][sides[sides.length - 1]];
for (int i = 0; i < sides[0]; i++)
ret[0][i] = 1;
for (int i = 1; i < sides.length; i++)
for (int j = 0; j < sides[i]; j++)
for (int k = 0; k <= j; k++)
ret[i][j] += ret[i - 1][k];
long res = 0;
for (int i = 0; i < sides[sides.length - 1]; i++)
res += ret[sides.length - 1][i];
return res;
}
LastMarble
Used as: Division One - Level Three:
When both Petr and tomek resubmit a problem, that is definitely a sign that there is something tricky going on, and this problem was no exception. Allegedly, based on buzz in the forums, among all problems with a non-zero success rate, only one other has been more deceptively difficult.
Value 1000 Submission Rate 130 / 548 (23.72%) Success Rate 3 / 130 (2.31%) High Score tomek for 558.48 points (23 mins 9 secs) Average Score 452.79 (for 3 correct submissions)
If this problem were simply a bag of red and blue marbles, without the unknown removed marbles, then it would boil down to a fairly typical game theory problem, where the goal is to make the move that maximizes one's chances of winning. In fact, that is still the case, but the question remains of how to properly calculate such values in light of the unknown removed marbles.
An initial thought might be to calculate each of the possible initial states of the bag, after the first set of unknown marbles is removed. Then, for each possible state, determine the probability of winning, compute the weighted average, and return the result. This approach is flawed however, since the player, during game play, does not know the exact state of the bag.
Those individuals well-versed in probability theory, including those who have recently competed in marathon matches where the topic frequently arises, may see Bayes Theorem written all over this problem. In fact, that is a mathemtically viable approach, but it creates a very large state space of the problem, and is fairly complicated, making it prone to subtle bugs.
The simpler solution, which is presented below, is to first make an important observation that the probabilities of randomly choosing things is symmetric. That is, from a set of n items, the number of ways to choose r of them is the same as the number of ways to choose n-r of them. What this means for us is that the probability of the bag being in any given state does not rely upon the order in which different random draws are made. In particular, the probability of the bag containing some quantity of red and blue marbles is the same regardless of at what point in the game the unknown marbles are removed from the bag. Thus, it is equivalent to play as though starting with a full bag, and only removing the unknown marbles at the very end. It may take some time to digest this, as it seems counterintuitive at first.
So, the end result is that we only need to consider a state space consisting of how many red marbles are in the bag, how many blue marbles are in the bag, and who last drew a red marble. The sample below uses three values to indicate if the last red was drawn by the player, opponent, or nobody. Two simple helper functions define the typical combinatoral choose function, and calculate the probability of drawing (r,b) marbles from a bag containing a given number of red marbles among the total.
public double winningChance (int red, int blue, int removed) {
int total = red + blue;
double[][][] dp = new double[total + 1][red + 1][3];
for (int i = 0; i <= red; i++)
dp[removed][i][2] = 1;
for (int i = removed + 1; i <= red + blue; i++)
for (int j = 0; j <= red; j++)
for (int k = 0; k <= 2; k++) {
for (int m = 1; m <= Math.min(3, i - removed); m++) {
double test = 0;
for (int r = 0; r <= Math.min(m, j); r++)
test += chooseProb(i, j, m - r, r)
* (1.0 - dp[i - m][j - r][r > 0 ? 2 : (k * 2) % 3]);
dp[i][j][k] = Math.max(dp[i][j][k], test);
}
}
return dp[red + blue][red][0];
}
private int choose(int c, int r) {
if (r > c) return 0;
int ret = 1;
for (int i = c; i > c - r; i--) ret *= i;
for (int i = 1; i <= r; i++) ret /= i;
return ret;
}
private double chooseProb(int total, int red, int b, int r) {
double ret = 1.0;
ret *= choose(total - red, b);
ret *= choose(red, r);
ret /= choose(total, b + r);
return ret;
}
