Блог пользователя induk_v_tsiane

Автор induk_v_tsiane, история, 15 месяцев назад, перевод, По-английски

We hope you liked the problems.

Task A was invented and prepared by induk_v_tsiane.

Task B was invented by induk_v_tsiane, and prepared by i_love_penguins.

Task C was invented and prepared by induk_v_tsiane.

Task D was invented by i_love_penguins and efimovpaul, and prepared by i_love_penguins.

Task E was invented by induk_v_tsiane and kristevalex, and prepared by induk_v_tsiane.

Task F was invented by induk_v_tsiane and Artyom123, and prepared by induk_v_tsiane.

1859A - Вместе мы сила

Hints
Tutorial
Author's code

1859B - Оля и игра с массивами

Hints
Tutorial
Author's code

1859C - Ещё одна задача про перестановки

Hints
Tutorial
Author's code

1859D - Андрей и побег из Капиграда

Hints
Tutorial
Author's code

1859E - Максимальная моногонность

Hints
Tutorial
Author's code

1859F - Телепортация в Байтландии

Hints
Tutorial
Author's code

Some notes/challenges:

  • We know about the $$$O(N^2)$$$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).

  • You can solve $$$D$$$ without the constraint that the segments are contained, but that is harder. It is solvable in $$$(ONlogN)$$$.

  • Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!

Разбор задач Codeforces Round 892 (Div. 2)
  • Проголосовать: нравится
  • +272
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks for fast editorial!

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for your texts!

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Problem C can be solved in O(n^2).

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +47 Проголосовать: не нравится

    Yeah, I solved it in O(n^2) by кукарек, I don't know, why my solution works correctly.

  • »
    »
    15 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    maybe can be solved in O(n) too, but I don't know how to prove it

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is the O(N) idea?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I think that the recalculation of the tail from step to step could be done in O(1) — you always know where is the maximal term and the delta to sum: -sum of all values + delta for border elements

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        First I got all the answers for n<=13 by brute force, then subtracted this answer from the sum of the squares of all the natural numbers less than or equal to n to get a series:1 3 7 13 20 29 40 52 66 82 100 120 141
        Then I subtracted each neighboring number in this series to get a second series: 2 4 6 7 9 11 12 14 16 18 20 21
        Then I realized that the second series is very much like an equal-variance series, but at the no.2*3,2*5,2*7... number this difference changes to 1.
        Through this strange pattern, it is possible to construct a second series (n<=250) by preprocessing, which inverts the first series to get the answer. For each example, we only need to find the sum of the squares of all the natural numbers less than or equal to n.
        This is my submission:218557375

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
        Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        First of all, observe that the maximum cost permutation is like this:

        $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, ... , $$$p$$$, $$$n$$$, $$$n-1$$$, $$$n-2$$$, ... , $$$p+1$$$ ;

        Secondly, it's provable that p=n-sqrt(2*n).

        And without precalculations or other things, we can solve this problem with a kinda brute force solution in O(n).

        My submission: 218725357 .

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      found that reversing the last k elements where k is the minimum value such that n <= k + floor(k^2/2) (which is oeis sequence) is optimal so its o(n)

      don't know why it works

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      is it possible to calculate all the answers locally then make a script to create many if else statements to achieve a O(1) solution? just a random thought :)

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is the O(N^2) idea?

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      For task C the optimal answer is a permutation that is the identity permutation with some suffix reversed. For example, for n = 4 you have 1 2 4 3, so you can get an O(N^2) solution.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +47 Проголосовать: не нравится

For task C the optimal answer is a permutation that is the identity permutation with some suffix reversed. For example, for n = 4 you have 1 2 4 3, so you can get an O(N^2) solution. https://codeforces.me/contest/1859/submission/218520660

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Damn, I've figured out how to solve problem B, but still didn't get it right. My solution have no difference between the one in the tutorial, but for some reason it failed on pretest 4.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where is precalc in author’s solution of the problem C???

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Do you really need a precalc when you have an $$$O(n^3)$$$ (or even $$$O(n^2)$$$ for most of participants) solution???

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    $$$\sum n\le500$$$,so $$$O(n^3)$$$ can solve it.As the result,you needn't use precalc.

»
15 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Very entertaining round keep it up :)

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
15 месяцев назад, # |
Rev. 4   Проголосовать: нравится +19 Проголосовать: не нравится

I found C through pattern:

The solution is always in form:

1, 2, 3, ... k, n-1, n-2, ..., k+1

