Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Разбор задач Educational Codeforces Round 29
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 12:17:11 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
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 l and r is 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
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 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.
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. :)
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.
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 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
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.
Can I get an explanation of the mathematical formula in C?
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.
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.me/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.me/contest/863/submission/111509228