### BledDest's blog

By BledDest, history, 13 months ago, translation, ,

•
• +37
•

 » 13 months ago, # |   +6 Good contest, Problems are interesting.Thank you BledDest, 0n25, PikMike for contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   0 I also don't get editorial's intervals, but consider these: 3 1 3 5 7 2 6 
•  » » » 13 months ago, # ^ |   0 Thanks, got it.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 I didn't get it. Shouldn't this also work while storing only l and r?
•  » » » 13 months ago, # ^ |   0 Why is it enough to take only (l — 1) as the additional case?
 » 13 months ago, # |   +8 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.
•  » » 13 months ago, # ^ |   +3 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.
•  » » » 13 months ago, # ^ |   +8 Why would you think that being red has anything to do with proving algorithms? :)
•  » » » » 13 months ago, # ^ |   +8 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. :)
•  » » » » » 12 months ago, # ^ |   0 I think so,too :)
 » 13 months ago, # |   0 For D, why do we have to run the query loop from reverse?
•  » » 13 months ago, # ^ |   0 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.
•  » » » 13 months ago, # ^ |   0 Thanks!
 » 13 months ago, # |   0 Can somebody explain more on how to solve D online using Cartestian tree please?
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 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
 » 13 months ago, # |   0 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 !
•  » » 13 months ago, # ^ |   +1 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.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 i was eagerly waiting for this ! you made my day thank you :)
 » 13 months ago, # |   0 Can I get an explanation of the mathematical formula in C?
 » 12 months ago, # |   0 plz explain problem C ??
•  » » 9 months ago, # ^ |   0 a cycle will form for long k due to same previous moves gonna get repeated again and dif=idx2-idx1
 » 5 months ago, # |   0 In problem E , Can someone explain why only taking l-1 will suffice for correct answer?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 3 1 7 0 35 8This should give -1 but it might output 1 if you don't consider l-1.
•  » » » 4 months ago, # ^ |   0 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..
•  » » » » 4 months ago, # ^ |   0 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 — 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.