I didn't prove this, does somebody have an idea why this happens? Sol is trivial O(N^2)

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    the stream is proving the statement uwu

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This pattern was so not obvious. Almost gave up on C but then decided to loop through every permutation(next_permutation) for n=10 to see what permutation gave 303 and the pattern was there clear as hell.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      same, the bruteforce was so obvious i just tried it to look for patterns (also i couldn't find the solution for 10)

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    initial permutation :- 1 2 3 4 ... n

    k = 1 to n let say you want to change positions only in last n-k (may be not all also). so permutation will be 1 2 3 ... k — — and now we need to find for what position of other numbers (k+1 to n) will we get max ans ;

    if we minimize the max value then remaining sum of values ( k+1 to n positions ) become larger and ans will be max .

    let say n is at position a and n-1 is at position b . if a > b ==> abs(n*a — (n-1)*b) > abs(n*b — (n-1)*a) . As we want all numbers(k+1*val at k+1 to n*val at n) to be closer to each other we give b position n and a to n-1.

    By considering all possible pairs 1 2 3 4 -- k n n+1 — k+1 gives the max ans when only we want to make changes in last n-k positions

    iterate this for k = 1 to n.

»
15 месяцев назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Just calculate everything, put all in a list and print and print

»
15 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Task D: "We assume that there is a data structure that allows us to add elements, remove elements, and quickly output the maximum. ...

We notice that to solve this problem, we can use the std::multiset} container, which automatically sorts elements in ascending order."

Which other structures can be used to solve this? (preferably easy to implement)

