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.
Deleted
Deleted
Nice proof that you have no idea what you are doing
Deleted
No, it will not make a difference. I'm totally fine with you stepping away from cp altogether.
Deleted
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.
Deleted
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..