BledDest's blog

By BledDest, history, 3 months 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  

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

Good contest, Problems are interesting.

Thank you BledDest, 0n25, PikMike for contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

»
3 months 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.

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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? :)

      • »
        »
        »
        »
        3 months 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. :)

»
3 months 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?

  • »
    »
    3 months 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.

»
3 months 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?

  • »
    »
    3 months 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

»
3 months 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 !

  • »
    »
    3 months 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.

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

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

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

plz explain problem C ??