|
Match Editorial |
Thursday, July 31, 2008
Match summary
Solutions to the Easy problem appeared quickly in Division I.
The medium took longer; Petr
and bmerry had solved both easy and
medium problems after 18 minutes.
After 40 minutes many more coders have managed to solve both of these
problems. Then, the
first solution of 1000 appeared, by Michael_Levin. When the coding
phase was over, there were many solutions of the 1000 point problem.
Michael_Levin was in the lead (1325 points),
followed by _pperm (1270 points),
Petr, misof,
and Vigothebest.
Challenge phase and system tests killed most of the 1000
point problem solutions. But Michael_Levin was still in the lead,
followed by Petr, ilyakor, bmerry, and izulin.
Note that both Michael_Levin and
Petr
managed to keep their first two places after
resubmitting their 250 point problems.
In Division II, two coders managed to solve all three problems
(soul3434 and Laise), followed by the five who solved the 1000
point problem without solving 500 correctly.
The Problems
TrueSpace
Used as: Division Two - Level One:
Value 250 Submission Rate 792 / 818 (96.82%) Success Rate 649 / 792 (81.94%) High Score xiaowuc1 for 249.39 points (1 mins 24 secs) Average Score 224.74 (for 649 correct submissions)
To solve this problem, one had to find the smallest multiple of clusterSize which is a multiple of sizes[i], then add these values for each i. There were many correct ways of finding such smallest multiple, for example, ((sizes[i] + clusterSize - 1) / clusterSize) * clusterSize always works correctly. A possible bug was to perform the calculations on ints instead of longs.
BirthdayReminders
Used as: Division Two - Level Two:
Value 500 Submission Rate 338 / 818 (41.32%) Success Rate 92 / 338 (27.22%) High Score hamdanil for 348.32 points (20 mins 45 secs) Average Score 228.94 (for 92 correct submissions)
A common way of solving this problem was to generate the next k
times each occasion type happens for each friend (thus, generating
k*o*f occasions in total, where o is the number of
occasion types, and f is the number of friends). Then, sort
these occasions by time, and output k earliest of them. It was
possible to timeout using this solution (if currentDate is 1000000,
birthDate is 0, and days is 1, then a simple solution would generate
all the 1000000 occasions between 0 and 1000000 on the way; multipled
by 50 friends and 50 occasion types, this leads to a timeout).
Another solution was to find all occasions which happen at currentDate,
then move to the next date. Again, checking the next day would lead to
a timeout; instead, you should skip to the next date when any of the
occasions happens. Repeat until k occasions have been found.
Used as: Division Two - Level Three:
Used as: Division One - Level Two:
Value 1000 Submission Rate 15 / 818 (1.83%) Success Rate 6 / 15 (40.00%) High Score soul3434 for 588.90 points (28 mins 18 secs) Average Score 494.07 (for 6 correct submissions)
Value 500 Submission Rate 313 / 571 (54.82%) Success Rate 258 / 313 (82.43%) High Score bmerry for 435.00 points (11 mins 20 secs) Average Score 265.07 (for 258 correct submissions)
This problem was hated by some for its length, lack of algorithmic subtleties, and using music vocabulary, and liked by others for its originality, "real" examples, and music background. One had to understand the problem statement and implement it. There were no difficult algorithms there, but care had to be taken to make sure that all the sorting of notes and strings is done like requested by the problem statement (although if it was not, the example cases would probably catch it).
ForbiddenStrings
Used as: Division One - Level One:
Value 250 Submission Rate 553 / 571 (96.85%) Success Rate 474 / 553 (85.71%) High Score Im2Good for 248.03 points (2 mins 32 secs) Average Score 200.25 (for 474 correct submissions)
One of the fast ways of solving this problem was as follows.
Let's call a string repeating if it is not forbidden and
has the last two letters equal, and non-repeating if it is
not forbidden and has the last two letters different.
Let ri and ni
be the number of repeating and non-repeating
strings of length i, respectively.
We are asked for
ri+ni. Now, how to find the values of
ri and ni? Well, each of
ri repeating strings of length i
can be extended to length i+1 by adding the same letter again
(thus obtaining a repeating string again) or by adding one of the
two different letters (thus obtaining two non-repeating strings).
For non-repeating strings, when you add the three letters possible,
you get one repeating, one non-repeating, and one forbidden string.
All the strings of length i+1 are created in this way. This
gives us a recursive formula for ri and ni:
ri+1 = ri + ni,
ni+1 = 2ri + ni
.
See Petr's
solution
for an example of this approach.
Other solutions used similar approaches (for example, considering all
the possible endings of length 2 (or 3) separately, instead of categorizing them as repeating and
non-repeating).
Used as: Division One - Level Three:
Value 1000 Submission Rate 54 / 571 (9.46%) Success Rate 18 / 54 (33.33%) High Score Michael_Levin for 713.64 points (19 mins 44 secs) Average Score 531.36 (for 18 correct submissions)
The first thing to note in this problem is that what is important is not
the positions of both knights, but only their relative position
(i.e., (xw-xb, yw-yb) where
(xb,yb) is the location of
the black knight and (xw,yw) is the location of the white knight).
Knowing that, we can assume that the black knight stands still at (0,0),
and both players move the white knight (and win if they capture the black
knight).
The next thing to notice is that the problem has many symmetries. If you
know the winner for (x,y), then we have the same winner for
(x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), and (-y,-x). Thus,
we only have to solve the problem for one quarter of the plane (or even an
arc of 45 degrees).
Now, we can explain a simple O(n3) solution. We call a position losing
if the player who is to make move from this position has no winning strategy.
A position is losing if and only if it is impossible to move to a losing
position from it. Since only moves which reduce the Euclidean distance are
allowed, this definition is not circular. We can now write a O(n3) solution
which checks for each position whether it is losing, using either DP or
memoization (in the case of DP we have to make sure that we analyze all
squares in the order of Euclidean distance, or at least never analyze square
A after square B when there is a legal move from B to A).
This solution has time complexity of O(n3) and would timeout. So, how to
make it faster? There are several possible ways.
Noticing a rule.
Most coders who have successfully solved this problem have noticed that all losing squares appear at positions of form (d,0), (0,d), or (d,d) (and their counterparts in other quarters of the plane). Noticing this allows one to write an O(n2) or even an O(n) solution. Such a conjecture can be found by examining the results of Example #1, or by writing an O(n3) solution and producing a map of losing positions for, say, x, y > 100. I don't know any mathematical proof for this, but it is quite easy to write a program which checks that the solution generated using this rule is indeed correct for |x|, |y| ≤ 4000. For an example of this approach, see Michael_Levin's quick solution. It is the same as the simple O(n3) solution, except one line: if(x != y && x != 0 && y != 0) return true;.Remembering winning directions.
This approach was used by testers, as well as several coders during the match. Let's number the directions by numbers d from 0 to 7, and dx[d], dy[d] are relative changes of coordinates for each move.Now, when we find that a position is winning, we not only remember that it is winning, but also we remember the set of directions in which we can move in order to win (as a bit mask). Then, we can win from (x,y) by moving in direction d if and only if (x+dx[d], y+dy[d]) is a losing position, or if we can win from there by moving in direction d again (assuming that the later position is closer to (0,0) than (x,y)). This allows us to finding the answer for (x,y) by just checking the 8 (or less) squares to which we can get in one chess knight's move, leading to an O(n2) algorithm. This solution probably needs to be optimized by analyzing only squares satisfying 0 ≤ x ≤ y and obtaining the results for the other ones by flipping. A solution using this approach was submitted e.g. by blackmath.
Remembering losing positions on each line.
Let a half-knight-line be the sequence of squares si, for i ≥ 0, such that a knight can move from si to sj iff j is smaller i, by moving in direction d (which is constant for a half-knight-line). There is at most one losing position on each half-knight-line, otherwise the knight could move from one to another. So, if we analyze all the squares, sorted by Euclidean distance from (0,0), then to check whether we can win by moving in direction d, it is enough to check whether we already know a losing position on a half-knight-line in direction d going through our position. When we find a losing position, we remember for all half-knight-lines containing it that we have found a losing position on them. This also leads to an O(n2) solution (which is a bit faster, but probably harder to implement than the previous solution).
