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.
The ProblemsTrueSpaceUsed as: Division Two  Level One:
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. BirthdayRemindersUsed as: Division Two  Level Two:
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).
Used as: Division Two  Level Three: Used as: Division One  Level Two:
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). ForbiddenStringsUsed as: Division One  Level One:
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 nonrepeating if it is
not forbidden and has the last two letters different.
Let r_{i} and n_{i}
be the number of repeating and nonrepeating
strings of length i, respectively.
We are asked for
r_{i}+n_{i}. Now, how to find the values of
r_{i} and n_{i}? Well, each of
r_{i} 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 nonrepeating strings).
For nonrepeating strings, when you add the three letters possible,
you get one repeating, one nonrepeating, and one forbidden string.
All the strings of length i+1 are created in this way. This
gives us a recursive formula for r_{i} and n_{i}:
r_{i+1} = r_{i} + n_{i},
n_{i+1} = 2r_{i} + n_{i}
.
See Petr's
solution
for an example of this approach.
Used as: Division One  Level Three:
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., (x_{w}x_{b}, y_{w}y_{b}) where
(x_{b},y_{b}) is the location of
the black knight and (x_{w},y_{w}) 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). 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(n^{2}) or even an O(n) solution. Such a conjecture can be found by examining the results of Example #1, or by writing an O(n^{3}) 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(n^{3}) 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(n^{2}) 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 halfknightline be the sequence of squares s_{i}, for i ≥ 0, such that a knight can move from s_{i} to s_{j} iff j is smaller i, by moving in direction d (which is constant for a halfknightline). There is at most one losing position on each halfknightline, 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 halfknightline in direction d going through our position. When we find a losing position, we remember for all halfknightlines containing it that we have found a losing position on them. This also leads to an O(n^{2}) solution (which is a bit faster, but probably harder to implement than the previous solution). 
