DEGwer's blog

By DEGwer, 10 years ago, In English

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://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

  • Vote: I like it
  • +28
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sorry, my bad...

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

          :)

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanx a lot :)

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanx a lot was really helpful :) !!!

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of using inclusion-exclusion explicitly, the code accumulates values for each index one at a time. Say, we want to calculate 2D prefix sums:

    $$$f[x+1][y+1] = f[x+1][y] \cup f[x][y+1] + ok(a[x][y])$$$

    We can calculate $$$f[x+1][y+1]$$$ by:

    Loop over $$$ f[x+1][y+1] = f[x+1][y] + f[x][y+1] - f[x][y] + ok(a[x][y])$$$


    But, we can calculate the same in this manner too:

    Loop over $$$ f[x+1][y+1] = ok(a[x][y]) $$$

    Loop over $$$ f[x+1][y+1] \ += \ f[x][y+1] $$$ // Prefix sum updated for each column

    Loop over $$$ f[x+1][y+1] \ += \ f[x+1][y] $$$ // Prefix sum updated for each rectangle (as we have calculated column sums above)

    Also, if instead $$$f[x+1][y+1] = f[x+1][y+2] \cup f[x+2][y+1] + ok(a[x][y])$$$, then we need to loop over in reverse order for both indices.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can explain in more detail Div1 B?

»
10 years ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Was the 4s time limit in Div I B set to allow also O(n4 + qn2) solutions?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 interval

But 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 :)

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
10 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are two main reason for TLE in your solution:

    1. LinkedList — slow data structure, it is better to use ArrayDeque.
    2. 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

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Shouldn't the answer for this be 1, coz 2->4->8->16->32

5

2 4 8 16 32

»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone please help me with my submission on div2C .

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess I'm lucky In Div 1/C, It is written that mnlogn will fail ButIt passed :))

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Someone please help me in 372B - Counting Rectangles is Fun

Why are we taking minimum of temp every time in 74816763 ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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