### DEGwer's blog

By DEGwer, 9 years ago,

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.

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

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

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

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

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

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

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

• +28

 » 9 years ago, # |   +1 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?
•  » » 9 years ago, # ^ |   +5 Sorry, we've fixed the solution's link. Please check it now.
•  » » » 9 years ago, # ^ |   0 Thanks...
 » 9 years ago, # |   +21 For Div2 D what does cumulative sums for 2D and 4D mean???
 » 9 years ago, # |   0 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?
•  » » 9 years ago, # ^ |   0 what do you mean by mountain ?
•  » » » 9 years ago, # ^ |   0 I mean there isn't such j that dp[i][j] < dp[i][j-1] and dp[i][j] < dp[i][j+1]
•  » » » » 9 years ago, # ^ |   0 It is called unimodal : ]
 » 9 years ago, # |   +12 it would be grateful if you can give a more detailed approach (not code) of Div2 D / Div1 B (the rectangle one). Thanx :) !!!
•  » » 9 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 9 years ago, # ^ |   0 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...
•  » » » » 9 years ago, # ^ |   0 It is dp[i or i+1][j or j+1][k or k-1][l or l-1].
•  » » » » » 9 years ago, # ^ |   0 sorry, my bad...but thanks for the solution... understood it better from your code and explanation...:)
•  » » » 9 years ago, # ^ |   0 Thanx a lot :)
•  » » » 9 years ago, # ^ |   0 Wow, this is so brilliant. Thanks for sharing your solution!
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 my solution: 5431756if 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.
•  » » » 9 years ago, # ^ |   0 Thanx a lot was really helpful :) !!!
 » 9 years ago, # |   +6 For Div1 B, Can anyone explain the idea behind tourist solution : http://codeforces.com/contest/372/submission/5421838
 » 9 years ago, # |   0 Who can explain in more detail Div1 B?
 » 9 years ago, # | ← Rev. 4 →   +8 Was the 4s time limit in Div I B set to allow also O(n4 + qn2) solutions?
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 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.
 » 9 years ago, # | ← Rev. 2 →   0 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: -You can buy w/k characters. --loop-- -Check the strlen of the current pointer. -Check how many numbers are left to purchase with this string length. -If you can purchase them all, then purchase them, set the current pointer to the smallest number of the next length, add the number of numbers you purchased, and loop again. -If you cannot purchase them all, then purchase the biggest amount you can (the remainder of your money / the length of the current pointer), add the number of numbers you purchased, and stop looping. --endloop-- -then print the number of numbers you purchased. Is there some logic error in this? My submission is failing on test 12.
 » 9 years ago, # |   0 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 ？
 » 9 years ago, # |   0 in div1 A whats wrong in the logic of sorting and then pairing largest possible kangaroo with the largest possible kangaroo it can accomodate
•  » » 9 years ago, # ^ |   +11 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.
 » 9 years ago, # | ← Rev. 2 →   0 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 // Line 32-34 of the code linked in the editorial for (lint j = 1; j <= interval; j++){ while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j]) dq.pop_back(); dq.push_back((int)j); } if i is the order of firework ( i Can be Maximum m) and j is 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 from DP[ 1-i ][ j-x ] through DP[ 1-i ][ j ] to DP[ 1-i ][ j+x ]Where x=available time(i.e t[ i ]- t[ i-1 ]) * D i.e DEGwer represents x as intervalBut in the code segment I blocked above, DEGwer have started the for loop from 1 to interval. for (lint j = 1; j <= interval; j++) But shouldn't it iterate through like for(int m=j-interval;m<=j+interval;m++) please explain what I am thinking wrong. Thanks in advance :)
 » 9 years ago, # | ← Rev. 2 →   0 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
 » 9 years ago, # |   0 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??
 » 9 years ago, # |   0 Could anyone recommend some problems about Sliding Window technique ? Thanks!
 » 9 years ago, # |   0 Please DEGwer , can you explain us your solution with (heavy-light decomposition) ?
 » 9 years ago, # | ← Rev. 2 →   0 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.
 » 9 years ago, # |   0 nice tutorial, glad you added the code solutions
 » 8 years ago, # | ← Rev. 2 →   +5 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/5628243Anyone that have an idea why?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 There are two main reason for TLE in your solution: LinkedList — slow data structure, it is better to use ArrayDeque. You create new long array "second" at each iteration, it is slower than fill array with zeros in "for" loop. There are my AC-submission, based on your solution with these modifications: http://codeforces.com/contest/373/submission/5628723
