Match Editorial

Match summary

The last SRM before TCO08 onsite finals became the most crowded TopCoder SRM ever as the limit on the number of participants was increased to 1750.

To finish in top3 in Division 1 it was enough to solve all three problems correctly, which was done by Petr, ACRush and Eryx, who finished first, second and third respectively. Because of many corner cases in the medium problem challenge phase was very fruitful, affecting final positions of many coders a lot.

In Division 2 nobody managed to solve the 1000-pointer correctly, so the top places were distributed between those, who were really fast on easy and medium and managed to make some successful challenges. This resulted in Al.Cash, taking the first place, followed by Duc, Landrew and a newcomer TheBlackParade.

The Problems

Value	250
Submission Rate	739 / 833 (88.72%)
Success Rate	266 / 739 (35.99%)
High Score	KnightOfTheSun for 249.01 points (1 mins 47 secs)
Average Score	197.21 (for 266 correct submissions)

First approach

Under the given constraints it was possible to iterate through all lattice points that lie in a rectangle with corners (min(x1,x2),min(y1,y2)) and (max(x1,x2),max(y1,y2)) and check whether they lie on the given segment or not. This check can be done using cross product of vectors (you can see this tutorial by lbackstrom for more information about geometrical basics).

See this solution by Sainell for implementation of this approach.

Second approach

The second approach uses the following notion about lattice points, lying on the segment: neighbouring lattice points lie on the same distance from each other. Now consider the greatest common divisor of max(x1,x2) - min(x1,x2) and max(y1,y2) - min(y1,y2). Then there can be at most this value minus one lattice point, lying on the segment as described above.

This approach was used by KnightOfTheSun to achieve high score on this problem.

Value	500
Submission Rate	260 / 833 (31.21%)
Success Rate	176 / 260 (67.69%)
High Score	dlwjdans for 484.98 points (5 mins 1 secs)
Average Score	286.72 (for 176 correct submissions)

Value	250
Submission Rate	587 / 650 (90.31%)
Success Rate	549 / 587 (93.53%)
High Score	ACRush for 246.54 points (3 mins 22 secs)
Average Score	187.12 (for 549 correct submissions)

First approach

This problem could be solved by simple dynamic programming. Let's construct FIELD diagrams row by row, starting from the first one (it will have index zero). Let dp[i][j] be the number of possible ways to extend a FIELD diagram that has all rows up to i-th already constructed and has the length of the last constructed row (the row number i - 1) equal to j. Then dp[fieldOrder][ANY_VALUE] should be taken equal to 1 (we have constructed a valid diagram) and dp[i][j] can be calculated as follows:

long[][] dp = new long[fieldOrder + 1][fieldOrder + 1];
for (int k = 0; k <= fieldOrder; k++) {
    dp[fieldOrder][k] = 1;
}
for (int i = fieldOrder - 1; i >= 0; i--) {
    for (int j = 0; j <= fieldOrder; j++) {
        dp[i][j] = 0;
        for (int k = 0; k <= Math.min(j, fieldOrder - i); k++) {
            dp[i][j] += dp[i + 1][k];
        }
    }
}    

This approach was used by ACRush to achieve high score on this problem.

Second approach

The second approach was to notice that the number of FIELD diagrams of order n is equal to C_n+1 - 1, where C_n is the n-th Catalan number. See description of monotonic paths (analogs of FIELD diagrams) in the article for further explanation of why this formula works.

Value	1000
Submission Rate	55 / 833 (6.60%)
Success Rate	0 / 55 (0.00%)
High Score	No correct submissions
Average Score	No correct submissions

The shortest message appears somewhere in the given text, let it length be PeriodLen. Taking the first PeriodLen letters of the text as the message will give us the same text, so we can assume that the shortest message appears in the beginning of the text.

The hardest thing is to find this shortest message in linear time. Here KMP algorithm will help us a lot (see description of KMP algorithm in this tutorial). Let's construct prefix function (which is called failure function in the tutorial) for the text and look its value on the last element of the text (let us call this value PrefLen, it gives us the length of the longest suffix of the text, which is at the same time its prefix). Now it is obvious that PrefLen is equal to TextLen - PeriodLen. This gives us solution shown below:

int textLength = text.length();
int[] prefixFunction = new int[textLength];
prefixFunction[0] = 0;
int cur = 0;
for (int i = 1; i < textLength; i++) {
    while (cur > 0 && text.charAt(cur) != text.charAt(i)) {
        cur = prefixFunction[cur - 1];
    }
    if (text.charAt(cur) == text.charAt(i)) {
        cur++;
    }
    prefixFunction[i] = cur;
}
return textLength - prefixFunction[textLength - 1];

Value	550
Submission Rate	244 / 650 (37.54%)
Success Rate	72 / 244 (29.51%)
High Score	gozman for 454.77 points (13 mins 36 secs)
Average Score	275.94 (for 72 correct submissions)

First approach

The first approach is to find points of intersection of a cylinder x^2 + y^2 = 1 with the given line (using equations x = vx * t + x0 and y = vy * t + y0), solving quadratic equation for t, and then check whether solutions of this equation really lie on the given spiral. A case when vx and vy are both equal to zero should be considered separately.

See very clear implementation of this approach in gozman's solution here.

Second approach

The second approach was to believe that intersections can happen only in points where z is half-integer. It turned out that under given constraints this was true. See discussion in forums here for some ideas about why this can be true for arbitrarily large input numbers.

I found four coders, who used this approach during the SRM: LayCurse, hhanger, crazyb0y and gerben.

Value	950
Submission Rate	11 / 650 (1.69%)
Success Rate	5 / 11 (45.45%)
High Score	Petr for 539.64 points (30 mins 6 secs)
Average Score	430.14 (for 5 correct submissions)

First of all let's notice that we can consider only N-cool segments that contain exactly N lattice points, covered by the polygon, and also have their endpoints in lattice points (let's call these segments N-really-cool segments) as long as all longer N-cool segments contain these segments as their part. So a point is N-cool if and only if it is an endpoint of some N-really-cool segment. This can be checked easily, because two points are endpoints of some N-really-cool segment if and only if their coordinates are equal modulo N - 1 (i.e. x1 mod (N - 1) = x2 mod (N - 1) and y1 mod (N - 1) = y2 mod (N - 1)).

Now if we find all lattice points, covered by the polygon, we are done, as we can easily check the property above. Because of the facts that the vertices of the polygon are given in random order, there can be duplicate points and three points, lying on the same line, it was really useful to construct convex hull of the given points first, rearranging them in some more useful order. Here comes the algorithm of finding a convex hull, constructing it as a union of the upper and the lower hull (see explanation of this algorithm in this tutoial by bmerry). Now points, covered by the polygon, can be found in a single line sweep pass, which studies every possible x coordinate, finding points with maximal and minimal y on this line and writing down all intermediate points.

You can see my implementation of this approach in the practice room.

Excercise

Prove that if there are more than N^2 lattice points, covered by the polygon, then there exists (N + 1)-cool segment.