Match summary

In Division 1 the coders were faced with tricky problems, all of which required careful implementation and creative thinking rather than fast coding of well-known algorithms. A harder than usual easy held up even some high-rated contestants for longer than usual, while rather simple example tests for the hard allowed a vast amount of seemingly correct submissions. The medium had to be approached with caution in order to avoid overflow of 64-bit integers. In the challenge phase the hunt for incorrect greedy approaches for the 1000-pointer (or uncovered corner cases in the easy and medium) was fierce and many coders managed to earn a fair amount of additional points. When the dust settled after the system tests, EmK was on the top thanks to 5 successful challenges, with marek.cygan close behind and KOTEHOK rounding out the top 3.

Division 2 was marked with a straightforward 250-pointer, an unusual 600-pointer and rather standard though clean implementation requiring 1000-pointer. Newcomer Hamed won the round and bigheadghost and mrc88 finished second and third respectively.

The Problems

TournamentsAmbiguityNumber

Used as: Division Two - Level One:

Value 250

Submission Rate 558 / 704 (79.26%)

Success Rate 522 / 558 (93.55%)

High Score abdo88 for 247.89 points (2 mins 37 secs)

Average Score 197.01 (for 522 correct submissions)

The problem is completely straightforward: as the constraints allow O(n³) solution, one should iterate through all triples of players (a, b, c) and check if a defeated b, b defeated c, and c defeated a. If so, increment the cumulative answer and proceed. Java code implementing this approach follows:

int ans = 0;
int n = table.length;
for(int i = 0; i < n; i++)
   for(int j = 0; j < n; j++)
      for(int k = 0; k < n; k++)
         if(table[i].charAt(j) == '1' && table[j].charAt(k) == '1' 
        && table[k].charAt(i) == '1') ans++;
return ans;

PointsOnCircle

Used as: Division Two - Level Two:

Value 600

Submission Rate 128 / 704 (18.18%)

Success Rate 23 / 128 (17.97%)

High Score stef2n for 463.78 points (16 mins 26 secs)

Average Score 314.30 (for 23 correct submissions)

Used as: Division One - Level One:

Value 300

Submission Rate 329 / 621 (52.98%)

Success Rate 184 / 329 (55.93%)

High Score PaulJefferys for 284.81 points (6 mins 37 secs)

Average Score 189.26 (for 184 correct submissions)

As everybody knows from high school geometry the locus of points (x, y) lying on the circle with radius r centered at the origin is given by x² + y² = r². Finding the number of lattice points lying on this circle means finding the number of integer solutions to the above equation. As noted in the problem statement this number is given by 4*(d₁(r²) - d₃(r²)). There are many correct approaches you could take at this point and I will explain one of them.

If we find the number of divisors of r² that leave remainder 1 upon division by 4, and the number of divisors of r² that leave remainder 3 upon division by 4 we are done. Since r is too big we can not use the trivial O(r) algorithm to find all the divisors of r². However, the maximal number of divisors is not huge and we can still analyze all of them. One of the ways to accomplish this is the following:

Note that we don't care about even divisors so divide r by 2 while r is even.
Find all the divisors of r using standard O(r^1/2) algorithm and store them in an array v.
Note that a divisor of r² has a form a*b where both a and b are the divisors of r.
Motivated by the third step, iterate through all pairs of elements of v (a, b) and check if we already encountered a divisor a*b (we store all previously encountered divisors in a set lookup). If not, check its remainder upon division by 4, increment respective counter (either for remainder 1, or remainder 3), and insert this divisor in lookup.

Knowing the number of both types of divisors we return the desired answer immediately.

For details of implementation of the aforementioned solution consult Jan_Kuipers code.

HittingPerfectTarget

Used as: Division Two - Level Three:

Value 1000

Submission Rate 28 / 704 (3.98%)

Success Rate 16 / 28 (57.14%)

High Score bigheadghost for 788.02 points (15 mins 38 secs)

Average Score 562.43 (for 16 correct submissions)

The problem was not hard but, as is usual with geometry, one had to be very careful to cover all the corner cases. The solution goes in following steps:

