Hello, Codeforces!
We are excited to invite you to participate in Codeforces Round 1115 (Div. 2), which will take place on Aug/06/2026 17:35 (Moscow time).
The round will be rated for all participants with a rating below 2100. Participants from Division 1 are warmly welcome to participate unofficially.
You will be given 6 problems and 2 hours to solve them.
The round was prepared by TomitaMatei and me, Bufu.
We would like to express our deepest gratitude to everyone who made this round possible:
- cry for their excellent coordination and infinite patience while reviewing the problems!
- Alexdat2000 for translating the statements to Russian.
- Our wonderful team of testers for solving the problems and providing highly valuable feedback: Intellegent, awesomeguy856, _istil, andrei_n, Friedrich, __baozii__, simplelife, omsincoconut, madlogic, nik_exists, Edeeva, SpyrosAliv, and Argentum47.
- MikeMirzayanov and KAN for creating and maintaining the amazing Codeforces and Polygon platforms!
- You for participating in the round!
The score distribution will be:
$$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — $$$2250$$$ — $$$2750$$$
Good luck, have fun, and may the rating be with you!
UPD: Congratulations to the winners!
Unofficial participants:
Official participants: (subject to change)
UPD 2: The editorial is now available!
Auto comment: topic has been updated by Bufu (previous revision, new revision, compare).
as a tester, idk what to say but round is orz
Nice Score distribution!
I hope to solve ABC in this contest
Solved A and B.. could have done C. But turns out I have to learn more. Good contest, had fun
C becomes really simple with multiset, erase operation in multiset is O(1),
Yeah, Ig I have to learn multiset again xD.. Anyway got C with some more tinkering and discussion with a friend
Lowk priority queue >>> and also is erase really O(1) cuz I thought you have to go to the pointer then erase so its basically O(logn)?
yes its O(logn), but if you want to erase a specific no and yk its index, then its O(1), like i used it to erase the first index, ofc you can use priority queue too
Actually, erase(iterator) is O(1) amortized because the iterator already points to the element. Only erase(value) is O(log n) since it needs to search first.
I hope to become pupil in this round, or atleast solve ABC :D
bro didnt you solve a bunch of 2000 problems? and 1500 overall???
Got humbled in A anyways
cap youre just trying to always barely not get 1200 i know it
Why do you say that? You know how much im trying? If i wanted to not get 1200 rating i will not even participate in Codeforces
Lol. I also got humbled by A and B and D.
Same :(
hope complete ABC in D2
Hope to solve problem E!
As a Python beginner, two problems were hacked due to hashmap last round, hope this time won't be hacked.
Hope I don't get -16 on C this time
As a participant, I can fly
Deleted
Deleted
Chinese can fly!
that's tuff
solve AB is enough wish me lucky
Same, but I hope I can solve C too!
npc..
-_- (Frisk face)
Can't wait to see my rating changes after this contest
I hope to solve most of them at, least ABCD
Hope to solve ABC plz GGGGGGGGGGGG
florr user spotted
Upvoting this Comment is counted as a ritual for complating at least ABC. :D
Yess
I upvoted
I upvoted it lil bro
I upvoted
downvoted
Hoping to solve ABC. :)
hope to return 1400
Downvote me
Bro figured out the secret to human nature.
I hope to cross 1500 in this contest :)
Hope to solve $$$ \gt 0$$$ problems ovo
Good luck to all participants!
why do not tester say "as a tester, ......." to get the upvotes?
as a tester, i have no ideea
Hey...
How to become the testers or problem setters in contest
Hoping that I don't go down to pupil again.
I really hope this is a good round.
Really hope to solve E this round.
as a participant i hope the contest will be easy>.<
manifesting solving at least 3 problems — will be back here after contest
I wonder why he didn’t come back
edit: no hate lol
hope to get +6 delta . Peace
i give up
same here
I met the same fate as you!
Hardest contest I've ever done
HOLLLLLY STAR WARS REFERENCE. W Contest btw
I was one contest away from pupil and then, this contest...
guys, wtf was this contest? i sure need to practice but damn
Confirmed I'll be staying a newbie for a while
I give up
is it just me or the contest was too tough >:c
Why are problems D, E, and F so classic?
How F?
it is just dp on virtual trees
Just greedy, centroid and virtual trees
D is similar to https://codeforces.me/problemset/problem/1110/E.
and https://codeforces.me/problemset/problem/1725/L
How could 2000+ people solve D in this contest if 1110E is rated *2200?
Codeforces deflation goes crazy
A>>>B
no, A >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>B
Why is B so difficult
the taskpool seems unfair and unbalanced
problem E is really too good that i cant even solve
A bad problem.
A bad day that I had penalties on almost every problem T_T.
as a tester, i give up at A
I solved $$$C$$$ by doing:
Submission
Please tell me this is not the intended solution.
well it can be solved using priority queue and greedy approach . just try to find sum of smallest number of elements greater than than the smaller level[i]
but yes i found b to be tougher than both a ,c
I was thinking about doing that for a minute, but there is one extra observation: for each row of length $$$m$$$, you never need to check more than $$$m$$$ $$$a_{i, j}$$$'s since the answer is $$$\le m$$$ (we can just knock down a row with $$$m$$$ moves). So you can just store a heap of the $$$m$$$ largest $$$a_{i, j}$$$'s as you're going through the $$$n$$$ rows to do it in $$$O(nm \log m)$$$.
Oh yes. It's kind of like Regret Greedy isn't it? We take all elements, regret it when our sum becomes too big, and them remove smaller ones.
In this case it's not really regret greedy since our heap will basically be a static length of $$$m$$$ for each row (where we store the $$$m$$$ greatest $$$a_{i,j}$$$'s of all of the preceding rows including the current one). If the sum of those $$$m$$$ $$$a_{i, j} \ge v_i$$$, then great, we can process the $$$m$$$ elements and see if we can do better than $$$m$$$. If that sum $$$ \lt v_i$$$, then we don't care since it is given that we can achieve an answer of $$$m$$$.
Do we have to enumerate all heap sizes less than m and select minimum heap size satisfying it ? That was my solution or can it be just solved with one pass ? I pop elements from min heap whenever total number of elements exceed target size for less than m. 1 <= target size <= m
I'm not sure, but either way it wouldn't improve the overall time complexity. If you could do that, you'd probably have to use some complicated data structure.
Notice that $$$ans \leq m$$$ where $$$m$$$ is the number of columns since deleting a whole row is an option.
With this in mind, iterate from bottom to top, maintaining a priority queue (or sorted set), and try taking the greatest numbers at or beneath your current level, stopping at $$$m$$$ numbers.
For each row ($$$n$$$), you access your priority queue $$$O(m)$$$ times so complexity is $$$O(mn \cdot log(mn))$$$
Used priority queue on A level question :D
I'm surprised that E isn't OEISable.
the contest was so hard for me, just I solved A
Problem A
output: 21
still passed all the pretests btw ✌
HOW
isn't the answer 30
passed the system test too ✌
I was just curious, your solution to problem A is giving output 25 although correct ans seems to be 30 then why is it accepted?
Obviously tests cant cover all possible variants, so sometimes your wrong solutions can be accepted. That is the main reason why hacking system exists.
on test
result == 15.
very well system tests.
Hello during contest i faced an interesting "bug".
In Friends Standings i was 3538th at 18.59.27.
And in Common Standings i was 3023th at 18.59.30.
Does anybody know why this happened?
(Unofficials not included to standings.)
I can't upload video but for confirmation you can ask onepersonintheuniverse and amodi .
Assuming u turned off the "Show unoffl",
in common standings the ranklist is based on all official trusted users
in friends standings it's all official users, regardless of whether they're trusted or not
What is a trusted participant and thanks for answer sir.
new accounts need to solve at least one problem per contest for the first few contests for their account to be trusted
these accounts will get their rating changes but they won't affect other's ratings
Ok Ok thanks sir.Hope you become expert soon.
thanks:)
Is it just me or B and C had easier observations than A?
Damn. I solved D but I have no time to write C.
YES
Good problems, but I found testcases (especially for C) a bit poor
Problem D is well-known:
https://codeforces.me/blog/entry/130338
https://codeforces.me/contest/1110/problem/E
I solve problem A and B only in this contest...
Can somebody help me understand why my solution for B fails. I am not able to figure out a test case where it fails. I find the number of zeroes "z" and ones "o" that we need to remove which would result in a alternating string. Then as long as the number of zeroes and ones differ by at max 1 we can just output z + o. If They differ by more than that we can consider the singleton 1s and 0s at the edges of the string. Submission
Consider a case like 00010.
You aren't considering that deleting a character may bring two groups together.
find pairs of 0s (say x) and 1s(say y). ex-> 000, means 2 pairs of 0s and so on.
now if diff b/w pairs of 0s and 1s is 0 or 1. ans is x+y
if it is abs(2), first and last digit comes into play. if zeros are more than ones and first OR last digit is 1, then ans is x+y+1
if it is abs(3), first and last digit comes into play. if zeros are more than ones and first AND last digit is 1, then ans is x+y+2.
is this approach ok????
i am also using the same logic but failing idk why
Question A and C were amazing
is editorial out?
Problem C in this contest is a nasty problem with strict constant-factor optimization requirements.
you can just kinda rawdog it with priority queue to keep track of the m biggest elements
You’re right, but I think it’s rather unreasonable to intentionally block a dynamically-opened segment tree solution with the same complexity purely due to constant-factor overhead.
can confirm the author intentionally decided to block segtree on the 1400 rated div2C problem
I don't think this is a wise choice at all. This serves no purpose other than to annoy the contestants.
This problem single-handedly lowered the quality of the entire round. I’d never make such a stupid decision.
son
you can use a map
You can solve C by mergesort in O(nmlogm)
What was the approach for B? Are you guys too grouping consecutive 1s and 0s and writing their frequenciez in an array?
find pairs of 0s (say x) and 1s(say y). ex-> 000, means 2 pairs of 0s and so on.
now if diff b/w pairs of 0s and 1s is 0 or 1. ans is x+y
if it is abs(2), first and last digit comes into play. if zeros are more than ones and first OR last digit is 1, then ans is x+y+1
if it is abs(3), first and last digit comes into play. if zeros are more than ones and first AND last digit is 1, then ans is x+y+2.
I solved A through D, but only came up with the solution for F right when the contest ended. I thought it was a 2.5-hour round, but it turned out to be only 2 hours. So after all that, I ended up solving F after the contest. /fn /fn /fn
But I feel F's solution is way more straightforward than E's.
For E, you need to derive the formula and then brute‑force to spot the pattern — I definitely can't prove that.
For F, centroids come to mind easily, then greedy, and finally virtual trees — it all clicks together step by step
for D ques Can anyone please tell me why my Maxheap priority queue solution is giving tle at test case 9 and how did you solved the problem
i wonder how many people will get WA2 on D because they didnt think about modulo of negative numbers. almost gave up on the problem before noticing it. fun contest though, thanks
i made the same mistake twice and nearly gave up hope of solving it
who else was misleaded by a dp approach in C :-(
IF someone Really completed C using dp, plz share!
I don't think there was a dp approach to C, I used a priority queue to keep track of optimal ones to use and went from bottom of tower to top to find min at each tower and keep min overall, note that the answer will always be min of that and m since by removing entire tower, it already topples
dp[i][j] -> for rows i to n-1 what is the sum of highest j elements we can pick
dp[i][0]=0 base case; and transition is what i really cant figure out
ultimately if everything is fine -> our ans will be the min of all dp[i][j] such that dp(i,j) < (the min stability index from 0 to ith row)
If interested, please find the transition and help me out
gng can someone tell me how to do A? I'm like stuck, i tried using a frequency table but I can't find what to do first :(. Brute force doesnt seem feasible at n = 50 either.
Ideally we would like all equal frequencies, as in this case we can use all numbers available. To get towards this state, use the most frequent element, then the second most frequent element (while at least two distinct elements remain) repeatedly.
consider the element with the highest frequency, lets call it max. if max<=ceil(n/2), then the answer is just the sum. because you can always pair up any number with a number that isn't itself. but if max>ceil(n/2), then you can notice that at some point you will be forced to put 2 of that number in a row (or rather if you are forced to make some amount of pairs then one of the pairs will have to be 2 of that same number). this is a pretty common idea used in many problems so its good to look it up and learn it.
yall are actually my saviors thanks to both of you i solved it. any tips for getting better at cf overall?
consistency and not being afraid to read editorials were the 2 main things that helped me improve. also do problems that are rated at about your rating+200/300. what are your goals?
to acheive usaco silver/gold next season, im using codeforces to prep for it. also a rating of like 1300+ here would be nice.
honestly I am not too familiar with usaco equivalents to like cf rating. so you're doing it to qualify for like irl competitions for usa or? I feel like each country has very different priorities and things they value in competitors so it really depends.
worst div2 ever
I disagree. I thought the problem quality was incredible. I personally didn't have the best contest and I know that if I didn't spend time checking the leaderboard I could have solved D and if the contest wasn't 2 hours I could have solved D but nevertheless I overall liked the problems. I somewhat had a false solve for A that costed me around 5 minutes and I think with 5 minutes I could have solved D and gained rating :sob: Second time failing to solve D when 97% done with the problem.
That is your own opinion. I think this div2 was much harder than other div2s. I tried to tell my thoughts about the question difficulty by typing the worst div2 ever. But the problem quality was good. I don't know if it was just me but i asked my other friends who participated in this contest, and they also agreed with me. Maybe it is just i got a little rusty with not working daily because i was having a break. But i think this div2 was harder than other div2s.
Yes any contest in which you solved 3-4 problems and you got not much minus rating delta for dont fall from expert will be incredible
Not necessarily, I don't think that personal achievements in a contest should dictate the quality of a contest. I recently did a virtual of 1112 and I think I had a fairly good performance (I didn't bother to impl c and d) but I thought the problems were of somewhat low quality despite doing well personally on this contest. In this contest particular I appreciated how it wasn't a "speedforces" round as much to the problems being more difficult. Also in this contest I don't think I performed nearly as well as I am capable of, I was planning (hoping) to get to 1700 this contest and while yes I didn't drop off too much despite only solving three problems it was still a rather disappointing performance.
Very good contest! Although i didn't solve E or F, i really liked them.
Thanks everyone for participating in Codeforces Round 1115 (Div. 2). Although it was initially difficult to understand from the editorial when I first participating in Codeforces contests. However I found that once I got used to it, the explanations felt very easy to understand, accurate, and highly academic.
We should read the hint and solution before reading code (Sorry for my bad English)
The problem D is very interesting. It's a good round I think.
Hello,
I would like to clarify that I did not share my code with anyone and did not have access to any participant's solution during the contest.
The solution I submitted was written by me during the contest based on my understanding of the problem. The approach used is a fairly standard one, and it is possible that multiple participants arrived at similar implementations independently. I did not intentionally copy code from any source or participant.
If the similarity was caused by a commonly known technique, editorial-style implementation, or another publicly available resource that existed before the contest, then the overlap was completely unintentional.
I respect the contest rules and would appreciate it if the submission could be reviewed manually. If any additional information is required from my side, I would be happy to provide it.
Thank you.
Hello, I received a system warning stating that my solution for Problem 2252D significantly coincides with others. I just want to clarify that I didn't cheat, share my code, or use any outside sources. The similarity happened because the mathematical reduction of this problem basically forces everyone into the exact same standard implementation. During the contest, I realized that replacing a[i] with a[i-1] — a[i] + a[i+1] is really hard to track directly. But if you transform the array into a difference array where d[i] = a[i+1] — a[i], it makes everything way simpler. If you apply the operation, the new value becomes a[i]' = a[i-1] — a[i] + a[i+1]. When you calculate the new differences with this updated value, the left difference d[i-1]' becomes a[i+1] — a[i], which is just the old d[i]. The right difference d[i]' becomes a[i] — a[i-1], which is the old d[i-1]. So, the complex operation from the problem statement is literally just swapping adjacent elements in the difference array. The problem also says the operation is only valid if a[i-1] and a[i+1] have the same parity, meaning their difference is even. Since a[i+1] — a[i-1] is equal to d[i] + d[i-1], their sum can only be even if d[i] and d[i-1] share the exact same parity (both odd or both even). Because we can swap any adjacent differences that have the same parity, the optimal way to get the lexicographically smallest array is just to find contiguous blocks of differences with the same parity and sort them in ascending order. When writing this in C++, I naturally used a while loop to find the boundaries of these contiguous segments and called std::sort(). It's such a direct way to code this logic that my variable names and loop structures ended up matching many other participants who figured out the same math trick. I kindly ask the admins to review my thought process, as this was just a natural implementation of a deterministic solution, not a coordinated leak.
Hello,
I would like to clarify that I did not share my code with anyone and did not have access to anyone else's solution during the contest. I did not use any external help during the contest . During the contest i realised if two alternate numbers a[i-1] and a[i+1] have the same parity then the difference between a[i-1] and a[i] and a[i] and a[i + 1] will also have the same parity . Using the first and second test case i realised that if a section of difference array having the same parity is sorted , this will force the resulting vector to be lexographically smallest.
While writing the cpp code I used while loop to find the boundary of the same parity substring. Once the while loop ends i sorted that section in parity and moved to the next section.
i request admins to review my thought process during the contest as I have no other proof of innocence , i would also like to add that i use the default VSCode formatter while writing all of my code so that may also have enhanced the similarity to other submissions who may have done the same.
practised so many questions still not able to solve A
It's called "problems" not "questions" :)
I received the plagiarism warning for my submission 385925201 (2252D) and would like to request a manual review.
I solved and implemented the problem independently during the contest and had no access to any other participant's code. A few days ago, I saw this youtube video and coincidently this question used a similar technique — Link (https://youtu.be/96RG7EBF8LI?si=k-KgX3StSScjr3L7), dated : 24 June, 2023.
I understand that my code is very similar to other people who have solved it. However, I did not view their submission or copy from them. I had no access to their code during the contest. I have my original VS Code files/development history as evidence of my independent work, and I can provide them if required.
I would be grateful if the case could be manually reviewed. Thank you.