### BledDest's blog

By BledDest, history, 3 years ago, translation,

• +37

 » 3 years ago, # |   +6 Good contest, Problems are interesting.Thank you BledDest, 0n25, PikMike for contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!
 » 3 years 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.
•  » » 3 years ago, # ^ |   0 I also don't get editorial's intervals, but consider these: 3 1 3 5 7 2 6 
•  » » » 3 years ago, # ^ |   0 Thanks, got it.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I didn't get it. Shouldn't this also work while storing only l and r?
•  » » » » » 5 weeks ago, # ^ |   0 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
•  » » » 3 years ago, # ^ |   0 Why is it enough to take only (l — 1) as the additional case?
 » 3 years 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.
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +8 Why would you think that being red has anything to do with proving algorithms? :)
•  » » » » 3 years 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. :)
•  » » » » » 3 years ago, # ^ |   0 I think so,too :)
 » 3 years ago, # |   0 For D, why do we have to run the query loop from reverse?
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   0 Thanks!
 » 3 years ago, # |   0 Can somebody explain more on how to solve D online using Cartestian tree please?
•  » » 3 years 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
•  » » » 17 months ago, # ^ |   0 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?
 » 3 years 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 !
•  » » 3 years 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 i was eagerly waiting for this ! you made my day thank you :)
 » 3 years ago, # |   0 Can I get an explanation of the mathematical formula in C?
 » 3 years ago, # |   0 plz explain problem C ??
•  » » 3 years ago, # ^ |   0 a cycle will form for long k due to same previous moves gonna get repeated again and dif=idx2-idx1
 » 2 years ago, # |   0 In problem E , Can someone explain why only taking l-1 will suffice for correct answer?
•  » » 2 years 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.
•  » » » 2 years 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..
•  » » » » 2 years 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.
 » 9 months ago, # |   0 Problem D video tutorial: https://youtu.be/0SElCl68xeI
 » 9 months ago, # | ← Rev. 3 →   -8 Thanks for a good editorial!
 » 8 months ago, # |   0 Hi,BledDest Please explain problem E, why we need l-1 inserted to compress the set. Thanks.
 » 6 months ago, # | ← Rev. 3 →   0 I saw a very different and simple idea to solve E just by sorting pair :submission link: https://codeforces.com/contest/863/submission/78505254 jai1234The 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 !!
 » 13 days ago, # |   0 Can anyone please implement E using a sparse table?