Round Overview
Discuss this match
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_Levinwas 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.
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
Problem Details
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:
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) |
Used as: Division One - Level Two:
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
Problem Details
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.
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;
.
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.
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).