As the vertices are given in any order it would be comfortable to have them in, say, counter-clockwise order. So apply to both given polygons steps 2 and 3.
Sort the vertices in the order of increasing value of x-coordinate (in case of ties in the order of increasing value of y-coordinate).
Fix the first vertex and sort the remaining vertices in the order of increasing value of angle (measured clockwise in this case, but this is not really important) between the ray (x[0], y[0]) ---> (x[i], y[i]) and the vertical down pointing ray with origin in (x[0], y[0]). We thus obtain an array of vertices in which two consecutive vertices are connected by an edge of our polygon and vertices are sorted in counter-clockwise order.
Iterate through all pairs of points (x, y) lying in the big square to check if in hitting this particular point one makes a lucky shot. To check this one has to check if the point lies both within the first and the second convex polygon. To check this for both polygons apply steps 5-6.
Check if a point (x, y) lies on the boundary of a polygon (or coincides with a vertex). To do this iterate through all edges and check if (x, y) lies on a current edge.
Consider a horizontal ray originating in (x, y) and going rightwards. Count how many times this ray intersects the boundary of the polygon. To do this once again iterate through all the edges and check if the ray intersects current edge. If the ray goes through a vertex of the polygon this intersection should be counted once if the preceding and succeeding vertices are on different sides of the ray, and twice otherwise.
The point (x, y) lies inside the polygon if the ray intersects the boundary of the polygon an odd number of times, and outside otherwise.
Knowing the total number of points that you can hit to make a lucky shot n return n/(201*201) (note that 201*201 is the total number of lattice points within the big square).

For more detailed instructions on the basic geometric computations used in this solution check out the geometry tutorial.

Note than it this problem our polygons are convex so to check if a point is inside one you can check if the point lies in some sense on the same side of all the sides of the polygon. This can be implemented exploiting the properties of the cross-product. See Hamed's solution for further inspection.

ArithmeticProgressions

Used as: Division One - Level Two:

Value 500

Submission Rate 228 / 621 (36.71%)

Success Rate 108 / 228 (47.37%)

High Score andrewzta for 430.78 points (11 mins 47 secs)

Average Score 300.58 (for 108 correct submissions)

We will prove the following lemma:

There exists a proper arithmetic progression having maximal possible aptitude and containing no more than 4 elements of numbers.

Indeed, from all possible proper arithmetic progressions that have maximal aptitude take the one that has least elements from numbers. Note that this progression is comprised of two subprogressions ("odd and even") both having the same difference 2*d (d is the difference of the original progression). Denote the number of elements of numbers in these subprogressions by a₁ and a₂, and the total number of elements (number of elements of subprogressions that lie in range [m = min(numbers[i]); M = max(numbers[i])]) by b₁ and b₂, respectively. Then the aptitude of our proper arithmetic progression is (a₁ + a₂)/(b₁ + b₂). Suppose, for the sake of contradiction, that our arithmetic progression contains at least 5 elements of numbers, i.e., a₁ + a₂ is at least 5. Then one of the subprogressions contains at least 3 elements and hence is proper. Without loss of generality say a₁ >= a₂, so that a₁ >= 3. Note that b₁ and b₂ differ by at most 1 by construction of subprogressions. If they were equal then the aptitude of the progression would be the arithmetic mean of the aptitudes of the subprogressions and hence the first subprogression (having at least as many elements of numbers as the second one) would be proper, have the same aptitude as the original progression (because its aptitude was maximal possible) and have less elements from numbers. So we would obtain a contradiction to the choice of the original progression. The case when b₁ and b₂ differ by 1 is left to the reader to convince oneself that still the first subprogression has aptitude at least that of the original progression and less elements from numbers than the original progression.

Having established the aforementioned lemma we proceed by iterating through all triples of elements of numbers and for each triple a < b < c finding g = gcd(c - b, b - a), the difference of the minimal arithmetic progression containing a, b and c. Knowing a, b, c and g we may check how many elements of this progression lie in range [m; M] in constant time. Knowing this number N we check if 3/N is a better aptitude than currently stored one. If so, we update the stored maximal aptitude. Afterwards we iterate through all 4-tuples a < b < c < d and analogously check if 4/N is better than currently stored aptitude. We may precompute and store the values of gcd in an array to save time. Note that, at any point of the solution, the numerator of the fraction representing the maximal aptitude does not exceed 4 and thus we would not overflow using 64-bit integers and cross-multiplication for comparison.

Java code implementing the above described approach follows.

//numbers is a sorted array of given numbers
//gcd is a fuction for the greatest common divisor of two longs
long[][][] G = new long[n][n][n];
for(int i = 0; i < n; i++) 
   for(int j = i + 1; j < n; j++) 
      for(int k = j + 1; k < n; k++) 
         G[i][j][k] = gcd(numbers[k] - numbers[j], numbers[j] - numbers[i]);