Golang doesn't have a built-in multiset. I tried to use a priority queue, but couldn't find a version that supports removing some element by index.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In problem D, I only use vector. You could consider to see my solution submission

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used stack for problem D

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you elaborate?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        So if I have an array of segments and we want to merge the intersecting segments together, I can sort the array of segments according to it’s first element, then I push each segment into a stack, either it intersects with the top of the stack, then I merge them together, or it doesn’t and then I just push it as another segment into the stack. Though I think using a vector would be better for this problem.

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yeah I used vector to merge intervals it worked quite well, Thankyou.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can simply use vector of pairs, and then a map.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Solution using only vectors (slices in Go) in a couple of words: 1. From l, r, a, b we build segment l, b and add such pairs to slice as a segment 2. Sort the segments by start coordinate 3. Use scanline to get union of segments as a new set of segments (which is already sorted as well) 4. For each query use binary search (sort.Search is very convenient in Go) on this new set and if the point is inside a segment, then the answer is the end coord of this segment

    Here is the solution in C++, which is easily convertable to Go: https://codeforces.me/contest/1859/submission/218541082

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      could you please explain what "scanline" is in brief? I'm finding it difficult to understand why we're processing l, r, b in a particular order (not necessarily in that order). Thanks in advance

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You don't need any fancy data structures to solve D. You just need to be able to sort the portals with respect to b 218826757, and thats about it.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C can be done in linear time as well. Notice the ans is always of the Patten 1,2,3...k, n, n-1, n-2...n-k type. For example, for n=10, it is 1 2 3 4 5 10 9 8 7 6. So just try all such for given n and return maximum. I wonder why constraints where so low. With above approach, we can easily solve for higer N also.****

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Minus delta :(. Btw fast editorial.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for editorial!

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

pattern recognition forces

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C can be solved in O(n^2). The idea is to reverse some suffix of the sorted permutation and finding which gives maximum power. 218547871

»
15 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

pattern recognition forces

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I spent 1 entire hour on C figureing an O(n^3) just to somehow get a O(n^2) instead and I don't event know how to prove it

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C can be solved in O(n^2+t*n).We can preprocess an array first and calculate it easily. My English is a little poor. You can see https://codeforces.me/contest/1859/submission/218569933 .

»
15 месяцев назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

My solution to the problem D (it can be easier to understand for someone).

First of all, we can use only $$$l_{i}$$$ and $$$b_{i}$$$ ('cause it is always beneficial to teleport to point $$$b_{i}$$$, and we do not really need to teleport to the point $$$b_{i}$$$ from the right)

So let's say we have got $$$n$$$ segments $$$l_{i}, b_{i}$$$. If two segment intersect each other we can squeeze them (we can do it by using simple stack)

After we squeeze all of the segment for each $$$x$$$ we just have to find the segment with the biggest $$$l$$$, which is not bigger than $$$x$$$ (we can do it by using binary search). After finding the segment the answer for $$$x$$$ will be max (x, $$$r_{i}$$$).

It takes $$$O((q+n)log(n))$$$ time.

btw, thanks for the fast tutorial!

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

still waiting on someone to prove why th does 1 2 3 k n-1 n-2 k+1 solution for C works i just noticed it while using next permutation and find the biggest possible answer

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I love this Round. Because I can learn a lot from it. Thank you!

»
15 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Are questions like c really relevant . Meaning which ability of ours is it testing.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got MLE in question D, my code is fairly straight forward.

Here is the link: https://codeforces.me/contest/1859/submission/218558458 Can someone tell me the reason please?

What I did is, Stored l, b Merged these intervals Then if query lies in the interval, then print the right val of interval else the query value remains same

»
15 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

The time limit was very strict for Problem D it seems.. Another nlog n solution with lazy segment tree got TLE... https://codeforces.me/contest/1859/submission/218564665 :-(

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it with segment tree as well and I get TLE on test case 9 though without lazy. If I added lazy I would also have the same result as you. I agree with you this was very strict. Maybe the author didn't even notice that there is a solution with segment tree. What would have been most optimal would be to split this task into 2 parts one getting 1500 points and the other 250 points and just say that the time limit is the only difference. Put 3 seconds on the easy version and 2 seconds on the hard version. If I have done all the correlation steps to achieve O( NlogN + QlogN ) complexity why should I get a big fat 0?

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yea correct.. seems the author and tester didnt notice the segmentree solution.. the code passes in g++20 actually.. :-(

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Like if they put the limit to be 3 seconds I don't see how a quadratic solution would pass anyways... It's a bit ridiculous if you ask me how they came up with 2 seconds as the time limit. I guess they just timed their solution and that was it.

        What's even more pitiful is that it doesn't really take much skill to switch from a segment tree solution to a PQ solution for this problem. It's the same observations that you need to make essentially and simply apply them using the respective container.

        But in any case: This can be a lesson for both you and me to always

        1) Check first if a segment tree solution can be easily changed to a PQ or iterative seg tree one. 2) Always submit as g++20 since we have already seen in many cases where the same code passes in g++20 and not in previous compiler versions.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Hi!

    Sorry that this happened, we did not want to cut off such solutions. One of our testers passed two segment trees, one with lazy operations and one without, so we thought that the TL was OK.

    I will try to be more lenient with TL's from now on.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      i got tle with segment tree beats at first too, then changed to set but still got tle because for convenience i substituted an array for std::map??? complexity's still right but i got stuck for a long time...

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help with my solution of D, I'm getting TLE on test case 9th also the time used is relatively high don't know why??

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with my solution of Task D I am getting TLE on test case 9 although my time complexity is qlog(n)??

»
15 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Thanks for the great round and nice hint based editorial !

Here is my advice about the problems I solved:

A
B
C
D
E
»
15 месяцев назад, # |
  Проголосовать: нравится +94 Проголосовать: не нравится

Thanks for the contest! Feedback on the problems:

A: Good easy problem.

B: Fine easy problem.

C: Decent problem; not terrible but not my favorite. I think the problem would have been better with a higher time limit--I don't think there's much risk of a brute force solution passing and I think it would have been better to clearly accept $$$O(N^3 \log N)$$$ rather than making its result implementation-dependent (my straightforward implementation gets AC in 2800ms without the optimization mentioned in the editorial). I could imagine using either ~5s or 1s, with 1s intended to clearly cut all solutions that don't optimize out the log factor. Especially because the slower solution requires some optimization to get AC, I don't love that there is also an $$$O(N^2)$$$ solution that seems pretty difficult to prove, since this pretty heavily rewards proofs by AC.

D: Good problem, probably my favorite of the round. The observation that the containment constraint is helpful is pretty nice and the implementation is fairly straightforward from there. (The bonus task is also nice, and I thought about it in-contest when I didn't read the containment constraint--I could imagine including it as a harder subtask with a score distribution along the lines of 1500 + 2500, but I think excluding it is fine too.)

E: Good problem; the absolute value maximization trick is a nice one for people who haven't seen it yet.

I don't understand why my solution gets AC: see here for my in-contest solution and here for the solution I think is correct. The difference occurs in case 4; I think my current solution maximizes |A[l] — A[r]| + |B[l] — B[r]| instead of |A[l] — B[r]| + |A[r] — B[l]| when the interval we choose has length greater than one. I have no idea why this passes, but at the same time I don't immediately see a countercase (it's a bit harder because I correctly handle the case where the length of an interval is 1).

My current theory is that the only two cases we need to actually consider are A[l] + B[l] — A[r] — B[r] and A[r] + B[r] — A[l] — B[l]; for the other two cases we could do better by splitting into smaller intervals. Indeed, this submission only considers these two cases and gets AC. If anyone has a proof of this, I'd be happy to see it; I'll also try to show that this holds myself later on.

F: Fairly good problem. The implementation was a bit annoying, but that's hard to avoid unless you want to exclude this type of heavy-duty tree problem entirely.

My one criticism of the statements is that I think "cost" should be replaced with "value" in C and E. Typically, we try to minimize a cost, so when I skimmed the problems and read the word "cost", I tried to minimize the answers rather than maximizing them for my first few minutes. I think it makes more sense to use cost for minimization problems and value (or e.g. score or similar) for maximization problems.

Overall, though, I enjoyed the contest--thanks very much to the authors!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    Geothermal Your intuition on E is correct! In fact, for the other two cases, you can do better by simply considering the singleton intervals at the endpoints.

    Claim
    Proof
    Corollary
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Wow, that's cool. We did not notice this during testing, thank you very much for your insight!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Regarding E: We can show that if A[l] — B[r] >= 0 and A[r] — B[l] >= 0 (one of the mixed case from above), it is always better to use two singletons instead of using a single interval of length > 1. Label the four numbers A[l], A[r], B[l], B[r] as x1, x2, x3 and x4 according to their order, i.e. x1 <= x2 <= x3 <= x4. There are six ways to arrange them such that the inequalities hold. I will discuss 2 of them:

    	l   r		l   r		
    A:	x2  x4	|	x3  x4	|	
    B:	x3  x1	|	x2  x1	|
    

    For the first case we have (cost of the interval on the left, cost of the singletons on the right):

    x2 - x1 + x4 - x3 <= 2x3 - 2x2 + 2x4 - 2x1

    because after simplification we have:

    0 <= x4 + 3x3 - 3x2 - x1

    For the second case we have:

    x3 - x1 + x4 - x2 <= 2x3 - 2x2 + 2x4 - 2x1

    0 <= x4 + x3 - x2 - x1

    We can verify the inequality holds for all other cases in a similar way.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks for the proofs, y'all! I forgot that the objective function is nonnegative in $$$k$$$, so I was trying to do something more complicated involving breaking the sequence into two parts whose union is the entire sequence. Using the singletons makes this very clean; nicely done!

»
15 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I solved problem C in O(n2) by 1, 2, 3, ..... n, n-1, ....., x. But idk how to prove it >:(, just wasted 1 hr.

»
15 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks for the great contest, really enjoyed it. Hope I will turn green today :)

»
15 месяцев назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

to C

define $$$k=n-\lfloor \sqrt{2n+1} \rfloor$$$

for 1~k, $$$p_i=i$$$

for k+1~n, $$$p_i=n+k+1-i$$$

so C can be solved in $$$O(n)$$$

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Please help me find out why I get the wrong answer in B pretest 4 please don't downvote, I'm trying for hours but couldn't find why I get WA.

Ok, so here is my code

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Note that due to the bounds given in the task, the maximum sum is about $$$25000 \cdot 10^9 \approx 2 \cdot 10^{13}$$$, which is outside the usual valid range for int (up to ~$$$10^9$$$).

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      OMG, thank you so much.

      I'm new to C++, I used Python before and didn't have to worry about using ints or longs lol.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why my solution gives TLE on problem E.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Looks like you’re unnecessarily memset-ing the entire dp table every time instead of only up to N, which could be slow.

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I removed memset and did the same manually Accepted solution, why it works now? Can you please explain. Thanks btw. :)

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Before you were filling the entire MAXN (3000) dp table everytime which is too slow, instead of filling only up to n for that test case

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the solution of C which has O(n^2) complexity?

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Problem C can be solved in O(NlogN) too. If you look carefully at the given test cases, all the solutions are obtained through reversing a suffix of the sequence 1 2 3 4 ... n. So it was deducible that the best possible answer will have a certain suffix reversed, but which suffix ? For that I calculated value of (∑ni=1pi⋅i)−(maxnj=1pj⋅j) for all possible suffix reversed sequences. Here is a simulation for n = 11:

For the array : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 :: 1015
For the array : 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 :: 1029
For the array : 1 2 3 4 5 6 7 8 9 10 11 12 15 14 13 :: 1040
For the array : 1 2 3 4 5 6 7 8 9 10 11 15 14 13 12 :: 1048
For the array : 1 2 3 4 5 6 7 8 9 10 15 14 13 12 11 :: 1051
For the array : 1 2 3 4 5 6 7 8 9 15 14 13 12 11 10 :: 1049
For the array : 1 2 3 4 5 6 7 8 15 14 13 12 11 10 9 :: 1040
For the array : 1 2 3 4 5 6 7 15 14 13 12 11 10 9 8 :: 1024
For the array : 1 2 3 4 5 6 15 14 13 12 11 10 9 8 7 :: 999
For the array : 1 2 3 4 5 15 14 13 12 11 10 9 8 7 6 :: 965
For the array : 1 2 3 4 15 14 13 12 11 10 9 8 7 6 5 :: 920
For the array : 1 2 3 15 14 13 12 11 10 9 8 7 6 5 4 :: 864
For the array : 1 2 15 14 13 12 11 10 9 8 7 6 5 4 3 :: 795
For the array : 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 :: 713
For the array : 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 :: 616

Notice that plotting the values (∑ni=1pi⋅i)−(maxnj=1pj⋅j) against the starting number(position) of the suffix reversed we get a Bitonic function!

Thus all we needed to find was the beginning of the suffix for the largest answer, or more simply the bitonic point, which can be done in log N time using binary search.

Here's my solution(218593697) for problem C.(I didn't even look at the time limit given and assumed it to be <= 1 second based on the constraints. Thus, spend unnecessary time on this optimized solution).

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I was trying to solve problem D with dsu, but I was missing an important part of the algorithm. Can someone tell me if it's possible to determine does point X belongs to some of N segments in O(log N) or O(1). Thank you in advance

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    1) Yes, it can be done. Let's sort all segments $$$(l;r)$$$ with condition $$$l_{i} \le l_{j}$$$ for $$$i \le j$$$. Ok, now we can do this by binary search:

    Let's find position $$$i$$$ with maximum $$$l_i$$$ with condition $$$l_{i} \le x$$$. For all $$$1 \le j \le i$$$ now condition $$$l_j \le x$$$ is correct. Let's just find maximum value $$$r_j$$$ on prefix $$$[1;i]$$$, and if $$$r_j \ge x$$$ result is YES.

    2) In this problem, we have offline queries, we can create event-type algorithm to calculate answer for all values $$$x$$$ in $$$\mathcal{O}(n\log{n})$$$.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for problem D, I tried representing each portal as a vertex and then found all connected components in the resulting graph, which consists of edges between vertices with overlapping ranges. I couldn't get AC. Did anyone try using this approach and how did you do it? Thanks!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I actually thought of this too and I also failed lol

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    Isn't graph will be too large? With $$$n$$$ vertex number of edges will be up to $$$\frac{n(n-1)}{2}$$$

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Since it can be observed that $$$r_i$$$ and $$$a_i$$$ are useless for each segment. I use $$$l_i$$$ to sort all segments($$$l_i; b_i$$$) and then use some kind of greedy to merge all intersecting segments. Then I only need to use binary search for each $$$x_i$$$ to find which segment is covering it.

    Although my approach isn't the same as yours, I hope it'll be useful for you. Here's my code:218556118.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C question can be solved in O(n) runtime. I noticed from the test cases that first, say k, elements of the permutation would be same as the index and the remaining n-k elements will be in reverse order of the remaining indices. i.e., the array will be 1,2,3,...,k-1,k,n,n-1,....,k+1. So we can just run a loop to see for what value of k the cost is maximized. As simple as that!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. that's what almost all people did
    2. it is a O(n^2), because u have to check sum for every k which is O(n)
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

