Hello, Codeforces!

Today I want to write a completely meaningless article. First, I must mention, reading this post will produce nothing. Reading it is, definitely, just a waste of time.

Are you ready to do the most useless thing of the world? OK. Let's start!

Some of you may think "Is it really meaningless?" or "Won't it be an interesting article, although there are no means?", but neither is true. I do not post this article for any other people, and I do not post this article for myself. Let me repeat. This article contains truly no meaning.

Some of you may think "Isn't it some experiment to verify the rumor "Red will get upvote, regardless of what the post say while if some Gray said the same thing he is downvoted", or more suspicious way, "You want upvote but you didn't came up with the idea, so you are posting such an article", but both are wrong. Even I do not know why I wrote such a useless article, and if I want upvote, I could write about a bit more useful things.

This article is completely meaningless, as I mentioned, but on the other hand, completely harmless. So if I got downvoted, I would say "Why downvoted???", or "I think you don't understand what I said", like some people often says. And if I got upvoted, I should say "Why upvoted?", or "I don't think you didn't understand what I say, as I wrote nothing, but you must be crazy", in the same reason.

How are you feeling about wasting time? Write the comment, if you want to waste even more time. I do not recommend, since time is precious.

Thank you and despise you for reading this article till the last. See you!

I'm studying Edmond's maximum matching algorithm and will write the code of this algorithm. Does anyone know where to verify?

Tomorrow, we have JOI Open Contest 2015 .

This is OI-like contest on CMS and prepared by Japan to practice IOI.

There are two rounds using same problems. You can participate whichever you want.

The first round is 04:00~09:00 GMT June 14, and second round is 10:00~15:00 GMT on same day. And since the server will be open until 14:00 GMT June 15, you can practice this round at any time until then.

Please don't talk about problems until second round will be over. I'm looking forward to see a lot of IOI-er and programming contest lovers at this contest!

UPD1: Contests has been over. It is free to talk about the problems from now. You can still practice until the server will be closed.

JOI(Japanese OI) spring camp and contest which chooses Japanese team of IOI are held from today to 25th.

Then, online contest of this contest will be held. Here is contest site.

http://cms.ioi-jp.org/joi-sp-2014/index.html

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

Hello.

Codeforces Round #219 will take place on December 13th at 18:00 MSK for both Div.1 and Div.2 participant. Make sure that it will be held unusual　time.

Problem setters are kagamiz and DEGwer, and we thank Gerald for helping us to hold this contest, and Delinur for the translation, and MikeMirzayanov for systems.

The score distribution will be uploaded soon, but probably we use the standard scoring system.

UPD1: The score distribution is standard, 500-1000-1500-2000-2500 for both division.

UPD2: Problem B from Div.2 and problem C from Div.1 have some problems, so all submissions to these problems are rejudged. I'm very sorry.

UPD3: Anyone who gets AC two or more times, because of resubmit before clarification, please, write to Gerald, your submissions that should be skipped. Sorry for inconvenience.

UPD4: Now system test has finished, congratulation for winners!!!

Division 1:

1.jqdai0815

2.tourist

3.PavelKunyavskiy

4.dasko1

5.al13n

Division 2:

1.Hwhitetooth

2.pcnc_zLq

3.wuyiqi

4.prok

5.aaaaajack

And also congrats for rng_58 and permin, who got AC on Div.1 E problem!!

UPD5: Now editorial is uploaded here.

I wrote Topcoder SRM 450 Div1 medium's solution and submitted and ran system test, I got segmentation fault on some case. I ran system test again and again, every time I ran it, segmentation fault appeared on different case on same solution. (Once I got RE on test 3, but another time I got AC on test 3, but I got RE on test 27... etc)

ryo_issy also say that he got same trouble on SRM573 Div1 medium...

What is happening?

I tried to solve a problem in C++, I tried to output the value which class is long double. When I used "%Lf" the output of my solution is -0.000000 on test #1 (it is a wrong answer) but according to my environment, the output is 1.333333 (it is a correct output). On Codeforces, can we use "%Lf" in C++? Or like "%lld", aren't we allowed to use it?

UPD: When I cast it to double, my solution worked.

I submitted the solution on practice, I got "Judgement Failed". I have never seen it, so I cannot understand what happened. Does it happen oftenly?

UPD1: The problem is cleared. Now judge system is available.

I participated to Codeforces #136, I submit the solution of problem C. My solution passed pretest, but I got wrong answer on test 25... The message is "wrong answer 6021st numbers differ — expected: '2', found: '1'", so I cannot recognize why my solution got wrong answer. Where is the bug?