Wednesday, September 12, 2007 Match summaryIn Division 1 the coders were faced with tricky problems, all of which required careful implementation and creative thinking rather than fast coding of wellknown algorithms. A harder than usual easy held up even some highrated 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 64bit integers. In the challenge phase the hunt for incorrect greedy approaches for the 1000pointer (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 250pointer, an unusual 600pointer and rather standard though clean implementation requiring 1000pointer. Newcomer Hamed won the round and bigheadghost and mrc88 finished second and third respectively. The ProblemsTournamentsAmbiguityNumberUsed as: Division Two  Level One:
The problem is completely straightforward: as the constraints allow O(n^{3}) 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: Used as: Division One  Level One:
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^{2} + y^{2} = r^{2}. 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_{1}(r^{2})  d_{3}(r^{2})). 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^{2} that leave remainder 1 upon division by 4, and the number of divisors of r^{2} 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^{2}. 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:
For details of implementation of the aforementioned solution consult Jan_Kuipers code. HittingPerfectTargetUsed as: Division Two  Level Three:
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:
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 crossproduct. See Hamed's solution for further inspection. ArithmeticProgressionsUsed as: Division One  Level Two:
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_{1} and a_{2}, 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_{1} and b_{2}, respectively. Then the aptitude of our proper arithmetic progression is (a_{1} + a_{2})/(b_{1} + b_{2}). Suppose, for the sake of contradiction, that our arithmetic progression contains at least 5 elements of numbers, i.e., a_{1} + a_{2} is at least 5. Then one of the subprogressions contains at least 3 elements and hence is proper. Without loss of generality say a_{1} >= a_{2}, so that a_{1} >= 3. Note that b_{1} and b_{2} 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_{1} and b_{2} 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 4tuples 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 64bit integers and crossmultiplication 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[n1]; 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:
First, apply the FloydWarshall 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 FloydWarshall may be adjusted accordingly. To obtain the minimal relabeling we will act according to the following algorithm:
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. 