IN problem B shouldn't the minimums be moved to array with smallest difference between second smallest and its minimum element rather than to smallest second smallest element????????????????????????

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No. Consider the case with two arrays $$$[1, 3]$$$ and $$$[3, 4]$$$. Your solution would suggest moving minimums to the second array leading to arrays $$$[3]$$$ and $$$[1, 3, 4]$$$ with $$$\mathrm{score} = 3 + 1 = 4$$$.

    The correct solution would suggest moving minimums to the first array leading to arrays $$$[1, 1, 3]$$$ and $$$[4]$$$ with $$$\mathrm{score} = 1 + 4 = 5$$$ which is larger.

»
15 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

https://codeforces.me/contest/1859/submission/218600658 O(n) solution for C. Approach of proof (not in English). Пусть f(n-k)=1^2+2^2+...+(n-k)^2, g(k)=(n-k+1)*n+(n-k+2)*(n-1)+...+n*(n-k+1). Тогда f(n-k) является максимумом скалярного произведения (1,2,...,n-k) и его перестановок, а g(k) является минимумом скалярного произведения (n-k+1,...,n) и его перестановок. Пусть M — максимальный элемент f,g. Мы ищем max(f+g-M)=max(k). max(0)=1^2+2^2+...+(n-1)^2=f(n-1). max(1)=1^2+2^2+...+(n-1)^2=f(n-1)=max(0). max(2)=1^2+2^2+...+(n-2)^2+(n-1)*n>max(1). max(2)-max(1)=n^2-n-(n-1)^2=n-1>0. max(3)=1^2+2^2+...+(n-3)^2+(n-2)*n+(n-2)*n. max(3)-max(2)=2n*(n-2)-(n-2)^2-n*(n-1)=n-4>=0 при n>=4. max(4)=1^2+2^2+...+(n-4)^2+2*(n-3)*n+(n-2)*(n-1), max(4)-max(3)=-(n-3)^2+2n^2-6n+n^2-3n+2-2n^2+4n, max(4)-max(3)=n-7>=0 при n>=7. max(k)=1^2+2^2+...+(n-k)^2+(n-k+1)*n+...+n*(n-k+1)-T, max(k+1)=1^2+2^2+...+(n-k-1)^2+(n-k)*n+...+n*(n-k)-S, max(k+1)-max(k)=-(n-k)^2+(n-k)*n+(n-k+1)*(-1)+...+n*(-1)-S+T= =-n^2+2nk-k^2+n^2-nk-k*(2n-k+1)/2-S+T= =nk-k^2-nk+k^2/2-k/2-S+T=-k^2/2-k/2-S+T k — четно => T=(n-k/2)(n-k/2+1), S=(n-k/2)(n-k/2), -S+T=n-k/2 => max(k+1)-max(k)=n-k-k^2/2. k — нечетно => T=(n-(k-1)/2)(n-(k-1)/2), S=(n-(k-1)/2)(n-(k-1)/2-1), -S+T=n-(k-1)/2 => max(k+1)-max(k)=n-k-(k^2-1)/2. Если n-k-k^2/2>=0 или n-k-(k^2-1)/2>=0 => max(k+1) — ответ. k^2+2k<=2n или k^2+2k<=2n+1 (k+1)^2<=2n+1 или (k+1)^2<=2n+2 k+1<=sqrt(2n+1) или k+1<=sqrt(2n+2) Подойдет значение [sqrt(2n+2)] или [sqrt(2n+1)], поскольку в ответ пойдет k+1, а не k. Если же вместо g(k) брать другую перестановку, тогда max(k+1)-max(k) будет выходить меньше, чем n-k-k^2/2.

