cyand1317's blog

VK Cup 2018 Round 2 and Codeforces Round #472 Editorial
By cyand1317, 6 years ago, In English

Long time no see!

As VK Cup Round 2 and its two parallel rounds (Div. 1 and Div. 2) comes to a close, we're here to congratulate on all who did well on the contest and cheer for everyone who participated — the queue won't stop you!

Here are the detailed tutorials for the problems. Feel free to discuss in the comments!

Kudos to arsor for translating the tutorials into Russian!

Tutorial is loading...
Model solution
Alternative solution (Errichto)

(by cyand1317)

Tutorial is loading...
Model solution
Alternative solution with DSU in O(nm alpha(n)) (skywalkert)
Alternative solution in O(nm)

(by cyand1317)

Tutorial is loading...
Model solution

(by KAN, prepared by fcspartakm)

Tutorial is loading...
Model solution

(by cyand1317)

Tutorial is loading...
Model solution

(by KAN, prepared by cyand1317)

Tutorial is loading...
Model solution

(by KAN)

Tutorial is loading...
Model solution

(by Claris and skywalkert)

My gratitude to the coordinators, problem authors, testers, and every participant. You made all this possible! Cheers \(^ ^)/

Tutorial of VK Cup 2018 - Round 2
  • Vote: I like it
  • +114
  • Vote: I do not like it

Comments Comments (44)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

funny python fact: in 956B NlogN solution in Python3 is very likely to get TLE. For the pretests, I got AC with 950ms out of 1000. I fixed it by switching to PyPy, and of course another option was to optimize the solution to O(N)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can some author pls check this my same solution got tle in contest and passes outside. TLE:- http://codeforces.com/contest/956/submission/36596404 AC:- http://codeforces.com/contest/956/submission/36601475

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

    Submissions to problems are not yet enabled. How did you submit the solution after contest?

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

      I don't know about other problems but submissions for div1 d is enabled.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

div2 E(div1 D) "That leaves us only with a binary indexed tree to be implemented." How to use a binary indexed tree to solve the problem "Inversion pairs".

The only way I can find out to solve this is using set or balanced binary search tree.

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

    Someone plz tell me about how to do it.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    Each plane can be represented as a line segment from (-w, a[i]) to (w, b[i]). So a pair (i, j) of 2 planes is counted if two segments are intersected. i.e. a[i] <= a[j] && b[i] >= b[j] W.L.G: a[1] <= a[2] <= ... <= a[n]. For each i from 1 to n, count the sum of values in [bi, ∞], then increase the value at b[i] by 1.

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

      "For each i from 1 to n, count the sum of value in [bi, ∞], then increase value at b[i] by 1." Yes, this is a clear way to do that. It is just like the way I found out by using set before. My way is just using a set, with inserting b[i] like your "increase value at b[i] by 1", and calculate the counts like your "count the sum of value in [bi, ∞]". Thank you.

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

      I spent a very little time and found out I can count the intersections of the set "segment((v+w)/x,(v-w)/x)", and I can't implemented it correctly and completely within a half our.

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

      I used about 25min, thinking about 2-pointers to solve this, and at last was some how convinced I should use some data-structure, and there was just 5min left.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I understand how number of inversions can be counted with BIT. But how two different type of planes which are (left to right plane) and (right to left plane) could be treated in the same time even though -w decreases speed of left to right plane but increases speed of right to left plane?

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the tutorial of DIV-2D: In order to satisfy later days, ti ≥ tj - (j - i) should hold for all j > i. What does it mean by this line?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    On each day we can increase t by at most one, thus ti ≥ ti + 1 - 1, which is equivalent to the condition that ti ≥ tj - (j - i) holds for all j > i.

    The tutorial will be updated soon, thanks for pointing out.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the best solution jury has for E? I think my solution can be optimized into S sqrt S (where S is sum of values, of course), and it's not significantly harder than S^2

What was the reason of such a small S?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    We know the solution, but we thought it was not interesting to accept only such solutions, the main idea is how to do the knapsack, not how to optimize it.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Anyone can explain or provide relevant link for the sqrt optimization of knapsack?

    Thanks

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me what's wrong with my code for Div2C? It is failing test #9. :( 36602743 Instead of using upper_bound to search for k (like everyone else did), I did lower_bound to search for i. According to me, it should give the same result, and I can't find my mistake. Please help! Thanks!

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Actually, it's not the same.

    For sample input:

    4 6

    3 5 6 9

    Answer should be: 0.75 — Triple (5, 6, 9)

    Your output: 0.66667 — Triple (3, 5, 9)

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

My solution for E:

  • it's clear that the bottoms of important boxes from the answer should form a subinterval [l, r] of [L, R] and their order doesn't matter; we need to put some boxes with sum of heights  ≥ L and  ≤ R - (r - l) below them

  • let's suppose that x boxes lie completely within [l, r]; if we don't need to use all remaining important boxes to get them high enough, the answer is at least x + 1; either way, it's at least x

  • these x boxes should be the smallest x important boxes; proof: if there's an important box a and a smaller unused important box b, we can replace a by b and decrease r; if there's a smaller important box b used below height l, we can swap a and b, which doesn't change r and increases l, creating another valid solution

  • thanks to this observation, let's use a fast enough DP to find all heights  ≤ R reachable only using unimportant boxes; then, we can keep adding to them important boxes in the reverse order of heights and before adding each of them, find the smallest possible l (that can be constructed using boxes added so far as a subset sum) and binsearch for the maximum number of important boxes that haven't been added to the subset sum candidates yet and have height  ≤ R - l

  • now we've got the maximum possible x (as defined above); the answer could be x + 1, but only if we construct it using these x smallest important boxes

  • let's find all subset sums of the remaining important boxes, remove the sum corresponding to their full set and add all unimportant boxes; if we can construct a height  ≥ L and , the answer is x + 1