long[] best = new long[2];
best[0] = 0;
best[1] = 1;
long m = numbers[0], M = numbers[n-1];
for(int i = 0; i < n; i++)
   for(int j = i+1; j < n; j++)
      for(int k = j + 1; k < n; k++) {
         long g = G[i][j][k];
         long a1 = (numbers[k] - m)/g;
         long a2 = (M - numbers[k])/g;
         long A = a1 + a2 + 1;
         long v = 3;
         if(A%3==0) {
            A /= 3;
            v = 1;
         }
         if(best[1] * v > best[0] * A) {
            best[0] = v;
            best[1] = A;
         }
      }
for(int i = 0; i < n - 3; i++) 
   for(int j = i + 1; j < n - 2; j++) 
      for(int k = j + 1; k < n - 1; k++) 
         for(int r = k + 1; r < n; r++) {
            long g1 = G[i][j][k];
            long g = gcd(g1, numbers[r] - numbers[k]);
            long a1 = (numbers[r] - m)/g;
            long a2 = (M - numbers[r])/g;
            long A = a1 + a2 + 1;
            long v = 4;
            if(A%2==0) {
               v/=2;
               A/=2;
            }
            if(A%2==0) {
               v/=2;
               A/=2;
            }
            if(best[1] * v > best[0] * A) {
               best[0] = v;
               best[1] = A;
            }
        }
String[] B = new String[2];
B[0] = String.valueOf(best[0]);
B[1] = String.valueOf(best[1]);
return B;

RelabelingOfGraph

Used as: Division One - Level Three:

Value 1000

Submission Rate 295 / 621 (47.50%)

Success Rate 41 / 295 (13.90%)

High Score Krzysan for 962.05 points (5 mins 41 secs)

Average Score 666.61 (for 41 correct submissions)

First, apply the Floyd-Warshall algorithm to our graph to find shortest paths between pairs of vertices. If in the resulting graph there are edges from some vertex to itself then in the original graph there was a cycle -- in this case, we clearly cannot assign a new label in the desired fashion. Otherwise our original graph is a topologicaly ordered set and the relabeling is feasible. We will not be interested in numerical values of computed paths between pairs of vertices but will want to know whether in the resulting graph there is an edge (i, j), i.e., whether i <_T j (henceforth notation i <_T j will mean that i and j are comparable and i is less than j, i.e., in our original graph there is a path from i to j). Bearing this in mind Floyd-Warshall may be adjusted accordingly.

To obtain the minimal relabeling we will act according to the following algorithm:

Analyse vertices v of our graph one by one in the order of increasing label in the original graph and for each vertex that has not yet been processed apply the following steps.
For a vertex v count for how many vertices we have i <_T v. Call this number m
Assign to v m-th (0-based indexing) yet not used label L(v).
Iterate through all the vertices i <_T v in the order of increasing label in the original graph and if some vertex i has not yet been processed process it right now (i.e., apply to it steps 2-4).

Following this algorithm we would clearly result in the lexicographically first relabeling, the only remaining problem is to show that assigning new labels in this way we would never violate our rule that for every edge v1 ---> v2 the label of v1 is less or equal than the label of v2. Suppose the contrary, and pick v the first vetex for which we violate this rule. Let A be the set of all vertices u for which u <_T v. Let B be the set of all vertices u for which v <_T u. Let C be the set of all the other vertices. By our assumption assigning to v m-th yet available value we violate our restriction. Note that this is not the case with the vertices from C, since clearly there are neither incoming, nor outgoing edges connecting v with vertices from C. Suppose our condition failed for an edge a ---> v for a in A. But this means that a has already an assigned value L(a) > L(v). But at the time when L(a) was to be decided it equaled m_a-th yet available label. m_a was the number of vertices i <_T a, and clearly all those vertices were counted in when counting m (because of definition of A and obvious transitivity of the relation <_T). So m_a < m (strictly less because we have to count in at least one additional vertex, namely a, when counting m ). But all the labels that were available when choosing L(v) were also available when choosing L(a) so this combined with m_a < m gives us a contradiction and we must have L(a) < L(v), as desired. We can not have L(v) > L(b) for b in B and this follows from the order in which we process the vertices. This completes the proof.

For an implementation of a somewhat identical approach see FloppyCat's solution.

The problem is tricky and that is clearly reflected in statistics. A multitude of wrong greedy approaches led to an eventful challenge phase allowing CO2 and Ying to write themselves in the most successful challengers in a single SRM statistics.

By Xixas
TopCoder Member