»
15 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

For problem E, the editorial says "Now we can look at out dp states as a table, and notice that we recalc over the diagonal". Does this mean one must look for patterns, or is there a way to notice this recalculation mathematically? Thanks in advance!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Basically, from dp(i,j) you are making a move to dp(i-1, j-1). Which is considered a diagonal move.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

We can use Centroid Decomposition to solve problem F in $$$O(n\log n\log w)$$$.

Code: 218616904

It works faster than the common solution(with LCA).

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    That is cool.

    It probably is due to the fact that the average centroid tree height is small, so you really do less operations constant-wise.

    Thank you very much for this cool submission!

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

C can be done in O(1). It is a straightforward formula, that can be derived with a bit of paperwork. We can prove by induction that for every n, the max cost can be found by reversing the last 'k' digits while writing 1 to n in ascending order. Eg- 1 2 3 4 5 6 10 9 8 7{max cost case of n=10}. So if we consider the general case, cost = (1^2+2^2+...(n-k)^2)+{(n)(n+1-k)+(n-1)(n+2-k)....(n-k+1)(n)}-max((i from 1 to k)(n+1-i)(n-k+i)). max(i.e. the third term in above formula) can be calculated by AM>=GM. so the final expression of cost is cubic in terms of k, which is to be maximized by d(cost)/dk=0. thus we get a O(1) solution. you can check my submission to see the final formula{I don't know how to add the link}.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem D, there seems exists a $$$O(n)$$$ solution using dsu. Considering combining the interval $$$[l_i, b_i]$$$, and setting the ancestor of these elements to $$$b_i$$$. Consider 218626575.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Sorry for forgotting the time consumption of sorting, which costs $$$O(n\log n)$$$.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Two intervals are combined in a single set if they overlap. Can you explain how to construct dsu(specifically union)? Since there are n intervals, I'm performing O(n^2) comparisons to check whether two intervals overlap and perform union.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sure. The fact is that cheking for overlapping of intervals may be unnecessary. We can just combine these overlapped intervals in a single set, which means that all beginners in the set can reach to the right-hand side endpoint of the interval.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hey, here is my code for the problem E. The time complexity should be O(N*N), according to me. However, even if it is not the case, how can the program pass 21 tests and give a TLE on the 22nd test case? The passed cases already involve worst-case values (N=3000, K=3000).

Please let me know where I am going wrong.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Your solution is O(N^3). In general you have N^2 states and the transition from one state to another is done in O(N) in your memo function. If N = K there are only O(N) visited states since i = k for each. That's why it works on other test cases.

»
15 месяцев назад, # |
Rev. 22   Проголосовать: нравится 0 Проголосовать: не нравится

I am weak in mathematical notation. I have solved problem D but do not understand tutorial. I don't understand the mathematical notation of this line "Let ansi be the maximum coordinate we can reach while being on segment i, and let pj be the answer to the j-th query. Then we notice that the answer to query pj=max(xj,maxni=1ansi|li≤xj≤ri)". Can you please explain this part "pj=max(xj,maxni=1ansi|li≤xj≤ri)". Thanks in advance.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why does this code take 1500 ms?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell why am i getting run time error in D . submission — 218670993

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain why i am getting run time error in problem D. 218670993

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How 2 prove my C's solution? QAQ Just enumerate every i from 1 to n, flip the last k numbers of an ascending sequence of 1 to n, compute each answer and arrive at the maximum value, the final answer.

I don't understand why it's correct even I Accepted D:

»
15 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Here is a sketch of why the faster solution to C works:

First, consider permutations $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$y-1$$$, $$$n$$$, $$$n-1$$$, $$$\ldots$$$, $$$y$$$. In this case, the answer is basically $$$1/12 (2 n^3 + 6 n^2 y - 3 n^2 - 6 n y^2 + 6 n y - 2 n + 2 y^3 - 9 y^2 + 4 y)$$$, the maximum occurs at around $$$y=n+1.5+\sqrt{2n+1}$$$, or $$$y=n+1-\lfloor\sqrt{2n+1}\rfloor$$$.

Let $$$x$$$ be the maximum of $$$jp_j$$$. Then, $$$ip_i\leq x$$$, $$$i\leq n$$$, and $$$p_i\leq n$$$ implies $$$i+p_i\leq n+\frac xn$$$. Let $$$C=n+\left\lfloor\frac xn\right\rfloor$$$. Consider the largest possible value of $$$\sum_{i=1}^n ip_i-x$$$ over all permutations satisfying $$$i+p_i\leq C$$$. By the observation in the editorial (local swapping arguments), the maximum occurs when $$$p_1=1$$$, $$$p_2=2$$$, $$$\ldots$$$, $$$p_{C-n-1}=C-n$$$, $$$p_{C-n}=n$$$, $$$\ldots$$$, $$$p_n=C-n$$$. In this case, we compute $$$\sum_{i=1}^nip_i-x\leq\frac16 (n^3 + 3 n^2 y - 3 n y^2 + 6 n y - n + y^3 - 3 y^2 + 2 y)-ny$$$ where $$$y=C-n=\left\lfloor\frac xn\right\rfloor$$$ since $$$ny\leq x$$$. This is less than the construction given above when $$$y\leq n-2\sqrt n$$$. When $$$y>n-2\sqrt n$$$, the optimal permutations are very easy to characterize: since the part of the hyperbola $$$ip_i\leq x$$$ where $$$1\leq i\leq n$$$ and $$$1\leq p_i\leq n$$$ is very close to a line with slope -1, you must have $$$p_1=1$$$, $$$p_2=2$$$, $$$p_a=a$$$, $$$p_{a+1}=b$$$, $$$p_{a+2}=n$$$, $$$p_{a+3}=n-1$$$, $$$\ldots$$$, $$$p_{a+1+n-b}=b+1$$$, $$$p_{a+2+n-b}=b-1$$$, $$$p_{a+3+n-b}=b-2$$$, $$$\ldots$$$, $$$p_{b-1}=a+n-b+2$$$, $$$p_b=a+1$$$, $$$p_{b+1}=a+n-b+1$$$, $$$\ldots$$$, $$$p_n=a+2$$$, which is easily verified to be optimal in the equality case above.

The details are left to the interested GM.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Hii, guys I am new to codeforces, can anyone please guide me why my sol failed on 4th pretest even though i used same aporach as author?

Link to sol — Your text to link here...

int main() { int n; cin>>n; for(int i=0;i<n;i++){ int n_arr; cin>>n_arr; vector<vector> v; for(int j=0;j<n_arr;j++){ vector temp; int sz; cin>>sz; for(int k=0;k<sz;k++){ int tp; cin>>tp; temp.push_back(tp); } sort(temp.begin(), temp.end()); v.push_back(temp); }

vector<int> abc;
  int mn = v[0][0];
  for(int j=0;j<n_arr;j++){
    mn = min(mn, v[j][0]);
    abc.push_back(v[j][1]);
  }

  sort(abc.begin(), abc.end());

  int ans = mn;
  for(int j=1;j<abc.size();j++){
    ans+=abc[j];
  }

  cout<<ans<<endl;
}
return 0;

}

Thank you for help!

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

O(log n) solution of C log factor is due to sqrt

218710354

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How my $$$O(n^4)$$$ solution passed in C ?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How my $$$O(n^4)$$$ solution passed in C?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm unable to upsolve the problem D by my own. And I have no idea why my solution isn't working. Can anyone suggest me some similar types of problems? Thanks in advance.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Problem E, had the problem ask for the minimum instead of maximum, is it still possible to solve it given the constraints? Maybe I'm missing something obvious.

»
15 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

I'm attempting a proof for the C solution using pattern: $$$1,2,3,4, ... , x−1,n, n−1,n−2, ... , x$$$.

Please feel free to comment/add/correct/improve.

1.If $$$n$$$ is paired with $$$x$$$, then $$$x$$$ is paired with $$$n$$$.

Proof

2.Pairings do not cross.

Proof

3.If $$$n$$$ is paired with $$$x$$$, then $$$n-1$$$ has to be paired with $$$x+1$$$ (if $$$n-1>x+1$$$).

Proof

To summarise, if the optimal solution contain pairing $$$n \rightleftharpoons x$$$, then the given pattern would be the best.

»
15 месяцев назад, # |
Rev. 5   Проголосовать: нравится +7 Проголосовать: не нравится

jiangly's solution to problem C using DSU was also O(n^3) if not better. (I don't really understand amortised analysis at all).

