Hello Codeforces,
We are glad to invite you to Codeforces Round 807 (Div. 2), which will be held on Jul/15/2022 16:35 (Moscow time). As usual, the round will be rated for participants with ratings lower than 2100, while those who have higher ratings are encouraged to participate unofficially. Please note the unusual start time.
You will be given 6 problems to be solved in 2 hours and 15 minutes. There may or may not be interactive problems, so you are encouraged to prepare in case they do appear by reading this guide.
The round is authored by abc241 and me, while joining us is also inwbearX who contributed significantly to the preparation. This is our first time setting rounds in Codeforces, and it wouldn't be possible if there were no support from the following people.
- errorgorn for fantastic coordination.
- KAN, mtw, geranazavr555, unreal.eugene and MikeMirzayanov for translating the statements into Russian.
- antontrygubO_o, kevinxiehk, mango_lassi, Adam_GS, mtw, Utkarsh.25dec, yz_, thanhchauns2, TLP.39, 36champ, jampm, DeMen100ns, Neothehero, and somerandomaltacc3034 for testing the round.
- MikeMirzayanov for Polygon and Codeforces.
The score distribution is $$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — $$$2500$$$ — $$$3000$$$.
We are looking forward to your participation. Good luck and enjoy our round!
Update: the editorial is up!
Update 2: Winners!
Div. 2
Div. 1 + Div. 2
As a tester, please give me contribution.
One of my favourite rounds.
ok, that's enough information to make me ignore this contest
As your senpai, that made me feel sad.
I would say when a candidate master (or higher) claims that a contest is in favor of his, it's much more overwhelming for me since I could only do up to 1400+ (maybe 1500 or 1600)
As we know, A round author must be at least expert. Then, how a specialist is the author of this round?
At least one of the authors must be. Not all of them.
oh wow
Absolutely no, I read all the problems. They are interesting.
As a tester, the problems are interesting and high quality, also be sure to read all problems.
"High quality"? Is that a caution for newbie,pupil and specialist guys? :")
Nope :D
I meant that the difficulties are well balanced, statements are easy to understand and the topics are also diverse. All in all, it's a fun contest for people of all ratings!
As a tester, this round's problem-set interested me so much. Highly recommend reading all problems.
Hope that this will be my last rated div2.
2099! I can feel your pain bruh :)
2099 :))))))
2099/kk
I think you will become Master in this contest,come on!
Anya motivation.
Anya going to make father proud!
Do you watch spy X family? I like your sophisticated taste. I watch it too XD. Edit: I'm going to keep my Santa hat on for this Christmas as well lol.
XD
Things turned out bad,details can be found in this blog.
You became master in the end anyway
As a tester, I gotta stop doing this as a tester comments but I mean this round is really really cool, the problems are very interesting idea-wise and that's smth I really appreciate. Congrats to the problem-setters, and I hope u enjoy this round as much as I did!
Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
Have a feeling that a lot of people will be one hour late for the contest.
I would have been an hour late if I didn't see this comment. Thanks.
Watch out! The contest is 1 hour earlier than usual time.I also didn't notice it first :3
I didn't get. Can u explain the meme?
Go to SlavicG's heat map and find the seven differences.
I found only 5.
Even better XD
Lol that is hilarious hahaha
No, it's GitHub Bathroom XD
seems like leetcode bathroom
Hope This round would be my last round as a pupil
Pupil Tag is not leaving me so easily :(
I'm hard stuck as well :)
Me too, though i became Specialist earlier 2 or 3 times, I want to be a real Specialist
me too
Congratulations, I think you'll be cyan today, I lost it with time and penalties:(
Hope ths will be my last div2 as Expert
Me too :D
Note the unusual start time :)
Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
Given the authors, it looks like the round will be IMO-forces (but in a good sense).
IMO — International Math Olympics? :)
Sorry I just don't know what does it stand for
IMO-forces is never good
I prefer IMO-forces/thinkforces :p
BTW, IMO is taking place right now.
As a tester, hi.
I wish high rating for everybody, who reads this comment )
I usually don't pass contests because I always forget about them, and this has happened so many times that I now set an alarm for each new contest and I will definitely pass this contest!(I really hope)
.
.
Very excited!!
same
I hope today's competition will be amazing. Let's try to solve more problems. I wish you all good luck and success! I believe in each of you.
good luck！！
As a participant, please give me contribution.
One of my favourite rounds.
.
I hope this will be my last round as newbie :) Good luck guys!
I hope i will be solve problem C
And i hope for D.
And I hope for E
And I hope for A
lol
I hope nothing
I am sure I will not able to do D problem.
+1 only 3 min left ...
Thanks for the support Alfheim. ::::))))
expecting to reach expert in next few rounds
same. Edit: It happened XD
interactive problems do make me scared
A friendly reminder that the contest starts in about half an hour. Good luck!
as a not good problem solver and 900 rating should i dare take participate in this contest?
10 minutes left before the start of the contest. Looking forward to it!
Looking at the submissions, C should be easy but holy hell I feel incredibly dumb for not being able to solve it
c is good problem,i am not able to understand how this much submissions happen.
idea was easy but implementation was tuff
yeah ...
Because Codeforces is unofficially sponsored by Telegram. If you know you know.
Deep one :)
I got TLE in some submissions where the verdict should be WA or RTE. Why did this happen?
Because your solution was not able to reach the final solution where it can be decided about the correctness of solution.
I think problems are a bit hard!
How to solve C ?
recursion. Try to find in which of the copy paste operation we performed.
can be done iteratively as well
For every query, process operations backwards one by one, keeping track of the current length of the string. Note that each operation adds (r — l + 1) length to the string.
Suppose k <= length before the operation. Then just throw away the operation and reduce the length.
Suppose k >= length before the operation. Then if the operation is from l -> r, then the answer for k — previous length is the same as the answer for l + k — previous length, so just recursively find the answer for such a k.
Similar to what EmilyBloom and barun511 said, you should answer each of the queries using recursion.
It can be done slightly faster iteratively. 164294136
Why cannot we see tutorial yet?
The editorial is up now.
waiting for solution ... i think it would take hardly 5 — 10 min... everyone is becoming fast here.
In some contests there is a hacking phase of 12 hours in some there is not. Can anyone tell me in which contests hacking phase is there and in which it is not??
in educational rounds , in div4 and in div3 we have 12 hrs hacking phase
Contests like educational, div 3 and div4 have a dedicated hacking phase of 12 hours whereas other contests (like div2) have hacking phases which are active only during the contest.
Any hint for D?
Think of the 1's as groups
Look at what happens to the groups of consecutive ones/zeros under the operation.
I may be wrong and fail the system tests so take this with a grain of salt, but I figured that the condensed version of the strings (let's say, the array
[1,5,2,3]for the string10000011000) cannot change its size using any number of operations (meaning no continuous segment of zeroes or ones can disappear or be born). That observation helped me.First Div 2 where I solved 4 problems! Edit: Yay! I'm an expert now!
For me, Problem B seems so much confusing. if we take a test case such as : n=5 the array looks like 2 1 1 0 4 how is the answer 5? I think the answer should be 7.
One sequence of moves is
No it should be 5 ig how 7?
can someone pls give me some hints for problem E?
Thanks in advance.
You can see some hints in the editorial :)
D was easier than C, right?
Very nice problems!Congrats to authors!
I really liked today's contest, I was able to solve the first three problems, but I didn't have enough time for the fourth one, in general, the problems were very interesting and exciting, especially problem C, thanks to all the creators of this contest!
A harder version of problem D appeared in yukicoder, a Japanese contest: https://yukicoder.me/problems/no/1209.
Well, I apologize for that, but please understand that there are just too many problems out there, and it's impossible to check them all. Thanks.
I don't think it should've been noticed, but I just think it is beneficial information so I posted. Sorry for misunderstandable post. Thank you for a great contest. I enjoyed it a lot!
In problem E, I try binary search + segment tree, its time complexity is O(nlog^2n), when n equal 2e5, it remain less than 8e7, why it get TLE? code link
Based on our testing, the segment tree has a high constant factor that an O(nlog^2 n) is very hard to pass. We apologize for the strict TL.
Oh, I ignored those constant. Thank you for your reply!
Oh my god, this isn't funny anymore. In round 804 my new rating was 1898, but I wasted 1 attempt on C because I put whe wrong module (998244353, from the previous round, not 1e9+7). But today, my new rating Again seems to be 1898, according to Carrot, and today I also wasted an attempt, because I forgot to write something I invented at the beginning, which makes me miss my first CM again, And a div1 round for the first time. F
But the round was great.
upd.: No, 1899.. That's insane.
Internet in Serbia is very good guys. First 25 minutes I wasn't able to submit A, and then last 55 mins internet was so bad that I can't submit B or C(both was ac).
Who is stemroot?
Guess. :)
Раунд очень приятный, мне понравился. Отдельный респект за задачу C и задачу E. Правда Е я, к сожалению, не успел сдать во время раунда.
Ratings updated preliminary. Unfortunately Mike won't be in touch until July 19th, so cheaters from this round and further rounds will be removed later. We can guarantee that they will be removed not later July 20th.
Добрый день
Извините, не могли бы вы подсказать пожалуйста во сколько сегодня примерно рейтинги обновятся?
Is there anyone E using bitset or set to do it, ask for a code
The bitset-based approach is possible. See the code above by errorgorn.
Thanks
Under the standings section of this round I see a positive delta of 39 but my rating change shows 15 positive delta. Anyone have an idea about this?
https://mirror.codeforces.com/blog/entry/50411
hope this helps
my friend：“Hello！” me：“How do u know I become a Expert？” （sorry...I got 807 mixed up with 808.But luckily，I can say it again in 808！）