JOIN
 Match Editorial
SRM 401
Tuesday, May 6, 2008

## 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

Used as: Division Two - Level One:
 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.

FIELDDiagrams
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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];
}
}
}
``````
Now the answer for the problem will be dp[0][fieldOrder] - 1 as we have counted a digram, containing no boxes.

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 Cn+1 - 1, where Cn 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.

RunningLetters
Used as: Division Two - Level Three:
 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];
``````

ParticleCollision
Used as: Division One - Level Two:
 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.

NCool
Used as: Division One - Level Three:
 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.

By griffon
TopCoder Member