After fixing $$$M$$$ and noticing that the greedy strategy of giving the highest available position to the numbers $$$n,n-1,...,1$$$ (in that order) is optimal, he used DSU to build the permutation in linear time.

For every n, the highest/rightmost position that satisfies that $$$p_i\cdot i$$$ will be $$$min(n,M/i)$$$.

If this highest position is available, then the value of its parent(as in DSU convention) is going to be itself and we can simply put $$$p \in P$$$ to this position. After doing so, we update its parent as the preceding position (via the merge/union operation). Doing this has the effect that, for all future elements that could have theoretically taken this position, are nudged to take the preceding position instead until they do find an empty position.

Overall, the idea was that we maintain the highest available position as the parent of the currently "formed" part of the permutation. So, whenever a theoretical rightmost position is pre-occupied, then the highest available position can be used up.

Implementation details: Omit union-by-rank/size heuristic because we want a very specific type of union such that we make the preceding position (even if it had a rank/size = 1 only) as the parent of a position we just filled up.

jiangly's submission 218527131

my submission (if useful to anybody) 218844879

UPD:: Afterthoughts, this is pretty much the same thing as the use of stack in the editorial. Complexity should be same/similar.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is this code giving TLE for Problem D. I used a different approach from the one given in the tutorial, but Time Complexity wise, it is still the same. I could optimise it as much as I could. Any thoughts?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O(N^2) Solution for problem C Link : SUBMISSION LINK

