Hello Codeforces!
We are glad to invite you to Codeforces Round 668 (Div. 1) and Codeforces Round 668 (Div. 2), which will take place on 06.09.2020 17:35 (Московское время).
The problems were created by Ari, Kuroni, ruanxiaoyu, Monogon, antontrygubO_o and hugopm.
We would like to thank:
dorijanlendvaj, Jatana and enoone for helping with the preparation of the tasks.
gamegame for always being nice and supportive.
DatVu, ruanxiaoyu, MofK and atoiz for stealing the round #666, forcing us to retheme around ponies.
Monogon for making the author list more colorful.
redblossom, thenymphsofdelphi, qlf9, mcfr, Tlatoani, aohkgnadnart_, McDic, cup_of_tea, bestial-42-centroids, Noam527, Mbfibat, wolfris, ffao, Falseeee, fpc_coder and fivefourthreeone for testing.
MikeMirzayanov for the Codeforces and Polygon platforms.
There will be 5 problems in each division and will be given 2 hours to solve them (or post memes in the comments if you can't solve any).
We tried to make interesting problems, short statements, useful samples and strong pretests, and we hope you will like it.
Scoring will be announced shortly before the round and editorial will be posted shortly after the round (it is already written).
Good luck!
UPD: The number of problems is now 5 in each division.
UPD2: Score distribution:
- Div.1: 500 — 1000 — 1500 — 2250 — 3000
- Div.2 : 500 — 1000 — 1750 — 2250 — 3000
UPD3: Editorial is out
UPD4: We are sorry for problem div1E being well-known. No setter or tester have seen this problem. We apologize and hope you still enjoyed the contest.
UPD5: Congratulations to the winners:
Div.1
Div.2
hi
🖐
@ Monogon
www.nohello.com
Namaste
This is how the problems were created:
As an author of two div1s in a row, give me contribution
Excited for this contest!!
AC round 4
Hope for strong pretests.
As a tester, I'd say the problems are really good. I wish everyone the best of luck and get a good rating after the contest!!
editorial will be posted shortly after the round (it is already written)Codeforces should make it a rule for authors.
i think editorials should be posted next to next day after the contest
so that everyone try to solve problems on their own and
this way people will learn things more quickly
if tutorials are available just after contest people just waste
a chance to think a solution of their own
that's all ...
I think this totally depends upon the person itself, if they don't wanna see the editorial, no one is forcing them. But think about the the person who tried everything during the contest and wanna see the solution badly.
In my opinion, it is good to have editorial as soon as possible after the contest is over.
..
..
No. We're downvoting because you are suggesting taking away our freedom of choice under the ridiculous pretense that you know better
I'm only putting my side
nobody is stopping you from voicing your opinion, but if people think it's stupid, they'll downvote you lol
they are downvoting me that's okay
but few of them are being very personal with me that's where real problem begins
are people sending you personal attacks in DM or something? I don't think anyone would do that over something as insignificant as this
Do not decide for me
He can't decide for anyone , Open his profile and check the college he is from , LMFAO you'll laugh your azz out if you know the scenario of his college
IIT Mandi , don't make me laugh , even the facchas from my IIT can do better coding than his CSE fourth years
i can also say bad words about other people through memes and personal attacks
but i am maintaining my well behavior in comment section till now i was just defending myself
i don't understand why people are so much offended by opinion of just one person and can't let it go
i think editorials should be posted next to next day after the contest
Hmmmm..... Interesting
You say that but ironically you commented on the editorial of Codeforces Round #665 within 30 hours of the contest itself ...
Practice what you preach is all I would say
Atleast read that comment carefully I had found mistake in my code on my own and then I asked for help in not repeating such mistakes
And if you are that much offended by my opinion dm me I can explain what I am trying to convey here
Well I wasn't hoping for you to understand my comment in the first go , I guess username checks out...
It isn't about the comment , It was about the fact that you read the editorial within at least two days contradicting what you originally said ...
Because if you commented on it , you must have clicked on it after reading EDITORIAL in the blog title , so much for the hyprocrisy of not going to the editorial within at least 2 days
If you still didn't understand anything above (chances of which are very high ) , you can DM me I can explain what I am trying to convey here
i had upsolved upto question D in that contest before commenting
as a beginner i am not supposed to solve after that level as it will not be beneficial for me ( so tutorials turned useless for me as i was not going to solve after problem D)
that's why i directly headed to solve my doubts in comment section
and about the thing of atleast 2 days, here i wanted to say is if editorials are not posted for 2 days then people will be forced to solve problems on their own and this will train their mind to solve problems beyond their knowledge
I like how you went from having an opinion of yours to making excuses for why you are a hypocrite in the same thread lol
cyans be trippin nowadays
atleast i am commenting through my original account and taking downvotes
not like you
fear of downvotes hh..
and if someone is calling me hypocrite then i have to and i need to prove my point
I like how you suddenly made it a rating dependent thing.
Btw if you didn't know, CF rating ONLY determines the performance of people in CP contest at CF. nothing more than that.
Also yea this guy first forces his opinion, then says it's just my opinion and also behaves hypocritically. It's hilarious
That would be nice too. But actually I don't mind delay as long as they're well-written
So I would prefer optimizing the quality of the editorials over the publishing time
Well, I think the quality would usually be better if the editorial is written before the contest, without time pressure.
As a tester, good luck!
Why is it unrated?
Ponies? Not again !
I wish I'd become green after this contest
same here
Hope for the best
yep
nice dp
it is not a tinder so avoid writing such cheap comments?
But for you, dp_is_life xd
I wish I don't become green now
hugopm: "post memes in the comments if you can't solve any"
me: well, now I know that studying Paint is a good option :)
antOn in the list of authors? I suggest everyone to skip the contest
There were not Anton problems in Div1 heh
(
)
6 sep, 8 sep, 12 sep, 14 sep <<div 2 days <3 >>
Sorry, I sent it in the wrong place.
It's a risk I'm willing to take. ;-)
"gAmeGaME fOr 4lWayS B1enG NicE AnD SupPorTiVE."
Obviously that was sarcasm. Gamegame is the most friendly and agreeable person I know, so to call him toxic is an instance of absurdist humor.
yeah lior5654 trying to ruin my reputation :(
My school starts two days after the contest... phew
So many reds ,red means danger xD
I am wondering who is the coordinator...
Obviously gamegame .
Why ponies? I am very scared of them.
No round coordination?
Always Hope for the best. and May this round increase everyone's rating.
increase everyone's ratingThis statement breaks rating calculation rules of codeforces.
You mean, it's as unrealistic as "May Peace Prevail on Earth"?
cout<<"Hello World"
Technically it might be possible actually. If new accounts all do just slightly worse than expected, they will lose real elo, but still appear to go up because of the new system. That would allow the good people to be allowed to very slightly gain elo as well. So everyone would have a net positive delta.
edge case detected
vivek1401 What if everyone comes 1'st?
I wish everyone a happy contest !
Why do you have so many downvotes?
Because he has changed the comment after he saw downvotes, you can read his previous comment.
i hope with this contest my rating will start to increase.previous 4 contests the rating is decreasing continuously
I'd like to take a moment to congratulate a special boy. Our genius leader who put us back on track whenever the future of this round looked bleak. Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
.
Happy birthday hugopm!
.
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Happy birthday hugopm!
Racism is everywhere (:low rating = downvote (:Happy birthday hugopm!
Happy birthday hugopm!
Belated Happy Birthday hugopm!
I always wonder how these comments say the exact same thing but the number of votes are so random
Ratism
Happy birthday hugopm!
Oh, at last I down voted everybody.
you forgot to downvote yourself, I helped you, have a great day :)
I like cowards just like you, who can't even write a comment with his real account. I am just laughing at you!!!
I can write comments with my main account, but guess what "It's my choice" + it has nothing to do with -ve contribution, what am i gonna do of CF contribution anyways.
Yeah in the world it is called "**Cowardice**"
Everyone less rated than a candidate master(except 2) in this "happy birthday hugopm" chain got downvoted a lot, and everyone >= CM(except 1) got heavily upvoted.
I'm really interested in how an average person in codeforces comprehends comments based on not the "content" but the "author's rAtInG".
That's basically how ratism in codeforces works.
Oh Yeah!
We tried to make interesting problems, short statements, useful samples and strong pretests.It's so cute <3 <3
just like mort in your dp <3
Go check out my graph, who thinks this round is gonna take me to Expert?
Problems with short statements are relief for an idle like me...
As a tester I want my contribution :)
Why do you feel the need to say something that contributes no tangible value to the community?
Edit: I meant as a joke based on my hypocrisy of having made similar comments. I realize now this didn't come across. No hard feelings.
My message was supposed to be a joke about all the testers like you who always ask for contribution :kappa:
USA Users, have a good contest on Labor Day.
Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).
hugopm How many common problems are there?
Three problems (d2c = d1a, d2d = d1b, d2e = d1c)
thanks!
Author: "or post memes in the comments if you can't solve any."
Me: "How to make good programming memes google?"
Why was one of the problems in div 2 removed? It appears that the problem A or problem B has been removed because they are the only two that are not common with div1!
Is there an explanation?
Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).
Please give me downvotes, Codeforces!
Oh no, I expected everyone to do the opposite :'( Anyway, thanks for the negative :)
Div.1: 500 — 1000 — 1500 — 2250 — 3000 Div.2 : 500 — 1000 — 1750 — 2250 — 3000
I'm not sure you know how score distribution works
can you tell? :)
Sure! The first thing is that you can't compare score distributions of div1 and div2. Also it just shows how much score you will get after solving the task
Can you kindly elaborate on how you came to this conclusion great sir?????
score != difficultyScore distribution of div1 500 is like div2 1500 or more. So, you can't compare these two.
thanks , u give the right information
so many reds. This contest is sure to have very good quality questions.
Orange Lives Matter.
at the cost of Newbie lives
Sliding through hilarious memes down here and forgot to register......
Congrats maroonrk for his very first win xD
Will only know for sure after system tests
speedforces
C > D
Thank you for a very nice C.
How to solve C?
He's not talking about div2C. But in Div2C you just observe that string has to be periodic with period k
I guess div1b is Monogon problem
You really "tried to make short statement" in Div1D???
The interactive part is totally unnecessary: Let judge always give the array and let contestants just ignore it for the First case. You have written so in the Hack Format, why didn't you use it as the input for the contestant...
We discussed making the format to 1D non-interactive in a few different ways. Ultimately we felt interactive was cleaner, though of course, you may disagree.
For that format in particular someone raised the point that you could try to find a valid play as Second, and then if you fail, submit the same input as First. Of course, that's not particularly helpful given that the actual solution, but it felt somewhat weird.
Thanks for the explanation!
I agree with you on that "Which is cleaner" might be personal preference.
I can't really agree on the second point because even in the interactive format the contestant could make some random partition to try and switch to First. Anyway I understand that it is somewhat weird, so, no clear conclusion...
Can someone give some hints for D and E(Div1)?
How to hack B? I kept getting
Validator 'validator.exe' returns exit code 3 [FAIL Unexpected character #13, but ' ' expected (test case 1, stdin, line 3)]You put n=100000 but didn't output 100000 numbers.
oh no! don't know why i thought 5 + 5 * 10 ^ 4 = 10 ^ 5 :/
how to solve C? I spend 1.8 hour on this task(
Same here
You have to make the observation that for "YES" answer, s[i] should be equal to s[i+k] for all i.
hi, could you provide a proof as to why no Balanced String can exist with the ith character not equal to the i+Kth character? Thanks. Also could you tell me a little about the intuition behind your solution?
from sliding window
when you move from [0, k-1] to [1,k] then the a[k] should be equal to a[0] for the new subarray to maintain balance. similarly you can keep sliding all the way up to n-1.
ohhh, right, thank you so much
But why it works?
Same lol, finally went to D and was able to do it in 20 mins
I missed some observation in 2C, 2D was simpler for me.
2C: k-periodicity
yup I agree
Am I the only one refreshing page for editorial :D
when will tutorial release?
When no one is looking for it.
Such a nice contest..
Any hacks on D ?
I guess I've forgotten a case in Div2D. Anyone has an idea of the solution? What I did: if distance between a & b is <= da, then Alice wins, if 2*da >= db then Alice wins, and then if the diameter of the tree is >= 2*da + 1 then Bob wins, else Alice wins
Bob needs to reach a diameter endpoint without colliding with brurrito. I am not able to think of a case but that could be one of the things.
Same bro, I made all other observations. But How I can be sure that Bob will reach on the diameter or end of it without colliding with Alice. How to prove this?
If diameter > 2*da && db > 2*da && dist[a][b] > da Bob wins. Else Alice wins.
and then if the diameter of the tree is >= 2*da + 1
But what if db < diameter of a tree? It should be
min(diameter_of_a_tree, db) >= 2*daAlice wins iff d[A][B] <= da OR 2*da >= min(diameter, db) But how to prove this?
When you submit the (what you think is) correct code ten seconds before the end but there's a last-minute compilation typo
imagine searching template (2SAT) on Anton's contest lol
How to solve 2E/1C ?
From left to right for each index i calculate maximum index L[i] such that you can remove a[i] if you only consider segment [L[i], i]. Segment is good if there is >= i — a[i] (you need to remove i — a[i] numbers from left to make a[i] = i) numbers that can be removed. Now answer on segment [l, r] is number of L[i] >= l from l to r.
I'm not sure which case I missed in D. If the initial distance is <= da, then Alice wins. Then limit da and db to be at most diameter. If
db > 2 * da, then Bob wins, otherwise Alice wins. Can anyone tell me what case I missed here? Getting WA on pretest 2.The case where 2Da >= diameter of the tree
Why would Bob win that case? If
db < 2 * da, then Bob will never be able to cross Alice when Bob is at the endpoint of a diameter?That’s what I meant to say, diameter can be a small number compared to Db. It can happen that Db is greater than 2Da but 2Da is greater than diameter so Alice will win but your code would output Bob.
I did
da = min(da, diameter)anddb = min(db, diameter). Then the actual logic holds right?I think I found the mistake in your code.
When you take the minimum of db and diameter, you are also incorrectly comparing db > 2 * da, Probably db was greater than the diameter and after taking the minimum, your db > 2 * da will yield a false value, incorrectly printing Alice, when it should have printed Bob.
That's not the issue. The logic is correct. I haven't marked the root node in my BFS as visited. Unforgivable error ;( :(
Yes, my bad. Looks like your logic was correct. Tough luck
Find the diameter of the tree. If da >= ceil(diameter/2), then Alice wins since she can just go to one of the center vertex(es) and get Bob on the next turn since she can effectively go anywhere in the tree in that move.
How to solve E?
I know we can answer (if only one query) in O(n) by ans+=(ans>=a[i]) but idk how to answer q queries in time.
What is the proof that every s[i%k] should have same value in problem C ?
Consider this: Every time you move to the next subarray, you are removing the first element and appending a new element to the end.
If the current subarray is valid, the next will be valid only if the removed element is equal to the appended element, else the balance will be disturbed.
Oh nice !!
Lets consider a subarray of length K, s[i], s[i+1], ... s[i+k-1]
and another subarray of length K as s[i+1], s[i+2], ... s[i+k-1], s[i+k]
the sum of both of these should be equal and equal to k/2.
Hence,
s[i] + s[i+1] + ... + s[i+k-1] = s[i+1] + s[i+2] + ... + s[i+k-1] + s[i+k]
which gives, s[i] = s[i+k]
Thanks , i missed this observation, feels bad now as I already applied this thing in some older problem.
Hi, I made a testcase on which my pretests passed code runs in 1.3s on my system. My code runs in $$$O(n*lg(n))$$$
Kindly check if it the same happpens for you.
TLE testcase for problem B
This makes your code O(n*logn)
Update: Sorry my bad, it's O(n^2). For ex, consider the array 1 2 3 .... N 0 0 ..... 0 -1
No,
whileloop in theforloop makes $$$O(n^2).$$$I made worse case
When
i=0many elements inqbecome0. For eachi>0,itgoes through.D1D easier than D1BC for me lol
Thanks for the amazing round, I enjoyed it
Tfw you read div 1 E in last 5 mins and realized it's the same problem you authored (which also turned out to be a duplicate of some old Topcoder problem) and you submit your old code to get AC in last minute :facepalm:
Moral of the story: READ ALL PROBLEMS!!!!!!!
It was a horrible contest for me. Whatever confidence as a colorless I gained in past 3-4 contest just vanished today, though the problems were good but I just lost myself, completely shattered ;(
Is div1E a duplicate of topcoder SRM577?
Yes, and zscoder just found out about it in the last minute https://mirror.codeforces.com/blog/entry/82288?#comment-691914
My original plan for today was to skip CF and only participate in JOI Open Contest (5hr contest). I started it 3.5hr before the CF because collision didn't matter.
And I solved everything in 2hr, so I could participate in CF. But I didn't care and just chilled.
10 minutes after the contest started, I casually checked the hardest problem. It was a problem I solved some months ago, which means it's just free rating.
I also had the exact same plan but I also joined cf later because I finished joi open in 3 hours.
STRONG PRETESTS..
Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).
aah the good old system testing errors
The vast majority of them are people writing n^2 with breaks on div2B, which we definitely didn't expect at all, and also when you can only have 3 pretests, one has to be a sample, one has to be a good correctness test with the max amount of test cases leaving only 1 possible n=100000 test. It's almost impossible to stop all possible n^2 with breaks with just 1 test case.
I think pretest 3 in question D is not valid. I got a runtime error when I tried to parse the input without trim, and I was able to pass the pretest when I did trim.(below is diff of code.)
I've send question about this and haven't gotten an answer back. I really want to rejudge to fix this issue because I lost 14 minutes and got 2 penalties due to this issue.
I read your question and you are right, I am extremely sorry both about the issue and about failing to reply to that question, you are correct that there's an issue in the format :(
I have fixed the issue now, and we're looking into the possibility of rejudging. Once again I am deeply sorry.
How does the checker work in problem D when $$$n$$$ is even and the contestant prints a pairing different from the official one? Is it $$$O(N^2/64)$$$ using bitsets?
Nvm I was stupid :(
We used bitset if n<=25000 and heuristics otherwise.
It is indeed $$$O(n^2)$$$ with bitsets for reasonable values of $$$n$$$. For very very large values of $$$n$$$, even that is too slow, so it works through some heuristics. Of course, this means you could get AC by printing something incorrect, but we didn't see it as a huge issue since the even $$$n$$$ case is easier anyways, and it's unlikely that someone will have a solution that is only incorrect for huge n.
As a challenge, you could try hacking the checker to get AC on a wrong output, might be fun :)
Nice contest!!
Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Mike is the best !
Hi, my rating change was rolled back, but isn't updated yet. Can you please look into this?
UPD: Just read comments below, and looks like it is the case for many people too. I guess you're looking into it then, still wanted to point it out.
Good for you
Ok
WTF ??can someone explain this submission
https://mirror.codeforces.com/contest/1405/submission/92045757
This is well known as code Obfuscation! TO avoid third party read code until you write an script to remove #define with original statements. This is a trick to avoid plagiarism issues. But since this solution is reported and this is out of contest rules thus this submission will be skipped and the rankings will be fixed!
1536-->1419 cool. Before contst-i have a chance to become xpert tonight.
After contest-god! please save me from becoming pupil!
Finally Green!
My bad luck.
I did the same mistake ,you can read my code.
Interesting Problems + short statements + strong pretests + quick editorial, one of the best CF rounds ever, thanks all
The best part of this contest is clearly 92063082 getting WA on pixel art.
Oh no! I want to be 1800 in this contest. :(
Why codeforces Round #668 become unrated. Can anyone tell me?
So is it rated at last? If it is rated, I can be a CM. Can anyone tell me?
Why this contest was unrated?can any one tell me please?
You won't get an answer until every participant asks this same question.
Well, he did his part.
Am I the only one or ratings change reverted?
Me too. Maybe it's Mike catching the cheaters? Don't know yet if there's a reason to cause this round unrated.
Me too.It seemed to be unrated?
why this contest is unrated?Due to Div 1 E. problem ?Someone help me out with it.
relax bro. u just chill
Hello! When will the rating for div2 be restored?
Now is a good time to ask
Is it rated ?
if the problem was a div 1 E , why div 2 ratings were changed while div1 ratings stayed the same?
Is it Unrated?
MikeMirzayanov?????
Why this contest got unrated? My ratings changed back to same as it was before the contest(div 2).
All of those who are thinking that the contest is made unrated, just wait for some more time? If it were really made unrated, you would get an update in the announcement about that. Ratings are just reverted temporarily for removing cheaters from the standings (as Mike's comment says) most probably.
I still have hope that it is going to be rated.
Yesterday I learned from the banner notice at the top that the rating for this contest rolled back, but before I knew it, the banner disappeared and the rating is still not reflected. Is this recalculating the rate? Or did you become Unrated? (I'm Div.2) (P.S.) The rate has been successfully updated to the pre-rollback rate. Thank you very much for your great work!
Why are the rating changes rolled back and not yet returned? Could someone please let me know?
MikeMirzayanov send help pls
I did not get any update on my rating for this, can you guys check it please
Something is definitely not right, otherwise Mike would have reverted the ratings by now
So it is rated now?
why not ratings ?
Is the rating change of the contest permanently rolled back?
Since there was no interruption due to server lag or problem statement, It's gonna be RATED. Can be the case DIV1E is a open ques OR some cheaters are getting punished OR some problem in rating update formulae, Let's wait for Mike. (My opinion)
But Round div.1 has been rated
Then It can be the case that some people might be using 2 ID's to get there D/E Correct to avoid penalties in Div2.
In this case, that codes will skip in the system test.
Is #668 Div2 unrated? Who can tell me
I think not。
A lot of time has passed。
qwq...
why isn't Mike or any co-ordinator giving some clarification as to what is going on ?
MikeMirzayanov antontrygubO_o hugopm
Please stop spamming the comment section to whether the contest is rated, it won't instantly solve things.
Just be patient and wait, probably the ratings are rolled back from removing cheaters from the contest.
Ironic , you just did what you are saying not to do
As we know,div2 + 5problems = codingspeedtest
Where is my +120?
The rating has been reset!
Thank you! :)
I solved B and C in this contest then why is it showing that I solved 0 problems??
punishing cheaterS?
I'd assume that if it was cheating then it would say skipped, not pretests passed.
interesting....
Auto comment: topic has been updated by hugopm (previous revision, new revision, compare).