Hi Codeforces!
I’m thrilled to invite you to Codeforces Round 638 (Div. 2), which will take place on May/01/2020 17:35 (Moscow time). It's rated!
There will be 6 problems, and you will have 2.5 hours to solve them. All the problems are written and prepared by me.
Huge thank you to everyone who made this round possible:
adedalic for awesome coordination, guidance, advice, and more <3
dragonslayerintraining for extensive testing, feedback, and buffing tests
awoo, walnutwaldo20, Benq, hocky, Geothermal, isaf27, McDic, bfs.07, iankury, songsinger, Agnimandur, dcshin, chrome, Rods, brian, and Khairy for taking the time to test and provide invaluable advice
MikeMirzayanov for wonderful platforms Codeforces and Polygon (preparing problems on Polygon is fun!)
You, for participating!
I hope everyone will enjoy the problems! I have tried to make short statements and strong pretests. Hopefully this contest will be even better than my previous one :)
UPD: Thanks also to darnley for proofreading statements and suggestions!
UPD: The scoring distribution is standard: 500 — 1000 — 1500 — 2000 — 2500 — 3000
UPD: Editorial is here
UPD: Congratulations to the winners! I hope most of you enjoyed the round. If you have any questions, feel free to ask in the comments.
Overall Winners:
Div 2. Winners:
Thanks for your hard work making the contest,
HOPE! to see some problem names starting with "Cows..."
agreed :p
Cowedforces. :-D
wow, that's very cool
Thank you Fiery for taking the time to write a contest for us. I am sure it will be a stellar contest since it was written by the god Fiery himself.
It is going to be good contest! GL & HF for everyone!
Ahh, more ans more contests!! I like it..
OMG BENQ TESTED A ROUND :O
OMG!!!
codeforces is saving me in this quarantine period.
Situation be like:
short statements and strong pretest very happy to see this
Agree, always loved to solve problems with short statements
Looking forward to some FieryProblems with FieryPretests !!
[Deleted]
Except yours.
:((((((
When people put "[Deleted]" on their comments, that just makes me want to downvote them more. I'm still gonna see the comment, but now I have to spend time pressing previous revision.
How to do that? Where is the option / button for that?
On top of every edited comment, left of the upvote button.
If a comment has been edited, there would be ← Rev. 2 to the left of the upvote/downvote count (or a higher number if it's been edited multiple times).
Click on that left arrow to go to the previous revision.
I seriously don't understand why my above comment deserves downvotes I just thanked a person It's not like I care about my contribution , but I would like to know what it is that i said which is troubling people? [Edit: I posted this when there were 21 downvotes]
Oky i wont edit them like that anymore, seems everyone has the same thoughts as you. In my opinion when someone deletes his/her comment, then it means he is shameful of what he said or he thinks his comment is nor fun neither helpful.
[Deleted]
I have no idea why someone would upvote this.
Kindergarteners are easily amused.
your rating curve is a nightmare....lol
WTF -125 0-0
I'm Waiting eagerly to participate in this contest in the quarantine period. Hope it will create an excitement a bit more
hope this will be wonderful
Thanks to Codeforces for saving me from my boring time,which gives me more opportunities to get in touch with algorithm knowledge and make lots of like-minded friends.Thanks for your hard work to make this meaningful contest.
I'm really looking forward to this contest!! Hope everyone have a good performance. Good Luck ! :)
[Deleted]
Can someone share his old contest's link ?
Goto problemsetting tab from top of the blog. Here you will find all his previous contest.
Your text to link here...
thanks FieryPhoenix... thanks codeforces... the only friend i can visit yet *_^ Always at the peak :))
I'm glad for the short statement. I hope the authors of future contests also think like you.
contestants who are bad at english also think like you :)
hahaha, maybe!
It will be great if there is no links in the statements:) -> it always takes me a long time to open them.:(
Thank you to make sure exact "problem number and contest duration" before 2 days .
Tight! Tight! Tight! Yeah!!!
Thank you and Codeforces team for making our quarantine enjoyable and productive.
Finally, you got some upvotes. :)
Еnvy silently! ))
Thanks for it "** I have tried to make short statements and strong pretests**"
Announcement: ...You, for participating!
Everyone :
""I have tried to make short statements and strong pretests."" ..Happy to see this..i think there have not any confused word like "simultaneously" (in the previous contest) ..GL everyone.
I appreciate your efforts for personally writing this post yoursef :)
Thanks a lot. But please make the problem statements clear enough and straightforward. Best Wishes <3
It felt so good to hear this.
i have a good feel about the contest ,I feel this contest have a nice ideas and problems.
FieryPhoenix OFZ
Hope no "simultaneously" to meant "at anytime".
Hey!
I'm sorry if this has been asked before — but I'm just curious about why rounds are becoming longer on average? There seem to be a few rounds these days which are either 5 questions in 2 hours or 6 questions in 2 hours and 30 minutes. A short while back, rounds seemed to be 6 questions in 2 hours on average.
Are authors and coordinators looking to make rounds harder, or maybe more implementation based? Or is this to account for more participants in some way?
Thanks!
It feels like I'm participating in the contest after ages
Nothing matters anymore
make codeforces, not coronaforces
I want to be Master !!! rp++
bilibil"l"?!
Please stop re-posting memes from last contests. Get something new man! We're bored of this.
Hi, I am new to this platform and would like to know more about the contest. Details such as — what parameters will affect my ratings?
For your site rating, the system is ELO based. For the rating for any particular contest, the problems are worth different amounts, and you also get less points for a problem as time goes on.
You can look up the FAQ.
Very happy to hear "short statements and strong pretests". This contest is how all contests should be. Also, one very very good thing is this guy thanks the participants , a new start on Codeforces . This practice should be carried on.
He didn’t thank the participators for first time. He also thanked participators in his last round.
You can check this
Scoring distribution please. :)
Score distribution generally ppublish just before the contest start
It's up now :)
Its great to see score distribution one day before the contest.
Hope for a balanced contest (hope so, because of balance score distribution)
As someone who tested this round, I can guarantee that FieryPhoenix's English is very good, and there are no major grammatical mistakes in the task statements!
I'm curious. Given the situation, you would have found "major grammatical mistakes in the task statements". What would you have posted here instead?
As a tester I would have fixed them before the contest even began by pointing them out to the contest writer :)
I would be very shocked if his English was bad, considering he is in United States.
Maybe you should hope that it does come in this contest itself! :/
Can u make it 30 or 60 minutes earlier?
When you ask for an earlier contest and all you got was downvotes
Do anybody here like long story type statements? I enjoy them, when the story has a character. The story of the character of one problem is related to the previous one.
I don't mind a story and sometimes I enjoy reading them. All I'm asking for, though, is clarity of the task. I think it is better for short contests like codeforces ones (2 to 2.5 hours) to have brief statements, as not every participant is equally educated to English.
Go read novel. Dont waste time here.
Hopes to see some new problems starting with COWs on codeforces!
Contest after 5 days. So much excited. Good Luck everyone. <3
Want to be pupil for the 1st time after so many struggle. Just 14 need..GL & HF .
Contest and Ramadan ... Both are enjoyable...
Hope this contest can be nice! Good luck for everyone!!
500 — 1000 — 1500 — 2000 — 2500 — 3000
After a long time, the score distribution is an arithmetic sequence! Really looking forward to this round!
Finally, well-balanced round
I cannot disagree more with this statement. Div2B was the hardest Div2B I have seen in a while.
I agree it was a bit harder than usual but I really liked the actual problem.
at the same time,it's the easiest div2D i ever met
Oh, It's May Day Contest.
and my rating sends mayday signal
i wish i would become specialist today. but not sure about it. need rank under 4500 or mostly i do bad in div2 haha.
Almost 20k participants... It's amazing!!
Upd. 20k+..sensationally
For the first time, I noticed in contest announcement to include You, for participating in thanks giving list. Liked it. You forgot to include yourself in the list. Thanks for your efforts to make the round!
2,5 часа — это слишком много, короткие конкурсы — это хорошо
here scoring distribution is standard, does that mean there is no difference between the guy who solves faster than other. And how does the ranking is decided? is there any penalty
As time passes, each problem is worth less points. So there is a difference between the guy who solves faster than the other.
yeah, thanks
Rip rating
How to solve C and D?
Let's make an array $$$A$$$, where $$$a_i$$$ denotes the increase in mass on day $$$i$$$. The answer can be easily restored from it, as exactly $$$A_i - A_{i - 1}$$$ bacteria split between nights $$$i - 1$$$ and $$$i$$$.
At most, on day $$$i$$$, twice as much mass will be gained, compared to day $$$i - 1$$$ (in case every bacterium splits in two).
At least, the increase will be the same as on the previous day.
Now forget for a while that there is a lower bound on mass increase (surely we can't kill existing bacteria) and greedily construct the abovementioned array (always splitting all bacteria) such that its sum equals $$$n - 1$$$ (we already have $$$1$$$ mass).
It will look like $$$2, 4, 8, ..., 2^k, x$$$, where $$$x$$$ can be anything from $$$0$$$ to $$$2^{k + 1}$$$. If it is larger/equal than $$$2^k$$$, then we're good to go. Otherwise we can just sort it, obtaining a valid sequence!
Sorry, I feel like, Yes, did all of the above. And then, what should I print as ans?
Second sentence
For c i used some observations. first sort the given string s. then try to distribute initial k characters for i = 0 to k-1. the remaining string rem = s[k:n] if rem contains more than one distinct char then it is better to add this whole rem to k-1 th string.Then ans = s[k-1] + rem
if rem only contains only one distinct char(like aaa , bbbbb) distribute those n-k characters equally , (n-k)%k will be remained after that. if (n-k)%k !=0 we need to add an extra character to ans then ans = s[k-1] + rem[0] * ((n-k)/k + ( (n-k)%k == 0 ? 0 :1)) )
note : "a" *3 = "aaa"
what was the TestCase 10 in E
Great round and great problems! Your contests are brilliant! I solved AD. I feel D and C should've been swapped. D felt a lot easier tbh. I found D easier than B, which I wasn't able to solve (and wasted more than 40 mins on) :( I was clueless on C after pondering and drawing stuff for 20-ish minutes. Read D, and happened to solve it in about 15-20 mins.
Also, does anyone know how to hack solutions? I locked my problems at around 2:20 and tried viewing other solutions for D, however, none of them loaded. Is it just my internet or servers being slow or am I doing something wrong?
Acc to me C was easy. You just need to know "aac" is greater than "aaaac" and bingo :)
Video Editorials for today's C and D
C
D
Enjoy watching!
orz, thanks for the videos!
How do you do C? I tried doing casework but miserably failed )):
D was pretty easy for placement though (for those who are more math-minded)
How did you did B it was a lot difficult
For c i used some observations. first sort the given string s. then try to distribute initial k characters for i = 0 to k-1. the remaining string rem = s[k:n] if rem contains more than one distinct char then it is better to add this whole rem to k-1 th string.Then ans = s[k-1] + rem
if rem only contains only one distinct char(like aaa , bbbbb) distribute those n-k characters equally , (n-k)%k will be remained after that. if (n-k)%k !=0 we need to add an extra character to ans then ans = s[k-1] + rem[0] * ((n-k)/k + ( (n-k)%k == 0 ? 0 :1)) )
note : "a" *3 = "aaa"
Why so much tight time limits for problem E. My code kept giving TLE on test case 33.
I guess they intended to optimise max computation :/
UPD
Wait, what? 78729467 78794202 I thought that n*k was the intended solution when I wrote this comment. But yes, indeed harsh time limit.
I guess you forgot to update DP and it calculates each of them too many times.
I am updating the dp, notice that I have used ll &ans=dp[ind][red] and not ll ans=dp[ind][red].
Oh right. My solution is very close to yours but not with recursive functions but with true DP.
All of our solutions ran very fast, but I didn't expect a recursive approach. Sorry about that.
So according to your estimate, recursive approach is how much slower than iterative one? this will help me in future.
In general, recursion has a higher constant factor than iteration.
There are some cases when recursive works faster since it calculates fewer states. Anyway, I think the main problem is long long arrays with many modulo operations
Why would you use long longs everywhere and not submit in C++64? Long long stuff run a lot faster in C++64.
I didn't notice that there is a C++ 64 also. I am changing my default to C++64 immediately. thanks for pointing out!
I think your problem are the multiple divisions and modulo operations over k. Since you are keeping red and blue to be modulo k, one easy (and actually faster) way to do this is using an if: if (something >= k) something -= k, ans++; I'm doing exactly what you are doing (actually added a second loop over the blue ones just to be sure) and still passing with the recursive approach.
Got AC with the optimization you used. Thanks.
Not sure what I am doing wrong, but my rating is going down rapidly. Nice problems anyway, thanks for that.
WOW Nice problems man, specially E and F, both were very tricky and interesting, C was too tricky in my opinion but still it was very nice.
Am I the only one who felt D was easier than C? lol
I wasn't even able to solve C but I solved D after around 20 mins of reading it :(
Yeah, me too lol. D was more like a math question that I've happened to solve in the past. Speedforced it in under 20 mins.
+1
Problem C was more complex to write code
Great problem!
Problem B was tough, I could not debug C on time. Nice contest.
Excellent contest FieryPhoenix! Problem D was especially unique and creative. Enjoyed :)
Solved D for the first time in a contest and in the last 30 sec, coudn't be happier :')
It was the toughest B for me
All you have to do in problem B is that check if total number of different numbers in array is less than or equal to k if this inequality holds means answer exist and take k numbers from array(include each number atleast once) and print them repeatedly n times .
Was I the only one who felt it was most difficult B ever and toughest C to implement?
C was a ton of casework, but if you write out all the cases, then the code is actually not too bad. https://codeforces.me/contest/1348/submission/78683019
nice implementation.thanks for sharing! Good takeaways for me!
You can get away with just 3 cases.
First sort the string.
Case 1: The bottom K letters are not all the same. Then the answer is simply the K-th letter from the bottom. Example:s="aabcccdddd", K=3 => answer is "b".
Case 2: The bottom K letters are all the same, but the rest of the letters aren't. Then the answer is a single copy of the bottom letter, followed by the entire top N-K letters. Example: s="aaabcccdddd", K=3 => answer is "abcccdddd".
Case 3: The bottom K letters are all the same, and the top N-K letters are all the same. Then the answer is a single copy of the bottom letter, followed by (N-1)/K copies of the top letter. Example: s="aaabbbbbbbb", K=3 => answer is "abbb".
thanks for this wonderful explanation!
Is ans for $$$D$$$ is highest bit set in $$$n$$$
This is what I had:
int days = Long.numberOfTrailingZeros(Long.highestOneBit(n));
How to construct the answer
What I did is have sum = 1, and count = 1. Important thing to notice is that you can only increase count from 0 to count. Greedily choose highest count you can without going over the limit N across the remaining days which can be calculated with binary search or a simple formula:
long here = Math.min(count, (n — sum) / (days — i) — count);
Then it is easy as count += here sum += count
Then print out here for the current day.
Do this for every i from 0 to days — 1
Earlier round of the same setter FieryPheonix was better than this round Round 621
Superfast Editorial thanks
I wish the pretests were strong. I was able to solve A,B,C for the first time in Div 2. Thanks for the amazing contest.
What is test case 2 of problem C??
Great contest,,short problem statements that were easy to understand..
Я: так, сегодня контест, надо потренироваться решать задачи на динамику.
Сегодняшний контест:
.
I made so many silly mistakes, and it caused me a lot of penalties, it is not happening the first time, can anyone plz suggest me some way or something to reduce these mistakes
Could you please help me why I got TLE in problem C
my submission:: https://codeforces.me/contest/1348/submission/78744306
.
This is your 11th contest.
Awesome contest..LOVED D....Tricky E...took a lot of time figuring out that it was actually a dp question but it was too late... :-(
This was literally the shittiest contest I ever participated in. Such types of problems are not expected to come in contests NO algorithms ONLY if-else based problems which are of no use at all.
Those if else case works are important for logic building. You can't be better by knowing only algorithms without case works.
Algorithms are tools,which help us solve problems.
Logic is the real thing that every contest should have.
What will you, and eventually,everyone say if the next contest is Algorithm-only, logicless?
So you mean algorithm based problems are illogical ??
Algorithms-only:If you meet these Algorithms-only Problems, you'll immediately know which algorithm to use.(Sorry, I should declare that)
Yes, they aren't absolutely illogical, but they only require a little logic
They should be used as upsolving problems, instead of contest problems.
UPD: I know that you didn't perform well in this contest. It doesn't matter. Everyone, including me, had some bad performance in the past.Try to perform well next time. If you are not good at logic-thinking, just practice. Practice makes perfect
I feel you brother, bad results are disapointing. But at least you solved B. Welcome back to green!
How could you solve problems D-E-F with if-else based solutions?
Logical,Mathematical,DS and algorithmic questions are the essence of competitive coding.
Just because there was no DP, graphs or other known algorithmic questions in the first 4 doesn't mean its bad.
I really appreciate that you used BABA in your examples, and also using Phoenix(i know its related to your name) reminds me CSGO's Shattered Web Operation, so i felt at home when solving the problems :D, thank you.
My greedy solution in E got AC. Most probably it shouldn't pass but I'm not able to break it.
Hacked it
Английский вариант F: But before he can take the photo, his friends get distracted by a duck and mess up their order. Русский: И тут вдруг пришли печенеги с половцами и всех переставили.
Как всегда отличный перевод, Дим Юрьич.
Why does using Priority queue gives TLE on test case 32 in problem C ? isn't it O(nlogn) which should pass ?
Link to Submission
Systests are pretty fast this time.It took less than 45 mins :D
**This is my solution for A **78678522
Everything was perfect in this contest! Thank you!
editorial is out at super fast speed :) nice
Java or CPP?
for CP , C++
Maybe first try English?
In problem C why this code gives TLE on test 8? 78747924
What is the meaning of this "checker log : wrong answer Unexpected EOF in the participants output" ? I am getting this in TC2 for problem C.
My submission : Here
Means the validator/checker is expecting more lines(i.e. more test cases or more data, whatever) but your input/output doesn't have any more.
Yes thank you very much.
I used return in testcases instead of continue, I just realized that(T_T).
same code
78704677 compiler: GNU C++17 verdict: WA
78705346 compiler: GNU C++17 (64) verdict: AC
But why??
I too wanna know why this happens, last contest i saw someone shared solution that got AC in g++17(64) and tle in g++17.
Editorial published so fast.. Thanks.
Did the edge between divisions change? I didn't see participants with rating 1900-2100 in official standings of Div2 round before.
when div.1 and div.2 both round happens then only 1900-2100 rated participants belongs to div.1 .
Got it, thank you!
In Div2 only contests (even Educational Rounds actually) are rated for Candidate Masters. When it is a Div2+Div1 contest, then Div1 is rated for Candidate Masters.
I have a problem in the judge of my submission to problem C:
This is my submission inside the contest:
https://codeforces.me/contest/1348/submission/78716961
It gives me TLE in test case 25
After the contest I try to copy and paste the code and submit it again here
https://codeforces.me/contest/1348/submission/78751136
It got accepted that mean it should be accepted in the contest too
What is the problem of this?
It sometimes happens that when you run your code multiple times, it takes different times to run.
So it will not be rejudged ? Or their is no solution now?
Nop, it wont get rejudged 90% of times.
I also try it here:
78753797
78753769
78753708
and still got accepted how could I ask for rejudge ?
I don't know, FieryPhoenix would answer here probable :).
There are so many submissions on system test stage, the server have lower performance than normal case. And you code runs 1996ms, it's too close 2000Ms. So your code get TLE on systen test stage.
I also try it here:
78753797
78753769
78753708
and still got accepted how could I ask for rejudge ?
I'm sorry to say that i think you will get TLE again on rejuding stage. And it almost impossible rejudge the contest again!
:''D
I mean 1996 ms for a time limit of 2000ms is goddamn close
Okay but also 1996 is accepted case.
I've just recived this message from System
Внимание!
Ваше решение 78721802 по задаче 1348A значительным образом совпадает с решениями других участников и находится в группе одинаковых решений try11/78721329, Hadiayoub7/78721802. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://codeforces.me/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован.
and these two accounts belong to me, should I do something about it ?
Multiple accounts are not allowed mate.
You should read contest rules carefully! The rules are as flows!
The registration confirms that you:
C++17: 78738413 gives TLE C++17(64 bit) :78750670 AC Both of them are same code. Why this happens?
Because C++17(64 bit) is somehow a little faster.
Learned Many things today....Thank you
Great round, thanks for super-fast rating updates and so well written prompt editorials(with easy to understand commented code)
Thankyou for hardwork. As it was said, short and clear statements. A lot of fun to solve. And become candidate master !!
A: 78733229 and A: 78665020
B: 78733627 and B: 78706022
C: 78734137 and C: 78731691
are exactly same.
Handle name is also almost same and submission time clearly indicates it's a cheating.
Please have a look FieryPhoenix
submission times indicate that submissions of the first account within the contest, while all submissions of the second account outside the contest time, so I do not think this is a cheating.
It was a 2 hour 30 min contest. So i think all the submission was during contest time.
acts of cheating like this harms the rating of others
i passed problem E,but still have questions
i used $$$O(n^3)$$$ dp at first and got tle on pretest 33
then i used a list to optmize and passed
is the complexity right after i optimize the algorithm?
78735089 here's my solution
You can ask in Luogu Discuss Area, some nice guys can help you there.
I think he definetely know that since he's a Master lol
Me too,I tried a $$$O(nm^2)$$$ dp and got TLE.
And the next morning I changed my code and used less
long longand%and it passed.Update:Fixed some stupid grammar mistakes.
Have anyone noticed that the checker comment in this round is "ok good job (xx test cases)"? Phoenix even makes the checker comment enjoyable:)
In my opinion, problem B was more difficult than most 2B's, but it is also one of the more interesting ones.
Thanks for the really nice set of problems.
ConstructiveForces
My O(n^3) dp isn't passing, getting WA in test 33. 78795957
Do we need something like O(n^3/x) to pass. And how can I optimize this?
Problem C is not clear. It can have many solution but it is accepting only unique answers.
There are multiple optimal ways to distribute the letters but the answer resulting from the distribution is always unique.
Did anyone notice that there are hidden messages in test 31 of problem C?
(vcubingx is a YouTube channel. I do not know about the meaning of the other text in this testcase. Can FieryPhoenix provide an explanation?)
Haha, this is just an Easter Egg relating to some of my friends. Nice catch :)
FieryPhoenix O.O
Fiery and the boys!
:|
vcubingx is a YouTube channelHey, that's me! The rest of the people are IRL friends of FieryPhoenix and I.
Hello, I am secret message.
Unfortunately 8 isn't a letter :(