Here, "fast enough DP" is the classic O(RN) DP for subset sums implemented using bitsets, which give us a massive speedup, something like O(RN / 64). My code runs in 30 ms.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

It's not hard to solve 956 A in O(n·m).Make a bipartite graph with rows and columns where row and column are connected if in there intersection there is #.Now just do Dfs on components and then check if in intersection of every row R and column C in component there is #.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    It's a bit advanced for problem A; we've tested it during preparation, though.

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

    There is an easier solution with O(n*m) complexity. You can just make array, f[i] — first row such that a[f[i]][i] = '#'. Now for each row iterate over columns and if there is more than one distinct f[i] for this row, answer is no. There are some other simple cases, just look this code: 36581433

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me debug this Div 2-C code. I can't figure where the mistake is

submission
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You're moving the two pointers i,k in the wrong order : what you're doing is for all k increase i until (i,i+1,k) is valid, then move onto k+1. But it's possible that increasing i further for the same i yields a better result : try "4 1000 1 100 101 200" You need to increase i one by one, and for each i it's true that the largest possible k (as long as e[k]-e[i]<=u) gives the best possible answer for this i.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I didn't understand Div2 D solution at all. Can someone please explain elaborately?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D passed pretests but failed same test case in system testing (TLE) . How is that possible?? http://codeforces.com/contest/956/submission/36599452 Also i think my solution is nlogn so there should not be any problem with time? Can anyone help?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Alternate solution for 956C - Речная загадка:

First, note that d[i] = d[i-1] + m[i-1] – m[i] + (0 or 1). The only condition is that d[i] >= 0. For each day from 2 to n, greedily "choose" +0. Now at some day i in the future, maybe d[i] turns out to be negative. In this case, we need to go back and change our choice from +0 to +1 on exactly -d[i] days.

What happens if I change the choice for day j <= i from +0 to +1? I get a +1 to all d[k] s.t. j <= k <= i. So, it's easy to see that if I need to overturn a choice, I should do so for the latest day on which I made a +0 choice. That means that every time I make a +0 choice, I can just push the index in a stack, and anytime when d[i] < 0, I can pop from the stack exactly -d[i] times and add (i – stack.top() + 1) to the answer.

Link — 36588535

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

    can u please explain how is d[i] = d[i-1] + m[i-1] – m[i] + (0 or 1) this equation formed ? thankyou.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      d[i-1] + m[i-1] + 1 imply the number of marks on day i-1. So the number of marks on day i equals d[i-1] + m[i-1] + 1 + (0 or 1), (0 or 1) mean the mark on day $$$i$$$ is coincided or not. => $$$d[i] = number\ of\ marks\ day\ i - m[i] - 1 = d[i-1] + m[i-1] + (0\ or\ 1) - m[i]$$$.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve knapsack in O(S sqrt(S))?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test cases for 924 A were weak.

The grid size was 50 x 50. I solved the problem converting every row (considering # as 1 and . as 0) to a binary equivalent integer. Now, for every two rows with integer values, I was checking if (a == b) || (a & b == 0).

But I took it as an integer, and so it was only taking the last 32 positions in the row. I was also checking for the column, and it was valid only for the last 32 positions in the col.

With a long long integer, having 64 bits (50 required in problem), the solution should be correct.

Any testcases where the grid is of size 50 x 50. And you place random elements in the top left subgrid of size 18 x 18, it should fail.

But my code still passed the system testing.

Link to solution: http://codeforces.com/contest/957/submission/36584331

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Please, help! (Task D) Why does these quadratic solutions get wrong answer on test 4. http://codeforces.com/contest/924/submission/36670452. http://codeforces.com/contest/924/submission/36671090. Firstly I calculte all pairs of points of left and rihgt side. Then i iterate over all points on left and right side and check pairs o them. I tried to find a bug in this code, but I couldn't.

P.S.: I undersand that i incorrectly calc pairs of points on the one side

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for div2E is giving slightly wrong ans for large testcases. Can somebody suggest why or give a smaller testcase where my code fails?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you describe your solution for Bonus2 of Minimal Subset Difference? Judging by the limits, it seems unlikely to be exponential, so I'm really curious to see what it is

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'm sorry that we are going to prepare another problem related to the Bouns2 approach, so please let us suspend for a while longer before revealing it. Also, we encourage people to come up with the same idea (or better optimized) individually.

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

    Hi, please check Petr's blog out, as he mentioned a problem like Bonus2 of MSD.

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

Regarding Problem C: Riverside Curio 1)The number of watermarks strictly above the water level on each day=m[i] and one mark is used to mark the water level so the minimum number of marks should be >=(m[i]+1), secondly, the number of watermarks on a day[i]>=day[i-1]so we should move from left to right and take the maximum of all indices to the left of index i and m[i]+1 to assign the the number of watermarks on the day i. 2)There is a possibility that after assigning the number of watermarks on each day there might exits day[i] and day[i-1] such that day[i]-day[i-1]>1 so we should remove such adjacent false relations as day[i]-day[i-1]<=1 so initialize day[i-1]+=(day[i]-day[i-1]+1) in such cases where day[i]-day[i-1]>1 and in order to do this step traverse from right to left. My submission: https://codeforces.com/contest/924/submission/94533526

→ Reply