Hello Codeforces,
We are very glad to invite you to participate in Codeforces Round 1057 (Div. 2), which will start on Oct/10/2025 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
All the problems are written and prepared by me and maomao90.
We would like to give our sincere thanks to:
- maomao90 for his wonderful coordination and careful adjustments to some problems!
- Alexdat2000 for translating problem statements.
- __baozii__, _istil, rui_er, AC-Automation, permutation, A_G, Andreasyan for red testing.
- -firefly-, K-423, frey4, Friedrich, Proof_by_QED for orange testing.
- xudian, Sofija06, qsmcgogo for purple testing.
- wink for blue testing.
- absi2011 for green testing.
- chou_maple for grey testing.
- MikeMirzayanov for the great codeforces and polygon platform.
- You for participating in the round.
The score distribution is $$$500 - 750 - 1250 - 1750 - 2250 - 3250$$$.
Hope everyone will enjoy the round!
Editorial is out now!
Some thoughts of mine (personally): I've used Codeforces for quite some time, and being able to have my round on it is really a milestone for me. I'm quite proud but also a little afraid that the problems may not be up to everyone's appetite, but they are the best I can do. This round marks quite a step for me and I wish nothing but the best for this round to go well!
Man, your profile is extremely impressive!! Zero unsolved problems, 5900+ solves, absolute consistency from last 3 years.
and he solves problems at his level, not just spamming 800s. Absolute unit!
Why doesn't he participate in contests ? I would want to see him as LGM given his impressive profile :)
This is also him: https://leetcode.com/u/Yawn_Sean/
How do you look for unsolved problems in any given (not yours) profile?
Get CF analytics extension
I am awestruck by the fact that he started solving high rated problems from the beginning itself.
Please start doing contest, We want to see you as a LGM soon.
Bro, I’ve been following you for a long time. I even messaged you in the inbox, but you didn’t reply. Since the beginning, I wanted to make my profile like yours, but suddenly one day it broke. I felt really down, and I even missed my semester exams because of it. Your profile is truly the best, bro .
spamming 800 questions is not enough solving 1400 is not good either (for you)
I know, but I want to start from the very beginning and do it properly. Right now I have exams, but after they’re over, I’ll start pushing. Thanks, bro.
After a contest try to upsolve (until possible) which is a better way to do problems above your rating.
Yeah, I did the same mistake as a newbie.
As a tester, I love the problems!
Hope to participate there in Pupil rank
As a tester, it is recommend to take a look at the activity in the author's profile.
Little_Sheep_Yawn is a green forest orz, and i thought i was pushing hard! gotta push harder!
You're pretty good too!
thanks a lot, appreciate it!
Amazon seems to be the second largest rainforest next to bro's problem solving figure.
lmaoo
fast
Try CF Submitter : https://marketplace.visualstudio.com/items?itemName=DevXSayan.cf-submitter
- Fetch all the problems of a contest inside vscode, run test cases, and submit in one click, all without leaving vscode
He doesnt goon , he Greens
The score distribution looks great, all the best to everyone!
Problems I’m guessing: A — Two Screens B — Binomial Coefficients, Kind Of C — New Game D — Attribute Checks E — Card Game F — Choose Your Queries G — Variable Damage
But there is no problem G
I have a feeling that this round's quality will match the date ... 10/10 :)
I so badly wanna give an unrated contest… just for peace of mind.
try virtual participate?
Contests these days...
I will enjoy your questions. nu~nu~
Little_Sheep_Yawn orz
As a tester, I love this contest and hope you enjoy it too!
I can't wait to participate in this wonderful competition !!!
can confirm this round will be nice as a participant by seeing __baozii__ and _istil in the testers
As a participant, Good luck to Everyone.
**Nice Score distribution,, wish there no interactive problem (: **
chinese people are built differnet holy fuck, this dude has given 5 contests and solved 5000 problems
Chinese versions always hit the records
so true....
As a tester, i don't want piece, i want probbbleeems allllwayyys
Div 2 thats so good competition for us
Oh God, give us a rating, we need one.
good luck everyone!!!
As a tester, I love this contest and hope you enjoy it too!
unrated testing ?
__baozii__ is finally testing this round
Hope i could reach Cyan this time :D
good luck !
Completely amazed by your profile. It's truly inspiring! hope to get +ve delta
As a participant, Best of luck Everyone.
What will be the penalty for each wrong submission?
they will take your firstborn watch out man its no joke here
A Yawn Sean div 2 followed by meta hacker cup practice round. Today is going to be fun!
ALL THE BEST GUYS
Hoping for positive aura delta this first contest.
Please pray that I reach 1200 rating today. Man I'll be so happy if I manage to get a 6k ish rank today.
I am praying
Is it just my code that's in queue for a long time?
Submission for D stuck for 4-5 minutes :( .. please check ..
ok it is resolved now for me , thanks
extend the time to make cheaters have more time to cheat, wow nice idea
good D
Geometryforces!!! :(
i really liked the contest!
In what time complexity did you guys solve F? Anyone solved with a square root decomposition type solution?
A square root decomposition solution is not supposed to AC
I have a $$$O((n + q) \cdot (\log {q} + \log^2{n})$$$ solution using a merge-sort tree and two persistent segment trees.
moved to the editorial
I solved F with a sqrt solution (342985427).
After the contest, I submitted a faster sqrt solution (343024311, 4874ms).
cant wait to see testcases to see what kinda BS edge case i was failing on problem C
ha ha lmao... I also made 2 WA
try this
1
4
1 1 5 6
For me it was a case like this 1 1 5 10. So Two equivalent sides, not enough to make a shape, and two additional values that are large enough to fail triangle inequality as also can't be merged together to make a parallelogram.
Me too
Auto comment: topic has been updated by Little_Sheep_Yawn (previous revision, new revision, compare).
i am really confused in E why for 36 68
ans is 13, if we take k = 31
then, for all a<31 ans = 0 and 31-36 ans is 1? am i missing something?
I think answer also depends on
68, although I didn't solve the problem.I was stuck at same thing thinking we need to find some largest prime less than
n... but then in the given test cases .. answer for6 7is1.. but6 10is0so it depends on
mas well.You have $$$\nu_{31}(32!) = \nu_{31}(33!) = \cdots = \nu_{31}(36!)$$$, so you're not allowed to use it because it would give $$$w_{31}(32, 36) = 10^{100}$$$.
oh yes, how could i miss that, i might have got confused.
how will you get 1 for x = 35
best m = 9 and ans = 8 i think
maybe something else
just starred at the screen for 1 hour on D :( anyone how to do it?
I made cases ..
and solved each one with DP .. I am hoping we can do some more analysis and reduces cases or make simpler code
but I used DP to solve each of them
Idea of DP is that if we can form a segment of length 'k > 2' with all values equal .. then we can break that segment into smallers segments of length
2 or 3and answer will remain same .. so the DP only need to look at last 2 or 3 elementsIdea of DP is that if we can form a segment of length 'k > 2' with all values equal .. then we can break that segment into smallers segments of length 2 or 3 and answer will remain same .. so the DP only need to look at last 2 or 3 elements
can you give an example for this?
yeah so final answer is circular array with some segments having equal values and length of each segment will be greater than 2 ( bcoz we can't have a lone value .. it has to have a neighbor with equal value )
so . it will be
xxxx..now this can be written asxx + xxLOLbut to handle odd case ..
xxxxx.. it will bexx + xxxso I guessed that if the answer is going to be
xxxxxx.. then I can solve forxxx + xxxit will give same answerwhat I am saying is if we want to convert last
5values to10.. then answer will be same if I converted first2values to10and then next3values to10.. so I don't need to look at segment ofsize > 3sorry don't have formal proof.. was a hunch and worked for given test cases on paper so I tried to code it coz I had no other idea !!
man nice!! thanks a lot
refer to chicken mcnugget theorem
(or you can use induction)
base case: 2,3 for n>= 4
n-1 + 2 + 2 — 3 = n
if you dont have 3 in n-1, then you must have a 2
n-1 + 3 — 2 = n
holds for all n >= 4
no, i mean like proof that breaking groups into size 2 or 3 will not make the answer worse.
wow. i m very sad , why this did not occur to me ?
I think I got lucky otherwise, I also generally miss ideas for problem D
https://mirror.codeforces.com/contest/2153/submission/343006371 , my submission for C, can anyone tell me a test case where it will fail? I am not able to figure out where it went wrong...
Answer is 22. Your code gives the answer 6.
thanks for sharing the testcase, so I am not able to choose the two leftover sides correctly...
thank you man helped me too
1
4
1 1 5 6
the answer for this should be 0, right? We can't choose atlest 3 sides such that two of them are equal?
You can choose all edges.
something like this:
-----
/ \
------
you can make a trapezium
with side
5and6being parallel on top and bottom and1s on the side.ohh got it, thanks for help…
Can anyone tell me The idea to solve problem D ?
If the array is not circular, using dp can solve the problem(try to think how).
And somehow, you can solve a circular array by solving non-circular version a few times.
Fail to solve D for over 100 minutes ): I believe it has a really wonderful solution (: but it really hits me fiercely when my rating is 2098 ):
where is the interactive brooo!
In problem D, is it true that the distance between any two adjacent elements that don't need to be changed doesn't exceed 3?
C has traumatized me honestly, can you tell why my code fails 343007268
This test case
help sir, i can't understand where i am going wrong and i am losing my mind over it
1
5
1 6 18 11 1
answer is 0
aaaah i see , i am just dumb, thanks brother
i guess you missed the triangle ineqaulity generalisation? that any side should be smaller than sum of all other sides
kinda i just added a block at the end checking if the number of used sides were 2 and if the calculated perimeter was less than or equal to any of the sides alone
to use your testcase, 1 6 18 11 1, my code ended up with 2 by adding 1 and 1, but then i needed one more side to complete the polygon but none of them were suitable, i was missing this check
string of bad contests mate
right..no issues come back stronger next contest
whoa!!!
I was overthinking
B.. but then I saw so many quick submissions and realized there will be some easy idea... then I counted set bits in 3 numbers, if at any position we have 2 set bits... we can't make it.
is there any other simpler idea ?
and(&) the 3 equalities and then and(&) equalities 2 by 2
holy moly !!!
so if they are not equal it is not possible .. is that it ?
I tried with this.
oh wow .. so clean !!!
can u please share intuition behind it ?
a&b = x b&c = y a&c = z
so a&b&b&c = a&b&c = x&y, similarly, a&b&c = y&z, a&b&c = x&z.
Then guessed that it's a sufficient and necessary condition. LOL
nice !!!
I was very shocked to see so many submissions for B so quickly, I think I was overthinking
Adding cyclic condition in D , just seems like adding forced difficulty.
I think it changes the problem for
div2B or div2Ctodiv2Dalthough I wonder if there is a clean way to handle that cyclic nature in code.you can just shift the array 0, 1 and 2 times and calculate the answer for the new array
then take the smallest anwser
oh nice !!! i think this is really cool and will make my code very clean.. will try to implement this tomorrow ..
thanks for sharing this idea.
this might help :)
create a larger array by adding first 2 elements in the last of the array then solve the problem for [0,n-1] , [1,n] , [2,n+1] and take the minimum.
343042497
makes sense I will try, thanks
this contest was great for A and B, but i think C was difficult a little bit
In Problem $$$D$$$, in the ideal division of the array into blocks, suppose there is a block of size >= 2 and it has some cost $$$c$$$, now we divide that block into blocks of size 2 and 3, so will the sum of the costs of these blocks be equal to $$$c$$$? How are we sure that it will be?
All elements in a block should be equal, so if there is a block sized 4 or above, you can break it down to blocks of size 2 and 3.
for example:
4 = 2 + 2
5 = 3 + 2
can prove that 2*a + 3*b = n, a,b always exist for n>=2
Nice contest, don't repeat this.
could someone please let me know why my C submission doesnt work My submission
i thought we distribute all sides/2 as much as possible and then take the remaining largest 2 left also some checks if ans should be 0
try
The answer is to choose all sticks =
17, but your solution gave11.It fell under the condition
if(cnt == 1 && cnt2 == 0).343005674 : My 1st submission for problem D got timed out after waiting in queue for long time most probably due to the issue in Judge but My soln is correct for sure. Anyone pls help resolving this.
i think you should try to submit it after system testing
if it is correct you can tag the authors mentioned in the post to get their attention.
343023427 : Exact Same Code, it Passed , I m getting an unnecessary penalty of 15 minutes because of this. Little_Sheep_Yawn : Pls look into this.
That's strange. I've already rejudged this submission and it did pass, but i don't know whether i can make it up to you since i don't have much permission to do a lot of things. I'll ask them.
My rank got decreased furthur after rejudging it :(
can anybody tell why its wrong ? unable to figure out
before adding the largest two leftover values you didnt check if they satisfy the degenerate polygon condition. Just run a loop and check for which two largest consecutive pair their absolute difference is strictly less than your current sum.
still wrong tc2
343027901
Just checking through the leftover was not enough. It may happen none of those pairs satisfy the degenerate condition. In that case you had to check if you can really make a polygon with your already picked sides else print 0. Also there is another edge case where even if leftover size is not 1 we can pick only one of the leftover elements and not a pair. In that case adding an extra 0 made the checking easier
oh! thanks a lot bro. got it now , was missing these small cases
SHAWW!!
PC Got TLE using unordered_map after the system test.
Why is it not allowed to use?
unordered_mapis known to be a bad choice as it has some operations run in linear time in worst cases. In your code, it's probably the access operator[]that runs linearly sometimes.code1(TLE)
code2(AC)
absolutely the same code, but the second code with a hash template
I think it shouldn't get TLE just because of using a hash template or not.
approach for problem C anyone.
Is there an option to see 100 users per page in standings? I am currently seeing only 20.
So I just removed 'unordered_' after the contest to get C accepted.
Honestly, I see no point in hiding a system test whose only purpose is to fail whoever used unordered_map with the default hashing. This feels more like a punishment rather than a lesson to learn from.
agree
https://mirror.codeforces.com/blog/entry/147101?#comment-1316388
They did not hide it. The recent rules are that pretests = systests, at least from the problemsetters' side.
It was one hack that is added to the system tests and made all such solutions fail. Unfortunately, this hack can only make C++20/C++23's
unordered_mapfail so C++17'sunordered_mapand PyPy'ssetorCountersurvived. I uphacked both, but it seems that one of the testers' PyPy code also used it, which is probably why my hack test against it gives 'Unexpected verdict'....
Fast Editorial! And a Fast Rating Update!
Happy to experience this contest. Thanks Little_Sheep_Yawn
sorry, if this comes out as ignorance but I am unsure why my solution gives TLE. It's nlogn in time complexity, something which was within the limits of the qn.
My submission I would really appreciate if someone could take their time out to look into this.
Also, all the test cases mentioned in the comments seem to get accepted by the soln.
You can read: https://mirror.codeforces.com/blog/entry/132929
Video Solution of A,B,C with C++ code of Codeforces Round 1057 (Div. 2): https://youtu.be/u9yVmNV6TrI
Very good contest ! Although I didn't solve E (miss an important optimization and keep TLE at test 8), but overall a very good round.
https://mirror.codeforces.com/contest/2153/submission/343043896
Why does my code of C give WA at test 4? Pls Help
A great Problem D, although I almost solved it during the contest. I figured out the non-circular case and also thought about enumerating split points, but I forgot that trying just three consecutive ones would be enough. Still, this taught me something new, and I believe this kind of problem is truly excellent—devoid of complex algorithms or data structures, yet highly insightful.
Video Solution of D. Not Alone with C++ code of Codeforces Round 1057 (Div. 2): https://youtu.be/EU9v463EjvM
Salam Aleykum
In problem (A) "_Note that you are allowed to skip an apple when you first encounter it, and you can choose to eat it later on a subsequent cycle._"
Is this statement misleading ? Because the 3rd sample testcase is not agreed with it. Or maybe I am not getting it ;(
I got flagged for having similar code in Problem D to another user. All my submissions are now skipped. Here's my code: submission, they say it's similar to: submission.
I believe it's a mistake. There aren't many ways to solve this problem, so similar code is bound to happen. While our code structures are pretty similar, you'll notice our coding styles are actually quite different. If someone who can help sees this, could you please review and remove the skipped status? Thanks a lot!
(Used LLM to help with translation, sorry for my bad English owo)
gou shi sha bi