Sorry for late.

This is the editorial of Codeforces Round #219. Div2 A, Div2 B, Div1 C are made by kagamiz, and other problems are made by me.

373A - Collecting Beats is Fun /\_/\

First, you need to count the occurence of each number (1 through 9). If none of them are greater than 2 * k, Cucumber boy is able to press the panels in perfect timing.

Complexity is O(1).

My solution : http://ideone.com/CwQtBv

373B - Making Sequences is Fun /\_/\

Naive simulation (subtracting S(i) * k from w while w >= 0) won't finish in 2 seconds.

At first, these two facts will make it easier to solve the problem : 1. k doesn't matter for solving this problem, so you can simply divide w with k at the first point. 2. S(10^x) + S(10^x + 1) + ... + S(10^(x+1) — 1) = 9 * x * 10^x .

There are many ways to solve this problem, and I'll show you 2 ways.

1. Binary Search Let's define f(n) as \sum_{k=1}^{n} S(n). This problem can be solved by finding largest x that satisfies f(x) — f(m — 1) <= w. If x satisfies the given inequation, also x — 1, x — 2, ... satisfies inequation since S(x) is always positive. So it can be solved by using binary search. By using fact2, you can quickly simulate the value of f(n). The answer can be rather large, so be careful not to cause overflow by too large upper bound. Overall complexity is O(log |upper_bound — lower_bound|).

2. Cumulative Sums Let's think to speed up naive solutions that I've written at first. If you use fact 2, the number of simulation will reduce from O(|answer|) to O(1). Also, simulation will be much easier if you add S(1) + ... + S(m-1) to w. Please see my source code for further detail.

DEGwer's solution (Solution 1) : http://ideone.com/cU78oe My solution(Solution 2) : http://ideone.com/NjxlwP

373C - Counting Kangaroos is Fun / 372A - Counting Kangaroos is Fun /\_/\

Because of the number of holding-held relations is at most , We can assume that first half of kangaroos do not hold any kangaroos, and last half of kangaroos are not held by any kangaroos. So we can split kangaroos in two set, such that first set contains the kangaroos whose size is in smaller half and second set contains the kangaroos whose size is in larger half, and use easy greedy algorithm. The time conplexity is O(N log N) for sorting and O(N) for greedy, so the time conplexity is O(N log N).

my solution: http://ideone.com/w8ch4w

373D - Counting Rectangles is Fun / 372B - Counting Rectangles is Fun /\_/\

We can precalculate all rectangles, in O(N^2M^2) with using consecutive sums for 2D. And then we use 4D consecutive sums, we can answer the queries. The time conplexity is O(N^2M^2+Q).

my solution: http://ideone.com/QOjwse

373E - Watching Fireworks is Fun / 372C - Watching Fireworks is Fun /\_/\

I think most of the participants came up with simple DP algorithm : dp[i][j] := the maximum happiness value that you can gain when you're on poisition j at i th launching. Each value in table can be calculated by this formula : dp[i][j] = max[k =  - t * d..t * d](dp[i — 1][j + k] + b[i] — |a[i] — j|) where t = t[i] — t[i — 1].

If you look up for all k, since the table's size is O(mn), the overall complexity will be O(mn^2), and its too slow to solve the problem. Now, We're going to make this algorithm faster. Since the second term in the DP formula doesn't depend on k, you have to find maximum value of dp[i — 1][j + k] faster. Using segment tree or sparse table can fasten finding from O(n) to O(log n), but the overall complexity is still O(mn log n), and the solution will get time limit exceeded.

Intended solution uses sliding window maximum (see this page http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html) for some information), since the interval [j — t * d, j + t * d] is independent for all the fireworks. It can be implemented by simple array or deque. This will speed up to calculate formula, and overall complexity will be O(mn).

kcm1700 has submitted faster solution than our intended one during contest! It's complexity is O(m^2). Please read his comment (http://mirror.codeforces.com/blog/entry/9907#comment-153963) for further information.

My solution : http://ideone.com/Unrfaa kcm1700's solution : http://mirror.codeforces.com/contest/372/submission/5431649

372D - Choosing Subtree is Fun /\_/\

We can use two pointers, which treat the interval of the consecutive numbers of node on tree. All we have to do is answer the query which requires the minimal number of size of subtree which contains all the vertices in the set, after the "add vertices to the set" and "delete verticesto the set" operations. We can calculate the distance between two nodes with LCA algorithm, then when we order the nodes by dfs order, we can answer the "add vertice" query that adds the vertice which is numbered s in dfs order, and assume that previous numbered vertices in dfs order in the set is t, and next is u, we can get rid of the "add" query that $(current size of subtree)+distance(s,t)+distance(t,u)-distance(s,u), and "delete" so on. The time conplexity of LCA algorithm is O(log N), so we can solve this problem in O(Nlog N).

There is another solution which uses heavy-light decomposition and segment tree. This solution is O(Nlog^2 N), which also pass.

my solution (heavy-light decomposition): http://ideone.com/XfJPsS

372E - Drawing Circles is Fun /\_/\

All circles we must consider pass through O, so we can consider the operation inversion. At this operation, the point (x, y) will be . From now, we think the plane as the plane after inversed. "The circumcircles of triangles OAB and OCD have a single common point, and the circumcircle of triangles OAD and OBC have a single common point" can be said, after the inversion, ABCD is parallelogram. And we can say it "the diagonal AC and BD have a common midpoint and the inclination of AC and BD are different". So all we have to do is make the list of the midpoints and inclination of all pairs of points and the line passes through them, and sort this array, and do some multiplication. It can be solved in O(N^2 log N).

my solution: http://ideone.com/x3Xrqe