Hello, Codeforces!
OutrunMyGun and I are glad to invite you to Codeforces Round 910 (Div. 2), which will start on Nov/19/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.
All problems are invented and prepared by OutrunMyGun and me. Special thanks go to Sofija06 and NemanjaSo2005, our two most dedicated testers. We would also like to honor:
- prvocislo, wuhudsm, Marckess, MateoCV, Wibo, curly_braces, LucaLucaM, null0124, OAleksa, AlphaMale06, Firefrog418, and sahaun for testing this round and providing valuable feedback!
- IgorI for coordinating the round well!
- dario2994 for reviewing some of the problems as the coordinator of a previous round proposal.
- KAN for his contribution towards hosting the round.
- MikeMirzayanov for creating the Codeforces and Polygon platforms!
We are looking forward to your participation!
UPD1: The score distribution is $$$500 — 1250 — 1750 — 1750 — 2000 — 2500$$$.
UPD2: Editorial
UPD3: Congratulations to the winners!
- hitonanode
- Rubikun
- femboy-wannabe
- potato167
- Golovanov399
- A_G
- AmazingTalker_Frank
- Geothermal
- StarSilk
- Farhod
UPD4: Also, congratulations to the Div. 2 winners!
910 Sounds good! :)
As a tester,the problemset is breath-taking!Hope you enjoy the round :)
As a tester, I recommend you to participate, I had fun testing the round and hope you'll also enjoy it!
indeed
IM NO LONGER BLUE DABADEEDABADIE
Been there, done that.
NemanjaSo2005 orz
TimDee orz
As a tester, I enjoyed the round. Nice that my friends did 2 rounds in a short amount of time (900 was also by my friends). Maybe I should join them?
I guess this comment makes more sense now?
this round is clashing with world cup final
world cup final is clashing with this round
this round is clashing with world cup final
Yeah let’s see the participation numbers tomorrow
There won't be any significant difference.
seeing the score now , I agree
Still ICC has 2 hours to postpone the final.
coding sport.
What is the score distribution among the problems?
hope i could calm down and focus on the problems
hope i could calm down and focus on the problems
5 questions were solved during the contest... It seems like you were able to calm down and focus on the problems :)... welcome to pupil
As a tester, you know what I did
Hope to get green after that one
expecting very less Indian participants
As a first-time problem setter, I hope you enjoy the problems and orz to all testers and participants!
Excited to reach cyan after this round!
I feel like Kapil Sharma in “Kis Kisko Pyaar Karoon”, as I have to juggle between a Codeforces contest, a cricket world cup final, and an end semester exam. Still trying to find my fourth one.
Life got no chill!!
can you recommend some movies like "kis kisko pyaar karoon" , I loved that movie
contest cancel karaao
Happy Men's Day :)
Scoring distribution when?
Before round with hope.
Sunday rounds are best!!!
n0sk1ll Could you remind me the name of that legendary game on your profile picture?
Chicken invaders
Yes
hope to reach cyan today
Dammnnnn score distribution :-!
Interesting score distribution. C = D = 1750. Hope not to lose CM)
GL everyone!
are codeforces mirrors down? m3.codeforces.com? dont seem to be working
lets see who become pupil first you or me
me
Participation is less due to ICC CWC Final
ummm.. who else sacrificed this round to watch the ICC world Finals... xD.
The authors of this wonderful round, I really hope that you will never do such cool tasks again
completely unbalanced round, all there is to say.
why it gives wrong answer on test 3 ?? ~~~~~ int n; cin >> n ; vector < int > arr ( n + 1 ) ; for ( int i = 1 ; i <= n; i++ ){ cin >> arr[i] ; }
int ans = 0 ; int last = arr[n] ; for ( int i = n - 1 ; i >= 1 ; i-- ){ if ( arr[i] <= last ) { last = arr[i] ; continue ; } int cnt = 0 ; while ( true ) { int left = arr[i] / 2 , right = ( arr[i] + 1 ) / 2 ; if ( right <= last ){ last = left; cnt++; ans += ( 1 << cnt ) - 1; break; } arr[i] = ( arr[i] + 1 ) / 2; cnt++; } } cout << ans ;~~~~~
Perhaps the answer exceed the upper bound of int?
code'output : 1 0 4 9
it should be 3 instead of 4 which is wrong on testcase 3 , wonder why ?
Oh, for the third sample input, i.e.,
3 2 1? Split the 2 into 1 + 1. Then split 3 into 1+2, splitting this 2 further into 1+1. Final array is [1, 1, 1, 1, 1, 1] with three operations in total.Here is a test case that fails:
Your code outputs 4, but the optimal answer is 2. Split the 12 into 8+4, then split the 8 into 4+4, so the final array is [4, 4, 4, 4, 5]
.....
Here is a failing test case:
Your program outputs 4, but the correct answer is 3. Split 46 into 11+11+12+12.
Not good problem $$$C$$$. Solve in $$$3$$$ min, but debugging output format $$$30$$$ minutes:) $$$ABDE$$$ are cool, thanks!
Please, either get better at balancing problems or don't host contests at all. This is the 2nd time this has happened.
every time i am close to reach cyan this thing happens i am really frustrated
Solved DE but failed to solve BC....
Wow, problems are actually incredible bad)
Why so unqualified testers? That's the questing...
A: Ok problem. And the last one tbh.
B: It's just unfathomable hard. Some observation maybe or just random greedy solution, as far as i can see... Didn't get it.
C: Statement is barely readable. Why are we coloring edges??? It is just too hard to visualize. It would be much more interesting if we were coloring cells and not the edges.
Other problems: Didn't even read due to unfathomable B and C.
I agree that B is too hard for Div2 B. Other things you said is just skill issue (or maybe you are too exhausted to think as you used to).
I agree, B is harder than usual Div2 B
Disagree. Maybe i am not the smartest person ever lived, but one i know for sure. I can solve more than 1 problem in div2, if the problems are prepared nicely
Hi, can you provide more feedback about the problems and their solutions? I want to improve as a problem-setter.
bro you broke my hope to reach cyan :(
Hi, 1) problems are good, although C was difficult to implement, (but we must be able to implement such stuff); 2) did you know about a very similar problem https://mirror.codeforces.com/contest/1513/problem/F ?
Yeah I found C super annoying (output format doesn't help either) but I found E quite nice on the other hand.
Congratulations on master you performed so good
Thanks a lot! Let's see if I can stay master after this round.
cringe
My worst round ever:( Spent all the time debugging.
Is it just me or has the problem B already occurred somewhere in this exact form?
It has.
Easier version of "Extreme Extension"
https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ same as leetcode question
That is really not fair.
But the thing is... Do competitive programmers really solve leetcode problems?
I find it more funny that in the editorial, they problem setters claim to be authors for the problem.
And D is just easier 1513F - Задача об обмене
Lol, what a notorious coincidence
Can I just appreciate your memorizing skills? I saw a blog from 2 years ago(https://mirror.codeforces.com/blog/entry/97103?#comment-860402) and you pointed out that a problem was similar to another problem you have seen.
I'm confident that i've seen problem B and D within the last six months in some codeforces contest.
Good bye hopes of getting cyan
div2 with div1 problems
we need more competitions from the person with the color blue. cringe
for real :)
Should have just named problem C Good colorings to add it to the collection of annoying coloring problems.
Also I think E shouldn't be worth 2000 points, one observation is enough to solve the problem on the spot.
thanks bro now i finally reached cyan
Messed up this contest so bad lmao
Problems themselves are very good(especially I like this kind of B,C,D,E), and score distribution is also good. But only hard D2B destroyed the experience for many contestants... This kind of downvote is so sad...
Highly agreed. The people who are complaining are just pathetic.
D2B is a super fun problem actually (although I didn't solve it during the contest). It is true that it may appeared in leetcode rounds before. But again, do CPers really care about leetcode? I am pretty sure most people haven't seen it before.
it doesnt matter do cpers leetcode or not (by the way they do). This problem has its editorial published and this is unfair
cry about it
Life is also unfair, maybe you shouldn`t participate either? Sorry,just a joke, but seriously, when preparing problemset, do you think it is easy to look through 10k+ different tasks in order to create something new? In my expirience,this collision may happen sometimes, but it happens quite rarely.
I can understand how testers and coordinators missed it, but when a problemsetter presents a contest with 2/6 problems having already appeared on codeforces, it seems suspicious and is usually not appreciated in the community
What is the second one? I am not quite familiar (D is actually not present, because the trick that solves D cannot be used to minimize the function)
To be quite honest I believe there is a very solid argument for making the round unrated, and I can base it on my own experience in contest. I read B, and immediately recalled the "Extreme Extension" problem as I already mentioned above. So I had the idea, then 3 minutes of debugging later I got AC. Now, to be fair when I first read Extreme Extension a few weeks ago the greedy algorithm for one subarray popped into my head about ten minutes later, but still — I was able to breeze through today's B about ten minutes faster than I should have. The low solvecount is quite odd in light of this collision, but those who did recall Extreme Extension or the leetcode problem or whatever and who are generally not good enough to solve B would suddenly get a huge rating boost for getting top 2000, which I don't find very fair.
Also I'm expecting +84 delta so I'm not saying this out of annoyance.
Edit: why is it rated?
Dude, https://mirror.codeforces.com/problemset/problem/1603/C
It is even solved by one of the authors... (https://mirror.codeforces.com/contest/1603/submission/133683209)
I'd say it's even more unfair if most people haven't seen it before and only few people gain advantages, comparing to the problems that most people have seen it before.
B is same as https://leetcode.com/problems/minimum-replacements-to-sort-the-array/description/ D is almost same as https://mirror.codeforces.com/contest/1513/problem/F how?
MAKE THIS ROUND UNRATED MikeMirzayanov
the same problem as problem B -> https://leetcode.com/problems/minimumreplacements-to-sort-the-array/description/
almost the same problem as problem D -> https://mirror.codeforces.com/contest/1513/problem/F
We can understand if only one problem is the same as some problems from the past, but having two is not fair. I'm also certain that problem C was a copy of some problem from the past.
UPD: https://mirror.codeforces.com/problemset/problem/1603/C one more proof, thanks Golovanov399
The trick that solves D cannot be used to minimize the function, so it's not copied
did you read editorial?
"I'm also certain that problem C was a copy of some problem from the past."
proofs?
As flammifer pointed out, 1603C (the harder version of problem B) was also solved by one of the authors: 133683209, so it cannot simply be an unintended coincidence.
Note that solving 1603C requires solving the easier subproblem of this round's problem B, whose solution is elaborated in detail in the editorial for 1603C, so the authors should certainly have been aware that those who have solved 1603C or even just viewed its editorial (and can find it again with some searching after recalling it) would have an unfair advantage here.
Ya'll are mad that similar problems have appeared before, yet D was solved by less than 1k official participants during the contest, and B was solved by less than 3k participants (this is D2B we are talking about that usually gets solved by over 5 thousands of people).
Either get better at problem solving or get better at googling problems.
Based
If you genuinely believe that I would respond to my own comment then you are a schizo
Also I might pop out of your walls eventually, be wary
.
The trick that solves D cannot be used to minimize the function
you'd better to do some research before commenting)
In this context, I think it's in the other way around. The key point is whether the trick that solves past F can solves this D.
The key observation for D is to reduce it to segment overlapping problem. After the reduction, it's just simple min/max trivial steps.
And this observation is exactly the same as the "observation 3" in the tutorial of past F.
If you've found same problem, why didn't you solve the problem ?))
.
hahahah you are newbie, you can't solve problems rated 2500)))
.
Ok ok your first account LGM ahahahahha
.
CM with rating(800)
Finally reach cyan :)
it's your second account ?))
Can anyone help me debug this Solution for A ?
you can always do the required task in only 1 operation.
I know that. See my submission please & tell me what is wrong with this solution .
I'm not really a fan of F, it took me ~10 mins to get the solution and ~45 mins to code it. The idea is sort of nice but the lengthy implementation sort of kills it. (Disclaimer — tbf this might be due to my trash implementation skills).
what a bad contest
Amazing I had +102 in this round
Congratulations, I wish you the best
Ngl, I've solved that similar to B leetcode problem before and I had the advantage of recalling an approach from https://leetcode.com/problems/maximum-of-absolute-value-expression/ similar to D. Feels like I didn't deserve purple from this round.
Problem D looks familiar with a Problem before,but i forget what is it infact,both two problems are analyzed by segment and calculate the contribution but i forget what problem is that=<
Absolutely two (1, 2) equal problems on codeforces. What happened to this platform?
dammnnn
I looked at the problem, and actually it's not the same, maximizing is much easier as compared to minimising.
https://leetcode.com/problems/minimum-replacements-to-sort-the-array/ Problem B is found on leetcode. This is unfair !
Problems were pretty nice, but C sucked (that's just my bias though because it was hard for me haha)
LOL, I straight up copied my solution for B from leetcode. Zero code changes required. Not sure how was it not flagged out during testing, it was a relatively recent problem.
I'm on the list!
Good luck everyone!
Thanks for the round! problem E was quite interesting, and DF are kind of standard-ish but it is still good enough :)
DA
I solved problem E immediately after the contest. I realy dissapoint about it. I could get about 69 rating, but i get only 2. But contest was really nice. Problem C and D is very interesting, and problem E fits it's position very well. Thanks to @n0sk1ll and @ELDRVD for this time spent.
how can someone with higher initial rating and lower contest ranking than me get more plus rating points than me??