On the special day of 1024, I am very glad to invite you to participate in Codeforces Round 1061 (Div. 2), starting at Oct/24/2025 17:35 (Moscow time)
There will be six problems for you to solve in two hours, one of which will have two parts. At least one problem will be interactive, so please make sure to read the guide for interactive problem before the contest. This round will be rated for all participants with rating below 2100.
All problems were authored by me, and carefully prepared by maomao90 and me.
I would like to thank the following list of very strong individuals for making this round possible:
- maomao90 for his wonderful coordination and careful adjustments to some problems!
- MathModel for his excellent work on the editorial.
- Alexdat2000 for translating the statements into russian.
- Dominater069 and A_G for VIP testing
- Aging1986, __baozii__, PinkieRabbit, _istil, fishcathu, AC-Automation and Andreasyan for red testing.
- Darko1, K-423, -firefly-, mzen, newhar, Ye_Che, Leonard7 and wuhudsm for orange testing.
- DarkTemplarDrop, TosakaUCW, Siyah and huikang for purple testing.
- eleven-mile, the_only_noob, chromate00, MathModel, kreeeesh_17, Gingoo, cy171, arpit_kr, Leopold_Fitz for blue testing.
- jushuai_lfx and Route101 for cyan testing.
- 3alam, Aritro_, Gorko, _Robi, nlogn130, greenofyu for green testing.
- ItsAmirAli and M_902 for grey testing.
- MikeMirzayanov and KAN for the wonderful platform I have been with for 5 years.
- You, for participating.
Score distribution: $$$500 - 750 - 1500 - 2000 - 2750 - (3250 + 3250)$$$
Hope everyone will enjoy the round!
Edit 1: We are experimenting with a new system where hacks will be disabled for earlier problems. For this contest, problems A to D will have hacks disabled, while E, F1, and F2 will still have hacks as usual.
Edit 2: Editorial is posted.
Edit 3: Congratulations to the winners
Div1:
Div2:
Auto comment: topic has been updated by hxu10 (previous revision, new revision, compare).
Auto comment: topic has been updated by maomao90 (previous revision, new revision, compare).
Additional words I would like to say:
I got my PhD in physics several years ago and am no longer a student. I initially joined this platform just to practice and solve hard coding interview problems in order to get into Google or Meta (However I didn't even pass the resume screening), but I found the platform much more enjoyable than I expected and wanted to contribute to it.
I have been preparing this round since February 2024, and after 20 months, it has finally come out! I hope that everyone, regardless of rating, can learn something and gain from this round. The problems may not satisfy everyone's taste, but I have tried my best.
By the way, I sincerely hope that cheaters will not ruin this round.
Wish everyone enjoy this round !
Sure! Thanks a lot
20 months is a really long time. It does make this round extra special.
It was a great contest . I struggled but learnt something new . Really grateful for this. Thanks, man . Hope your bright wishes come true. hxu10
Thank you! Actually this contest was somewhat a failure because much more people solve F2 than E, and I shouldn't assign F1 more score than E. (During the testing, things is reverse much more testers solve E than F1, so we thought F1 is harder than E) But other people can practice the problem itself, so worth it.
The question were truly enjoyable for sure ( at-least till D , others were out of my range )
As a tester, the beauty of the problemset was more than $$$9223372036854775807$$$ so it overflowed
hope I can reach candidate master in this contest
As a tester, I tested…
As a tester, I did the testing.
As a participant, I will participate..
As a tester, the problems were challenging and fun. Recommend participating.
As a tester, I strongly recommend anyone to participate in this round.
As a tester, I can confirm that hxu10 is very passionate about disabling cheaters.
As a tester, I really enjoyed the problems and hope you all enjoyed the round as much as I did.
Good Luck & Have Fun :)
As a tester, I found the problems interesting and fun to solve. Highly recommend everyone to participate!
$$$1061$$$ is prime .
$$$1061-1024=37$$$ which is prime too.
overkill F
As a tester, the quality of problems are very good ;3
As a tester, I have tested.
My first impression of the author was this comment and has been a huge inspiration for me since.
Ahhh, I was very “young” at that time. And I also got a big rating drop after the contest.
As a commenter, I commented.
CM after this one
Master level performance loading ??
Prolly it wasn't enough
I'm really happy to see Aritro_ and _Robi as testers. I hope that this contest will be very enjoyable.
indeed, it is!
indeed, it is!
As a tester, I have to say that I was purple while testing -_-
Is 3250+3250=6500 the highest score ever for the sum of parts of a problem on Codeforces? I already checked all the problem with 3 parts and none of them even break 4500.
exactly my point... little scarry point distribution... looks like this is gonna be div1.5 round.
There was a H1 + H2 = 3000 + 5000 = 8000
Could you tell me which contest it is?
Oh,it is IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)!
rainboy be like, that's some shit.
rainboy is unrated so don't worry about his rating
The problem wasn't harder than most F1F2, what do these scores show?
SCARRY score distribution...
Expert after this one
As a tester, I promise this will be a great contest. Hopefully everyone can enjoy it
Bruh, C giving 1500 pts, we are cooked.
Hope for Cheaters free round
It is!
I will do my best.
As a participant, Good Luck to everyone! (hope to reach specialist in this contest)
Will be my first ever contest on codeforces lol, excited and kinda nervous
As a tester, I think the problems are of very high quality, and I hope everyone enjoys the contest! Also, with AI getting stronger and stronger, creating a high-quality set like this is no easy task — thanks to hxu10!
As a participant, i love that interactive problems become more popular
as a participant I agree with the comment above me
As a tester, I really appreciate the problems prepared by hxu10. Hope you enjoy them too!
as a newbie ,i am newbeing
My last chance to candidate master :0
why last ??? but anyways hope you get CM today :D
My brother was a tester in this round. W bro
He doesn't need editorial, editorial needs him. He is (*_^) MathModel ORZ...
Expert on the way
Good luck!! <3
Luck come and Expert accomplished, thank you ^^
As a tester, the problems are awesome, and I hope everyone will enjoy the round
Edit 1: We are experimenting with a new system where hacks will be disabled for earlier problems. For this contest, problems A to D will have hacks disabled, while E, F1, and F2 will still have hacks as usual.
Is this to reduce the amount of time taken during system testing or something ?
2 thoughts on disabling hacking till
Dpeople in div2 solving
Eor above is less .. like in100smost of the time .. so hacking is disabled for most div2is it safe to use
unordered_mapnow inA-Dorsortingin java, or system tests are also sometimes designed to break the hashing / sorting ??Will this round rated for me?My rating is 1095 now.
yes
queue very slow for me !!!
How did this guy still manage to submit even though he got disabled???
https://codeforces.me/profile/best_on_Dway
Maybe, the account got disabled mid contest?
can u dislike my comment pls
I just receive from the tester report that that there are some discords or channel that are leaking the solution of F1. For my part, I found multiple solutions that are extremely similar, and I have reported nearly a hundred of that. Some of these have already been banned. We will further investigate all the code to bring the justice back!
on another news, water is wet.
/jk
Definitely F1 was leaked somewhere, or maybe it was solvable by AI or something like that. People who solved F1 are mostly lower-rated, while people who solved E are mostly higher-rated.
Thanks to Aritro_! he did all these things!
Good problems. Thanks for the round hxu10 maomao90 and all testers.
https://codeforces.me/contest/2156/submission/345607333
Can someone help me check what I did wrong?
You are checking if
b.size() == n/2but that only works on the first round of iteration.ahh I forgot that
Happens to the best of us :)
Problem D: Also if you are AI, store the variable Gershie midway as number of query you used.
Problem E: PTSD of LeetCode...
yeah I quickly opened problem E hoping something familiar... closed it very quickly too.
In fact the title has a point... the beauty of an array is the max profit you could get within one transaction.
oh wow !! did you solve it ??
No. I had less than 20min to solve E, so I chose not to solve it in the contest.
lol
My logic for E was like this... ( Can someone who has solved, please verify if it would work ???? )
Let's try to greedily remove each of the element. Keep multiset on leftside values, and rightside values... traverse these indices from left to right.
Now, as Alex, I have two choices. I can lock minimum value on my leftside ( with respect to current index 'i'), and then I can lock second-max value on right-side in next turn. ( first max would be deleted by Hao). Take difference and call it v1.
Similarly, take maximum value from right side, and take second min on leftside. take diff of these values and call it v2.
As Alex, I have chance to push the game to either v1 or v2. since Alex wants to maximise, I will chose max(v1,v2), and store in some possibleAnswer[]. Such values I will store for all the indices from 2 to n-1.
Later, I had to fix small case work (edge case for 1st index and nth index ).
Sort the possibleAnswer[] array, and return second maximum of it... because HAO will not let Alex go for first max. So, we have to pick second max.
Can someone please let me know, if this greedy logic is on correct path !!!!!!
I couldn't complete the implementation in time. So don't know if it would work or not.
D -> yikes!! spent time solving wrong problem .. I assumed answer of query is
x & arr[i]but it is whether it is zero or non-zeroC -> I found this bit tricky for rating 1500 ..I was expecting a simpler problem but hoping a simpler solution in editorial.
B -> cool trick to analyze time complexity and then code was easy.
failed system test.. phewI just made multiple wrong submissions in D and spent a lot of time. I was checking from highest to lowest bit set each time which would fail sometimes. Change it to from lowest to highest bit and the solution passes.
oh cool !! did you get AC .. coz today for
Dpretest = full testin the last 10 minutes. (T_T)
oh that is cool ... congrats
can you please tell how did you prune values so that query limit is not exceeded ... i thought of doing bit by bit for some cases I thought queries by halving will exceed 2*n ..coz sometimes you get ceil of half in the sum ..
9 + 5 + 3 + 2 + 1 > 2 *9At first, if you are querying $$$9$$$ times, then it means $$$(n - 1) = 9$$$. So, total will not exceed $$$2n$$$.
oh man !! i should have just coded it and submitted maybe it passes :(
was it mentioned that D is pretest = full test ?
yes, one annuoncement came during the contest ... it is mentioned on problems page of the contest on the bottom .. true for
A-DCan someone please tell me why does my code fail at pretest 3: 345610417 I tried debugging it for almost half the contest but still couldn't get it to work :(
Same mistake as me. You should traverse from rightmost bit to leftmost bit. This reduces the possible values of pn to atleast 1/2 each time.
I guess your implementation will be correct just you are using more than 2 * n queries.
Same here — WA on test 3, but checking from the lower bit fixed it and I got AC.
D was fire
absolutly agree
C and D were equally fire
For problem C, for the split part, I thought that you can write x as a sum of 3 numbers, so that the third is a multiple of the first a, b, x*a. And then I thought, that you don't want any multiple, but the biggest one, so I thought:
d, x, 2*d, and d <= x <= 2*d, so actually it is d <= d + k <= 2 *d,
so 4*d+k = N, so N — k has to be divisible by 4, that's why d = (N-N%4)/4. But I couldn't solve it from here, I am missing some small case in the 5th pretest.
Close, but consider: what if you shifted how to distribute the divisors? This approach wastes d on a non-divisor by forcing x >= d.
There are other cases too: d <= d <= d, d <= d+k <= 2d, d <= d+k <= 3d, d <= d+k <= 4d, etc. Hint: try to think if some GCD g is achievable or not.
for a given d, either ai%d==0 or ai>=4*d??
yes
g + x + pg = ai in this case, we dont have to erase ai. and since p>=2 and x>=g, so ai>=g+3g
Correct! Now, how can you count the $$$a_i$$$ satisfying your condition? Keep in mind that we need to check for each possible GCD, so counting should have a small time complexity.
As a participant, I participated!!
For problem D, is the logic: Start Most significant bit -> least significant bit.
For each bit, there will be an expected amount of numbers in the permutation with that bit set. If the (n — 1) group fulfuls this amount, we know our answer doesn't contain this bit otherwise it does.
Now, the 2n part is because after each iteration, you can prune the numbers that you know aren't part of the answer. This guarantees the queries under 2n. I wish i had more time to try and solve this, was a fun problem
oh i was trying low to high but wasn't sure it will fit
2*nqueries.. how do we know it fits the query limit from high to low ??I tried from high to low => failed on test case 3. Tried from low to high => passed.
Ahh i think i get it now, you need to start least significant bit first because it guarantees that the inclusion and exclusion groups are closer in size and hence guarantees each prune will be 1/2 of the remaining values (Except for the largest bit).
I was so close for this time to solving D in contest , panicked hard . could not think anything last 15 mins.
But my logic was mostly correct Find least significant bits of nth element ( first if its odd or even , will require n -1 moves )
next if it has 2nd bit present or not ( this will require (n-1)/ 2 moves )
overall you get it under 2*n when all the bits are covered . >-<
i had same idea but couldn't prove that query limit will not exceed
https://codeforces.me/blog/entry/147606?#comment-1320634
I only found this because of query limit hint
2n = n + n/2 + n/4 ....
ok cool, thanks for sharing your idea !!!
From low to high, the complexity would be approximately n + n / 2 + n / 4 ... = 2 * n.
yeah but i was worried at some terms it will be
ceil(n/x)which might accumulate and make sum bigger than2*nCan anyone enlighten me on problem C. Btw i'm just a newbie :<
the fast way to calculate how many moves needed: N — ((cnt(value), cnt(value*), cnt(value*3)) + cnt(i > (n * 4))
Oh my dear senior... sorry you wasted valuable time and yet this stupid brain didn't even understand a single said.
I think it's like if you want GCD to be equal to $$$g$$$, then you must delete all elements less than $$$g$$$ first. For elements greater than $$$g$$$, only $$$2g$$$, $$$3g$$$, and elements greater or equal to $$$4g$$$ will be able to turned into multiples of $$$g$$$ ($$$2g$$$ and $$$3g$$$ are already multiples of $$$g$$$)
additional information:for any number>4*g ,you can break down like this:
g, g+n%g, ([n/g]-2)*g
Assume we have a fixed divisor $$$d$$$, then for each elements $$$a_i$$$, we have to either erase it, or change it into multiples of $$$d$$$. To determine if we can turn an element into multiples of $$$d$$$:
Let $$$a_i = kd + m$$$ where $$$0 ≤ m \lt d$$$ (i.e., $$$k$$$ and $$$m$$$ are the quotient and remainder after dividing $$$a_i$$$ by $$$d$$$).
If $$$m = 0$$$, $$$a_i$$$ is already a multiple of $$$d$$$ and we don't have to modify it.
Otherwise, if $$$m \gt 0$$$ and $$$k ≥ 4$$$ (i.e., $$$a_i \gt 4d$$$), we can turn $$$a_i$$$ into two multiples of $$$d$$$ by performing a split operation with $$$x_1 = d$$$, $$$x_2 = d + m$$$, $$$x_3 = (k-2)d$$$, which satisfies $$$x_1 + x_2 + x_3 = a_i$$$ and $$$1 ≤ x_1 ≤ x_2 ≤ x_3$$$ and leaves us with two multiples of $$$d$$$ ($$$x_1$$$ and $$$x_3$$$, while $$$x_2$$$ is removed).
With a bit of thought it can be proven this is the only way to turn a value into multiples of $$$d$$$ (in particular, using more than 1 split operation is never helpful, and turning a value below $$$4d$$$ into multiples of $$$d$$$ is impossible).
So to summarize: the only elements that we can keep are those that are either a multiple of $$$d$$$ or greater than $$$4d$$$. All other elements must be erased.
Now we know that, we can simply try all values of $$$d$$$ from 1 to $$$n$$$, and return the highest value of $$$d$$$ where the number of elements to erase does not exceed $$$k$$$.
To implement this efficiently:
You need a way to count for a given divisor $$$d$$$ how many elements of $$$a$$$ are neither multiples of $$$d$$$ nor greater than $$$4d$$$. One way to do it is to sort $$$a$$$, and count the number of elements in the four ranges $$$[1,d-1]$$$, $$$[d+1,2d-1]$$$, $$$[2d+1,3d-1]$$$ and $$$[3d+1,4d-1]$$$ by binary searching in the sorted array $$$a$$$, for an $$$\mathcal{O}(n \log n)$$$ solution, which is fast enough.
It's also possible to precalculate the frequency of each value in an array (since $$$a_i ≤ n$$$ this only requires a counting array of size $$$n + 1$$$) then calculate the number of elements below $$$4d$$$ minus the count of elements that are exactly $$$d$$$, $$$2d$$$ and $$$3d$$$, for an $$$\mathcal{O}(n)$$$ solution.
orz round
orz
Why is there an need for rejudging , when there were no hacks made in this contest
are there extra test case added by the authors?
for problems >
Dya but , no hacks were made and also no extra test case were there
okay !! I don't know in that case
How to solve D?
Divide & Conquer on the bits bit by bit, and on each step dismiss the space of numbers which you are sure the missing number is not one of them (you can determine that by the completeness of their count).
The complexity is something like $$$N+\dfrac{N}{2}+\dfrac{N}{4} + ...$$$, which is bounded by $$$2N$$$.
but it can be ceil of division ??
Yesh, but we are working with n — 1 not n. So it should be fine.0
oh ok .. i will check the editorial and try to upsolve it later.
Yeah I also was doubtful if it would be $$$ \lt = 2n$$$ but honestly by seeing the query limit $$$2n$$$ you can kind of feel that this would be the right approach, the summation must be bounded to $$$2n$$$.
Honestly in a lot of interactive problems the query limit gives away a lot of information. I remember solving this problem from the other day which has a query limit of $$$\frac{n^2}{a}$$$, and that can be written as $$$n \cdot \frac{n}{a}$$$, so that gave me the idea of "do $$$\frac{n}{a}$$$ queries, $$$n$$$ times".
yes, true, I also thought of pruning half elements but couldn't prove the bound of 2*n
It was a real relief to be sure that submissions to A-D will never be touched once pretests passed. Thanks to the authors for the new system, which is in my opinion a great improvement over the previous one.
nvm
no bro wtf, don't pollute here, you just check first k elements if they are the solution? what about
1 2 0 8 12?A-D, enjoyed each one of these. Thank you !!
ragebait contest :((
Thanks for the great contest hxu10! I particularly loved problem C, it's very pretty.
+1. I also enjoyed solving problem C.
That C was one of the best Cs I've seen actually
D is cool, thanks!
D is ass, C is cool
Great problems, great contest, but it’s a shame that cheaters ruined this contest.
That was a very nice round! I liked all problems which I attempted to solve.
Great job! That was a very well prepared round.
Thank you, and you can also thank the coordinator. I proposed 20+ problems for this round and only 6 survived. The whole process last 20 months.
I have reached Pupil by getting a +56 delta.
I am just so happy..
congrats bro!!!
Will you show us how your funny thing with D and F went? Like how many people fell for it?
If pretest == systest, what's the point of doing systest again for problem A to D? And why not only test the hacks in the systest for problem E to F
Thanks for the $$${\color{darkOrange}{Orange}}$$$.I loved problem D.
Great problem set, after much time enjoyed the contest and solved till D.
Thanks!
That was a great round! C and D were really on fire.
Hello, I received a plagiarism warning for submission https://codeforces.me/contest/2156/submission/345561374 on problem 2156B. I wrote this solution completely by myself. I used CodeChef’s online IDE to test my code, which I now realize might have made it publicly viewable. After checking, I found that the other user (https://codeforces.me/profile/Seraphablo ) submitted multiple completely different codes for the same problem, which suggests they copied from various sources, possibly including mine. I did not share my code with anyone or post it anywhere. Please review my case — I’ll make sure to use a local/private compiler from now on. Thank you.
Regarding plagiarism notice for submission 345584258:
Hello, I want to clarify that I did not share or copy anyone’s code intentionally. I wrote my own solution. The similarity might be because many people used a common approach for this problem. I never uploaded my code publicly or shared it anywhere. Please reconsider this; I can explain my solution or provide proof if needed. Thank you for understanding.