BledDest's blog

Educational Codeforces Round 29 — Editorial
By BledDest, history, 7 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +37
  • Vote: I do not like it

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

Good contest, Problems are interesting.

Thank you BledDest, vovuh, awoo for contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

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

For problem E, can you elaborate why storing l and r is not enough? I don't notice anything special about the intervals you listed.

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

    I also don't get editorial's intervals, but consider these:

    3
1 3
5 7
2 6
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, got it.

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

        I didn't get it. Shouldn't this also work while storing only l and r?

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

          3 years late but here I am, in case anyone has the same question. If you try to draw this test case (a line with the segments covering their respective spaces), you'll see the segment [1, 2) of the line would be uncovered if you were to remove the TV [1, 3], for example. As the size of the range [1, 2) is not 1 (**not an integer**), we can safely remove it and the answer would be valid. The same would happen if we were to remove segment [5, 7], as it would uncover (6, 7], so it would also be a valid answer

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

      Why is it enough to take only (l — 1) as the additional case?

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

For F, my solution passed, but I'm not exactly sure why it works.

Basically, for 1 ≤ i ≤ n,  there exist optimal li and ri such that li ≤ ai ≤ ri. First set ai = li for all i. Then while there exist i, j such that cnt(i) > cnt(j) + 1,  then we try to change one occurrence of i to j. This terminates when we find that we cannot make any more changes.

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

    Wow, I always thought that to get the red color you should prove the algorithms before writing and do a lot of things that I don't do, maybe I have a chance of get the color.

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

      Why would you think that being red has anything to do with proving algorithms? :)

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

        If you will solve a problem and know that your idea is right by a formal reason you gonna probably receive AC, but if you use pure intuition ( what I am doing in everything) you can receive a lot of verdicts and waste a lot of time coding for nothing. Also this can be just something that I thought to accept my rating. :)

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

For D, why do we have to run the query loop from reverse?

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

    The positions in input are the final ones. And by applying the last query you translate them to the positions before the last query. Thus after all queries applied you get the positions from before all the queries, numbers at these positions are the ones you are actually asked for.

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

Can somebody explain more on how to solve D online using Cartestian tree please?

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

    Is Cartestian tree much like a non-rotate treap?(in mainland we call it fhq-treap)

    If it is like that...then you could write such tree,

    for operation 1,you can split the whole tree into two parts:a-[1,r],b-[r+1,n]then split the [1,r] to c-[1,l-1],d-[l,r]then split the second part to lef-[1,r-l],rgh-[r-l+1,r-l+1](maybe draw a picture of segment is useful...) then,you can merge those segment like this:merge(merge(c,rgh),merge(lef,b))(means just swap the lef and rgh in original tree,because lef is the first element in the segment[l,r],as you see);

    for operation 2,you could just give a tag means reverse(a little like lazy tag in segment tree)to the certain segment(it can be got from split the tree to[1,r],[r+1,n] then split the first part to [1,l-1],[l,r],then now the second part is the segment we will perform the operation),and be careful when you merge or split something,you should push down such tags.Then queries can be given answer as find the b_i th number in the tree(it's also easy in such treap...you can just jump to the left child or the right child depends on the condition.)

    Here is the code in this method

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

      for operation 1: lef and rgh splitting is vague to me. let d[3,7], then according to code:split(d,7-3,lef,rgh). I think it means lef[3,4] and rgh[5,7]. but should be lef[3,3](the first element in the segment) rgh[4,7]. can you please explain?

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

i have a doubt in problem D suppose we skip a query(as the considered position is outside the range) and after second query suppose we land on another position . Now, how can we say that we don't need the first update as it may happen that the position we are currently at is in the range of first update , so, it's value is not that we are considering !

I know i am missing something please correct me !

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

    Like the tutorial said.In the reverse version, We consider which position will the ith number land on, but NOT which number will land on the ith position. To solve the former problem, Obviously we can just ignore the "outside" queries each time. That is to say, every number in the old array has its specific position in the new array. We can follow the same strategy to recover the original positions.

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

Can I get an explanation of the mathematical formula in C?

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

In problem E , Can someone explain why only taking l-1 will suffice for correct answer?

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

    3

    1 7

    0 3

    5 8

    This should give -1 but it might output 1 if you don't consider l-1.

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

      Yes , I know ... thats not what I am asking , I know why we are adding l-1 , so that we can take care of some "gaps" that may come in between .. but my question is there a proof as to why only l-1 will do ? why cant we take r+1 as well ....

      I am asking for the proof that taking l-1 is both necessary and sufficient!

      Thanks by the way, almost forgot about this..if you get any idea, post here , any source or your thoughts..

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

        Yes, instead of l-1 you can also take r+1 and there are AC codes taking r+1.

        You can prove that all the "gaps" are included in the compression by taking (l-1)'s. Let's consider every pair of segments (l1, r1) and (l2, r2). If l1==l2 there's no gap between these two, if l2>l1 let's swap the segments so that we can consider l1<l2.

        Then if r1 >= (l2 — 1) it can be seen that there's no gap between these two segments. Then r1 < (l2 -1) must be true and therefore we can pick (l2 — 1) node which well be our "gap" node in compression.

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

Hi,BledDest Please explain problem E, why we need l-1 inserted to compress the set. Thanks.

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

I saw a very different and simple idea to solve E just by sorting pair :

submission link: https://codeforces.net/contest/863/submission/78505254 _Jupiter_

The Idea Used : In sorting the pair with lesser first val(p.fi) is placed before but pair with equal first value are sorted non-increasingly and then just by checking for everypair answer could be find !!

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

Can anyone please implement E using a sparse table?

→ Reply