Codeforces Round #905 (Div. 1, Div. 2, Div. 3)

Hello, Codeforces!

We are happy to invite you to our experimental round for three divisions, which will take place at Sunday, October 22, 2023 at 11:05UTC. Please note the non-standard start time for the round. Each division will have 5-7 tasks. The round will be held according to the Codeforces rules and will be rated for all three divisions. A few changes regarding the ratings of participants in this competition:

• In Div.3 the rating of participants is less than 1600.
• In the Div.2 ranking, participants range from 1600 to 2099.
• In Div.1 the rating of participants is no less than 2100.
• Please note that after Codeforces Round 904 (Div. 2) the rating will not be recalculated until the end of this competition.

Let us note that two team Olympiads will be held in parallel on this day and the rounds are based on their tasks:

• XXI Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad.
• III Open Team Olympiad UMSh in programming.

We would like to thank everyone who helped me a lot with round preparation.

We wish you good luck and high rating!

UPD: One of the problems will be interactive, so please read guide for interactive problems before the contest.

UPD: Score distribution:

• Div.3: 500−1000−1500−1750−2500−2750−(1750+2000)500−1000−1500−1750−2500−2750−(1750+2000)
• Div.2: 250−500−1000−(750+1250)−2250−2750250−500−1000−(750+1250)−2250−2750
• Div.1: (250+500)−750−1000−1250−2000−2750(250+500)−750−1000−1250−2000−2750

UPD: Editorial

UPD: We will retest the solutions to the problem div3F and div2C. This may make minor changes, the rating will be recalculated later.

UPD: Retesting took several minutes. Now all the results are correct :)

• • 2 months ago, # ^ | If one's division changes after round 904, will round 905 be unrated for him?

    • 7 weeks ago, # ^ | 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.

    • 7 weeks ago, # ^ | No. If you participate in the round 905, it will remain rated for you regardless your results in the 904.

    • 7 weeks ago, # ^ | Thank you!

• 2 months ago, # ^ | same question..

  • 7 weeks ago, # ^ | really?

• 2 months ago, # ^ | will div3 follow icpc rules or div2 like score rule?

• 2 months ago, # ^ | it'll be really weird though, since div 3 would just be clash of specialists

  • 2 months ago, # ^ | hell yeah

  • 2 months ago, # ^ | that would actually be cool. Div 2 clash of experts, div 3 clash of specialist and div 4 clash of pupils and newbies.

    • 2 months ago, # ^ | I agree, hopefully we'll see 1+2+3+4 one day.

• 2 months ago, # ^ | no, since #904 is also based on a competition.

• 2 months ago, # ^ | how do you know

• 2 months ago, # ^ | Same for the Div.2 :(

• 2 months ago, # ^ | 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

• 2 months ago, # ^ | the delta will not consider round 904 when distributing rating, so it is a good chance to boost up

• 2 months ago, # ^ | You can't become master before round 905, because we will calculate ratings for both 904 & 905 only after 905's end.

  • 2 months ago, # ^ | ← Rev. 2 →   0 But what about our profile, sir? won't there show that an expert attending a div3 ?

    • 2 months ago, # ^ | bruh he just said the ratings will be given after 905 ends

      • 7 weeks ago, # ^ | ← Rev. 2 →   -10 bruh it link was my question answer (: i knew what u said (:

• 7 weeks ago, # ^ | Round being shorter dealing with rating volatility is stupidest opinion I've ever heard.

  • 7 weeks ago, # ^ | Short rounds are better, my point wasn't about them still. Division distribution is far better.

• 7 weeks ago, # ^ | True but preparing such a large problem set is hard

• 7 weeks ago, # ^ | 2h is the normal round duration... Can we not make rounds longer for absolutely no reason?

  • 7 weeks ago, # ^ | Does actually wanting to try out harder problems in a contest not count as a reason?

  • 7 weeks ago, # ^ | Easy for you masters' to say, here I am getting gotchas for B after submitting 2 wrong attempts of C!!

• 7 weeks ago, # ^ | +1, 2h was too short for this round imo.

• 7 weeks ago, # ^ | Practice 800 rated problem in problemset

• 7 weeks ago, # ^ | 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,2 and 7,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

  • 7 weeks ago, # ^ | thx Ryan, I had the same mistake..

• 7 weeks ago, # ^ | because it is O(km)O(km) in worst case.

• 7 weeks ago, # ^ | 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

  • 7 weeks ago, # ^ | orz！！

• 7 weeks ago, # ^ | 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

  • 7 weeks ago, # ^ | or you can make a custom comparator for right border multiset which will eliminate the need for binary search.

• 7 weeks ago, # ^ | 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.

