Tuesday, December 11, 2007 Match summaryDivision 1 was presented with slightly unusual problem set, with technical 250, tricky 500 and relatively easy 1000 problems. After challenge phase, Petr was taking lead with impressively quick submissions on all problems and +175 points on challenge. But system tests have find flaw in his medium, which allowed Eryx to win his 10th SRM and became target again. He was third after 75 minutes of match, but intensive challenge phase (7 successful and 6 unsuccessful challenges, +200) gave him top position. Second was Egor, and inazz took third place. This SRM is also remarkable because of a new record – after it there are 12 active targets in TC rating, more than ever. Division 2 problem set was uniformly harder than usual. Only 49 coders correctly solved 500, and only 3 solved 1000 problem. Newcomers araste and mhwu solved all problems and took first and second places. pszemsza_ took third with relatively quick submissions on first two problems. 1000 problem was also solved by newcomer YaoJinyu, but with incorrect 250 and 500 problems it brought him only fifth place. The ProblemsContiguousSubsequencesUsed as: Division Two  Level One:
Because of small constraints, the problem was pretty straightforward. To solve it you should process all contiguous subsequences of length K and more, calculate their average values and lengths and select the best one, as pointed out in the statement. The only thing we need to care about is precision. We can use epsilon, when comparing floatingpoint numbers, or even calculate average values as common fractions to avoid floatingpoint arithmetic at all. The following code demonstrates such approach. public int[] findMaxAverage(int[] a, int K){ int bestp = 1, bestq = 1; int ret[] = new int[2]; int acc[] = new int[a.length+1]; for(int i = 0; i < a.length; ++i) acc[i+1] = acc[i] + a[i]; for(int i = 0; i < a.length; ++i){ for(int j = i; j < a.length; ++j){ if(j  i + 1 < K) continue; if(bestq * (acc[j+1]  acc[i]) > bestp*(ji+1)){ bestp = acc[j+1]  acc[i]; bestq = ji+1; ret[0] = i; ret[1] = j; } else if(bestq * (acc[j+1]  acc[i]) == bestp*(ji+1)){ if(ji > ret[1]ret[0]){ ret[0] = i; ret[1] = j; } } } } return ret; }CollectingRiders Used as: Division Two  Level Two: Used as: Division One  Level One:
First, we can notice, that distance in Krider moves between two cells can be easily expressed in terms of knight (1rider) moves: distance(K, from, to) = ceil(distance(1, from, to)/K). This leads to the following solution: first, calculate distance in knight moves between every pair of cells; second, search over all possible "collection points", calculate total time for each of them and select the optimal point to collect all riders. We can implement BFS, FloydWarshall or even floodfill for the first part of solution, due to small constraints. You can see some clear solutions demonstrating different approaches here and here. CharmingTicketsEasyUsed as: Division Two  Level Three:
This problem is the easy version of Division 1 Hard, so it also can be solved in optimal O(K^{2}) way. Here we describe nonoptimal, but possible O(K^{3}) solution, which will pass because of small constraints. Let's denote S1 and S2 sets of numbers containing only good digits and satisfying first or second conditions, correspondingly. By inclusionexclusion principle, the answer is S1+S2S1 ∩ S2. We find out these values, using the following DP: calculate N(k,i,j) the amount of kdigit numbers composed only from good digits, with sum of digits equal to i, and difference between digits in odd and even positions equal to j. Thus, we can find S1 (and S2) as sum[N(K,i,j1)*N(K,i,j2) over all i,j1,j2], and S1 ∩ S2 as sum[N(K,i,j)*N(K,i,j) over all i,j]. It seems that nobody from Division 2 have correctly implemented this approach during the competition. PointsOnACircleUsed as: Division One  Level Two:
First thing we can notice is small number of points and integer values of angles. So we can try all possible rotation angles (no more than 360), and solve corresponding subproblem for each. Imagine that rotation is fixed. Some point will overlap other points after rotation. Imagine graph, whose vertices are points on original circle, and arcs goes from first point to second one if and only if the first point overlaps the second after rotation. Our task is to color two different subsets of vertices in red and blue in such way that each blue vertex will have outgoing edge to some red point, each red vertex will have incoming edge from some blue point, and the total size of subsets is maximized. This task seems to be hard in general case, but it's easy to notice that in our problem graph will contain only nonintersecting chains and/or cycles. So, the answer is sum of 2*floor(V(C)/2), where V(C) is the number of vertices in connected component C of corresponding (here undirected) graph, over all connected components. There are different ways to calculate this, see Eryx solution for an example of fastimplementation. CharmingTicketsUsed as: Division One  Level Three:
As it was mentioned in CharmingTicketsEasy analysis, our task can be solved by finding S1 and S1 ∩ S2. First of all, we can find S1 by the following standard DP: calculate numbers N(k,i)  amount of kdigit numbers composed only from good digits, with sum of digits equal to i. Then S1 can be found as sum[N(K,i)*N(K,i) over all i]. Denote this function from K as Lucky(K), it will come into play further. Let's find S1 ∩ S2. Write out necessary and sufficient condition on digits for number from S1 ∩ S2: x[1] + x[2] + ... + x[k]  x[k+1]  x[k+2]  ...  x[2*k] = 0 (1) x[1]  x[2] + ...  x[k] + x[k+1]  x[k+2] + ...  x[2*k] = 0 (2) x[i] is good digit for all iThis system is equivalent to x[1] + x[3] + ... + x[k1]  x[k+2]  ...  x[2*k] = 0 (1*) x[2] + x[4] + ... + x[k]  x[k+1]  ...  x[2*k1] = 0 (2*) x[i] is good digit for all iHere (1*) is the sum of (1) and (2), divided by 2, and (2*) is the difference of (1) and (2), also divided by 2. First equation will have 2*ceil(K/2) variables, second – 2*floor(K/2) variables, and each variable is present in only one equation. Solutions of (1*) and (2*) are independent. Thus the number of solutions of this system equals to (number of solutions of (1*))*(number of solutions of (2*)). It's easy to see, that both equations are like the first condition from the statement, so it will be Lucky(ceil(K/2))*Lucky(floor(K/2)). The final answer will be 2*Lucky(K) – Lucky(ceil(K/2))*Lucky(floor(K/2)) (of course, all calculations are made modulo 999983). See Petr's solution demonstrating this approach. 