Idea : we will go for the following pattern : n = 6 6 5 4 3 2 1 1 6 5 4 3 2 1 2 6 5 4 3 1 2 3 6 5 4 1 2 3 4 6 5 1 2 3 4 5 6

Calculate answer for each in O(N^2) and take maximum.

»
15 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

O(N^2) solution for problem C. Link : SUBMISSION LINK

Idea : We will go for the following pattern - n=6

  • 6 5 4 3 2 1
  • 1 6 5 4 3 2
  • 1 2 3 6 5 4
  • 1 2 3 4 6 5
  • 1 2 3 4 5 6

We will calculate answer for each and take maximum.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the O(n^3) solution of problem C for me, I can't understand what the stack does there and can't figure out how it makes the time complexity to O(n) in the loop

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi!

    First we notice the solution which uses $$$std::set$$$, where we greedily pick the maximum available while iterating from $$$N$$$ to $$$1$$$.

    Now let's do the following — we say that we can pair each number $$$k$$$ from $$$1$$$ to $$$N$$$ with the following prefix: $$$[1; \lfloor\frac{mx}{k}\rfloor]$$$, where $$$mx$$$ is the current maximum which we are iterating over. We can notice that we always pair the number with the highest available — so, for each index $$$i$$$ we create a vector of numbers which "become available" for all indexes $$$k \leq i$$$. Then we just use stack to maintain all available elements in descending order.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me understand the optimisation in Que E?

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi!

    The idea is that $$$|x| = max(-x, x)|$$$, and we can use this to simply consider different cases of modulos instead of always doing it correctly.

    After that we use a simple vector to store the maximum sum.

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

in D I did binary search + dfs (also it's kinda dp)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello,

I think in the editorial of the First Problem "United we stand", writer have missed to add "end of line", while displaying two arrays.