Merhaba Codeforces!
We are proud to invite you to Codeforces Round 1118 (Div. 2), which will be held on Aug/29/2026 17:35 (Moscow time).
The round will be rated for participants whose rating is below 2100, but higher rated users are also welcome to participate out of competition. You will be given 6 problems, one of which will be divided into a subtask, and 2 hours to solve them. Also, there is at least one interactive problem, so you are recommended to read the guide to interactive problems if you have not encountered them before.
The problems were authored by me (ItsNotMeItsYou), carcinisation, mychecksdead and Seferoglu.
This round was prepared by some members of the 2025 and 2026 IOI team of Türkiye, and we hope you enjoy all our problems.
We would like to thank:
cadmiumky for his outstanding coordination of the round,
Um_nik for the preliminary review,
Alexdat2000 for Russian translations,
MikeMirzayanov and KAN for Codeforces and Polygon,
Our testers: destructive_criticism, tolbi, dinohaur, anpaio, kalimm, nifeshe, https, kafamcokkaristi, FatihCihan, LucaLucaM, PieArmy, int23_t, temporary1, robert9524, Kel_Mahmut, dead0ne, kawasaki, Synd209, elotelo, Anfeco,
anpaio for improving at least one problem,
destructive_criticism and dinohaur for at least one unused suggestion,
You for participating in the round.
Score distribution: $$$500-(750+1000)-1250-2000-2250-3000$$$
Good luck & have fun!
UPD: The editorial is out! Sorry for underestimating the difficulties of the problems, especially B2 and D. We tried to serve as many cool problems as we could. And apparently, this led to some difficult ones.
Congratulations to the winners:
Official participants (subjects to change):
Unofficial participants (subjects to change):
ItsNotMeltsYou Codeforces!
As a tester, I can confrim that this is a funny joke and I laughed.
Were you said that you are testing Div 1 + 2 ? Bro WTFF THIS ROUND WAS LIKE SO LESS POINTS LIKE WHO MAKE B2 THAT MUCH HARD with 750 points GUYS IT'S DIV 2 NOT 1 SHOW MERCY MAN like wtf
Yeah I knew it was div2 idk how much they changed since the version I tested tho. Im sorry to hear this I know how frustrating it can be when a contest is hard.
as a tester, i can write comments
As a not tester, finally
Merhaba Codeforces!ItsNotMeItsYou goat
since when dinohaur had this crazy pfp
Real
As a tester, I didn’t generate tests for any problem
AHHAHAHHAHH you made me laugh for a while
As a not tester, I can confirm the problems will test me.
I love how ItsNotMeltsYou is a GM in the announcement... I guess he/she agrees with Errichto's idea...
Yep
As a problem, hope the participants are fun
Also crazy B distribution
As a contest, I hope that you are going to be easy to solve
It's crazy that I haven't seen subtasks in Div.2 B since I came to Codeforces:)
Sonunda, we have a Turkish round
Planning to give this round while eating Turkish Baklawa :yum (Apologies for wrong spelling in advance).
wtf strong
As a tester I can say that I tested the round.
I also can say that if you are reading this you are obligated to participate.
as a person i cannot confirm that the problems exist
A Turk Round
Finally, a contest with an interactive problem
"new mask same task"(by iron man)
As a not tester this will be the best contest ever on CF
B1 B2 are crazy
Great contest, Hope you guys have fun!
As a tester, my favorite moment was when carcinisation said it's testing time and tested all over the place!
OHAA TR ROUND LESGOO
going to be my first contest here.. :)
first contest and directly Div 2 ??
Don't know how this system works, just registered for it..
im a newbie too but i only solve Div 4 past contest ques... should i register for it too???
Great to know that I'm not the alone newbie here :) I think you should give this contest a try..
yeahhhh but havent tried any Div 2 problem... i think i should give it a try
basically problems are categorized here... Div 4 for beginners Div 3 for intermediate type and so on.., higher you go problems become difficult
I'm a final year engineering student and still don't have any good amount of knowledge about these platforms.. So just a newbie here trying to figure out things on my own.. Can you help me understand these concepts? I mean we can connect.. I have tried reading documentations but they are just too long to finish in hr :(
esshhh.. im a first year student yarrr ><
T_T Keep working buddy at least uh have started on time..
Tip: You should solve all divisions, or at least try div 3. Div 4 problems are mostly really easy even for newbie level and won't get you very far
yeahhh... but even in Div 4 last ques like F or G are good though. Well I solve Div 3 and 4 both. Haven't touched Div 2 or 1.
You should try doing div2s because there are only 4 div4s last year. We might get GTA VI before a div4...
lolll... that's hilarious... alright i will register for this... ( ╹▽╹ )
The "You" is reverse-nutella T_T
Yeah it's called "tourist" I believe, he got it when he crossed 4k rating
It's actually a rank named after whoever has the rank, for jiangly it says jiangly as rank not tourist
Oh sorry, I didn't know this I genuinely thought jiangly and tourist were dif ranks lol
Hope get rating up XD
ItsNotMeItsYou I know you're from Turkey, and I'm from Azerbaijan. :)
azerbaijan and turkey brothers <3
why -10?
before seeing author's profile i didn't know that rating may be negative
+1
Oh, there's been worse.
"faaaaa"
*realizing that all of the authors agree to Errichto's opinion*
What opinion?
dementia got to bro 🥀
It seems like dementia has been spreading across multiple codeforces users
Seems like dementia has been spreading across multiple CF users
Disagree, I still remember well.
Agree, I have met many people on CF who have dementia
At first, I thought that only ItsNotMeltsYou agree, after that, I realize the thing I said above
6 7
mecukuryurt we need to lock in dude
yeah mate trust me, i am going to get ac on B2 /s
-6 on B1 TUT
oops, we don't talk about that lol
lol, chill bruh i couldnt even solve A :.)
I am really interesting for the contest [contest:Codeforces Round 1118 (Div 2)] .. Thanks to [user:ItsNotMeltsYou] and Me som__ is preparing for this.. All the best to all.. Good buy .. Sayonara...
carcinisation Seferoglu orz!
vixxa is my favorite Macedonian fr
as a not tester give me contri
fu*k you why you give me negetive
Asking for contribution is useless and annoying
When testers say this and get contribution it’s not because they asked for it it’s because they contributed by testing
Good luck to all participants!
waiting for contest
First time seeing 2B's in a div 2 since I started. Context: I have started very recently :)
Finally Turkish contest. This contest will be different in good way. Good luck for everyone!
I just want to add 50 rating，and up to pupil..... if my dream comes true,it will be a fantastic gift in the end of summer holiday! (I'm a chinese student,and must go to school in 0901,the contest is the last one in summer holiday TAT)
Congrats u r pupil now
thx! I got +30 and become pupil!!!
Looking forward for this contest for having at least one interactive problem
as a tester, i don't know why people always say as a tester.
WTF IS "Apologies for the previous announcement, the original statement was correct."?
worst round ever
Incorrect announcement is entirely my fault: a question asked during the round made me believe that the statement was incorrect. This has nothing to do with the quality of the round.
That was just me being impulsive, sorry about that.
WHY ARE THE PROBLEMS SO HARD. Like you can see C has ~1k5 while D & E only has < 100 solved (up to 11h05)
Testers forgot thought that they were testing a Div. 1 so they approved these problems
D is too hard for D :(
god i hate interactive problems
B was way too hard
I spent 1.5 hours on D and got TLE on pretest 3 using python
$$$B2$$$ is a good problem, but need to be very careful with implementation and time of the solution. $$$C$$$ is so much easier, it's basically the diameter finding algorithm.
100 solves on $$$D$$$ and $$$E$$$ is crazy.
Finally a contest with an interactive C
What was your strategy? I kept on getting WA.
You just need to do the same thing as this problem
For that problem, you need to find the furthest node from the root, and then the furthest node from the node you found before
Got absolute cooked
nlog^2n intended for E?
I hope so :(
how do you do that? i could only get n^2logn
Nice B1. Thanks.
loved the problems; especially D
who else remembered the tree diameter algorithm from Antti Laaksonen's book for C?
What the hell even is B2
COOKEDFORCES
maybe testers opinons about a problem being too hard matters...
how the hell do you solve B2, C is exponentially easier, how do they have the same amount of solves
Probably because people saw it earlier and gave it more brain power.
yeah I wasted 40 minutes on B2 then solved C in 10
the jump from c to d/e was insane
and am i crazy or was b2 significantly harder than c
What in the world was D?
How are you so bad at cheating that you don't realize you can reuse B2 for B1? :sob:
Buddy, there are people who are not here for the rank but solve questions for the approaches, I get where you are coming from due to the high amount of cheaters, there are ways to find them rather than just blindly pointing fingers at everyone, in this for more than 3 years now so have seen alot.
Sir you have your codeforces rating in your linkedin bio.
literatureforces C, B2 was too tough imo
I gave up on B2 , solved it 1 min after contest when i re-tried it in the last 30 mins . hate my life :(
Nice contest
i'm usually pretty good at magic tiles
My solution for D:
First, disregard the statement about $$$2$$$ columns, these are just some random intervals. Remove any interval that is inside another interval. Split the intervals into connected components. Notice that any point is covered by at most $$$2$$$ intervals.
Each interval has at most $$$4$$$ possible states in the final solution: either cut or keep the left part and same for the right part. Say we processed the first $$$i$$$ intervals. There are $$$2$$$ solutions we should keep: the one where interval $$$i$$$ was not cut on the right and the one where it was cut. This allows us to extend to interval $$$i+1$$$ (there are like $$$4$$$ possible solutions of which we need to keep $$$2$$$). When multiple solutions are available, sort them in decreasing order and compare them lexicographicaly. The bigger one is the one you want.
If you implement this with multisets (I think maps work too but didn't check) then you get something like $$$O((N+M)^2*\log(N+M))$$$ which somehow fits in $$$4$$$ seconds (my solution takes $$$2.1$$$).
I think there are better ways to solve this though
I think this solution is $$$O((N+M)^2)$$$ with no log factor. You're doing $$$O(N+M)$$$ insertions and $$$O(N+M)$$$ comparisons; insertions are $$$O(\log (N+M))$$$ and comparisons are $$$O(N+M)$$$ (even though searching for a single element takes $$$O(\log (N+M))$$$, you can traverse the entire tree in $$$O(N+M)$$$ time, not $$$O((N+M) \log (N+M))$$$ time).
I think you're right
Thank you bro
My brain is offline
Good contest
easy C, hard B2
Problems D,E and F have no business in Div.2 round.
Is it just me or this contest was genuinely hard for a div.2 round?
It was hard for me too.I could only solve A,B1 and C.I have seen way easier div 2s both in practice and live.
This contest was actually tough even on an absolute scale. Could solve only A and B1 (don't really like interactive problems). The last time I solved 2, my rating decreased by 27, this time it increased by 21.
editorial link
Thanks for contest and interesting tasks!
Bruh why are the proplems so hard (I didn't participate)
Bro WTFF THIS ROUND WAS LIKE SO LESS POINTS LIKE WHO MAKE B2 THAT MUCH HARD with 750 points GUYS IT'S DIV 2 NOT 1 SHOW MERCY MAN like wtf
IMO this was one of the hardest Div.2 rounds in terms of difficulty distribution.
A was a good standard A problem, and B1 was also reasonable, but the jump from B1 to B2 was quite large. B2 was not just a harder version; it required a completely different level of observation and understanding of the structure.
C was an interesting problem, especially because of the interactive nature, but it was still within the expected range of a Div.2 C.
The main issue was D. Magic Tiles felt more like a serious algorithmic problem rather than a typical Div.2 D. The combination of compressed input, huge coordinate range (10^18), and the need to construct a compressed optimal answer made it a very heavy problem for a 2-hour Div.2 contest.
E was also a very interesting but difficult problem. The LCM and divisibility observations required a strong mathematical insight.
Overall, I liked the problems because they were creative and educational, but I think the difficulty curve was too steep after B1. The gap between B1/B2 and D was much larger than what I usually expect from Div.2. For many participants, the contest probably became a race of solving A+B1+B2+C rather than gradually progressing through the problems.
Still, great round and very high-quality problems.
Some solution sketches:
A: No operation can remove the first or last elements, and all remaining elements can be removed (by performing an operation on the element we want to remove, the first element, and the last element). Thus, the answer is the GCD of the first and last elements.
B: Fix k and suppose we will sell carrots with length $$$x$$$. To start, let's figure out how many carrots of length $$$x$$$ we can create by splitting a carrot of length $$$l$$$. We can make a few straightforward observations:
This tells us that we can create at most $$$\min \left( \lfloor l / x \rfloor, 2^k - 1 \right)$$$ carrots of length $$$x$$$ from a single carrot, plus one extra carrot when the length is equal to $$$x \cdot 2^k$$$. This bound is achievable by performing cuts of length $$$2^{k-1} x, 2^{k-2} x, \cdots, 2x, x.$$$
In the easy case, with $$$k = 1$$$, this tells us that if our carrot length is $$$x$$$, the number of carrots we sell is equal to the number of carrots starting with length at least $$$x$$$ plus the number with length exactly $$$2x$$$. We can compute this efficiently for each $$$x$$$ in $$$O(N)$$$ time.
In the hard case, carrots of length between $$$x$$$ and $$$2x-1$$$ contribute $$$1$$$ ending carrot each, carrots between $$$2x$$$ and $$$3x-1$$$ contribute $$$2$$$ each, and so on, until all carrots with length at least $$$(2^k - 1) x$$$ contribute $$$2^k - 1$$$, except that carrots with length $$$2^k x$$$ contribute $$$2^k$$$.
We can iterate over $$$k$$$, and for each $$$k$$$, iterate over $$$x$$$. Using prefix sums, we can count the number of carrots whose lengths fall in each of the intervals described above (e.g. $$$x$$$ to $$$2x-1$$$, $$$2x$$$ to $$$3x-1$$$, etc) in $$$O(1)$$$ time per interval. This takes $$$\frac{n}{x}$$$ queries for each $$$x$$$, and summing over all $$$x$$$ gives a total complexity of $$$O(n \log n)$$$ for a fixed $$$k$$$.
Then, note that when $$$k \gt \log n$$$, taking $$$x = 1$$$ is sufficient to cut a carrot of length $$$l$$$ into $$$l$$$ pieces, which is the best we can do. Thus, for large enough $$$k$$$, the answer is just the sum of the entire array, which implies that we only need to do the computation described above for the smallest $$$\log n$$$ values of $$$k$$$. Thus, the total complexity is $$$O(n \log^2 n)$$$.
C: A well-known algorithm for finding a diameter of a tree is to root the tree arbitrarily and find the furthest vertex from the root; call this vertex $$$v$$$. Then $$$v$$$ must be one endpoint of a diameter; we can find the other endpoint by finding the furthest vertex from $$$v$$$.
We can execute this algorithm using the provided queries. Let $$$d$$$ be the largest distance between any two vertices we've found so far. Then, to find the furthest vertex from the root, maintain $$$d$$$ and a vertex with distance $$$d$$$ from the root. For each vertex, check if its distance is at least $$$d+1$$$, and increment d while this is true. In the end, the last vertex that caused us to increase $$$d$$$ is the furthest from the root.
Now, reroot the tree at the vertex found above and apply the same algorithm, without resetting $$$d$$$. The furthest vertex from the new root is the other endpoint of our diameter.
To bound the number of queries, note that each query causes us to either increment $$$d$$$ or to move on from a vertex we're currently checking. Since the diameter of the tree must be at most $$$n$$$, we do fewer than $$$n$$$ queries that increment $$$d$$$, and in each of our two iterations, we need to handle $$$n-1$$$ vertices each. The total number of queries is thus less than $$$3n$$$, so we're good to go.
D: First, note that the scoring function just means we want to lexicographically maximize the list of segment lengths when they're sorted in descending order.
Observe that if an interval in one column is contained within an interval in another column, we can ignore the first interval (because if we were to use any segment of it, we could achieve at least as high a score by instead using the corresponding segment of the second interval). This reduces the problem to the case where no interval contains another.
Index the endpoints of the segments and let dp[i] be the lexicographically largest list of segment lengths we can achieve before reaching the i'th endpoint. Iterate over $$$i$$$ in increasing order. Note first that if $$$i$$$ both the starting point of one segment and contained in another, the next segment we add should come from the segment starting at $$$i$$$, as if we wanted to use the other segment, we could do better by starting it before position $$$i$$$. Thus, given $$$i$$$, the segment we want to start from is uniquely defined.
Then, to transition, we should either use the full segment or the part of the segment until the starting point of the next segment in the other column. This gives us two transitions from each of the $$$O(N+M)$$$ states. We can compare two sequences in $$$O(N+M)$$$, so each transition takes $$$O(N+M)$$$ time to process, giving a solution in $$$O((N+M)^2)$$$ in total.
The one catch is that storing the entire DP table consumes $$$O((N+M)^2)$$$ memory, which is too much. However, all of our transitions take us to the next starting/ending point in one of the columns, so we only need to maintain $$$O(1)$$$ states at a time. Thus, our solution works in a total of $$$O((N+M)^2)$$$ time and $$$O(N+M)$$$ memory, which is enough to solve the problem.
E: First, observe that the answer must be a power of a prime. Indeed, if $$$k$$$ is not a prime power, then when we write $$$k$$$ as a product of prime powers, anything divisible by $$$1, \cdots, k-1$$$ must be divisible by each of the constituent prime powers, and thus by $$$k$$$ itself.
Now, suppose we want to find $$$l$$$ and $$$r$$$ satisfying $$$f(l, r) = x$$$ for some prime power $$$x$$$. We might as well make our subarray as large as possible, so either $$$l = 0$$$ or $$$a_{l-1}$$$ should be a multiple of $$$x$$$, and likewise either $$$r = n-1$$$ or $$$a_{r+1}$$$ should be a multiple of $$$x$$$. In other words, the subarray we choose should be an interval between two elements of $$$a$$$ that are multiples of $$$x$$$ (with no multiples of $$$x$$$ in between them).
Iterate over the elements of $$$a$$$ from right to left and say our current position is $$$p$$$. We'll maintain an array $$$nxt$$$ where $$$nxt_i$$$ is the position of the next multiple of $$$i$$$ with position greater than $$$p$$$ in $$$a$$$. Then, if $$$nxt_i \gt nxt_j$$$ for all prime powers $$$j \lt i$$$, we can set $$$l = p+1$$$ and $$$r = nxt_i - 1$$$ to get an array with $$$f(l, r) = i$$$. Storing $$$nxt$$$ in a segment tree lets us perform these queries in $$$O(\log n)$$$.
By the above observation, it suffices to only check cases where $$$a_p$$$ is a multiple of $$$x$$$. As we iterate over $$$p$$$, we'll check the above condition for all prime powers that divide $$$a_p$$$, then we'll update $$$nxt$$$ accordingly. At the end, we'll check the condition for all prime powers to handle the subarrays starting at index $$$0$$$.
The number of prime powers dividing $$$n$$$ is bounded by $$$\log n$$$, so at each index we perform $$$O(\log n)$$$ updates and queries. Our total complexity is therefore $$$O(n \log^2 n).$$$
F: We perform tree DP. For each vertex $$$v$$$, we'll compute the minimum possible sum of costs in the subtree of $$$v$$$ for each possible value of the sum of $$$x_u$$$ over the subtree of $$$v$$$.
In the base case, the cost of a leaf is always 1, and depending on the starting value, $$$x_v$$$ can be $$$1$$$, $$$-1$$$, or both.
To transition, we need to combine this data over all subtrees. To do this, we'll use the slope trick: for each subtree, we'll store the minimum possible subtree sum and its cost, plus an array containing the differences in costs when we increase the balance by 2 (for any subtree, the parity of the balance must be equal to the parity of the number of vertices in the subtree). It can be proven by induction (using facts from the rest of the solution) that these slope arrays are always increasing.
To combine two arrays, we just merge their slope arrays and sort in increasing order. Then, if the root vertex of our subtree has value 1 or -1, we can just add or subtract 1 from the minimum possible subtree sum. If the root has value 0, then we subtract 1 from the minimum possible subtree sum. Now, the cost of achieving slope $$$x$$$ is equal to the minimum cost of achieving slope $$$x-1$$$ or $$$x+1$$$; this can be simulated by adding a $$$0$$$ to the set of slopes. Then, we update by adding -2 to the slope over the interval where the subtree sum is negative and 2 to the slope over the interval where the subtree sum is positive.
These operations can be handled efficiently using a treap. Treaps can merge subtrees of sizes $$$n$$$ and $$$m$$$ with $$$n \gt m$$$ in $$$O(m \log (n/m))$$$ and can perform range updates in $$$O(\log n)$$$, and this is enough to achieve a total complexity of $$$O(n \log n).$$$
If you don't have a treap library on hand, another approach is to maintain two sets for slopes greater than or less than $$$0$$$, eliminating the need to split before performing range updates. We can maintain a fixed tag for each of the two sets in order to perform updates over the whole set. This approach has $$$O(n \log^2 n)$$$ complexity.
This sketch is great. Also you can solve F in a greedy way, we will add that solution tomorrow. I said because of maybe you want to try :)
Thanks everyone for participating in Codeforces Round 1117 (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
<and>operators ofstd::vectorcan conveniently perform lexicographical comparisons.D problem is best problem in this contest
wallahi I got cooked
this contest made me ragequit
I received a plagiarism warning for submissions 388806569 (2258B1) and 388825898 (2258C). I would like to clarify that I did not copy these solutions from the mentioned users. I solved both problems independently during the contest. The approaches I used are standard/direct approaches for these problems, which may explain the similarity. I am happy to provide an explanation of my reasoning or any additional information needed for review.
i was late for this contest but i checked questions and it was really good. Turkish people do more contest like this. and specially for div 3 and div 4 for beginners.
acc
@cadmiumky, I received a plagiarism warning for submission 388819264 (2258C). I would like to clarify that I did not copy this solution from any of the mentioned users. I solved it independently during the contest. The approach used is the standard adaptive-query technique for finding the diameter in an interactive setting (as described in the editorial), and the resulting code is quite short, so there is limited room for stylistic variation which likely explains the similarity across many submissions. I am happy to provide my code or any additional information needed for review.
Hello Codeforces team,
I received the system message regarding my submission 388802642 for problem 2258B1, which significantly coincides with someone.
I want to clarify that both accounts belong to me. I recently created the second account with my different gmail id and mistakenly participated in the contest using both accounts. I submitted the same solution from both accounts, which is why the submissions are identical.
I was not aware of that using multiple accounts in the same contest is against the rules. This was my mistake, and I apologize for it. I will use only one account for future contests and will not repeat this.
Thank you
Hello Codeforces Team,
I received the plagiarism warning regarding my submission
388804450for Problem 2258C. I want to clarify that I wrote my solution independently and did not copy or communicate with the other contestant.I understand that my implementation is similar to another submission. However, the underlying approach is based on a standard tree-diameter technique using distance queries, which predates this contest.
For reference, similar techniques were publicly available before the contest: * 2020 write-up on finding the diameter of a hidden tree using distance queries: https://anonymous3141.github.io/blog/2020/Tree-Graphs/ * “Finding the diameter of a tree with distance queries”, published on arXiv in September 2025: https://arxiv.org/abs/2509.23326
I am providing these sources to show that the underlying approach was publicly known before the contest and could be independently derived. I did not use the other contestant's code or communicate with them. I respectfully request that my submission be reviewed in this context.
Thank you.
b1 i solved this way only freq[x] and freq[2x] matter and using binary search easy way https://pastecode.io/s/3phi2vwi
can somebody give the optimal solution of b1
My O(N log N) approach for Problem B:
Intuition:
When we consider any even value x present in the array, the maximum operations we can perform on it is bounded by m >= x / 2.
If we fix this operation, any element already greater than or equal to x / 2 will contribute to the valid subset.
We sort the array initially so that for each valid even number x, we can find the count of elements >= x / 2 in O(N) using a two-pointer pass.
We also add the frequency of x itself and compare across all candidate even numbers to get the maximum possible count.