• 7 weeks ago, # ^ | ← Rev. 5 →   0 Yeah, so basically you can maintain two multisets starts and ends, then for every operation if starts.size() (or ends.size()) is <2, the answer is NO, otherwise we can check that min{end} < max{start} (think about why this works by drawing intervals on a paper or something), if this is true then the answer is YES, else NO. Here is my submisison for reference.

• 7 weeks ago, # ^ | I quickly came up with an approach of C, but it took me a while thinking about D2. In my opinion, D1 < C < D2

• 7 weeks ago, # ^ | You can try to first solve D2 instead of D1 next time as I did this time :)

  • 7 weeks ago, # ^ | ← Rev. 2 →   0 I guess I'll try that :) (or solve A faster to have time to do E :clown:)

• 7 weeks ago, # ^ | 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.

• 7 weeks ago, # ^ | Which calls for hacks... :( I am considering accepting the O(log(n))O(log⁡(n)) and going with the ordered versions.

• 7 weeks ago, # ^ | 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.

  • 7 weeks ago, # ^ | Yeah you're right, I think they should try this format and see how it goes

• 7 weeks ago, # ^ | As a Div1 participant, I like this format rather than usual(Div1,2). We can reduce the number of easier problems and make a time to tackle hard problems during contest (without extending the length of contests) Soften the nightmare rating drop of very bad performed contests More hacking attempt opportunity. Increse the number of participants who PT-passed harder problems in the same room.

• 7 weeks ago, # ^ | ← Rev. 2 →   0 Kinda same thing, still don't understand what happened. Curious if somebody can clarify why did that happen. (ExTrEmE AmoUntS of ClariFiCation is required) 229253714

  • 7 weeks ago, # ^ | 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

    • 7 weeks ago, # ^ | Why would anyone include such tests without putting some in pretests, this is retarded

• 7 weeks ago, # ^ | I found an argument suggesting people should use unordered_* with extra care on CF: https://codeforces.com/blog/entry/62393 It is possible that Test 17 is a hack.

  • 7 weeks ago, # ^ | I think so, a constant log(10^5) * 5 = 80 looks like something unimaginable for std::unordered_map in basic cases... This is at least not pretty, in relation to the participants of the round, to use antihash tests only in systests

• 7 weeks ago, # ^ | Got FST because of this as well...

• 7 weeks ago, # ^ | ← Rev. 2 →   +7 Div2C(Div3F) has testcases for anti-unorderd_map for C++. For example, testcase16 contain only 107897 * n as follows. 1 107897 215794 323691 431588 539485...

  • 7 weeks ago, # ^ | how sweet it is :) the author of the problem (test) is probably very funny

    • 7 weeks ago, # ^ | He is thou

  • 7 weeks ago, # ^ | All the love from the bottom of my heart to the autors for accepting some python O(nlogn) solutions over c++ hashes

• 7 weeks ago, # ^ | number of operations can be large so a[i] can overflow 229293522

7 weeks ago, # | ← Rev. 3 →   +20 After all this time

• 7 weeks ago, # ^ | Good job !!

• 7 weeks ago, # ^ | maybe CF should add a new tag call "understanding" lol

• 7 weeks ago, # ^ | why use it if you know that there are anti-hash test cases?

• 7 weeks ago, # ^ | ← Rev. 2 →   0 Same thing happened to me, just use custom hashes.

• 7 weeks ago, # ^ | Yeah, I literally solved C, D, and E and then came back to B. B was kinda weird and very caseworky

• 7 weeks ago, # ^ | That's life

• 7 weeks ago, # ^ | 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.

• 7 weeks ago, # ^ | 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.

• 7 weeks ago, # ^ | They rolled it back to check solutions for plagiarism, everything will return after some time.

  • 7 weeks ago, # ^ | There should be a message about this at the top of the screen during the plagcheck, ain't it?

  • 7 weeks ago, # ^ | 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.

Note that a subarray suits us if a[l] is the leftmost occurrence of the number a[l] in the array and a[r] is the rightmost occurrence of the number a[r] in the array.

• 7 weeks ago, # ^ | ← Rev. 2 →   +4 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)

  • 7 weeks ago, # ^ | Understood bro! Thanks!

• 7 weeks ago, # ^ | That's beautiful though XD

• 7 weeks ago, # ^ | ← Rev. 2 →   +3 5 4 12 17 11 16 20 9 8 6 4 For above testcase, correct answer is 12. Your code is giving 15. 6 2 20 12 6 10 10 15 16 8 8 14 15 For above testcase, correct answer is 2. Your code is giving 5. Happy debugging!

  • 7 weeks ago, # ^ | thank you, it got accepted i forgot about considering upperbound(m+1)

• 7 weeks ago, # ^ | {2,1} is not valid

  • 7 weeks ago, # ^ | Yes, I misunderstood the problem. Thanks.

• 7 weeks ago, # ^ | Sorry??