Sorry for late.

This is the editorial of Codeforces Round #219. Div2 A, Div2 B, Div1 C are made by m.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.

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|).

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://codeforces.com/blog/entry/9907#comment-153963) for further information.

My solution : http://ideone.com/Unrfaa kcm1700's solution : http://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

Why does it say "You are not allowed to view the requested page" when trying to see some solutions...

I couldn't understand what exactly Div2C explanation meant so I wanted to check the solutions...

Not sure if this is because I myself haven't solved it or what?

Sorry, we've fixed the solution's link. Please check it now.

Thanks...

For Div2 D what does cumulative sums for 2D and 4D mean???

Hi, Thanks for the Editorial!

A questions about problem Div1.C: I assumed that the dp array is always like a mountain and then I solved the problem and got Accepted : 5440832

But now I am not sure about my prove for the assume,

Is my assume true? If yes, How can I prove it?

what do you mean by mountain ?

I mean there isn't such j that dp[i][j] < dp[i][j-1] and dp[i][j] < dp[i][j+1]

It is called unimodal : ]

it would be grateful if you can give a more detailed approach (not code) of Div2 D / Div1 B (the rectangle one). Thanx :) !!!

Let

f[i][j][k][l] denotes the answer for rectangle from (i,j) [top left cell] to (k,l) [bottom right cell] , then there are four possibilities for the subrectangles: Exclude the first row OR first column OR last row OR last column, so the answer will be union of all these.Now use Inclusion-Exclusion to expand.

See my solution for reference.

Correct me if I am wrong in understanding anything... Otherwise, tell me I understood correctly...

Your 's' array keeps a count of cumulative sums so that you can check whether any (i,j,k,l) rectangle is only zeroes or not...

After that, dp[i][j][k][l] is set to 1 or 0 based on whether (i,j,k,l) is valid or not...

Then, dp[i][j][k][l] is incremented or decremented (by inclusion exclusion principle) by dp[(i or i-1)][(j or j-1)][(k or k+1)][(l or l+1)] // Here by 'or' i mean the english meaning of 'or' and not bitwise 'or'...

At the end of calculating all of dp arrays values, dp contains all the answers ready to be given out in O(1) time for each query...

It is dp[i or i+1][j or j+1][k or k-1][l or l-1].

sorry, my bad...

but thanks for the solution... understood it better from your code and explanation...

:)

Thanx a lot :)

Wow, this is so brilliant. Thanks for sharing your solution!

my solution: 5431756

if u can understand this solution without any explanation, hats off to u. but since i submitted it at

`01:59:48`

, i coded the last part in a hurry and i doubt that u will be able to. i apologize for that, but i have posted a very detailed explanation under this comment.Thanx a lot was really helpful :) !!!

For Div1 B, Can anyone explain the idea behind tourist solution : http://codeforces.com/contest/372/submission/5421838

Who can explain in more detail Div1 B?

Was the 4s time limit in Div I B set to allow also

O(n^{4}+qn^{2}) solutions?Yes, I did it in O(n^4 + qn^2) and it passed in 3.5 sec however when I saved to queries which I had already computed it dropped to 700mls so it could be solved even in 1 sec by this order.

I see. Since this approach would also pass a time limit of 1 second, the organizers decided not to punish solutions without memoization and set a 4s time limit.

What does the "easy greedy" look like for Div2C? Is the gist of it that all kangaroos less than the median height must be carried (or not) and the kangaroos taller than the median height must be carrying (or not)? I'm still confused as how the greedy works on this one.

Also, for Div2B, the solution I came up was something like this:

Is there some logic error in this? My submission is failing on test 12.

I want to ask what's the mean of the "ans[i+1][j+1][k+1][l+1]" in Div2 D ? how it's calculated ？

in div1 A whats wrong in the logic of sorting and then pairing largest possible kangaroo with the largest possible kangaroo it can accomodate

That is a wrong strategy. Consider the case when sizes of kangaroo are {2, 2, 4, 9}. According to your approach the answer will be 3. While correct answer is 2.

Can someone illustrate the idea of Watching Fireworks is Fun more clearly.

I have read DEGwer's editorial and tried to understand his code. But I can't figure out what is this part doing

if

iis the order of firework (iCan be Maximumm) andjis my position on main road ( At most 150000 positions)As far I understand , if I am at State

DP[i][j]I need to find out the maximum value between the interval fromDP[ 1-i ][ j-x ]throughDP[ 1-i ][ j ]toDP[ 1-i ][ j+x ]Where

x=available time(i.e t[ i ]- t[ i-1 ]) *Di.e DEGwer representsxasintervalBut in the code segment I blocked above, DEGwer have started the for loop from 1 to interval.

But shouldn't it iterate through like

please explain what I am thinking wrong. Thanks in advance :)

In fact, in problem C sparse table got accepted in upsolving easily without any optimizations in 1.8 sec http://codeforces.com/contest/372/submission/5434984

I'm still new to programming and I had a hard time solving kyubeats. Please anyone tell me how according to his code, mp[i][j] could be treated as an integer altough mp[i][j] is string type??

Could anyone recommend some problems about Sliding Window technique ? Thanks!

Please DEGwer , can you explain us your solution with (heavy-light decomposition) ?

I have implemented 372D with the same logic on editorial, but it does not work on test#6. Can anyone explain me what is wrong with my solution or what is the difference between the editorial? Below is the link. http://codeforces.com/contest/372/submission/5533094 Thank you.

nice tutorial, glad you added the code solutions

I've tried implementing (in Java) problem Div2E "Watching Fireworks is fun" using the proposed Sliding Window algorithm (which in total gives O(nm)), but it gets Time Limit Exceeded on test case #9: http://codeforces.com/contest/373/submission/5628243

Anyone that have an idea why?

There are two main reason for TLE in your solution:

There are my AC-submission, based on your solution with these modifications: http://codeforces.com/contest/373/submission/5628723

Thanks! Did not know that LinkedList was that slow... The time limit seems to be quite tight! :D

About the O(N log N) solution for 372D: Does the dfs order mean something like preordering or postordering? I guess it doesn't matter which you use?

If I have a subtree with nodes {1, 5, 7, 9} and then I add a node 6, then t = 5 and u = 7? But shouldn't it then be: current size + (distance(s, t) + distance(s, u) — distance(u, t))/2?

If I have understood correctly, I still have one problem that I couldn't solve: What to do when there is no node with a greater or a lesser value than s?

I think current size + (distance(s, t) + distance(s, u) — distance(u, t))/2 is right. And if there is no node with a greater or a lesser value than s, I will use the begin of the set as T and the end of the set as U. my code 7674438

I am getting correct output for every test case. But while submitting i am getting WA for test case 12. bt for that test case i am getting right answer on ideone. :( I have checked for all other inputs, its giving correct ans on ideone. Link to my code : http://ideone.com/EVFnZO