JOIN
 Match Editorial
SRM 382
Tuesday, December 11, 2007

## Match summary

Division 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 Problems

ContiguousSubsequences
Used as: Division Two - Level One:
 Value 250 Submission Rate 431 / 537 (80.26%) Success Rate 267 / 431 (61.95%) High Score itsmemyself for 249.19 points (1 mins 37 secs) Average Score 161.88 (for 267 correct submissions)

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 floating-point numbers, or even calculate average values as common fractions to avoid floating-point 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*(j-i+1)){
bestp = acc[j+1] - acc[i];
bestq = j-i+1;
ret[0] = i;
ret[1] = j;
}
else if(bestq * (acc[j+1] - acc[i]) == bestp*(j-i+1)){
if(j-i > ret[1]-ret[0]){
ret[0] = i;
ret[1] = j;
}
}
}
}
return ret;
}
```
CollectingRiders
Used as: Division Two - Level Two:
 Value 500 Submission Rate 86 / 537 (16.01%) Success Rate 49 / 86 (56.98%) High Score araste for 374.44 points (17 mins 44 secs) Average Score 250.14 (for 49 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 358 / 438 (81.74%) Success Rate 258 / 358 (72.07%) High Score Triple_M for 234.37 points (7 mins 26 secs) Average Score 161.07 (for 258 correct submissions)

First, we can notice, that distance in K-rider moves between two cells can be easily expressed in terms of knight (1-rider) 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, Floyd-Warshall or even flood-fill for the first part of solution, due to small constraints. You can see some clear solutions demonstrating different approaches here and here.

CharmingTicketsEasy
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 15 / 537 (2.79%) Success Rate 3 / 15 (20.00%) High Score mhwu for 573.25 points (29 mins 38 secs) Average Score 562.83 (for 3 correct submissions)

This problem is the easy version of Division 1 Hard, so it also can be solved in optimal O(K2) way. Here we describe non-optimal, but possible O(K3) 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 inclusion-exclusion principle, the answer is |S1|+|S2|-|S1 ∩ S2|. We find out these values, using the following DP: calculate N(k,i,j) -the amount of k-digit 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.

PointsOnACircle
Used as: Division One - Level Two:
 Value 500 Submission Rate 270 / 438 (61.64%) Success Rate 65 / 270 (24.07%) High Score Eryx for 471.31 points (7 mins 5 secs) Average Score 301.70 (for 65 correct submissions)

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 non-intersecting 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.

CharmingTickets
Used as: Division One - Level Three:
 Value 1000 Submission Rate 44 / 438 (10.05%) Success Rate 32 / 44 (72.73%) High Score Egor for 837.58 points (13 mins 2 secs) Average Score 590.41 (for 32 correct submissions)

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 k-digit 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 i
```
This system is equivalent to
```x[1] + x[3] + ... + x[k-1] - x[k+2] - ... - x[2*k]   = 0  (1*)
x[2] + x[4] + ... + x[k]   - x[k+1] - ... - x[2*k-1] = 0  (2*)
x[i] is good digit for all i
```
Here (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.

By dkorduban
TopCoder Member