Привет, Codeforces!
Мы рады пригласить вас на наш экспериментальный раунд для трёх дивизионов, который пройдет в 22.10.2023 14:05 (Московское время). Обратите внимание на нестандартное время начала раунда . В каждом дивизионе будет предложено по 5-7 задач. Раунд будет проведён по правилам Codeforces, будет рейтинговым для всех трёх дивизионов. Немного изменений относительно рейтинга участников в этом соревновании:
- В Div.3 рейтинг участников меньше 1600.
- В Div.2 рейтинг участников от 1600 до 2099.
- В Div.1 рейтинг участников не меньше 2100.
- Обратите внимание, что после Codeforces Round 904 (Div. 2) рейтинг не будет пересчитан до окончания этого соревнования.
Отметим, что параллельно в этот день будет проходить две командные олимпиады, по задачам которых и составлены раунды:
- XXI Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП.
- III Открытая командная олимпиада ЮМШ по программированию.
Также хотели бы поблагодарить всех, кто оказал бесценную помощь в подготовке этого раунда:
- Координаторов Artyom123 и Vladosiya за отличную координация и полезные советы.
- Авторов задач 74TrAkToR, Mangooste, TheEvilBird, Tikhon228, teraqqq, valerikk, Dmitry07.
- Тестеров pavlekn, zwezdinv, plagues, JuicyGrape, Maks_Simenkov, orolik, tmari_sun, OR_LOVe, NicoRobin, TimVen74, zarubin, myav, ctraxxd, Gassa, OAleksa, Acanikolic73, AndrewPav, AlphaMale06, NemanjaSo2005, dorijanlendvaj, defnotmee, meOwO, mzen, CIXTEEN, malachi_toney_goat, gotexans, FairyWinx, v0s7er, adepteXiao, induk_v_tsiane, Alexdat2000, Be_dos, mr.kolya, kevinxiehk, alexxela12345, mutant, allvik66 за качественное тестирование раунда!
- MikeMirzayanov за прекрасные системы Codeforces и Polygon.
Желаем всем удачи и высокого рейтинга!
UPD: Одна из задач будет интерактивной, поэтому, пожалуйста, прочитайте руководство по интерактивным задачам перед контестом.
UPD: Разбалловка:
- Div.3: $$$500-1000-1500-1750-2500-2750-(1750+2000)$$$
- Div.2: $$$250-500-1000-(750+1250)-2250-2750$$$
- Div.1: $$$(250+500)-750-1000-1250-2000-2750$$$
UPD: Разбор
UPD: Мы перетестируем решения задач div3F и div2C. Это может внести небольшие изменения, рейтинг будет пересчитан позднее.
UPD: Перетестирование заняло несколько минут. Теперь все результаты корректны:)
As a tester I tested the round and it was a fun one!
"Please note that after Codeforces Round 904 (Div. 2) the rating will not be recalculated until the end of this competition.". Does that mean that our div in round 905 will be determined by rating before round 904?
Yes
If one's division changes after round 904, will round 905 be unrated for him?
No. It has happened before that if someone with a rating > 1600 gives a div3 contest and loses rating even though it should've been unrated for them.
No. If you participate in the round 905, it will remain rated for you regardless your results in the 904.
Thank you!
As a tester I recommend you to read all the problems
I'm proud to be a tester of the first div123 round on Codeforces ever, and I recommend you participate in it
As a tester I can say only that the tasks are really interesting and well-balanced! Don't forget that it is the first div123 Codeforces round ever, so why not to participate in it? Good Luck!
Is Div 3 will based on ICPC like prevoius Div 3 round or rather it will follow Div 2 Pattern
same question..
I am a tester.
Finally standard rule of Div3 and 2100+ Div1! Exciting!
will div3 follow icpc rules or div2 like score rule?
May be we could soon see (Div1,Div2,Div3,Div4) happening at once just like this.
it'll be really weird though, since div 3 would just be clash of specialists
.
I agree, hopefully we'll see 1+2+3+4 one day.
OMG first div123 ever!
First time div 1,2,3...... 1600~2099 div 2Hopefully it will be interesting..
Will there be score distributions(especially Div.3)?
It isn't a good idea for 2 contests on the same day. Because #905 is based on a competition, maybe we can move #904 to another day?
no, since #904 is also based on a competition.
This round div3 equal to div4.
how do you know
i can register on both div 2 and div 3. What if i spam wrong solution on div 3 then submit the right one on div 2?
I have a 50% chance to wake up early enough for this contest :)
Looking very interesting round, the first Div.1,2,3 contest on codeforces.
Good luck to everyone!
The average strength of the opponents will be very high in this Div1, and I'm very afraid. Should I participate in？
Same for the Div.2 :(
So for the first time div 3 won't follow icpc rules. Very interesting
Score distribution is so weird.
does each div have questions that are on other divs? like is div3G the same as div2D and div1A ? or each problemset is unique
So why is there a 3 problem difference between Div.1 and Div.2? Is it because purples are now in Div.2?
This is not related to rating or anything, they need to set a big range difference if they have a large amount of tasks or else they will need to increase the number of tasks per division
For Div1?2?3?Or for all Div 1,2,3?
this is a historic moment
First ever Div 2. that I've not been able to participate in because of my rating :/
I don’t understand if div3 will be rated for me if I raise the rating to div 2?
the delta will not consider round 904 when distributing rating, so it is a good chance to boost up
oops
“Please note that after Codeforces Round 904 (Div. 2) the rating will not be recalculated until the end of this competition.”
Does that mean even if I become Master now I should still participate in Div.2?
You can't become master before round 905, because we will calculate ratings for both 904 & 905 only after 905's end.
But what about our profile, sir? won't there show that an expert attending a div3 ?
bruh he just said the ratings will be given after 905 ends
bruh it link was my question answer (: i knew what u said (:
So excited for this contest. Best of luck everyone...
After this round ends and the round 904 rating is calculated, will the seed for calculating round 905s rating be based on the final rating after 904? Or will both of these be calculated in parallel and added to current rating?
I wish I can AK!!!
Speedforces
One of the best contests i have ever had :)
Was it just me or div2 A seemed harder than usual and div2 E was easier than div2 D?
Seems like a good system going forward, let's keep using this for future rounds. It should also deal with rating volatility better IMO.
Maybe even div2+div3 rounds when we only have a div2.
Round being shorter dealing with rating volatility is stupidest opinion I've ever heard.
Short rounds are better, my point wasn't about them still.
Division distribution is far better.
True but preparing such a large problem set is hard
Guys, please help. My solution on D3E fails on 4th test. Can anyone spot the mistake? 229288636
rip, didn't see you could reorder in D1. It's a very easy problem for its position
Can we not make round 2h for absolutely no reason? Ok thanks.
2h is the normal round duration... Can we not make rounds longer for absolutely no reason?
Does actually wanting to try out harder problems in a contest not count as a reason?
+1, 2h was too short for this round imo.
statment in Div2D is really confusing for me
Thanks for the great contest! gonna hit expert this round :)
couldn't anyone explain, why in the last example test, answer is 28? Div2, C
Make sure you are not double counting the same segments. (I was getting 26 instead of 28 in the last test of pretests).
Segments [1;2], [1;4] — [3;4], [1;5] — [4;5], [9;10], [8;10] — [8;9], [7;10] — [7;8], [3;10] — [3;4] are bad segments, plus amount of repeating numbers (segments of length one) in total equal 29, but actually I double counted segments
7,2and7,2,3, so the amount of good segments is 28.Basically if you have 2 repeating numbers somewhere in your array, a good segment can't end at the repeating number that comes before, and can't start at the repeating number that comes after
thx Ryan, I had the same mistake..
Why is my solution TLE on E?
because it is $$$O(km)$$$ in worst case.
mb ty
Can you someone give some hints on how to solve div3 D?? dont know which data structure or approach to take..
You always only need to know if the shortest end time <= the longest start time for the segments. If so then print yes else print no
This is how I solved it. Maintain a multiset of all left borders and a multiset of all right borders. For each query binary search on the right border, if there exists a right border greater or equal to the current middle value of binary search and there exists a left border strictly greater than the found right border, the answer is yes. If you dont find such right border, the answer is no; Submission: 229250762
or you can make a custom comparator for right border multiset which will eliminate the need for binary search.
If there is some right bound which has smaller coordinate than some left bound, the answer is YES. Otherwise its NO.
Now you need some data structure that can store all bounds that are still not removed and return the smallest/greatest one.
Yeah, so basically you can maintain two multisets
startsandends, then for every operation ifstarts.size()(orends.size()) is<2, the answer isNO, otherwise we can check thatmin{end} < max{start}(think about why this works by drawing intervals on a paper or something), if this is true then the answer isYES, elseNO.Here is my submisison for reference.
Nice contest, I almost made it to E, and now we have to wait one more week till the next div2 TT.
Div2 C >>> D1, D2
I found the hacking system is much more enjoyable in this Div1+2+3. In the past div2 rounds, I often found participants in my room only solved A, and there is not much to do, but in this round there are 3 participants in my room solved A-E and many others solved A-D.
Maybe CF should consider arranging participants with similar rating in the same room in the future rounds?
Maybe Div2 D1/2 is much easier than Div2 C , only in my opinion.
So I think take part in Div1 is a better choice for me,probably.
But I'm quite far from Master. :(
I quickly came up with an approach of C, but it took me a while thinking about D2. In my opinion, D1 < C < D2
Problem difficulty in Div1:
B < D < C < A.
One of the most intense contests in my life
Thanks to the authors for having
div1, div2 and div3 at the same time
another div2 on the same day!
Here is my advice about the problems (div2) :)
I think that this problem was a decent div2 A but the A from the div2 this morning was much better imo (shorter implem, more "idea" than casework...)
This problem was a bit too easy as B as k <= 5 kinda spoils everything (although I liked the problem). I still prefered the B from this morning, which was, in my opinion, perfect as a div2 B.
This is definitely too easy for div2 C (I personally spent more time on A than on C). I still liked the problem but yeah, it's too easy I think.
I liked D2 a lot, it is pretty cool that depending on how you solved D1, your solution generalises differently to D2. It was most likely perfect for this spot.
I didn't have time to read it during the contest but I just solved it and I think it's a pretty cool problem. It is a bit rare to see shortest paths problems (as most of the things are usually well known), I like the fact that expressing clearly the problem ("we want to find the earliest key moment to get to a node...") mostly solves it!
Overall I think that it was a good round! I'm looking forward to another russian olympiad round :)
You can try to first solve D2 instead of D1 next time as I did this time :)
I guess I'll try that :)
(or solve A faster to have time to do E :clown:)
I think problem B from this morning is enough for problem C. I feel this B in actually the normal difficulty of a div2 B.
Don't use unordered_map without custom hash... lesson learned
Which calls for hacks... :(
I am considering accepting the $$$O(\log(n))$$$ and going with the ordered versions.
By the way, I wonder what are people's opinions about the format of cf rounds. I think that it was pretty cool having div1, div2 and div3 separated to make the problemset more adapted to each division.
However, I think it would be cool to make the contests at bit longer, like 2h or 3h to avoid having one or two problems that are mostly solved by alts/new accounts and not tackled by others.
I think a separate division for expert + CM should be used more often in the future because it makes the experience a bit more enjoyable for people in those rating ranges (e.g. less complacency at the end of contests).
But I think maybe in such cases we should set problem A to be the difficulty of a typical div2B, problem B should be like an easy div2C (1400), etc.
Yeah you're right, I think they should try this format and see how it goes
As a Div1 participant, I like this format rather than usual(Div1,2).
anti-unordered system tests? That's not very nice is it(
It seems that problem F in this round is just the same as this problem. Is this just a coincidence?
Pleasant limits in div2C. Nice day to the author for impeccable time limits and wonderful pretests!
std::unordered_mapstd::mapKinda same thing, still don't understand what happened. Curious if somebody can clarify why did that happen. (ExTrEmE AmoUntS of ClariFiCation is required) 229253714
In C++ unordered structures use default hashes unless you explicitly replace the hash. For int default hash is just int's value, so if you add a lot of elements with the same residue over some known modulus, the operations will start taking linear time and the solution will get TL. Didn't expect the authors to inlcude such tests though
Why would anyone include such tests without putting some in pretests, this is retarded
I found an argument suggesting people should use
unordered_*with extra care on CF: https://mirror.codeforces.com/blog/entry/62393It is possible that Test 17 is a hack.
I think so, a constant log(10^5) * 5 = 80 looks like something unimaginable for
std::unordered_mapin basic cases...This is at least not pretty, in relation to the participants of the round, to use antihash tests only in systests
Got FST because of this as well...
Div2C(Div3F) has testcases for anti-unorderd_map for C++. For example, testcase16 contain only
107897 * nas follows.how sweet it is :) the author of the problem (test) is probably very funny
He is thou
All the love from the bottom of my heart to the autors for accepting some python O(nlogn) solutions over c++ hashes
Div3 E: https://ideone.com/whDTDf
Does it gives wrong answer because I updated the values in the array, so it overflows, or this is not the reason ?
.
why does a basic while(a[i-1]>a[i])a[i]*=2, count++ not work? Please give a tc where this fails. also what's the intended solution?
number of operations can be large so a[i] can overflow 229293522
After all this time
229221092
maybe CF should add a new tag call "understanding" lol
I solved problem A in div3 correctly (that was the only problem I solved, and my only submission) but got my rating reduced by 65, pls does anyone know why this could have happened?
I'm not sure if there was an update after this, but in general:
https://mirror.codeforces.com/blog/entry/20762
https://mirror.codeforces.com/blog/entry/77890
I don't think Codeforces current rating system is compatible for conducting Div 1 + 2 + 3. As number of participants is much less in Div 2, as compared to other rounds, as expected rating update is very peculiar on the normalized same rank.
I don't think Codeforces current rating system is compatible for conducting Div 1 + 2 + 3. As number of participants is much less in Div 2, as compared to other rounds, as expected rating update is very peculiar on the normalized same rank.
Got FST on div2C for using
std::unordered_setinstead ofstd::set. Of course, anti-hash table test cases come from hacks, and this goes to show that hacking is a negative mechanic in Codeforces rounds.The purpose of hacks has become that of giving a few people easy points by breaking hash-based solutions, and nothing more.
No one would argue that this is a positive thing, and Codeforces really doesn't shine when allowing this sort of unfairness to happen on the site.
why use it if you know that there are anti-hash test cases?
Same thing happened to me, just use custom hashes.
Thanks guys for the contest!
Problem Div3B made me spend lots of time, luckily solved it after problem C!
Yeah, I literally solved C, D, and E and then came back to B. B was kinda weird and very caseworky
Due to significantly low number of participants in division 2 , The rating changes were not satisfactory : (
Just a little personal opinion.
It's clear that contestants who've solved problems [A-D2] in Div.2 have the capability to solve all problems in Div.3.
For those who solved all the problems in Div.3, their performance score is greater than 2100. We can see some Experts (who got promoted from the last contest so they can participate in Div.3) receiving a +150 delta.
However, those contestants in Div.2, if they solve D2 at the same speed, would only get around an 1800 performance score. Some Experts might even see their rating dropped.
I think this seems a bit unfair. I'm not saying that the contest was bad; the problemset was excellent!
That's life
Thats life, I did real bad in the 904div2, got demoted to specialist but still had to participate in 905div2 bcoz ratings were not updated. Still managed to get back to expert somehow.
but CF needs to modify the algo if they wanna continue doing this div1+2+3 thing.
I think this problem is already present in div1/div2. There are some rounds where almost everyone in div1 solves div1AB but in div2, barely anyone solved div1B (maybe because an earlier problem was annoying or something). Then a low CM in div1 who solved AB would maybe get negative delta but in div2 he would have gotten huge positive delta.
I am just wondering if someday there will be parallel div-1/div-2/div-3/div-4 contests.
Thanks for both of the contests :D
A good day for me, gaining $$$200+$$$ delta!
great contest, had a little mess up on E & g2 I really like it when the number of alts is reduced due to most of them attending from their main bcoz of div1&2&3
Hi,
This was my first Codeforces Div 3 contest. I solved three problems and gained some rating. However, when I checked back in the evening, my rating was gone, and the contest had become unrated. Can you help me understand why this happened?
They rolled it back to check solutions for plagiarism, everything will return after some time.
There should be a message about this at the top of the screen during the plagcheck, ain't it?
Alright, thanks for explaining. I read something about needing to confirm my intention to participate as "rated" in the contest, and it got me a bit worried.
In Div2C/Div3F,
What is the intuituion behind below statement?
In Div2C / Div3F,
What is the intuition behind the below statement?
suppose that you have the l r of the subarray, when does this subarray can be reproduced as a subsequence if and only if the first value (or more with the right order) are with index <l (the same logic with the end of the subarray for index>r) we can think about the first and the end of the subarray (to lessen the cases)
Understood bro! Thanks!
Maybe I'm the only one using segment tree + lazy prop in div3D LOL.
That's beautiful though XD
nice problemsets! really challenging and interesting, RP++
can any one tell why this submission 229370372 is giving WA on testcase 2 for div2D2.
For above testcase, correct answer is 12. Your code is giving 15.
For above testcase, correct answer is 2. Your code is giving 5.
Happy debugging!
thank you, it got accepted
i forgot about considering upperbound(m+1)
Where is the information about icpc challenge? The button in the main menu links to an empty page...
upd. issue resolved
Why the answer to 4th Example test case is 7 in Problem F[problem:1883F] Div 3. According to me it's 8. The segments are {3},{1},{2,3},{3,2},{2,1},{2,3,2},{3,2,1},{2,3,2,1}. So there should be 8 segments.
{2,1} is not valid
get back to Expert lol :(
I have recently got a plagiarism notification for question 1883-D. The solution which I submitted was a pretty generic solution. It coincidentally matched with some other participant (Shivam_Jha) who even had a similar template like I have. In fact many other participants and even the editorial had a similar (almost same) solution. I am attaching some similar solutions that I have a found.
My Solution
Shivam_Jha's Solution
Other similar solutions: 229297769 229325508 229223552
As far as the template part goes, we have been using this similar template for over a year now.
Hello, Codeforces.
I managed to solve 5 problems in this round. But later Codeforces algorithms found my solution to the D1 problem similar to another solution. I looked — yes, the solution is almost identical. You can make sure that the solutions are indeed similar: https://mirror.codeforces.com/contest/1888/submission/229228883 — my code, https://mirror.codeforces.com/contest/1888/submission/229262126 — someone else's code. But I would like to challenge the decision to write off.
Firstly, I do not know the person who owns the second code. Secondly, I think that copying so close to the source code is stupid, since there is a check for cheating. Thirdly, task D1 is a problem with an obvious solution. If solutions to problems where it is necessary to derive a formula are not banned, then why is the task where it is necessary to write a standard bin search for O(nlogn) banned?
I hope for an individual consideration of this case.
Good luck to everyone!