Hello, Codeforces!
I am very excited to invite you to participate in Codeforces Round 1122 (Div. 3), which will take place on Sep/21/2026 17:35 (Moscow time). You will be given $$$2$$$ hours and $$$30$$$ minutes to solve $$$7$$$ or $$$8$$$ problems. All problems were authored and prepared by me, WorldWarV.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution but the usual penalty of $$$10$$$ minutes for each wrong submission, following the rules of educational rounds.
You should remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a rating of $$$1900$$$ or higher at any moment in time.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than $$$1600$$$, then the round will be rated for you (unless you register unrated).
Also, note the rule restricting the use of AI. If you are caught breaking this rule, you will be dropped into cry's basement, which happens to be a permanently active volcano.
I would like to thank the following people for making this round possible:
- cry for spectacular coordination of the round and answering all 998244352 of my questions;
- Edu175, __baozii__, Arpa for red testing;
- omsincoconut, CatsAreCool, Edeeva, Lilypad for orange testing;
- wakanda-forever, Argentum47, yse, SpyrosAliv, linearspace for purple testing;
- simplelife, Eikyu, nik_exists, silverkeep, expertaq, femboy for blue testing;
- ByteRaider for cyan testing;
- koseitsukamoto for green testing;
- Vladosiya for Russian translations and testing;
- MikeMirzayanov for developing Codeforces and Polygon.
GLHF!
Update: Editorial!
Auto comment: topic has been updated by WorldWarV (previous revision, new revision, compare).
Look who is the actual orz one now. WorldWarV how are you so orz.
Also how you ask a negative number of questions? Did cry ask you a question?
first off, greateriorz.
second, I think I actually might have asked $$$998244352!$$$ questions.
I asked chatgpt and it said wilson's theorem makes this congruent to -1 mod 998244353.
Is this a hint that the contest problem will somehow involve Wilson’s Theorem?
bro probably accidently leaked the problem topic.... :skull:
so, if p>1 and (((p-1)!)%p)==p-1 return True else false
As a tester, good luck to everyone in this contest!
as a tester, i test
lmao thanks
Vladosiya is purple in this announcement, can I guess that the blog was written in 2025?
I wrote this blog an hour ago :)
I just gave testers max rating because I consider rating drops a display bug.
Sry... Now I know it.
As a red tester, I'm no longer red :(
You will be red, I can feel it (●'◡'●)
Bro is back to red hehe (due to rollback)
The one thing i do not like about codeforces is that i have to stay up at 11 pm to do contests
bro you haven't given any contest and you have to stay awake
if you can't give just don't give who cares
Good luck guys. Don't think Div3 just for newbies. The last problems are cool. And don't use AI because we are just studying and practicing, MORE THAN THAT IF WE USE AI AND WE WILL be in cry's basement with NO toilets
cry's darn 'n' blast basement is famous all over CF, isn't it? I don't even believe that cry has a basement. Now, i'd fancy cry give a picture of his basement to show me if the 'permanetly active volcano' and the 'no beds and no toilets' myth is true. Huh, cry! Stop exaggerating! I think there will be some myth(s) for me to smash on CF! I'm not joking, i really need a look at cry's basement! I'm not being nosy, i am just being ABSOLUTELY fed up with those stories!
Every time that a guy on codeforces doesn't get a joke an angel loses it's wings
Oh yes, I forgot. I'm Chinese, not used to this much humour. I've heard this before, didn't I?
As a C++ user tf is this
As a C++ user too, I think [::-1] just reverses the string (i guessed)
as an ex-python user and currently a C++ user, I can say that this line of code means:- 'as a tester i tested the round'
The code's output is: "as a tester i tested the round".
the magic of python
GLHF everyone! See you on the leaderboard !
Hoping least participants will be thrown into an active volcano.
It would be nice if the contest could be moved to Friday or Saturday, because if I participate, I have to stay up late and then I can’t wake up early for school the next day. :(
You will be given 2 hours and 30 minutes to solve $$$7$$$ or $$$8$$$ problems.
Why not $$$6$$$ or $$$7$$$ problems???
Because three of the following conditions hold:
The number of problems is an integer.
The number of problems is not $$$6$$$ or lower.
The number of problems is not $$$9$$$ or higher
im convinced...
i expected that they will follow the announcements trend
As a forcaster, I will be a pupil after this round (no joking) :)
Thanks nik_exists and whoever WorldWarV is for the round, unfortunately I won't be able to participate but I hope it's fun to virtual
really hoping to hit Pupil this round
this ain't a rated contest... i also didn't knew that
no, it's rated
whattt??... i only solved first two problems in about 20 mins then left due do some personal work... so how much score i might get ??? it wasn't mentioned anywhere about score per problem so i thought its unrated
you’ll get your points after the hacking phase
bro it was my first contest i have solved 4 quest..will i get ratings after the calcn??
Don't worry you will be rated by tomorrow
yeeeeeeeeee....thankuuu thankuu so muchh
might participate glhf
godsplan. Let's go everyone
Contest author's name is a spoiler!
Fun fact, I made this username when I was 7 years old and was coincidentally learning roman numerals and WW2 in school at the same time! So, I just fused the two together, and it has remained my online username ever since. I should change it soon though...
In a not too distant future on a sunny summer day, the fat and stupid crazy people in the USA, said this global warming really sucks the planet is the pits, the world's really getting screwed let's blow it all to bits. So one day at the white house while the president was stoned he thought it would be awesome if the Russians all got owned. When the Russians saw the rockets they knew just what they would do. If you shoot us with your rockets we will shoot some back at you.
It's World War V. The world's about to end. There's more fire and destruction than the mind can comprehend. It's World War V. I think we can conclude, we really had it coming now I guess we all get screwed.
As someone who forget to test, the problems surely are orz
I love femboy!
As a tester who remembered to test, there may be at least 6 or 7 problems.
thank you all for organizing this contest.
Can we roll back the roll back and decrease my rating by 1 so I can participate in this /j
As a tester, I tested! (wdym I couldn't come up with a good comment)
At Monday 22:35 to MIDNIGHT here. Wanna cry.
as a unrated --> hoping that this contest would made me the rated one!! excited
solved 4
thank you sparklecodes for sharing this btw
good luck for the contest everybody :)
might participate just to practice
7 or 8 problem is scary
You will find this even scary but try that before round you will see btw...
bro... it will be better, if you:
OR
Good problems are the lasts...
Auto comment: topic has been updated by WorldWarV (previous revision, new revision, compare).
whatttttt I just have taken part in only 2 contests wtf
Hello, I know it doesn't bother you at all, but will there be further rounds later? I'm division 1 currently but I have been a student at Codeforces for 2 years. Thanks for the attention.
no actually this was the last one
Auto comment: topic has been updated by WorldWarV (previous revision, new revision, compare).
As a tester, GLHF! best of luck to everyone
this is gonna be mine first time giving the contest.
I love div3 very much
manifesting positive delta for all!
Problem F is almost the same as this one on NowCoder. Maybe it's a little unfair for some contestants?
Bro what website is that :skull:
NowCoder, a Chinese oj
obscure chinese oj strikes again
The statement was written by dXqwq lol
$$$D$$$ is hard.
Hint: Define b[i] = a[i] — i. Then, the operation described can generate any permutation of b.
why b[i] = a[i] — i? Making every permutation of a with some adds for every i is obvious, but I can't figure out what to do cause this is kinda not simple object
Every element in a subarray (excluding the last) faces an increase by 1 in its value as well as index. The last element faces a decrease of j — i in its value as well as index. In both the cases a[i]-i is preserved.
why? This doesn't sound like truth
What does not sound like truth? The fact that the signed change in value is exactly equal to the signed change in the index?
like u can establish one to one map , between the original array and this a[index] — index array while doing operations .
finally what u want after ops in original array looks like x , x + 1 , x + 2 , x+3 , x+4 , ... , x + n in this set up of subtracting position from the value
amazing H!!! does anyone know where i can find more like these?
https://codeforces.me/problemset?tags=data%20structures,dp
thanks!
I stucked on D for soooooooo long XD
And although I AC-ed it I still dont know how does it work
how u arrived at whatever eventually , then?
In the last 15 minutes, I was so f** that I just wanted to do something to kill time. But then I tried setting b[i] = a[i] — i and noticed the pattern. So I took a gamble, and somehow it AC'ed
Same, but the idea that we can make an array of all values of a[i] going to the first index then just finding the longest consecutive subarray is quite beautiful.
I suck :(((
One bad contest doesn't define your level :)
Yeah Dude crazy I got +3 i thought for sure -50 as I did only 3 with 2.30 contest so thought for sure minus now happy for no minus and sad couldn't see that ai-i is the invariant in this operation:/
Loved D. Was E simple or did I miss something?
Define dp[i] to be the cost of reducing i to an integer less than or equal to k. How can you efficiently find dp[i] ?
Yeah, I solved E via a dp on the prime factors of $$$n$$$ where:
$$$\operatorname{dp}[n] = 0$$$ for all $$$n \le k$$$ and $$$\operatorname{dp}[n] = 1+\min_{p \mid n} p\cdot \operatorname{dp}[n/p]$$$ for prime $$$p$$$.
Then, the answer should just be $$$\sum_{i=0}^n \operatorname{dp}[a_i]$$$.
Solution implementing this: 391524995
Did with recursion + memoization. I think even naively, it should fit in the time limit.
any hints for G?
also, gave contest after a long time...and H has only 89 solves despite AI. are people not cheating enough, or are these problems difficult for even latest models?
What is the minimum number of elements that we have to check whether we can achieve them (excluding elements which already are in the starting multiset)
It's logarithmic in terms of n and the maximum value of any y_i
How to efficiently check whether we can achieve a fixed number x ? (finding the answer to this would be enough to solve the problem :))
edit: nevermind I got confused anf thought you were asking about F lol. For anyone else still feel free to use this as hint to F tho.
for G, the candidates are part of a series that looks something like a[i],a[i]+step[i],a[i]+2*step[i],...a[i]+k*step[i]<b[i]. try to find step[i]
also to answer your question for H, i believe a lot of people got stuck on G, imo it's way harder than H
what exactly is wrong with my solution for E?
I felt like D was much harder than E
That was. I spent 1:30 hrs but couldn't.
When you have been solving C with DP is actually a greedy one.
Somebody explain solution for Problem D please!!
Define
. Now, the operation described can generate any permutation of
.
The question permits subarray of any length but we will assume the length of subarray to be always 2. This is fine cuz any operation on a subarray of length $$$l\gt2$$$ can be split up into several operations
For example
Try performing the given operation on a subarray of length 2
Let this subarray be [x,y]
It becomes [y-1,x+1] upon applying the operation
observe what happens to x: x moves 1 step to the right and gets incremented by 1
observe what happens to y: y moves 1 step to the left and gets decremented by 1
So, we can move around the elements as needed but need to update it's value as per it's change in position
Let's move every element in array a to position 0. So, update every $$$a_i$$$ to $$$a_i-i$$$
For an array to be valid, every element should correspond to exactly 1 position among 1 to n (inclusive). So, let's think of moving it to form an array.
When moving it again, each element will be incremented by it's new index. So, if we want contiguous elements with equal values, we need the values to be differing by one... (like [1,2,3], [5,6,7,8], [45,46,47,48,49,50], etc... so that correspondingly some indices like [3,2,1], [6,5,4,3], [9,8,7,6,5,4], etc... can be added up to have constant level 4,11,54, etc... respectively)
Thus, the length of the longest Arithmetic Progression of common difference 1 will be the final answer
We can do this by removing duplicates and sorting updated values of the array...
For the first time in my life, I solved 6 problems and i did it in the last 3 minutes(after 6 WA and TLE) :)
Please don't hack me
difficulty: D>E imo
C and D are great problems :-)
thanks!!
does anyone have clean sol for F? i binary searched for answer and then to check if an answer is achievable, i converted all nums>=ans to 0s and then constructed each number from ans-1 to 0 once. its kinda messy since i just kinda guessed the maximum for answer, although its pretty easy to see its like not bigger than n+100 at least. my 2nd problem was that i had overflow so i just put in an if to break if it was ever close to overflow. my solution works but surely there is cleaner way to do it right?
Screencast with commentary
Very cool contest, kudos to the authors!
omg thanks!!
Auto comment: topic has been updated by WorldWarV (previous revision, new revision, compare).
as a te.. ouch I forgot to test
I registered for this round as rated because I was 1599, then IDK why CF decided to change my rating to 1601 and now the round is unrated, xd. It was going to be a really good round for my rating :(
Amazing contest!!! very interesting and non standard problems thank you authors!!!
my friend BOSS_SV69 is getting a user is disabled by administrators whyyy?? he got no email rearding he is cheating or something , any help so he can get his account back???
It shows that I gave the contest in unrated form. Because it doesn't show up in rated filter. I'm sad that I gave so much effort like this.
I think Problem F in this contest is exactly the same as this one. I wonder if the problem setter checked for existing problems before setting this.
https://ac.nowcoder.com/acm/contest/135884/B
I have mentioned this above:) Maybe a bunch of Chinese contestants have solved this problem.
Can anyone walk me through the thought process behind solution D?
Key observation: if a longest congruent segment exists, it can always be moved to start at position 1.
Proof: any segment [l, r] can be shifted step by step to [1, r-l+1]. Suppose the longest congruent segment starting at position 1 is [1, R], and a[1] = x. Then for every position i (which must lie within [1, R]), there must exist some j such that a[j] — j = x — i, making it valid. Here x is fixed while i takes consecutive values, so x — i is a consecutive range of integers; therefore a[j] — j must also be a consecutive range of integers. Hence the longest consecutive-integer run among the a[j] — j values equals the longest consecutive range of values that i can take, which is exactly the length of the longest answer segment.
I spent over an hour on this problem during my virtual participation. I had figured out all of the points above, but I just couldn't spot this key consecutive-integers insight. I kept trying to find a fixed x to verify against — I'm so stupid.
Man, I'm so dumb — I got stuck on D for over an hour, but I solved F in just a few minutes.
Of course, this was during my own virtual participation — I couldn't take part in the contest on time.
Great Contest
hey, new here. I wanted to know if we're getting rating points or not ?
same question. ratings aren't updated even after the system testing is finished (?)
it's updated now
yes, thank you!
Interesting contest. Thanks!
i used to be specialist, now my alt is newbie for 2 continious contests.
As a beginner, I enjoyed this contest a lot...problems A and B were a piece of cake...kinda feel like problem B was too easy..lemme know if anyone feels the same.
However problem C was tough for me..solved it using prefix and suffix logic and eventually cracked it.
Problem D and onwards were simply put out of my domain gotta work on that.
Lemme know if anyone else felt the same way!
Regardless, this contest was fun! Gonna remember this going forward as i cracked the O(1) solution for A and B very quickly.
My submission was skipped why
you cheated
yeah, H in 8 minutes is... yk
but it as wrong that's why
Hello, my submissions in Round 1122 (Div. 3) were skipped due to a rules violation on problem D (2266D — Falling Concrete). I believe this may be a mistake. I wrote my solution myself during the contest and would like to request a manual review of my submission. Could you please check the reason for the violation? Thank you.
Subject: Appeal Regarding Account Freeze: daemonfork (Round 1122)
Hello Codeforces Moderation Team,
I respectfully request a manual review of my account, daemonfork, which was disabled during Codeforces Round 1122 (Div. 3). I am sending this directly because my main account is freezed and this is my Alt account forking.
I strongly believe this flag is a false positive triggered by an unexpected performance spike. I invite you to review my entire Codeforces submission history on daemonfork. Even though it is a relatively new account, my history from day one shows a consistent, dedicated grind. I have spent months practicing algorithmic problem-solving offline specifically focusing on data structures, DP, Game thoery, Math ,binary search, and monotonic stacks in C++.
If you look closely at my submission logs, you will see the reality of that grind: staying up until 2 or 3 AM fighting for a single AC, and pushing through multiple problems in a single day. A cheater who is lazily copying AI does not sacrifice their sleep to debug late into the night. During this round, that intensive human practice finally paid off, allowing me to solve harder problems than my Newbie rating would normally reflect.
My submissions were typed entirely by hand. The code is clean, concise, and structurally consistent with my past genuine submissions. I did not use AI generation, and I am confident that a manual review of my source code and problem-solving history will show a purely human progression rather than an automated script.
Thank you for your time, your hard work on the platform, and for considering my appeal.
Best regards, daemonfork
This is what i did for A to G approches:
Problem A: Good Contest Problem A was a pretty standard warmup. We just needed to check if the scores in the array followed the "good" rules. The approach is a basic $$$O(N)$$$ linear scan to compare adjacent elements. I just set a boolean flag to true, looped through the array, and if any pair broke the condition, I flipped the flag and broke out early. Super simple logic, didn't need any complex data structures, and the basic
forloop passed pretests instantly. Definitly a fast one to get the contest started.Problem B: Three Piles B was a mathy/greedy problem about balancing three stone piles. If you try to simulate it step-by-step you'll get TLE for sure. The optimal trick is to just sort the three pile sizes first. Then you can use an $$$O(1)$$$ formula to figure out the max operations based on the diff between the largest pile and the sum of the other two. My code just reads the inputs, sorts them using the built in sort, and outputs the math formula result. Very quick if you catch the pattern early on.
Problem C: AND, OR, Sort! C looked tricky but the key observation is that replacing two numbers with their bitwise AND and OR perfectly preserves the total number of set bits at each position. So the appraoch is just to count the frequency of 1s at every bit pos across the whole array. Then you greedily reconstruct the optimal sorted array by placing those bits into the largest numbers from right to left. Used a nested loop with bitmasks, runs easily in $$$O(N \log(MAX_A))$$$. Took a sec to debug but worked great.
Problem D: Falling Concrete D asked us to simulate concrete blocks falling down a grid till they hit the floor or an obstacle. A naive $$$O(N^2)$$$ simulation would time out, so I processed the grid col by col from the bottom up. By keeping track of the "next available empty cell" in each column, I could drop blocks instantly to their lowest valid spot. The working code just iterates columns, updates the positions, and prints the final grid. Kept the complexity strictly to $$$O(R \times C)$$$ which was fast enough.
Problem E: Prime Destruction E was a classic number theory task about eliminating numbers using prime factors. The best approach here is precomputing the largest prime factors using a modified Sieve of Eratosthenes up to the max limit. After building the sieve, I used prefix sums so I could answer all the testcase queries in $$$O(1)$$$ time. I declared the sieve globally before reading the testcases, then just did the math to find min operations. Passed within the 2s time limit without much hassle.
Problem F: MEX Replacement For F, we had to dynamically track the MEX while doing replacements. Brute force is a guaranteed TLE. My solution was to maintain a frequency map and a
std::setto track the missing numbers efficiently. I initialized the freqs and dumped all currently missing non-negative integers into the set. When elements update, I update the map; if a count hits zero, it goes back in the set. Then the current MEX is literally just*set.begin(), which is $$$O(\log N)$$$. Had a tiny bug here initially but fixed it fast.Problem G: Modular Tree G was a pretty heavy graph theory one needing us to calculate path weights on a tree using modular arithmetic. The approach is basically Tree DP combined with a standard DFS traversal. I built the adjency list first, then ran a recursive DFS from the root to compute edge weights and push state transitions up from the leaves. The main thing in the implementation was making sure to apply modulo at every single addition/multiplication to avoid integer overflow. The $$$O(N)$$$ logic worked perfectly on the pretests.
Nice proof that you have no idea what you are doing
Id honestly like to break down my exact thought process for those problems. ur comment makes it sound like i just blindly copy pasted without using a single brain cell, which isnt true. i put real thought and effort into building that logic. i genuinely respect u for taking the time to look at my appeal, and i know u have the connections to help get this reviewed. but im already getting hates in the comments too, so thats why im not typing out a massive algo breakdown just to be ignored and roasted. if u honestly think explaining my code and how i reached thier solutions will make a difference, ill break it all down right now. if not, ill just accept the situation and either start a fresh acc later or step away from cp altogether.
No, it will not make a difference. I'm totally fine with you stepping away from cp altogether.
honestly this was only my 3rd contest and my first time making an account here, so i genuinely didnt fully understand the policy. i knew copy-pasting a whole solution was an instant ban, but i didnt realize that just using it to get hints would trigger the exact same thing. i took hints on a few questions, but i tried to write the actual code based on my own understanding. also, i cant just walk away from cp over one single mistake. yesterday i was just super tense and stressed out because of this whole ban situation, so i replied out of some frustration when i said i would just quit. i just need one chance man. i definitely learned my lesson about how strict the system is and what happens if u cross that line. just asking for a little grace for a newbie mistake."
brother. You should look at yourself in the mirror, because I don't see a real man in this comment; I see a scared little boy left alone in the dark. His only fear is that people will judge him because of his rating. So please, behave like a real man, stop being afraid of what people think, start practicing, and get 'real' results.
I know it might seem like that, but the point is that a good rating can give your resume a boost (Even working professionals need this while switching). I think already have a good understanding not master level of problem solving; I’m just new to CodeForces, so I wanted to see where I actually stand.
I’ve solved tons of problems on LeetCode, HackerRank, GFG, etc. I just want to establish myself on a popular platform and get my rating up to a level that reflects my actual ability. That’s all.
It’s just a personal goal or a bit of a craze for me, nothing more. Hope u got me
yeah, but I think a rating is less valuable if you achieve it the dark way. So my advice for you, as a guy around your age, is to just put in the hard work. It will click one day—it can't go any other way, it has to click eventually. And if you need help, you can just ask your friends. If you don't have friends, you can ask me! :) I am open to conversing with new people (of course, if you use Telegram or WhatsApp).
one of the best div 3 contests that I had. question statements were short and main focus was on theory not implementation . very nice and thank you for problems :)
Hi Team,
I just received a warning that my submission for the problem 2266D significantly coincides with solutions of few other users. If you look at the solution, it is common logic with variable names anyone uses. If this level of violation message keeps coming, I would be scared of even participating in contests. I'm already losing enthusiasm of participating in contest after seeing these violation messages. I don't think I'll participate again. I'm just sharing this here to let you know that this level of code similarity can be common and just because of this you skipped my submissions. I loved this platform but I don't know what to say.
I received an anti-plagiarism warning for my submission 391524794 for problem 2266E, which was reported as significantly coinciding with submission 391519495 by Siddham_N.
I want to clarify that I solved the problem independently during the contest. I did not view, copy, or communicate with the other participant regarding the solution.
I was surprised by this warning and would appreciate it if the two submissions could be reviewed manually. I am happy to provide any additional information or evidence that may help with the review.
Thank you.
Hello Codeforces Team! My UserID: Harsh4
Regarding submission 391531738 for 2266G
I received the coincidence warning for my submission and submission 391524168, so I wanted to clarify how I arrived at my solution.
I did not copy the other submission or use it as a reference.
My first solution was actually quite different from my final one. In my initial approach, I rooted the tree at 1, processed the nodes in reverse BFS order, and for every node I only kept the sum of the values obtained from its children. The main part of that solution was:
sum = sumChild[node]; gd = gcd(sum, b[node]); largest = b[node] -gd + (a[node] % gd); and then I propagated largest to the parent.
you can even check the previous submission to this question (391526660).
After thinking more about the operations, I realized that this was not enough. The children do not only contribute their final values; their possible changes also impose GCD restrictions on what can be done at their parent. So I changed the information propagated upward.
In my final solution I keep two pieces of information, baseSum and s. For a node, I calculate:
gd = gcd(gcd(b[u], baseSum[u]), s[u]); largest = b[u] -gd + (a[u] % gd);
and when processing a child I propagate: baseSum[p] += a[u] % gd; if (gd < b[u]) s[p] = gcd(s[p], gd);
I arrived at this by working through the GCD constraints from the children upwards. I still used the same basic tree-processing technique from my first attempt- rooting the tree, storing parent, doing a BFS to get an order, and processing that order in reverse, but the actual state and transition changed after I realized the first solution was incomplete.
I wanted to provide my actual progression from the first solution to the final one so that the similarity can be reviewed in context. I would appreciate a manual review of the two submissions.
I hope this can be reviewed as an honest submission, as the warning has affected my contest points despite solving the problem independently.
Submission: 391531738 Coinciding submission: 391524168
Hey! How can a user get a disabled account back? I would appreciate any external help..