Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 203 |

3 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 29

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/28/2021 15:25:28 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Good contest, Problems are interesting.

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

For problem E, can you elaborate why storing

landris not enough? I don't notice anything special about the intervals you listed.I also don't get editorial's intervals, but consider these:

Thanks, got it.

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

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

can anyone explain this line in problem E

Now moments of time are up to 6·10^5constrains for l and r are up to 10^9 then why 6* 10^5 ?

I'm late but the question was good, so, the editorial started with "Firstly lets compress the moments of time", that means we are creating a map to store the values of time. This will help us in such a way that if we want to iterate over all the numbers from 1 to 1e9 (10^9), then after making map, now we have to iterate only over the keys of map that are 6e5 (6*10^5) in numbers eliminating all those unnecessary numbers in expanse of some memory.

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

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

Basically, for 1 ≤

i≤n, there exist optimall_{i}andr_{i}such thatl_{i}≤a_{i}≤r_{i}. First seta_{i}=l_{i}for alli. Then while there existi,jsuch thatcnt(i) >cnt(j) + 1, then we try to change one occurrence ofitoj. This terminates when we find that we cannot make any more changes.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.

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

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. :)

I think so,too :)

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

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.

Thanks!

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

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

lefandrghin 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

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?

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 !

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.

i was eagerly waiting for this ! you made my day thank you :)

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

plz explain problem C ??

a cycle will form for long k due to same previous moves gonna get repeated again and dif=idx2-idx1

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

3

1 7

0 3

5 8

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

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..

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.

Problem D video tutorial: https://youtu.be/0SElCl68xeI

Thanks for a good editorial!

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

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

submission link: https://codeforces.com/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 !!

Can anyone please implement E using a sparse table?

I tried to do that but it seems that the range of data is too large.

Maybe I use sparse table in a wrong way

https://codeforces.com/contest/863/submission/111509228

as I understand the question of E: it means that we find a segment [a,b] such that after removing this segment, the remaining segments still cover every integer points which is the union of the available segments?

=> we can remove either 1st or 2nd segment?

we can remove 2nd segment since the remaining [1,2] and[3,4] cover {1,2,3,4}?