•  » » » 8 years ago, # ^ |   +5 Thanks! Did not know that LinkedList was that slow... The time limit seems to be quite tight! :D
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   0 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
 » 7 years ago, # |   0 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
 » 4 years ago, # | ← Rev. 2 →   0 Shouldn't the answer for this be 1, coz 2->4->8->16->32 5 2 4 8 16 32
 » 3 years ago, # |   -10 I submitted a solution for div1C in practice, then realized it was wrong. Yet it got accepted (poor testing?). Still, my hacking skills are poor so I don't know how to break it.Code: 47856014
 » 3 years ago, # |   +1 can anyone please help me with my submission on div2C .
•  » » 3 years ago, # ^ |   0 copy(v.begin()+n/2+n%2,v.end(),back_inserter(vi)); a2 = (int)vi.size() — 1;
•  » » » 3 years ago, # ^ |   0
•  » » » » 3 years ago, # ^ |   +1 Hi, thanks for the reply. Can you please explain why that works and why my solution fails ( especially the typecasting ).Also, why to include n%2 as v.resize(n/2) makes v contain elements from index 0,n/2-1 so vi should start from n/2 and not from n/2+n%2 ???? Please explain . . . . .
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 Hmmmm.... Your solution works :) You just had to write a1 = (int)v.size() — 1 and a2 = (int)vi.size() — 1, because the value of v.size() is unsigned and when the value of v.size() is equal to 0, v.size() — 1 = 18446744073709551615 :) This will help you :) https://codeforces.com/contest/372/submission/54988783
•  » » » » » » 3 years ago, # ^ |   +1 Thanks Again
 » 2 years ago, # |   0 I guess I'm lucky In Div 1/C, It is written that mnlogn will fail ButIt passed :))
 » 2 years ago, # | ← Rev. 2 →   0 4D prefix sum seems to be quite amazing in DIV2 D. I solved it with 2D though. it worked in 3915 ms, time complexity O(N^2*M^2 + q * N^2), I got TLE first and then optimized it a bit, luckily :) it worked under 4sec. 74680893
 » 2 years ago, # | ← Rev. 3 →   0 Someone please help me in 372B - Counting Rectangles is FunWhy are we taking minimum of temp every time in 74816763 ?
 » 23 months ago, # |   0 Can someone explain why does the dfs order work in problem D(div1)
 » 12 months ago, # |   0 For this solution in Counting Rectangles is Fun, https://codeforces.com/contest/372/submission/28160041, can anyone explain why we do: if (i == 1-1 && j == 2-1) System.out.print("");Why for i == 0 and j==1? Why not i==0 and j==0 as well?Also in the 4 for loops how are we counting vertical rectangles? consec only does horizontal rectangles?
 » 10 months ago, # |   0 Can someone please help me in Div 1 C / 2 E....I am doing the same as all others, taking dp[i][j] for when ith firework gets lit at jth position, and using sliding window maximum to get corresponding previous range maximums.But I'm unable to understand why it's wrong. (as test case 4 has 100 positions so its difficult to debug). I tried testing with new test cases but I am not able to find error.Submission link.Thanks in advance!
•  » » 10 months ago, # ^ |   0 Update — has been resolved!The error was on the window part when the right boundary of window exceeds the array bounds, then r = array.size(), thus window max gives [n — window*2, n] instead of [j — window, n]AC link