Hello, Codeforces!
I'm very glad to invite you to Codeforces Round 639 (Div. 1) and Codeforces Round 639 (Div. 2). This contest will take place on May/06/2020 17:35 (Moscow time). In both divisions, you will have 2 hours 15 minutes to solve 6 problems. The score distribution will be announced closer to the start of the contest.
Of course, this round would not be possible without the help of many people, who I'd like to thank:
- isaf27, for coordinating this round, and helping with solution ideas.
- My ICPC teammates Kuroni and strongoier, and coach cnh355, for encouraging me to pursue competitive programming. In particular, I'd like to thank Kuroni for being so spectacularly bad that a barely-orange user like myself actually has a place on our team.
- 300iq, antontrygubO_o, Ari, ffao, fpc_coder, gamegame, Kuroni, entropy07, McDic, richzli, and VilgefortzOfRoggeveen for testing and providing valuable feedback.
- KAN for checking the problem statements, making them even clearer.
- MikeMirzayanov for providing the Codeforces and
MonogonPolygon platforms.
I've done my best to write clear problem statements and strong pretests. Don't forget to read all problems, and I hope you enjoy the round. Good luck!
Because I know you all have so many questions, I have compiled an FAQ:
- Q: Is it rated?
- A: Yes.
UPD
Here is the score distribution.
Div. 1: 500 — 1000 — 1500 — 1750 — 2500 — 2500
Div. 2: 500 — 1000 — 1500 — 2000 — 2500 — 2750
UPD Unfortunately, this contest is delayed due to problems in the Codeforces system. It is temporarily scheduled, but I will update this announcement when a final decision on scheduling has been made. It is sad that my contest is delayed, but let's be grateful that the issue was detected early instead of arising in the middle of the round. On the bright side, this may be the earliest announced score distribution in Codeforces history.
UPD The final decision on scheduling is to keep it as is. The contest will take place on May/06/2020 17:35 (Moscow time).
UPD Unfortunately due to the long queue and other issues, the contest is unrated. There was also a bug that gave us trouble in answering your questions. I'm sorry if you asked a question that went unanswered for a long time. I promise we did our best to answer as many questions as we could! Despite all the problems, I hope you enjoyed the problemset!
UPD Editorial
As a tester, I enjoyed the problemset! Participation is recommended :)
Would be strange and funny if you said "contest is bullshit".
Can't disagree
But if that was what he thought of the contest, he probably wouldn't post anything at all.
Some testers do that
I just downvoted you just because I hate Petyr Baelish =))
update: Just a joke! why so serious?
downvote for u ^ _ ^
that should be a really positive feedback if i get it right xD
good one.
I hope it means "go and increase your rating":D
+1, I had fun testing this too!
it's ok to postpone it instead of doing unrated round.
Underrated comment
sad
-looks like bait.
-yup definitely bait.
When reds say I enjoyed solving a problem, for me, it generally means that I will enjoy reading editorial for this problem after the contest.
quite true.
How people get the chance to be a tester for any contest? :)
Most likely you will get a message where somebody asks for your help.
Like this is random?
Well, somebody chooses to send such a message to you, or do not. So it is not really random.
There is a channel where coordinators can ask for testing. It is not public of course. People try to cheat even without access to problems.
Most authors usually ask their friends to test.
Codeforces Round #639 lost in queues somewhere....... TRUE. But enjoyed problems.
Very true indeed
Any specific reason for exactly 2 hours 15 minutes? :o
Yes.
I am intrigued.
And it is?
Ok now it's making sense why extra 15 minutes were given. But 15 minutes is very less for such long queues. Should be 6 hour contest atleast.
long queue
long long queue.
queue < long long >
Good luck for you too for 1st problemsetting. Hope we will get a new problem setter who makes good problems.
Btw, the era of "is it rated?" almost ended. Now burning FAQ is "Are pretest strong? Is problem statement short?"
The contest is unrated! Though the problems are really good.
New one has come "Is it queueforces?"
2 hours 15 minutes hmmmmMM
wow another clear statements ans strong pretest contest <3
Is there any specific reason that many people downvote a comment? or just to minus my contribution?? i didn't get any point though.
It's ok bro don't bother too much about downvotes/upvotes.
ok
Don't forget to read all problems
It didn't end well the last time the announcement had this text.
Why?
Well.....
This aged well
Omg. Are you from the future?
I am a simple man. I see "clear problem statements and strong pretests", I upvote.
Nope, you still can.
Maybe you forgot to say — "Nope, you still can. With many downvotes."
Do you know if it's rated?
Is it rated?
Is it unrated? :P
It is going to be true...
FAQ is surprisingly helpful.
But it contains incorrect information.
Why exactly is it unrated? Yes, I did read the announcement, but isn't the disadvantage the same for everyone? By that argument, the contest would still be fair.
Sitting through such long queue, shifting to another problem only to receive a non-AC verdict after half an hour. Incidents like this during contest is irritating. Some people give up and leave the contest. No one wants to sit through such a contest only because "the disadvantage is same for everyone"
I can feel u from ur profile pic.
LMAO
Please make the pretest as strong as you can (/ T — T )/ .
RIP Kuroni
Hello!! CODE FORCES :)
Help Please!!
I want to set Macros and shortcut templates for faster Programming in C++ .. Please!! tell me how can i set it so that it will be easy to realize.. Please Share your submission code and give me some advice!! :)
Check out this blog C++ Tricks
Why people are giving down vote in this Comment!! Is it wrong to want help from elders!!? :(
Because you wrote it under an irrelevant blog post instead of asking in an appropriate place. And such posts pollute the contest announcement.
OK. Sorry for this. Please, tell me where i can post this!!?
In your current case I think you should just look around on Google and post only if you are sure that for some reason nothing matches what you found on Google.
In general though, make a new blog post.
You can also ask in your blog. I think this is the right link to create a new blog.
super short FAQ and i have nothing to ask.XD
thank u Codeforces... Thank u Monogon and all writers :D I hope the Statements are short :)) Good luck to all participants and Stay at home with Codeforces *_^
avatar checks out
whats ur point :(
Always keep an eye on baby lions. They will become a grown up lion someday and make your life hard.
avatar checks out, too XD
Hope to become mamme_hunter this time 😜
Monogon What is the proof your existance, except for the analogy with names of other polygons?
hopefully this round would be like the same as previous one..short problem statements and fast editorial..
I will participate with gratitude for you!
Schools are like:
Taught in Class: Div2 A
Solved for practice: Div2 B
Homework: Div2 C
Exams: Div2 D,E,F
why people are downvoting such a good comment :(
❤
❤ man I thought CF doesn't support emoji, you showed me the path ✌✌
Exams: Div1 D,E,F
Exams: April Fools Day Contest A,B,C
Really helpful FAQ. Thanks
Why there is Pupil in the Div.1 registration?
[Edit : It's fixed now.]
[deleted]
I think that this rarely happens.
Probably because when they signed up, their rating was greater than or equal to 1900, but after a few contests they scored lower
That's only true for the Expert in the registration. What I mention is Pupil in the registration, and it's virtually impossible after the registration CM becomes Pupil because the registration is opened usually within 2 days before the contest. :(
[deleted]
Ramadan Mubarak And Happy Coding
Striking of the word Monogon . Was it suppose to make u feel cool .. I m sorry my friend u failed to do so.
It's supposed to make me look degenerate.
It was better to 2 hours & 30 minutes .
I hope it's 2 hours.
Another question that everyone wants to know:
Q: Can I participate without rated?
A: G̶o̶ ̶t̶o̶ ̶t̶h̶e̶ ̶h̶e̶l̶l Good question! The answer is no.
Every game is a record of our experience. Although these scores are not rising all the time, on the whole, we have surpassed ourselves in the past. Good luck!
Why did you say that to me?
Anyway what you said is true, except that it does not depend only on luck but also effort!
Wait another 3 days for such emotions
It's how I felt in the previous contest
I like your previous avatar :D
I failed in the last contest,I wish to be Master in this contest. up,up,up !
Don't know about u, but if I participate I am becoming Candidate Master in this round.
isitrated?
Are you kidding?
Many experts are registered in Div 1 contest!How? And I knew that candidate masters are participants of div 2 contest.Also I was rated in last div 2 contest.But today I can't register for div 2 as rated one.Why?Actually,I'd been candidate master recently...Thanks
Understood the system of my second question.
The experts who are registered for div1 were candidate master before round #638 rating change. They registered for contest before rating change so they are registered in div1. After rating change there rating decreased to less than 1900. This might be the reason behind invalid registration which will be hopefully fixed before contest.
are problems sorted?
Yes, the problems are sorted by difficulty.
last statement was funnny
Monogon System
I am waiting for darklight13 to become blue:)
Queue got freezed before the contest ........ What does this indicates ???
That indicates judging system will be smooth during the contest (hope it will
When you couldn't do anything but you can hope.........
This indicates the rescheduling of the round
Have I not noticed this before or is it the first time a handle is green in the testers list?
i think so too
i hope that this contest will be more interesting as that of the previous contest
because you have you first contest...>
FieryPhoenix contest was excellent hope Monogon your contest will also be amazing best of luck to you too...!
ready for Queue forces
Q u e u e forces
It could be cancelforces if they can't fix this issue on time =))
the_midnight_sun, are you from the future?
Q u e u e.......
Is it unrated?
it is rated i think
So u want to break worse record?
Well, it is....
QQ for the problem setter, I really liked the problem
Hope Simple statements and Good Luck for everyone!!
One general question, why do some Legendary Grandmasters have the First Letter of their initials as black and rest of the name as red? What does the Black character signify?
It looks cooler.
The Legendary Grandmasters have rating over 3000,but the International Grandmasters don't
People whose rating crossed 1900 in the previous contest are still in the participant list of Div2 will they be shifted to Div 1 during the contest?
No, Codefoces takes the rating when you register. If you have a rating of lower than 1900 and you register, then you get over 1900 after you register and before the competition, you are still a division 2 participant.
I hope this contest will also have short problems and strong pretests like the previous one, At least strong pretests.
Q: Will it be some live stream on YouTube to up-solve the problems straight after contest?
A: Algopedia: https://youtu.be/HneuObfyDtw
Auto comment: topic has been updated by Monogon (previous revision, new revision, compare).
Why are there two problems with the same score in Div.2 but not in Div.1?
UPD: Sorry for my mistake. I'm used to putting the score distribution of Div.2 at the top when I prepare contests. And personally I think that looks better because the problems are in increasing order.
The two problems with same score are in Div. 1, not Div. 2.
Div 2D is again 2000 points. :( That did not go well for me in the last contest.
new to CF, so can anyone tell me what the score distribution means?
every problem comes with a different score based on difficulty. as the contest proceeds the score of every problem keeps on decreases.
While you're waiting for the contest AOE2 tournament
...well, this is a DauT round.
Seems Div2 E and Div2 F are equally tougher.
Why has the contest date changed?
Mike has posted the reasons for rescheduling.
Codeforces is under lockdown due to covid19 for 3 days
Hope Problems and scoring remains same!
After round is rescheduled for 3 days later
Q: Is it rated?
A: Well yes, but actually no
Auto comment: topic has been updated by Monogon (previous revision, new revision, compare).
Just curious if there's any specific reason why the score distribution is not announced much before the contest??
So that people cannot pre-plan strategies or try to guess their way out about the problem difficulties I guess.
Hi, i have a question. The score distribution of div 1 is less than div 2. Why is that?
Why down voting when someone asks question? I know its not the place to ask and his question is literally trash.
Auto comment: topic has been updated by Monogon (previous revision, new revision, compare).
In general, are you allowed to write a program that basically makes your submission unreadable so it is harder to hack? For example, the program can add comments, remove/insert whitespace, etc but it doesn't change that basic functionality of your submission.
No. Code obfuscation is explicitly prohibited by Codeforces rules.
So the question is WHY don't you want others hacks your program?
If your program really has a bug, others may find it out and correct it for you. Thus you can fix it in the contest in time instead of receiving an unexpected WRONG ANSWER verdict. This case is profitable for you and others.
So my advice is: TRY to write clean programs. (Although I'm still not good at it :v)
Lol. Why is the score distribution for Div.2 higher than that of Div.1?
Because the div1 guys just act if they would have the harder problems ;)
Thanks for the faq. Much appreciated.
Today, i got notice for an internal test (online ) from my college which clashes with this contest . After waiting for 3 days i have to skip this contest , hope its timing can be changed :-(
forget_it lol ,just kidding
Wow! over 2K registration of Div.1, thanks to the delay.
Perhaps it will be the biggest one of the whole time.
Also over 1.6K upvotes before the beginning of the contest. :D
And now about 25000 registration of Div.2!
All the best guys!!!
I hope everything is going fine today and remains fine until contest ends.
We will be live upsolving the round 10 minutes after it finishes on Algopedia: https://youtu.be/E7fiCGAqNJM
I will stream poker after the round here. please donate!
if my bro gives me a microphone I will sing too
Comeback!!!!!!!
The network is so unstable and I frequently experience 502 and 504 as I reload
queueforces
Long queue again !! :(
Queue is now infinite, but is exactly one submission assigned to each room ?
Queue > 10 mins rn
Queue > 40 min!
Unrate?
I am unable to submit solution. it's showing "unexpected error".
Waiting like should i move with next question or should stick to it till verdict
Great servers, thanks Mike!
Hi, I registered for the contest but I'm being redirected with the message that I should have registered for the contest when I try to re-register it says that I'm already registered :/
Unable to enter contest area, bad gateway :|
You can catch my (little) rate. I'm give up for this constest.
The long queue makes it really difficult to analyse the bugs(if any) on wrong submissions since the verdict comes after a long time. This really affects the aura of the contest. Though the efforts put by the contest designers and testers and also by you Mike are great, please consider making this contest unrated.
Getting logged out, timed out on changing pages. Not really able to solve sadly :(
and here I though something is wrong with my browser :(
Getting logged out, again and again!
QUEUEFORCES ...
wtf is wrong with codeforces ................. pretty demotivated
whats up people suffering in queueforces
Every time I try to submit a solution(without knowing my previous verdicts) I am finding myself being kicked out of contest arena kindly look into it
getting logged out again and again stuck in queue since beginning
And again $125658, Karl!
long queue... it will be great if u make this contest as unrated
All codeforces in slow motion.
Is it still rated?
Login-Bad Gateway-Refresh-Logout Repeat
The problems are nice but it's upsetting to see that the website is not working properly :(
I've a very strong feeling that this round will be unrated!
SLOWFORCES
QUEUEFORCES
Looks like this contest can't be a rated contest. Is it so, please make the announcemant!
I really feel sorry for the problem setters, the round was delayed in order to fix everything and still it ends in this horrible way :(
I am not blaming Mike thought, I am sure they did their best :(
But then, this is life. We can just put the best of our efforts!
Over 200 pages of submissions (that's ten thousand) in the queue as of writing... Is this a new record?
Make it unrated already!
Refresh is the new Logout!!
Really!?
I know right, so ironic.
please make this round unrated
The round should be unrated. Even now, I have been experiencing severe session issues. (i.e., I'm being logged out automatically) Even when I go to the m1.codeforces site, the queue is so long that the code I have submitted for Div2 B is not judged in the time I read, conceived, and submitted a solution for Div2 C. Update: The first one was judged after 30 minutes.
Seems like this round was cursed
Make this round unrated.I fill pity for problem setter. Problems were good.
Ya please make this round unrated we are not able to submit also and even logout several times and the queue is persisting for hours
please unrated div. 2. it's almost post-apocalypse
I'm going to sacrifice my left testicle if the round remains rated.
Congratulations! You protected your testicle!
lmao same here
I will suggest Mike take your testicle and make it rated for you
Please delete this, it's vulgar.
Every time when I am going to refresh, it's automatically logged out, does it only happen for me !!
This aged well.
I am getting logged out for no reason at all :/
Nobody:
Codeforces: Delay the round with apprehensions of queueforces
3 days later
Codeforces: Good to go with the contest
Me: start contest
Codeforces: Double impact — queueforces and "keep logging you out every 10 minutes"
Me: I won't give up
Hour and a half later
Codeforces: Contest is unrated
Me: Let's give up and go read the comments
scrolls to this comment
Me: Bro! Same feels — hit like
Codeforces: You need to enter into the system before you vote
We need quantum computer as soon as possible
This is by far the worst queueforces ever !!
Why the questions about the problems and during the contest are not answered by the problem setters?
Rank 6, +148, and with Div1.D in queue --**unrated**
This round should be unrated.
I Think We have reached 35 minutes of queue. Unrated Contest seems to be inevitable now
Waiting for a submission verdict be like:
The judge queue is too long. I have to wait almost half an hour to get the answer. This is the most uncomfortable Codeforces Round I have ever participated.
Is Div2 also unrated or not? Div1 got an unrated announcement but not Div2, not sure if I should discuss problems with friends who are in Div2 or not.
Mike: We have rescheduled the contest to avoid long queues.
Users right now:
Is it a way to show that we have to be reaaaaaly careful with our submits? Otherwise getting 30 min penalty :D
Long queue + Bad problem statement
Worst Experience on codeforces ever.... I had to login more than 10 times during contest
I think MikeMirzayanov should take it seriously bcz it annoying the contestant.
is Div2 still rated? As there is no such announcement in Div2
Ok, this is too much. Situations like this happen too frequently on Codeforces. Maybe we should donate even more so you can stop this from happening every 3rd contest or so?
Dear problem setters, please submit your problems to other, more stable platforms. The quality of your problems deserves much more than this.
i mean they could have just added advertisements to codeforces to keep more servers? also I heard they use Windows servers for testing. Maybe Linux would work better? idk
I don't know why people complain about cf when it has bad rounds. It's not so frequent for rounds to be unrated in such a way, when was the last unrated round because of queue issues? Surely not 3 contests ago ... It's hard times for codeforces too, number of participants in rounds doubled during pandemic. And I think at this time we shouldn't have such negative thoughts about cf.
Can we have a contest with hidden verdict?
No
In China, we have 'OI' contest rules, and it works as follows:
Chinese OI rounds, please.
I hate null feedback rules. Newbies should especially hate them.
In fact, the first time I see the long queue, I have pretended to participate in OI rules, and because I have participated in so many OI rounds in China, it seems perfect!
In addition: I would probably become 2900+ had this round been rated.
That's real bold, calling your rating increase based on 0.5 hours of evaluated submissions before the round was announced to be unrated. I've also had very good results in some quickly unrated rounds, guess why.
How about this: make your own website where you'll host contests with these rules. I'm sure all the Chinese LGM-tier contestants will appreciate it for the same reasons as you do.
That looks similar to what Topcoder does.
If this round is still rated, I think it is really unfair for contestants as the judging time is too long. It took more than half an hour for a single submission!!!
It's unrated.
wtf
Offlineforces:/
Mike: Coronavirus, can't get into our systems. Becoz its not the software based virus, it's a physical one.
Corona: Causes lockdown worldwide, increases the number of participants in contests, blows up servers.
Mike: wtf !
The problems are so cool, so it's a pity that we can't enjoy them completely because of the long queue :( I hope that everything will get better. Live Codeforces!
Because I know you all have so many questions, I have compiled an FAQ:
Q: Is it rated? A: Yes. Mike: Actually, no.
This is what happens when the contest is postponed by 3 days---> Unrated
the answer to FAQ turned out to be wrong
Besides the long queue, why the overlap between div1 and div2 is too high? So if someone solves all problems in div2, they could be top10 in div1.
Do you really think it's so easy to fc div2? Pfft, please...
Anyways, if this was actually a rated contest without the queue issues, div1 top 10 will definitely not be 4 ACs by end of contest (it's a six-problem round, probably at least 10 people will solve E or F). So your point is pretty much invalid.
Read my comment again. I talked about the high overlap not being easy of solving all problems.
Now you know how a TopCoder SRM feels like
Declared unrated now. Feeling bad for the contest organizing panel. Though it was a bad experience for all of us, but I still appreciate Monogon along with the whole contest organizing panel for their efforts. It is not easy to be on the other side of the table. Thank you!
i submitted sol of a in 8 min but it was not showing in submission tab there i reload the page several time around 10 min because i was continuously logged off and my submission was not showing in tab and also not showing in queue either therefore i resubmitted again .and after 5 min of reloading i see two of my solution in queue! miracle ! REWARD -50 points(resubmission) and headache/tension. if site cant handle too much traffic just make more divison to handle lesser participants per division. AGAIN SED LYF MONOGON .
That's... not how divisions work?
The irony is that the one question answered by the FAQ has been answered wrongly.
thanks for wasting my time !!
Contest contained a lot of good tasks, solving them was definetely not a timewaste
My brain: NONONO! Don't say that, please, grow up!
Me hysterically laughing: QUEUEForces xDDDDDDD
My brain: Idiot...
Because I know you all have so many questions, I have compiled an FAQ:
Q: Is it rated? A: Yes.
T.T
It was my first chance to go to Expert. But it is unrated kkkkkkkkkk WTF
feelsbadman
logged out even during writing the comment Atleast the questions are good
Is testcase 5 correct in question c (div2)? There is no guest 2 technically as there is guest 0 and 1 only
It's correct
Can't edit my other comment.
It's correct. Now that the contest is unrated — all guests will be moved from room i to room i + a[k%n], not just the guests from 0 to n-1.
There are infinite guests. Read the question correctly, I made the same mistake.Not just 0 and 1 but every integer from -inf to +inf. You've to ensure that after shifting, everyone goes into a unique room.
"Just solve problems for fun." Can't even do this because the website is crashing after every reload.
Try the mirrors, they work for me more consistently.
The problems were beautiful .. I feel bad about making them unrated .. Thanks Monogon
This was unrated, but I could enjoy for this round! Monogon , MikeMirzayanov and all member, Thank you!
Man, I knew how to do A-E this contest (or at least am pretty sure my solution is correct, it's still loading :( ) wish the website didn't have problems today.
"Because I know you all have so many questions, I have compiled an FAQ:
Q: Is it rated? A: Yes."
Q. Is it really rated? A: No.
What a waste of good problems... :( Solved ABC before round became unrated. Read D and E till now and will go for D. E seems interesting but haven't been able to come up with anything. Also, Monogon, I'm looking forward to more rated rounds of you. Good problems! Thanks for the contest.
RIP servers but nonetheless, hope you do your best Mike at having such issues fixed :)
It should be cancel the round :D
New record? Is this an unrated round with most upvotes?
For meme material, refer to the FAQ in the post.
This round will be remembered for great memes
Probably because everyone can agree that (at least for Div 1) the questions were really great.
Nope, that's because the blog was already upvoted before the round.
Problems weren't bad but weren't amazing either. A-C are fine/whatever, D is boring/standard,
E is too easy (if I got a correct idea)and F looks quite artificial but I heard a minute ago that it has a very nice solution, that's something. This should be an average round on Codeforces, I guess.Independently from this, I obviously pity the author who put a lot of effort into this and created problems without any visible flaws or mistakes.
I think C was cool once you got what was going on. Or maybe I just suck, so it felt cool to me. :')
How did you solve D? My submission currently still in queue and I'm not sure if it's correct or not. Does the solution have to do anything with connected components?
He is talking about div 1. Btw I also think number of white will be number of connected components. First we check whether columns and rows are continuous, I mean there should not be --B-W-B-- kind of sequence, that is just my idea.
On top of this I think you should also check if there exists an empty row(or col) while all the cols(or rows) are non-empty.
Oh yeah that is also to be checked for placing the south monopoles
As you mentioned in your comment D is standard, Can you please provide me some reference or explain Div 1(D) because I'm not getting editorial's solution.
I guess it might help to solve many problems about binary searching the answer or some other parameter. This is an easier version of parametric search (or Lagrange search or Aliens trick) from IOI 2016.
Okay! Got it. Thanks for the help.
Nice problems, bad luck.
No matter what happend, I will still love the Codeforces. Thank you, the CF. I will cheer on you. P.S.:In my country, it's called "add oil"(加油). I love this website.
are you taiwanese??
Actually, I am a Chinese man lives on the mainland. Nice to see you~ 我们都是一家人
ffs, that was painfull experience
Thats what she said.
While I am struggling to solve E, Mike is working on "Problem Z: Fixing Codeforces".
when you finally solve B after a long time(pun intended)...only to realise the round is unrated...
RIP 609
The testers were right! Nice problemset, thanks Monogon, what a pity we couldn't enjoy the contest even more! Please don't stop preparing more rounds!
when you delay the round because you afraid from long queue, then fix the problem, then make the round, then round becomes unrated because of long queue
![ ](
)
I'm Stack.
When you realize wrong submission isn't just -50 points, it's -150 points because of queues.
I really like the problems of this round, congratulations for the authors Monogon! I'm hopping for the next time you organize a round. And I hope that Mike could solve the issue soon, thanks for all!
my CF predictor was showing +163 (ಥ﹏ಥ)
Codeforces is under quarantine and maintaining social distancing
I got 2734 point in the contest but it's now unrated! What would the people who got high points think?
I'm at the beginning of the round thinking about my ranking( I got off to a good start)
P.S. Thanks to Motogon for the round, the tasks were good!
Because I know you all have so many questions, I have compiled an FAQ:
. Q: Is it rated? . A: No.
Now the comment section be like — "Its time for memeforces"!
FAQ stands for falsely answered question.
Very nice to see the difference.
What's wrong with this approach to Div1C?
Create a graph where $$$(i, j)$$$ is an edge if $$$x_i$$$ < $$$x_j$$$. If there's a cycle output -1. Else every node with in-degree 0 gets an A, all others get an E. This doesn't pass test 5, and I cannot find a countertest.
The counter-test is:
2 1
2 1
The output should be AE whereas your code gives EA
This should be AE in my opinion, but still different :P
Ok, Edited.
Well, I think (and hope) that we greedily give every vertex an A if possible. No matter what this (let's say $$$v$$$ )vertex got, we mark all vertices $$$u$$$ such that there exists a path $$$v->u$$$ or $$$u->v$$$ that they cannot be A in the future.
My solution was basically to give A to all sources in the graph such that all nodes reachable by these sources are numerically greater than or equal to them.
Edit: It is wrong.
Check this case:
I think the answer should be
EAAAA
Again -> that's the same case as below. Errichto's case will trigger that. In your case it should be AEEEE
Well the answer is not EAAAA, because if "there exists a value for $$$x_1$$$" you'll have fixed values for $$$x_1$$$ in the sub-formula behind $$$\forall x_1$$$. And it is clear that you can't get every $$$x_2$$$ larger than a specific $$$x_1$$$. The answer, instead, should be AEEEE.
What does the problem statement really means, why this case will be EAAAA? Really confuse about the logic.
Consider this test, where you can get 4 A's. The order of vertices matters and it isn't enough to look at things with in-degree or out-degree equal to 0.
Consider a diamond-shaped graph. Only the top will have in-degree 0, but we can count sides as A
If I'm not mistaken, this should be it:
You will select 1 and 3, whereas you can select 4, 5, 6 which is better.
clearly ans is -1 for ur test case
Consider this:
3 2 1 2 1 3
Your ans 1 AEE
Correct ans 2 EAA
I think that correct ANS is 1 AEE
The interpretation of 2 EAA: there exists x1 such that for every x2 and x3 x1 < x2 and x1 < x3 -> which is false.
Consider x1 = min(x2,x3) -1
I'm sorry — could you rewrite your test if you have different considerations? The written test is a valid test and the answer is 1 AEE.
You have to pick x1 before picking x2/x3, so the answer is AEE, as P___ is saying.
I think the answer will be:
If there's a cycle output -1. Either all the nodes with indegree 0 will get an A others E or all nodes with outdegree 0 get an A others E. Choose the case where A is maximum.
Also wrong, consider a disjoint graph
I was calculating the min vertex which is reachable from v and the min which enters v. If these values equal v, then set A otherwise E.
Not sure if this is correct though.
Imagine a graph like this: x3 > x1 x2 > x1 It seems your approach fails on this case.
How many solutions are in the queue?
I waited 40 minutes to find that I missed the limit on B.
Video Tutorial for div2C / div1A
my Discord Server
that was ease made a video for E plz
Condolences for your contest, Monogon.
Thank you for the contest! I have really enjoyed the Div1's problemset
Problems were quite interesting this time. Too bad it's unrated.
yeah good one.
Not sure if this was discussed before, but can we maybe have a separate infrastructure for div1 queue?
+1
or div1-only contests
or put new CF users in div3 by default, and create lowerbound for div2
Div3 contests don't happen too often though (the last one was two weeks ago), so it would make harder for new users to participate in rated contests.
But they are easier to make and then there would be more incentive to make them.
Can people make Div3s? Seems like only vovuh has.
The problems will not waste! They will reside in the Archive forever.
If you accuse me of being a ratist, I have to disagree. Div2 contestants have more contests, so this update would just make things fair between Div1 and Div2.
Div1 only contests would be good. There's no guarantee that a separate infrastructure would prevent errors, it's not like computing power is a bottleneck in current year + 7.
F was a brilliant problem! I enjoyed it a lot.
However constraints seemed pretty high as for a solution in $$$O((4n)^3/64)$$$... (I now see it is more like $$$O(3000^2 \cdot 2000 / 64)$$$, but anyway)
How to prove for div 2 B (card construction) that you can only have a very small number of total contructions?
trial and error? need only around 30k levels to reach $$$10^9$$$
Let F(n) be the number of cards at level n. Just draw some picture and you'll see that F(n) = F(n-1)+3n-1. So we know that the limit is O(sqrt(1e9)). Second, if we can build n floor but can't build n + 1 floor, it means you have card less than 3n + 2 after you build the n-th floor tower.
Thanks. I didn't think of taking the difference between n floors and n+1 floors.
What is the testcase 17 in D?
probably something like
2 2
..
.#
answer is 1
Thanks. I found a mistake.
Damn, made a bug in counting the number of switches after I've found the time in E. Feel so stupid. :(
On the bright side, I think now I understand how link-cut trees work. :)
Was it necessary to give so high constraints in D? I don't think it is unreasonable to wish that we can solve quadratic equation on long longs (in order to omit logarithm from binary search), but intermediate computations barely exceed long long... Because of that I used int128 (probably unecessary) and long doubles with my own "SafeSqrt" function...
Binary search to solve the quadratic equations easily fits TL though, my code took around 1s on pretests: 79187272
I mean, I was aware it can be done by binary search and thought it is probably gonna be sufficient and a bit easier, so it is not a surprise to me. Just was not sure it would be and it kinda didn't feel right since solution with better complexity is comparably easy. Only after I coded it I noticed hypothetical issues with it. And of course there is no reason to set $$$a_i$$$ up to $$$10^9$$$ instead of $$$10^8$$$.
Sad that this round became unrated. This was my best performance till date.
Consider for a moment the idea that maybe your rank is so good because many people might have given up after seeing that the round is unrated.
Bye +200 rating change :C
Well, good that you moved it.
Still 99 page submission is in queue
Although it's sad what happened but I can safely say that the entire cf community will be there for any test rounds, any kind of testing MikeMirzayanov and the dev team needs. We'll see this through.
1-hour long screencast and 30 minutes of refreshing submission status: https://youtu.be/0PPz7XFQAh4
Got it.
Monogon Irrespective of the fact that the contest is now unrated, I just want to say that it was a great problemset. Great Work. Hope to get more contests from you in the future :)
Enjoyment from MEMEs on this round>> Enjoyment from the round
getting wrong answer after 1 hour queue is frustrated
I got to know my solution failed the pretest after the contest :\
Really liked the intuition behind Div 2-C.
Auto comment: topic has been updated by Monogon (previous revision, new revision, compare).
I really did enjoy the problemset. It's a shame it turned out this way. I want my time back. I want the problemsetters to get their time back.
For Div1, I think B and C are interesting problems, D seems to contain a well-known technique in China (I don't know if it's well-known to other countries), so it's relatively easy to think for me (not very easy to code).
Fortunately I wasn't affected too much by the queue, I made all accepted submissions. But it's not hard to imagine if someone's code is wrong, and don't know about it in such a long time, his/her experience is gonna be terrible.
Last two rounds I participated in are all unrated, and I got satisfactory rankings in both of them. If they were rated, I may get 2800+ or so. My feeling is just... so sad :(
Seems that CF's users are toooooo many for the server, I hope there will be fewer situations like this, they'll just make everybody sad. But I don't want to blame the Headquaters, I believe they did their best. But it's indeed a serious problem, hope we can come up with a solution ASAP.
Well-known in US too, see this. :P
That's only because all the contestants from US are Chinese anyway.
I'm not from China or US and didn't solve USACO very attentively and still consider the trick in D well-known. It's just efficient simulation of "select the largest $$$K$$$ elements from $$$N$$$ decreasing lists". Not bad but I wouldn't see it as div1D.
Can you share the trick?
I felt I was doing horribly and was happy the round got unrated, but now I'm somehow 12th before systests, which would probably have gotten me to LGM. I guess you get what you ask for QAQ
E was a great problem, though maybe a bit unfair for those who don't know how link-cut trees work.
On the other hand, what was up with D? The idea was trivial to find (increases in the sum are decreasing, so greedy works -> binary search the last increase we use), but the bounds were so high that you had to be paranoid of overflows. I suspect this was intended to be the difficult part of the problem? I don't really find that kind of problems enjoyable.
I feel that ABC were easier than they usually are on Div1 rounds.
Your place would be worse if everybody participated till the end ;p
Bruh, it isn't unfair to those who don't know how link cut tree works. Those who just copy-paste without understanding should suffer.
You don't really need to know link-cut trees to solve E -- that was the author solution but small-to-large merging gives you that the number of switches is small, which is everything you need to solve that problem.
As for D, I think we knew it was a bit easier than typical D -- overflows aren't really a problem since the highest bound you need for your binary search is less than half of signed long long range. And even if you do pick the bounds incorrectly and overflow, chances are you're still getting the right answer anyway if it decides to behave like unsigned integer overflow.
Talking about the bounds on D, during the testing I nonchalant set the bounds to be
LLONG_MIN
andLLONG_MAX
. It turns out the binary search actually overflowed 3 times, where themid
value goes:and since
-3026418949592973313
is always an invalid answer, the binary search behaves normally from that point on :)Problem E has a really strong pretest number 5, well done)))
For c question of division 2 how 0 and 1 are getting 3?
Probably the round could have been rated with rating chages maximized with zero
net delta rating change for a contest is zero always! please have a look on ELO rating system. Check here for more info .Thanks
Not always.
Also, on the very post you mentioned:
Oh sorry for a wrong discussion! I wrote what i read in a comment on some post. Thanks for correcting!
You are right though, that it should never be positive to that extent.
In div2-C, for the test case:-
n=2 array={0,1}
why the answer is "NO"?Please explain it someone.
number 1 goes to 1 + 1 = 2, number 2 goes to 2+0 = 2 so there are 2 residents in the same room.
Why 2+0 0%2 is zero @holden1
The formula is that each number i goes to i + a[ i % n ]. Let a = [ 0, 1 ], therefore n = 2. Let's see what happens for i=1,2.
i=1: i + a[ i % n ] = 1 + a[ 1 % 2 ] = 1 + a[ 1 ] = 1 + 1 = 2
i=2: i + a[ i % n ] = 2 + a[ 2 % 2 ] = 2 + a[ 0 ] = 2 + 0 = 2
I think you modded the whole thing while the modulo operator is in the subscript of array a.
thanks for the help!!
Cool, CE after the end of the contest (int128 on 32bit g++ instead of 64bit g++)
same bro, I just named array "data" ;(
It had very nice problems but this accident ruined the enjoyment of its competition.
I wish to see more contests from Monogon
Your problem set was very nice and interesting. But unfortunately your first rounds got unrated. Hope to see you in a rated round with such interested problem very soon.
Some thoughts about the round:
1: I'm disappointed that the round was unrated, but (as someone who tends to get very salty about rounds being unrated...) it was obviously the right call, so I can't be too frustrated about it. I do think it would have been good for the round to be postponed 10-20 minutes since CF was quite unstable before the beginning of the contest, and perhaps then the technical issues might have been discovered and the round could have been postponed further so that they could be fixed, but that's a very optimistic take, and it's honestly just unlikely that every single issue like this can be fixed. Overall, I'm somewhat comfortable declaring this round's issues mostly unavoidable.
2: I'm very grateful to the problemsetter and testers for preparing the round--obviously, the issue was outside of their control, and I thought that the problems were exceptionally high-quality. (I feel bad for Monogon, though--it must be incredibly frustrating to have your round postponed, then unrated, and all for reasons you couldn't have done anything to change.) As many others have said already, we as a community need to appreciate their hard work. In spite of the queue and the fact that it was unrated, I enjoyed the round and would love to see everyone involved in creating this problemset write more contests in the future.
3: As others have mentioned, the solution to D has appeared before: see here. I don't think this is a big enough issue that D should not have been used, though, since I haven't seen this trick on Codeforces or in any other rounds since USACO three years ago, and it's a nice enough idea that it deserves to be dug up once every few years. I also think it's reasonable to expect people to derive it from scratch in-contest without having seen similar problems in the past.
4: I really enjoyed A and C--both of them were some pretty fun and original takes on mathematical concepts I had seen already.
5: I think the FAQ jinxed the round :(
Updated F.A.Q:
Contest changed to unrated was very desperate. However, I loved the problemset. Thanks for all contributors!!
Sorry to see a good contest wasted even though the problems were very interesting. I especially liked how the problem writer clearly explained the background in almost all the problems (for eg. Div2 E does an excellent job of succinctly explaining some of the mathematical concepts before building on them).
I'm, however, having a little trouble understanding the objectives of D. Here are the specific problems in case someone can clarify (perhaps all have a common answer) :
1) The problem asks for the minimum number of north magnets. However, won't that always be 0? The three conditions specified apply to the south magnet and the possibility of where a north magnet may be placed (not a mandatory requirement for north magnets).
2) For the second example, couldn't the following placement work?
3) For the third example, why do we need the overlapped north magnet on the upper right (why can't that be just a south magnet)?
You should be able to visit all black cells using some north magnet. So the answer can't be zero when there are black cells.
Oh, of course that's what it meant.. thanks
1) Due to rule 2, at least one N magnet should exist at the black area. I understood rule 2 as N magnet must able to move any of black cell after some 'sequence'. 2) There is no S at the second row, so it violates rule 1. 3) It is because of rule 2. If N is not at the upper right, it violates rule 2.
Sorry for my bad english, and I hope this helped.
You cannot satisfy rule 2 without north magnets, unless there are no black cells. Every black cell requires some north magnet to be able to occupy it.
How will you satisfy rule 2 on the bottom left black cell? Also, rule 1 is broken since there should be a south magnet in row 2.
Because rule 2 must hold on that black cell.
Understood now. Thanks!
Not understanding what's wrong in my algorithm (Wrong Ans on Test 17):
If there isn't any black square: 0
If there exist discontinuous black string in any row / col: -1
Now, observe one thing, if it is possible to fill the grid, then filling any 4-connected component entirely with S doesn't harm us. But, also since S should be present every row and column, I mark those columns and rows as "done" if they consists any black cell.
So if any row / col if doesn't contain black cells: -1 (mostly this is wrong) (Perhaps, we can insert S on white square whose row and col doesn't contain any black cells, so maybe this is the only thing i am missing???)
Finally, answer is just number of 4-connected components.
There can be an empty column/row but only if both exist. You can then place S magnet on the intersection of those two
Yeah, I wonder how to improve myself. I always get stuck at some minor cases, if I push up the ability, perhaps I can be Expert, and then even Candidate Master.
Can you suggest some techniques to improve faster(other than overall “practice”)??
As regards the long queue — I just observed on the status page, that problems which were being executed, were moved back to the queue again. Maybe this is the problem with the queue, that you keep adding new elements to it, even though they were already scheduled for execution.
A really cool problem set. Looking forward to more. Lightly upset about the contest being unrated -- I solved Div 1 ABC, think I probably would have solved D if I'd continued, and I'm only rated 19-something, so that would've been a big boost -- but it's just numbers.
why is there a queue now that the system tests are over
It looks like some machines are unresponsive. Add a comment and submit again, hoping that this time you will get a different worker. It worked for me -> the second submission was judged while the first one is still in the queue.
How to calculate what rating change would be if this contest was rated?
https://cf-predictor-frontend.herokuapp.com/
Hvala vam!
I genuinely sorry that everything happened as it happened, but I liked a problemset pretty much. Good luck in the next rounds!
What is the testcase 15 in div2 D?
Can we probably just have +ve rating changes? instead of completely unrated
Where is the editorial?
https://codeforces.me/blog/entry/76819
Moral of the story: never to compile a FaQ about the contest being rated.
Why same code 79221325 passes on using c++17 but shows 79185573 MLE with c++17(64)?
Your union_1 function doesn't return anything. Fixing this gives AC.
Ok thanks, But why this happens as function may return any undefined value and as I am not using this value anywhere so it should work fine.
There's nothing that code should do. It's undefined behavior, the code can do anything at all.
While participating in the contest, I was repeatedly getting logged out from codeforces on its own. Does anybody have any idea why?
why same algorithm 79234301 passes on using c++17 but 79234579 got TLE with python 3?
EDIT: pypy3 passes... whaaaaaaat??? I have no idea now...
python is too slow, pypy works faster. but c++ works the fastest for all time.
Editorial?
Editorial
you can't have that S on white because then it creates a possibility for the N to go there
There is no restriction on how much a magnet can attract. It can attract as much as to bring it right onto itself.
Is the editorial gonna come out anytime soon?
Editorial has been out for a while, I just forgot to link to it :)
I'm looking forward to your next Div.1 contest, hope it will be rated. :)