Привет, Codeforces!
Мы рады и с нетерпением приглашаем вас принять участие в Codeforces Round 1123 (Div. 2), который состоится 25.09.2026 17:35 (Московское время). Вам будет дано 2 часа и 15 минут на решение 7 задач. Задача F будет разделена на подзадачи.
| Задача | A | B | C | D | E | F1 + F2 | G |
| Баллы | 250 | 500 | 1000 | 1250 | 1750 | 1000 + 2000 | 3000 |
Задачи были подготовлены KluydQ, Aldk, YF_YUSUF, Dibamboo и Wansur.
Мы хотели бы выразить особую благодарность:
- Um_nik за предварительное ревью контеста.
- 74TrAkToR за отличную координацию и возможность провести этот контест.
- makrav, Kude, Friendiks, Error_Yuan, Sugar_fan, JovanB, lewc, Noobish_Monk, Daki-sa, ImDMka, Abilmansur-007, barbie, k1r1t0, Away_in_the_heavens, aryanc403, feresatcccccccc, Egorov_Dmitriy, QazLon, magagam, Arkanefury, Yessimkhan, liexes, GRIVA_, BzL16082010, spajzmand, knatwila, NickFuryy, PoDuReMaN, Dibamboo, AIibi за их время и усилия, потраченные на тестирование.
- MikeMirzayanov и KAN за отличные платформы Codeforces и Polygon.
UPD: Разбор доступен по ссылке https://codeforces.me/blog/entry/157126
Поздравляем всех победителей:
Div. 1:
Div. 2 (доверенные участники):
First time seeing a 250 points problem.
Same.
As a participant, my goal is to solve two problems. Good luck to everyone!
I hope, I also can solve two problems.
On Div.3 i has been really bad. I solve only 2 problems. On Div 3.
So... I hope, i can solve 2 or 3 problems. I really need up my rating (I hope, i finally can make my rating more than 800).
you need to solve more problems with rating over 1200, 1300 to do this. I wish you success.
Thanks!
brother, and also please consider taking english classes serious
Yes. I learn English.
I'm just giving you friendly advice, cuz your English kinda sucks
As a participant like you, I hope to solve two or more problems! Good luck!
Good luck
I didn't see A and B have this low points in a while. I hope I get my color back
show them the power of leek
As a tester, I love Wansur
Is 1000 point F1 a typo? If not why isn’t it just non-adjacent subtasks?
problem A :
2 + 2 =
Me in my FIRST contest: Problem A : 2 + 2 = 5 ???
Div. 3 disguised as Div. 2? 'Cause wym A is only 250
is F1 ez as a normal 1000pts prob :)?
I don't have a good feeling about this if C and F both have the same amount of pts.
No it's 74TrAkToR we are in great danger
I really enjoyed the last contest he coordinated
I really enjoyed goodbye 2023
As a coordinator, not as an author :)
What's wrong?
First time where an author is a pupil ;)
Wait his peak is CM...
Everyone but Wansur aren’t on their peaks
I want to be the first pupil author ;))
Good luck then, but you will need master+ teammate to purpose a contest
you are late https://codeforces.me/contest/2107 , check the authors
bruh
What about the first contest where all of the authors are pupil ;)
Автокомментарий: текст был обновлен пользователем KluydQ (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by KluydQ (previous revision, new revision, compare).
The F1 and A being worth that low scare me
As a tester, post contest discussion stream here
As a participant, I'll enjoy the contest instead of the mid-autumn festival.
Is that your kitty? :)
Spelling Mistake: "probmles" — > "problems"
fkikfrfoeroreoreoreo49349498934983499935893459345893459854
Auto comment: topic has been updated by YF_YUSUF (previous revision, new revision, compare).
Why the kitten looks flat ToT
I like the cat
glhf. Plan to solve 3 atleast...
that's a cute cat >.<
I will be pupil.
Oh, is this kitty yours? I love it
Is F1 actually intended to be easier than D? I was a bit surprised to see F1 with a 1000-point score while D has 1250. Could you clarify the intended difficulty/order?
Maybe I have to give up the mid-autumn festival.
idk what to do, just.... waiting... and having fun.
crazy score distribution
I agree.
Cat above the tractor but under the sky, is it cat or not ??
Yeah it’s cat above a tractor
Давненько казахов не было. Надеюсь контест будет легендарным!!! Алга Казахстан!
Tomorrow is Mid-Autumn Festival!!!Hope it will be a good match.
As a tester, I really enjoyed the problems!
tell me the probblems
Can’t share them before the contest, sorry. I’ll send them to you after the contest though!
I wish I could take this contest but i'm drowning in work rn
hope you get out of it soon and might as well be able to give the contest!
Problem F1 is only of 1000 points does this means it will be of the same level around C which is also of 1000 points.
not really, its just because F1 is a subtask of F2
F1 is so troll
ragebait points
Hope everyone giving this contest will get a huge negative delta and will never recover from that
Really hope i am able to solve E in time. GLHF
is it rated?
wish everyone happy Mid-Autumn Festival！
excited for this
Is the F1 going to be easier than D ..? What i am able to see from the score or it's something else.!
I expect that round will be interesting and balanced good luck to everyone!
I hope to become expert in this contest :-)
UPD: yay!!
Good luck.
And may the Monolith help us!
UPD: Monolith help you!
im new to this competitive programming can i attempt this one? im having knowledge in python as i worked in ai and data science and automations (weak in data structures)
Problem A:
A and B together are only 750, then C jumps straight to 1000 and D is just 250 above that. With 2h15 and F split into F1 and F2, feels like the round actually starts at C. Good luck everyone.
i am student
As a participant, I don’t know what awaits us there, but I can say that this DIV will be unforgettable.
че там, сложно вообще будет / нет?
good luck everybody :)
hahahaha i am gonna level up to green broooooo
cute car
哦哦哦
i wish the problem problem A be like that :a+b
w contest
too many cheaters top 40:
A bit of a weird contest, but C is a nice problem.
B = https://www.luogu.com.cn/problem/P9143
You have several positive integers in the range $$$[1,n]$$$. For each $$$1 \le i \le n$$$, there are $$$a_i$$$ copies of the integer $$$i$$$. Let
For a sequence $$$p_1,p_2,\cdots,p_l$$$, define its mode $$$\text{maj}(p_1,p_2,\cdots,p_l)$$$ as the value that appears most frequently in the sequence. If multiple values have the same maximum frequency, the largest among them is chosen as the mode.
You need to arrange these $$$S$$$ integers into a sequence $$$b_1,b_2,\cdots,b_S$$$ so as to maximize
Output the maximum possible value.
uh oh...
so many people solved F1 ... How to do it ?
Brute force is enough
no wayyy !!! . I was guessing everything would go to zero, but couldn't prove after how many turns..
CP is not like MO, we often use "guess" instead of "prove":)
let
Bbe msb currently in the array. supposecelements have bitB = 1andn - celements have bitB = 0.pairs with matching bits cancel bit
Bto0, producing values strictly< 2^B. the number of such pairs is:f(c) = c*(c-1)/2 + (n-c)*(n-c-1)/2 = c^2 - n*c + n*(n-1)/2this quadratic minimizes at
c = n/2, where its minimum value is:f(n/2) = (n^2 - 2n) / 4for this minimum to be
>= n:(n^2 - 2n) / 4 >= n <=> n*(n - 6) >= 0 <=> n >= 6because the transformation strictly selects the
nsmallest values, pairs with bitB = 0are always chosen before any pair with bitB = 1:n >= 6: there are always>= npairs with bitB = 0, so the highest bit is guaranteed to be eliminated in strictly 1 turn.n = 5: the worst split (c = 2or3) leaves only one single1in the array, which vanishes on the very next turn (at most 2 turns per bit).since
a[i] < 2^30(at most 30 bits), the highest bit strictly decreases every turn, meaning the array is theoretically guaranteed to reach all0s in at most 30 turns (at most 60 forn = 5).Try to generate tests and check what happens to the array after you apply the operation a few times.
Too large gap between F1 and F2
i am done
How so many solves on $$$F1$$$?
Personally, I just generated random tests and checked how many times the operation is applied before the array becomes all zeros. The result is intuitive for big n: the bits become 0 very quickly, from the MSB down to the LSB. For n <= 4 the array can cycle (see 0, 0, 1, 1)
Watch me TLE on F1
Good contest, I love C, and definitely will try and upsolve D. First time solve Div2F ;). I don't really like F1 tho because it needs nothing but implementing
F1 just 20 lines bro, wdym "implementing"?
My point is, it's literally brute force, which requires no thinking. I might express my point (int the first comment) wrong tho (since my English is quite bad)
Thanks for the great round! I enjoyed Problem C.
Was anyone else getting TLE on test 23 for D? It was running about 100ms on my (fairly slow) computer for $$$n=250000$$$, one test case and <1ms for $$$10000$$$ cases with $$$n=20$$$.
First contest!!! Now I know I do not deserve this username
does anyone have a riguros proof for C?
Isn't it like, we are only considering the distinct prime factors of x, so at max 15 or so factors so that makes the time complexity about O(k * N) or so, where k is at max 15
Yeah that's the idea, i'm just asking for a proof that it's correct, it's pretty easy to guess it gets AC :)
I dunno if this counts as proof, but the thought was that, the final value of x would always be a multiple of initial value of x, so doing just the distinct primes works
Assume x > 1. After any operation x > 1 still holds. Look at the final value of x in an optimal sequence of operations. Take any prime factor p of the final value of x. Since p remained as a factor of x, all numbers that we took must have been divisible by p. If we take all values divisible by p, it will also be a valid sequence of operations.
Thanks!
yeah I did something during contest... the point is that transformation of X -> g can never add a new prime factor, it can only remove it,
so I realized that in the end we can't pick up two different prime values ... so all values to be picked has to be multiple of one of the prime factor.
i did it dp first if u perf oper btw x , a[i] regardless how many time u repeat the operation with same elemnt x will end to be gcd(x ,a[i]) so it's like if u did it once the optimal is to keep till a[i] = 0 second x always go to some divisor of it (very clear)
So before anything any a[i]%x == 0 then finish these values then dp[x] = max{sumOfaiDivisbleBy d + dp[d]} where d is divisor of x not equal of x and to solve the problem of taking ai twice u notice that if u are at x then u dont need to take any multiple of x so dp[x] = max{sumOfaiDivisbleBy d -sumOfaiDivisbleByx + dp[d]}
Can you please Link your submission if you don't mind, I would like to see the code for this
392032969
proof-by-AC is enough
this is the mathematical proof for my solution
let X_0 be a natural number greater than or equal to 2, and a_1, a_2, ..., a_n be natural numbers.
Define the set of reachable divisors R recursively as: 1, X_0 is in R. 2, If d is in R and g = gcd(d, a_i) > 1, then g is in R.
The maximum number of coins S_max that can be stolen is: S_max = max over all d in R (excluding 1) of the sum of all a_j such that d divides a_j.
Proof:
Upper bound: S_steal <= S_max Every valid operation updates x to gcd(x, a_i), implying x_new divides x_old. By induction, x is in R at every step. Let d_end in R (excluding 1) be the final parameter value before the operation stops (or transitions to x = 1) Any pile j touched when the state is x_k satisfies x_k divides a_j (if cleared) or gcd(a_j, x_k) > 1 Since d_end divides x_k for all active states x_k, any pile j contributing coins must satisfy d_end divides a_j Thus, S_steal is less than or equal to the sum of a_j for all j where d_end divides a_j, which is less than or equal to S_max.
Lower bound: S_steal >= S_max Let g in R (excluding 1) be a divisor that achieves S_max
by definition of R, there exists a sequence of piles picks i_1, i_2, ..., i_k such that iteratively applying x to gcd(x, a_i_m) transitions X_0 to d_1 to ... to d_t, call it g Execute one single operation on each of these piles to reach state x = g.
once x = g, consider any piles j where g divides a_j. Here, gcd(a_j, g) = g > 1. Taking g coins leaves a_j' = a_j — g and updates x to gcd(a_j — g, g) = g Repeating this a_j / g times reduces pile j to 0 coins while maintaining x = g.
Executing clear for all j where g divides a_j empties these piles, yielding S_steal = sum of a_j for all j where g divides a_j = S_max.
Combining the bounds give S_steal = S_max
i think the lemma the other person posted should be enough though
i need to sleep it's 1am
Also really nice F although it's a bit hard on the implementation :p
nvm
It's possible to solve G by calculate the number of ways to reach $$$i$$$ for all $$$i \le n$$$ with a simple dp then use convolution + CRT to solve the rest part...
my submission
B is atleast 1000 rated
It was hard to come up with sorting -> printing -> cleaning -> repeat till u reach the highest frequency of element
Abnormally easy contest
It's like div2.5 for me :)
I think this is the best round i have ever participated so far
Huge thanks to authors for this amazing contest
Can anyone tell me why the maximum number of transformations is low in F? Can't really seem to prove it, its $$$O(log n)$$$ right?
Consider
the most significant bit
Well it can be proven that for n>=5 each transformation lowers the amount of active bits by 1. Every xor of 2 elements with the same value for the highest bit will always result in 0 for that bit, which is always smaller than considering two elements with different values over that bit.
The number of ways to pick elements with the same value for a bit h is C(cnt0,2)+C(cnt1,2) where cnt0=nr of elements where bit h is 0 and cnt1=nr of elements where bit h is 1. This value is smallest when cnt0=cnt1 and if you check for n>=6 the sum C(cnt0,2)+C(cnt1,2) is always at least n, therefore the n smallest xors will have bit h=0. for n=5 you can check by hand :)
I hope this is clear enough, i'm not that good at explaining things...
Amazing F1 good job writer
for me not really, because F1 is just guess and implement, F2 seems to be an interesting problem
any hints for D
You can permute the even and odd indices. $$$1$$$ must be at the first or last position, then where should $$$2$$$ be? what about $$$3$$$?
the hill can be constructed by creating
deque<int> dq;then
dq.push_front(n)/dq.push_back(n)dq.push_front(n - 1)/dq.push_back(n - 1)...
dq.push_front(1)/dq.push_back(1)what if $$$n$$$ and $$$n-1$$$ appear in both even indices or both odd indices?
Consider if $$$n-2k$$$, $$$n-2k-1$$$ appear in both even indices or both odd indices, if there's any, then no solution (
"NO"), otherwise there must be solution ("YES")Am i the only one who doesn't have to allocate a $$$O(n^2)$$$ array every transformation? Just use a multiset/priority_queue and keep the $$$n$$$ smallest!
then priority_queue is also ok i guess
me noob.
I got A and B but got stuck on C ....
Does anyone know how to approach C ?
i thought it like sort array according to maximum frequency ? then apply key idea
this is how i did it .....
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//code
int coins = 0;
for(int i = 0;i < n;i++){
while(a[i] > 0 && __gcd(a[i],x) != 1){
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
so while loop does calculates till it get 0 or gcd == 1 but i was unable to get the proper solution it still got wrong idk y...
If anyone knows pls let me know>>>>>
so if u choose a prime factor u can always finish a stack since a[i] — p is divisible by p too but if u pick a prime factor u cant move anywhere but this is still effective
Suppose you perform a steal on $$$a_i$$$, and let $$$g = \gcd(a_i,x) \ne 1$$$. Note we immediately have that $$$a_i$$$ is divisible by $$$g$$$. After this first operation, $$$a_i := a_i-g$$$ and $$$x := g$$$. Now $$$a_i$$$ is still divisible by $$$g=x$$$, meaning $$$\gcd(a_i,x)=g=x$$$. So now you can keep applying the operation to $$$a_i$$$ without $$$x$$$ changing, eventually getting $$$a_i$$$ down to zero. So if you can perform an operation on any element, it always makes sense to keep doing it until that element reaches zero.
Now you only need to choose which elements to try to steal from. Suppose you pick the elements $$$a_{i_1},a_{i_2},a_{i_3},\dots,a_{i_k}$$$, in that order. To pick those, you must have $$$\gcd(a_{i_1},x) \ne 1$$$, $$$\gcd(\gcd(a_{i_1},x),a_{i,2}) \ne 1$$$, $$$\gcd(\gcd(\gcd(a_{i_1},x),a_{i_2}),a_{i_3}) \ne 1$$$, etc. You can rewrite this as $$$\gcd(a_{i_1},a_{i_2},\dots,a_{i_k},x) \ne 1$$$. In other words, all those values must share a common divisor greater than 1.
Note that this common divisor must be a factor of $$$x$$$, so to solve this, I found every factor of $$$x$$$ greater than 1. Then for each factor $$$i$$$, I summed up all the array elements divisible by $$$i$$$, and I then took the max of this across all factors. 392035843
Thank you man appreciated (*_*)/`
Intresting contest, wanted to try F2 but time is money
D>>F1 in my opinion
nahh dude !!
F1 looks like 800, it give AC by brute force lol
D was like 1100-1200 for me
Yes, it was even announced before the contest that D = 1250, F1 = 1000
Amazing contest excellent problems thanks to authors good job guys!
is this unrated?
Did i overcomplicate D?
Basically i'm saying that the lowest element can only be at indexes 1 or n (let's call them i,j). Suppose we put it at index (i) then the next element would need to go to index (i+1) or (j). By the operation when can we move an element to an index? When the parity of the target position is equal to the parity of the original position. Therefore instead of tracking the positions of i and j, i track the parities. I did the transitions by caseworking all combinations. Then notice how for the maximum element there should be just one choice (i==j) therefore the parities should be also equal, so just check if the dp[n-1][ev][ev] is reachable and the parity is of the maximum is even or dp[n-1][od][od] id reachable and the parity of the maximum is odd.
I'm sorry, i'm not really good with the markdown for math, i hope it's clear.
Amazing contest BTW
edit: it looks like i did
Difficulty is all over the place. Genuinely how is $$$F1$$$ an $$$F1$$$? That deserves like a $$$C$$$ at best.
Its almost as if the score distribution hinted this might be the case...
I'm in a great mood today, and I really enjoyed focusing on the topic.
Big +ve delta, thanks for the contest!!!
A pretty natural screw-up found its way into F2.
Автокомментарий: текст был обновлен пользователем KluydQ (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by KluydQ (previous revision, new revision, compare).
Where is the editorial ??
good round
Easy for a cheater to say lol, AK's the entire contest within 1 hour.
u da next GM!!!!!
Auto comment: topic has been updated by KluydQ (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем KluydQ (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by KluydQ (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем KluydQ (предыдущая версия, новая версия, сравнить).
So happy in appearing in my first winner list!
I would have made it up there if there was a first solves section...
Hello,
I request a manual review of the coincidence flag on my submission 392048627 for problem 2267G in Codeforces Round 1123 (Div. 2).
My solution was written independently. I did not copy from or share code with Nours200, whom I don't know also and I didn't access their solution during the contest.
The submissions use the same underlying DP idea, but the implementations differ. I use calc(), dp, add, and a cumulative recurrence, with bit extraction inside calc(). Submission 392059274 uses buildDp(), g, y, a differently written recurrence, bit preparation outside the function, and an explicit i == 0 case. The function structure, loops, and modular updates also differ.
I believe the overlap comes from the mathematical approach to the problem, including the powers-of-two DP, applying the transformation twice, and the final condition (m & x) == x. Please compare the full source codes and reconsider the flag.
My submission: 392048627 Compared submission: Nours200 / 392059274
Thank you.
Hello, I want to ask for a manual review of the coincidence flag on my submission 392063124 for problem 2267D. I came up with my solution to this problem and coded it myself. I didn't copy or receive code from any of the users named in the warning, and I don't know any of them. What I did was store the index of each number and then check the pairs (n,n-1), (n-2,n-3), etc. For every such pair, I checked whether the indices of the two numbers have different parity. If they had the same parity, I printed NO; otherwise, I continued checking the other pairs. I thought about it myself during the contest and coded it myself. It will be great if you could review the coincidence flag manually and compare the full submissions. Submission: 392063124 Problem: 2267D Thanks.
Hello, I respectfully request a manual review as I've received a warning that my submission 392055948 for the problem 2267C coincides with submission 392069096.
I want to clarify that I solved and wrote my submission independently and had no communication with these users and I don't know them.
I understand that the implementations are very similar. The solution is basically factoring x and then find sum of elements divisible by each prime factor and store the maximum one. That was how I approached to the solution.
However I've attached a screenshot from my VS Code timeline showing the developement history of the actual source file. It shows that the code was in an incomplete state at 10:05 PM(GMT+6,Dhaka time) on sept,2026 during the contest. and then the remaining logic was added at 10:07 PM, which was submitted at 10:08 PM. ScreenShot
I'm providing this as evidence of my own development process. The solution is so simple and short that it naturally coincides with others. And prime factorization has common template that I used from this published 2 months ago.
Hello,
I received a plagiarism/coincidence warning for my submission
392059274to problem2267G.I want to clarify what happened. I wrote the solution myself during the contest. However, my local C++ compiler was not working correctly at the time, so I used an online compiler to compile and run my own code because I needed to check whether my implementation was producing the expected output.
I did not copy the solution from
tapandutta46779, and I do not know this user. I also did not use their submission or communicate with them during the contest.I understand from this warning that using a public online compiler can potentially expose submitted code and cause an unintended coincidence. I was not aware of this risk at the time, and I apologize for using it during the contest.
Could you please review submission
392059274and the other submission involved in the warning? I would appreciate it if the circumstances could be taken into consideration when reviewing the case.I will make sure not to use public online compilers during contests in the future. Thank you.