induk_v_tsiane's blog

By induk_v_tsiane, history, 15 months ago, translation, In English

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!

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

| Write comment?
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for fast editorial!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your texts!

»
15 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

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

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

      What is the O(N) idea?

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

        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 months ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        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 months ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        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 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      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

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

        @eric.dai.kj yeah even i did same by obervation, but do we have any proofs for it

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

      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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the O(N^2) idea?

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 months ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Read about int and long long datatype in c++

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

      Thanks for noticing. I didn't consider the sum being greater than 10^9. Spent last 30 minutes debugging the solution when the answer was out there.

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

    I think, use long long, the sum can excess int

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

    In my opinion,I always use #define int long long so I don't need to care that I use int or long long.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

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

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

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Very entertaining round keep it up :)

»
15 months ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    the stream is proving the statement uwu

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +48 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Bruteforcing all permutations of 250 elements goes brrrr

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No it's impossible as 12! is already 479001600, which is very large, we need to realize this. Then brute force for a permutation takes O(n^2) time.

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +33 Vote: I do not like it

        Bruh why do we need the table then?

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

          because I had been generating 10 first permutations and realize the pattern, so I pre-calculate all and submit then pray for luck, luckily it's Accepted lol

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it +23 Vote: I do not like it

            Couldn't you submit the program that calculates answers instead of the table?

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

              you can visit my profile and look at my submission for C, it still have the precalc part

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it +27 Vote: I do not like it

          Bro had to calculate answers by hand.

          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            yes, to be honest I don't like this way, it makes me have feeling of cheating. But I couldn't think of proper way, so I had to do like this, isn't it a wise choice :)

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

        Yes but $$$t\leq{30}$$$

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

          I'm telling that generate all permutation is impossible, not O(n^2) is not good enough

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    What if we use 100% of our brain:D

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    XD

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    I used stack for problem D

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

      Can you elaborate?

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

        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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Minus delta :(. Btw fast editorial.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for editorial!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it +26 Vote: I do not like it

pattern recognition forces

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

    Nah only C was pattern (and it was also unintended, the actual solution looks very legit)

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 5   Vote: I like it +21 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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 months ago, # |
  Vote: I like it +94 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
15 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my solution gives TLE on problem E.

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

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

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

        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 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually thought of this too and I also failed lol

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

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

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No it's O(n) only. For any k, you can write a mathematical expression for the sum of last n-k elements instead of looping through it. Also to find the max element, it will be the middle element of last n-k elements, which can be done in constant time. Check out my solution at https://codeforces.me/contest/1859/submission/218596825.

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

        is it possible for you to post a proper Mathematical proof for this series sum which then can be done in O(1) for every k.

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

        my bad, I didn't think about formula

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 months ago, # |
Rev. 22   Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this code take 1500 ms?

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

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

218710354

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 5   Vote: I like it +7 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand the optimisation in Que E?

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

    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 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.