Hello Codeforces,
I'm so excited to invite you to participate in Codeforces Round 1111 (Div. 2), which will be held on Jul/18/2026 17:35 (Moscow time)!
You will be given $$$6$$$ problems to solve, one of which will be divided into subtasks. The problems were authored by me, makrav, and PvPro.
The contest was prepared by two IOI 2026 participants from Russia, so you can be sure that the problems are of the highest possible quality.
I would like to thank these people for making the contest possible:
- PvPro for coming up with an enormous number of problems for this round (and having most of them rejected by me).
- nifeshe for outstanding coordination and helping with problem preparation.
- Um_nik for preliminary reviewing the round.
- Intellegent, dinohaur, DizzyGroovy for being the first, second and third coolest testers respectively.
- allvik66, __baozii__, _istil, Wansur, TeaTime, Noobish_Monk for VIP testing.
- The rest of our testers: Mark_Pr, temporary1, Proof_by_QED, Arpa, omsincoconut, shorya1835, Argentum47, simplelife, naneosmic, nik_exists.
- MikeMirzayanov and KAN for the Codeforces and Polygon platforms.
- And You for participating!
The score distribution is as follows: $$$500 \ — \ 750 \ — \ 1250 \ — \ (1500 \ + \ 1250) \ — \ 3000 \ — \ 3500$$$
UPD: Editorial
Congratulations to the winners:
Unofficial participants:
Official participants: (subject to change)
First solves (subject to change)
A. 00:01:14 by sivi_21
B. 00:03:32 by sevlll777
C. 00:05:38 by AshikeRuet
D1. 00:03:09 by HugeWide
D2. 00:20:32 by potato167
E. 00:29:55 by soumya_ranjan17
F. 00:46:05 by SleeplessSouris
Our 15th contest
Waiting for our 16th one
I am so lucky to witness the last binary contest of my lifetime
last binary contest :|
who told you that cf will die before round 10000.
*last binary contest of the century
(assuming 1 to 2 contests per week on avg)
There are more people learing competitive programing. And most of us don't die in the next 50 years. The number of people who learns programing will increase a lot, and then maybe MikeMirzayanov earns much money and buy servers and the hold contests twice a day or more?
what if we die before 10000? :(
At least we get ternary contests for a while
And base 10 contests, weird, seems like every contest is a base 10 contest
Even more weirder, if we use binary representation for every cf round number, all bases $$$i$$$ $$$(i \gt 1)$$$ seems to be happy :|
PS: Came up with a problem based on this
https://codeforces.me/problemset/problem/2228/C2
Nice work. This is a more general form of your problem.
thanks:)
if contests pick up speed in the future, I will take in another binary contest when I am 90 (¬‿¬)
I guess it's speedforces for Problem A,B and C:)
Why downvote me....
Because most newbies/pupils and even some specialists struggle at C, so they disagree with you. (me too)
Got it,sorry.
I mean that maybe D1 and D2 this round are too hard to solve(because they have higher scores than usual) for most participants so who solves A,B and C fast can get higher rank than usual contests:)
exaclty i am a newbie a struggles a lot while what i see just after opening the contest is the a lot have already done upto c
sen niye her yerdesen
Yalanci turist sene ne? Her yerde ne demek? Codeforces ikinci evim kimi di.
I'd say speedforces ABCD1,
if lucky D2, if blessed by Great Mike E.
As a tester, i can't read
aaa_Pigeon2 ..., please, don't post
.Your begging will not stop his descend into the comment section.
is next contest after this one really 2 weeks later?:( or there will be contests between this contest and the contest that is shown in contest section for 2 weeks later :)
Maybe the admins will add more contests between the two.
Even if they won't, you can still enjoy contests like ABC or ARC:)
Our last binary contest for us all :(
Last binary contest.
Hopefully no more NASA-level constructive algorithm and game theory.
as an unlisted tester i secretly tested
Thanks for the round , Wishing everyone the best of luck
Hope my rating keep 2026 after this contest :)
It's so legendary to witness the last binary contest in person.
Pov:: Rate -200
Amazing number!
We got last palindrome contest before GTA 6 :)
what if this contest is full of bit manipulation and palindrome based question, just saying.
i want to be pupil please make questions easy level
I will be live post contest discussion stream here
UPD: ok ok... my guess was wrong :(
B was good
Ideas for $$$D1$$$?
Answer is always a power of two (or zero if the array is already sorted).
$$$2^{mx}$$$ where $$$mx$$$ is the maximum bad index, i.e., we compare $$$a$$$ and a sorted version of it and a bad index is where $$$a_i \ne b_i$$$? This is what I tried, but it's wrong :(
i think we need the maximum different power of $$$2$$$ between an index and the index the value is supposed to be at. so if a number is at index $$$j$$$ and should be at index $$$k \neq j$$$, we look at $$$2^{\lfloor log_2(j \oplus k) \rfloor}$$$ and take the max over all of these and $$$0$$$
That was exactly what I found out but still gott wronng ansss
why??
(Using ^ to mean xor here:) Suppose we want to swap indices i and j. We can express i^j as a sum of powers of 2 corresponding with the 1-bits in the binary representation of i^j, then perform a sequence of swaps at distances that are powers of 2.
That means if the highest one-bit in i^j is pow(2,m), we can swap i and j if and only if k ≥ pow(2, m). Values of k in between powers of 2 don't change the pairs of indices that can be swapped (indirectly): only values of k that are powers of 2 unlock new swaps.
Concrete example: to swap 11 (0b1011) and 17 (0b10001); we can calculate 11 ^ 17 = 26, so when k ≥ 26 we can swap them directly. But we can decompose 26 = 0b11010 = 0b10000 + 0b01000 + 0b00010 = 16 + 8 + 2.
This means that already when k ≥ 16 we can swap: 11 with 11^16 = 27, 27 with 27^8 = 19, 19 with 19^2 = 17. Now the element at index 11 is at index 17. (The element that was at 17 is now at 19; we can do the swaps in reverse to move it to element 11, and then the effect is that 11 and 17 are swapped while no other elements have moved.)
Wow, thank you
I can tell it we had to go by powers of 2 I suppose, however I couldn't figure out, but point of interest was near the powers of 2. Waiting for editorial
I thought the the value of k would at most be highest bit of the largest index not in its correct sorted position. I tried but it didn't work. I suppose you can reduce the value of k further if there were other guys with the same highest set bit so they cancel out..can anybody tell me was this the solution...
Binary search
When checking for k, you can notice that each block of size x (smallest power of 2 greater than k) can be swapped arbitrarily, so the smallest x numbers need to be in the first x, next x numbers in the next x positions, ect
idk for D2 tho, someone pls help, is it segment trees?
Yep, segment tree of (min, max, k_needed)
The thing is that we group elements by groups of 2^m from left to right. For example: A = 2, 1, 5, 2 -> [2]. [1]. [5]. [2] -> [2, 1], [5, 2] -> [2, 1, 5, 2] And we check whether sorting every group independently sorts the whole sequence: A = [2], [1], [5], [2] Not sorted A = [1, 2], [2, 5] Sorted so we print the size of the group.
This solution works for every array A except for when A is already sorted, in which case we print '0'.
In case of a group missing elements, for example when A = 1, 2, 1 we get [1, 2], [1, _], we fill the missing numbers with max_a[i] because it doesn't affect the result. In the case of 1, 2, 1, the groups would be [1, 2], [1, 1000000000]
huh but it doesn't work for this array 2 5 3 4 1 6
Here the answer is 4 but sorting 4 elements by group [2 5 3 4], [1, 6] doen't sort the array
Sorry, I forgot to say "divided by two" so we would try with 8-sized groups and we print 4. Also, in case we try with 1-sized groups, we would print 1/2 which would be rounded to 0.
k = max(k, MSB(current index after sorting ^ index before sorting))
I need stronger examples in C and D
You can try this. First,a = [1,0],b = [1,1] Second,a = [0.0,0],b = [1,1,1] These two pairs of data helped me find my bug.
Try this Python script: https://pastebin.com/0Xypd6RZ
It writes a bunch of testcases to
C-test.inand the answers toC-test.ref. I used it to debug my own solution, so I might as well share it.How D2 awa
First solve D1 with merge sort.
Then, the initution of that using some data structure comes out.
Well, let's try segment tree first(for convience, push $$$10^9$$$ to the back of $$$a$$$ until length of $$$a$$$ is a power of 2). So, our segment tree must maintain the answer itself.
Let's say a chunk is an interval starting at $$$x \times 2^y$$$ with length of $$$2^y$$$. $$$y$$$ can be 0.
By looking at the procedure of D1, we'll see that for a chunk, if the maximum of the left half is strictly greater than the minimum of the right half, then $$$k$$$ must be at least the length of the chunk divided by 2.
So we just maintain range minimum, range maximum, and answer(note that we made the length of $$$a$$$ a power of 2, so a node on the segment tree just maintains a chunk).
TC: $$$O(n + q \log n)$$$
Implmentation
Thank you！
D1 GOOD problem.
I could NOT submit my solution to D2 due to cloudflare. How to solve this problem.
I forgot that merge sort tree works in O(log^2) and tried to use it in D2. Does anyone have ideas on D2?
I thought log(n)^2 = log(n^2) = 2log(n) lmao :(
I got a O(q*log(n)^2) solution using binary search and segment trees, but it TLEs :(
Having blocks-split array, and knowing max and min in each block, array can be sorted if $$$max_i \leq min_{i+1}$$$. You can keep such "broken" pairs of blocks for each log-level if you do segment tree updates, and verify the vertex against it's left and right neighbors
D is a really awesome problem. I am not sure why $$$10^6$$$ is needed as constraint considering solution seems to be $$$n log n$$$, but anyway really cool one. And the update part adds some cool complexity.
It was really unexpected for me to have a need for formula of left/right neighbor in a segment tree (and generally, analyzing it's layers seems super cool!).
For E it was not obvious that (n, 1) path is also needed. The problem without closing the loop seems maybe even more interesting, so I spent quite some time on it and seems to be a bit late to solve:(.
I think the $$$10^6$$$ is meant to prevent some $$$O(n log^2n)$$$ ideas for D2 like maintaining a set for each $$$2^k$$$-sized interval.However they didn't make it tight enough to prevent some $$$O(n log^2n)$$$'s from passing on D1 (like sorting on each $$$2^k$$$ interval)
A,B,C were fire :D
https://codeforces.me/blog/entry/133949
Was there really a necessary reason for D2 to have n,q <= 1000000 rather than 200000 or even 500000 on a 2 second time limit? All this really did was pretty much screw over anyone using Python. (https://codeforces.me/contest/2247/status)
Did anyone have a segment tree implementation for D2?
Here is from somebody in my friend list Solution
Problem C with subarray instead of subsequence could be interesting. Wondering if there is an efficient solution. Wasted most time trying to solve that.
In problem c the only observation was you have to see how many 1's you have to invert as you can invert any number of zeros with a 1. So if number of 1s to invert are even than answer is 2 otherwise answer is 1. However you have to also check one case where number of 1s to invert are zero but there are zeros you have to invert to 1. so in this case the answer depends on whether ther is a 0 that doesn't need to be inverted in which case answer is 2 otherwise answer is -1.
edit: yeah there is one more annoying case when there are no 1s than the answer is -1. I was dumb enough to get wa on this case and got stuck in it for nearly an hour :(
That was my logic, but i missed the part where the numbers of 1s to invert are zero but there are zeros that you have to invert, and i lost a 250 points because of that :(
sad life....cheer up you'll do better next time
Finished this game and I had to say there are so many construction games in this contest
Was an honor lost rating to the last binary contest
Really awesome contest!!!
I'm so unlucky... I did not have time to participate... nooo... BTW good problems. I could be MASTER XD
I think i got lucky because i coded D1 like almost brute-forcably only adding pragmas it is like 60% brute
(if there is a hacking phase i wouldnt think ill be safe from TLEs)
Bro went from DSU to bs in 3 min :)
D is a great problem, I got D1 but unfortunately, I couldn't solve D2 in time.
hi, can you explain mei D1
Let's call i is the original index of a[i] and j is the index that a[i] needs to be be placed in in order to get the array non-decreasing and i<j (if i>j we can swap i and j). If you make 1 operation, it will need x = i xor j. Note that the statement says that we must minimize the k, not the operation, so we can just xor i with every bit 1 of x in binary to get j and the maximum k needed is the highest bit 1 of the x. For duplicating a[i]s, we have an approach that the a[i] from left to right must be placed in b[i] also from left to right, with b is the array when sorted a.
thanks
You're welcome.
E < C. The first guess works. 3000 points for what, yikes.
I had made 3 submissions for the problem D1. Initially 3 of them were accepted. But, after the contest ended, 2 submissions were marked with the verdict "Skipped" and only the last Accepted submission of D1 has the verdict "Accepted". Due to this, my score for D1 got reduced. Any idea why this happens?
From the official Codeforces rules:
Hello, could you please explain why my account was blocked during this contest?
Account:
https://codeforces.me/profile/troyanorte
https://codeforces.me/submissions/troyanorte
How can I submit an appeal and get my account unblocked? I solved all the problems during the contest, but my account was blocked afterward. I would appreciate it if you could review my case and explain the reason for the ban. Thank you.
New to codeforces and solved all the questions in a div 2? Lol
Do you think this can't be real? The main problem is that I did not receive any notifications and I do not understand the reason for the ban. How can I appeal the decision to block my account?
all odds are against you, this is a very clear sign of cheating. if you really want to clear your name i'd suggest taking a screencast of you doing the next contest
what was question D man it was genuinely tough atleast try to sympathise us and give a little easy
Good Round, take me to Specialist again!
Oh no, I didn't realize that resubmission doesn't count toward the first solve. Missing the first solve of F because of this :(
Fixed
Dear codeforces
I want to sincerely apologize for my actions in this contest. I didn't think my cheating would have consequences like this.
I have learned my lesson from this time. I feel I deserve to be punished for this, but in my account i have a lot of course about coding, so i hope i will be forgiven for my actions to continue practice (and skipped all my submission in this contest to roll back my rating).
I promise I won't join any contests after and will only use my account to practice
Against, I apologize for my actions last week, and I knew rating isn't important, it's just a number
Thank you for your understanding, and I look forward to practicing more on Codeforces
Thanks a lot, have a good day!
(Sorry for my bad English)
Well, this afternoon I recieved a message from the system that tell me my submission for D2 was similar to many others submissions, and all of my submissions got skipped. So I was about to write a message to the Codeforces team since I have concrete evidence that can prove I wrote my code (with logs and the idea for the problem was kinds of classic and identical) and the reason my code seems similar to many others is because I used the segment tree template from VNOI Wiki, a published educational community of competitive programming(see this: https://wiki.vnoi.info/algo/data-structures/segment-tree-basic.md). But after a while I realized my submission verdicts changed from skipped to Accepted again, while some of the other's in that message still got skipped. Of course I don't have any problems with this=)))), just being curious what exactly happened? Did they kind of doubled-check or something like that? And do I need to do anything else to prove to the Codeforces team that I wrote the solutions myself?
Hi, my submissions are marked as skipped and my participation shows Out of Contest. I received a similarity warning but i wrote my solutions independently in vscode(i can provide timestamps) and did not share or use anyone else code.
Also, the warning seems to reference my own submission ID as a match, which looks unusual. could you please clarify the reason or this and review the case?
Thank You.
Subject: Appeal for Plagiarism Warning — Problem 2247D1 (Template Coincidence)
Hello contest admins,
I am writing to politely request a manual review of a plagiarism warning I received for problem 2247D1. My submission (383347453) was flagged as significantly coinciding with submission 383369119 by user 12345678raaz.
This similarity is entirely coincidental and might be due to the use of a template. I usually keep a template of the type of pattern questions. I don't know how it coincided with the other person because I don't even know that guy. Also I don't even know if he is from the same country or not.
Could you please manually review the submissions? I am confident you will see that the overlapping sections are strictly boilerplate code.
Thank you for your time, hard work on the platform, and understanding.
Thanks everyone for participating in Codeforces Round 1111(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.
Hiii everyone i am looking for friends that will put me through and you know just chill. I really want to get better so if you feel you could help me with that i'd appreciate it
Upvote me
is it me you're referring to ?
Don't ask. Just upvote me. Thanks. Signed, Sicilian Defense
During the recent Codeforces Round 1111 (Div. 2), I noticed that the code of user DancingInTheLight shows signs of being written by two different people or of using an LLM. Specifically, in problems D1, D2 (383370496, 383373125), he changed the entire algorithm within just 6 minutes, and the subsequent code uses long, uppercase variable names, so I strongly suspect it's AI code. I sincerely hope that the administrators MikeMirzayanov, awoo, KAN, and the contest organizing team makrav will permanently ban this user.