Tuesday, May 6, 2008 Match summaryThe 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 1000pointer 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 ProblemsDreamingAboutCarrotsUsed as: Division Two  Level One:
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. FIELDDiagramsUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 ith 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:
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 C_{n+1}  1, where C_{n} is the nth Catalan number. See description of monotonic paths (analogs of FIELD diagrams) in the article for further explanation of why this formula works. RunningLettersUsed as: Division Two  Level Three:
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:
ParticleCollision
Used as: Division One  Level Two:
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 halfinteger. 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. NCoolUsed as: Division One  Level Three:
First of all let's notice that we can consider only Ncool segments that contain exactly N lattice points, covered by the polygon, and also have their endpoints in lattice points (let's call these segments Nreallycool segments) as long as all longer Ncool segments contain these segments as their part. So a point is Ncool if and only if it is an endpoint of some Nreallycool segment. This can be checked easily, because two points are endpoints of some Nreallycool 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. 
