Saturday, March 22, 2008 Match summaryA healthy turnout of 1500 coders was faced with tough problemsets in both divisions. However, that was no obstacle for Petr to show impressive times on both medium and hard and to win Division 1 achieving the bestever rating of 3799 (and with such high rating revealing a bug in the rating distribution application, as well :)). In Division 1 coders were faced with a tricky easy which suggested a possibility of greedy approaches (many of which were incorrect), a somewhat involved geometrical medium and a notsostraightforward graph DP as a hard. The submissions of the medium and hard were scarcer than usual and only 11 coders submitted all 3 problems. However, only 8 of them survived the challenges and system tests with no losses. Another sixtysomething had two problems standing in the end. The Top 3 was comprised solely of Russian coders: Petr won the match with two best times and a comfortable lead, andrewzta was the second thanks to two successful challenges which helped him score higher than Jedi_Knight, who was the third. Division 2 coders found an Easy which required careful coding, a Medium which many of them found quite hard to figure out and a Hard which asked for some clever ideas. Noone managed to solve all three problems correctly. venkateshb seemed to win the match thanks to the best score on Hard, but his violation of the UCR took the victory away from his hands. bbi5291 was the author of the other 1000pointer which survived the system tests, bringing him the victory, while Alex_KPR and ahmed_aly rounded out the Top 3 with quick submissions of the first two problems and the help of challenges. The ProblemsMountainWalkUsed as: Division Two  Level One:
The problem was a simulation of a walk with some details not to be overlooked. The following code is self explanatory. public int cellsVisited(String[] map, int heightDifference) { int X = 0, Y = 0, n = map.length, m = map[0].length(), ans = 0; int dx[] = {1, 0, 1, 0}; int dy[] = {0, 1, 0, 1}; boolean[][] were = new boolean[50][50]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) were[i][j] = false; boolean go = true; while(go == true) { ans++; were[X][Y] = true; go = false; for(int k = 0; k < 4; k++) { int nx = X + dx[k], ny = Y + dy[k]; if(nx >= 0 && nx < n && ny >= 0 && ny < m && were[nx][ny] == false) { int diff = map[nx].charAt(ny)  map[X].charAt(Y); if(diff < 0) diff = diff; if(diff <= heightDifference) { X = nx; Y = ny; go = true; break; } } } } return ans; }RoughStrings Used as: Division Two  Level Two: Used as: Division One  Level One:
Counting the number of occurences of each letter in our original string we may reformulate the problem: Given k natural numbers a_{1}, a_{2}, ..., a_{k} you can modify them by repeating the following procedure no more than n times: pick a number a_{i} > 0 and replace it by a_{i}  1. Denote the resulting sequence of natural numbers (zeroes you throw out) b_{1}, b_{2}, ..., b_{m}. Find the minimal value of max b_{i}  min b_{i} you can obtain. There are quite a few different approaches to this problem varying in "greediness" involved. Perhaps the simplest one is not greedy at all: just iterate through all possible values M = max b_{i} and m = min b_{i} and then iterate through all a_{i}'s to see which ones have to be thrown out/reduced in order to make them fit in the interval [m, M]. For each such a_{i} one adds cost of its modification (which is a_{i} if a_{i} < m, a_{i}  M if a_{i} > M, and zero otherwise) and if the cumulative cost is less than or equal to n one checks if M  m is better than the current answer. Consult yuhch123's code to see this approach in practice. You may also want to see kalinov's solution for a neat implementation of a somewhat different idea. ProperDivisorsUsed as: Division Two  Level Three:
The problem was quite easy if one noticed what should be done. The constraints were too high for a straight forward 'iterate over every m in the interval and compute the number of its cool divisors' approach since in the most naive form this would be O(b*a^{1/2}) which is circa 10,000,000,000. The last example suggested that one wouldn't get away with plain brute force. Some coders decided to try their luck anyway, exposing their solutions for easy challenges. We solve using the usual gun  change the order of summation! Instead of summing over all m's in the interval we sum over all candidates to cool divisors k and count how many times a particular k is calculated in the sum d(a) + d(a + 1) + ... + d(a + b). But given k this is easy: it is equal to [(a + b)/k]  [(a  1)/k]  ([(a + b)/k^{n}]  [(a  1)/k^{n}]) for obvious reasons (here [x] is the integer part of x). If k is greater than a  1 then in this way we count it as a divisor of itself once which requires some adjustments (the last if in the code) since cool divisors must be less than numbers themselves. With these observations the resulting code is really short: public int P(int k, int n) { if(n == 1) return k; return k * P(k, n  1); } public int analyzeInterval(int a, int b, int n) { int sum = 0; if(a == 1) { a++; b; } for(int k = 2; k <= (a + b)/2; k++) sum += ((a + b)/k  (a  1)/k); for(int k = 2; P(k, n) <= a + b; k++) sum = ((a + b)/P(k, n)  (a  1)/P(k, n)); if(a <= (a + b)/2) sum = ((a + b)/2  a + 1); return sum; }CentersOfSymmetry Used as: Division One  Level Two:
Geometry problems are certainly one of the most 'beloved' among contestants. CenetrsOfSymmetry was no exception: a fair amount of coders that openned it soon gained some confidence and decided to check out the Hard straight away. No, but seriously, the problem was not that hard, especially if one has some prewritten libraries for handling the most common geometrical operations. And if not, well, this was a chance to create some. Note that if we have some intersection point of two given lines then after a symmetry with respect to some point it goes to an intersection point of two given lines (maybe to itself). Thus if there are intersection points then the only candidates to centers of symmetry that we are looking for are midpoints between pairs of (not necessarily distinct) intersection points of given lines. Moreover, since any intersection point behaves this way when treated with symmetry, while iterating through pairs of intersection points and checking their midpoints we may fix one of the points to optimize a bit. Calculating intersection points of pairs lines is a standard operation and checking if the symmetry of the given line is again a given line is easy: just check if the images under symmetry of the two given points on the line are collinear with some two points defining another (or possibly the same) line. Constraints were low enough so there was no need to worry about precise calculations of the coordinates of points and choosing any decent precision should have been enough. Another case is when there are no intersection points, i.e., all the given lines are parallel. Now the answer is 0 or 1. It is not hard to see that the answer is 1 in this case if and only if the lines are "symmetrically spaced", i.e., the sequence d_{1}, d_{2}, ..., d_{k} of distances between adjacent lines possesses the property d_{i} = d_{k  i + 1}. This may seem exotic to check but it is not really hard. One may calculate the intersection coordinates of the given lines with one of the coordinate axes and, after ordering the obtained numbers, check if the sequence of differences between adjacent numbers possesses the aforementioned property (Thales' theorem suggests us that this is equivalent, though it is trivial anyway). Another way to do it is to convert all the lines into "normal form" (i.e., find the defining linear polynomials P_{i}(x, y) = a_{i} * x + b_{i} * y + c_{i} of the lines) and check if the "shiftings" (i.e., P_{i}(0, 0) = c_{i}) are "symmetrically spaced". By the way, it is not hard to prove (exercise!) that the answer is always 1, 0 or 1, i.e., if there are at least two centers of symmetry then there are infinitely many of them. The idea of the proof is to show that if A and B are two distinct centers of symmetry then the image of A under symmetry centered at B is once again a center of symmetry. An interested reader is invited to work out the details. Though it is difficult to read codes for geometry problems one may wish to look at the submissions of ACRush here or Burunduk1 here. PseudoRandomKingdomUsed as: Division One  Level Three:
First of all, it is not hard to see that the map of the roads of the kingdom is a tree. It is also quite evident that the problem begs for a DP solution. Let's find one! Let's consider our original tree as a rooted tree with root 0. For each node x we wish to find an array dp[x][] such that the subtree rooted at x has probability dp[x][c] of having the most costly path from x to one of its leafs to have cost c, while not violating an assumption that the cost of any path in this subtree does not exceed savings. Indeed, this is what we want: if we know dp[0][] then the answer we must return is dp[0][0] + dp[0][1] + ... + dp[0][savings]. So how do we find such dp[x][]? Well, we iterate through all children y of x and compute dp[y][] first and then update the current version of dp[x][] which is initialised as {1, 0, ..., 0}. How does the updating work? Well, we know dp[x][] when we analyzed the first k children of x (initially k = 0) and we want to update to new_dp[x][] (latter we will assign dp[x][] := new_dp[x][]), where we also analyzed (k + 1)'st child y. How do we do that? Well, that's easy  just iterate through all costs b of an edge connecting x to y, and all costs a of the most costly path from y to one of its leaves, and all costs d of the cost of the most costly path connecting x to one of its leaves (where we analyzed only first k children) and add new_dp[x][max(d, b + a)] += p * dp[y][a] * dp[x][d] (new_dp[x][] is initialized as {0, 0, ..., 0}), where p = 1/(cost + 1) is the probability of an edge having cost b. Surely, this must work  we do not do anything fancy, plainly consider all possibilities of costs. But there are also some restrictions not to be overlooked. Namely, while iterating we skip those triples of (b, a, d) for which b + a + d > savings because we can not have paths of cost greater than savings in our subgraph rooted at x. A realquick implementation of this solution is Petr's code. 
