Hello, Codeforces!
We are glad to invite you to participate in Codeforces Round 1116 (Div. 1) and Codeforces Round 1116 (Div. 2) on Aug/09/2026 17:35 (Moscow time).
The round will be rated for participants from both divisions. You will be given 6 problems and 2 hours and 30 minutes to solve them. At least one of the problems will be divided into subtasks.
Please note that this contest contains at least one run-twice (communication) problem. Please read the guides for run-twice problems before the contest if you are unfamiliar with them.
All problems were authored and prepared by Error_Yuan and me, paulzrm.
More than eight years after Codeforces Round 449, Chtholly Nota Seniorious — the happiest girl in the world — is returning to Codeforces!
In this round, you will once again meet Chtholly, Nephren, Ithea, Willem, and other characters from What Do You Do at the End of the World? Are You Busy? Will You Save Us?, and help them overcome a new series of challenges.
We would like to thank:
Error_Yuan for his excellent coordination, patient guidance, and invaluable help throughout the preparation of the round.
Alexdat2000 for translating the statements to Russian.
HugeWide, my teammate, for VIP testing and for all his help throughout the preparation of the round.
HHH666666, XG0000, Mitsukasa_Ayase, zt17, a_little_cute, aaa_Pigeon2, StarSilk, tiger2005, Proof_by_QED, _istil, nifeshe, floptron1, arvindr9 and WorldWarV for testing the round and providing valuable feedback.
KAN and MikeMirzayanov for the great Codeforces and Polygon platforms.
You
for participating in this round.
The scoring distribution will be announced later.
We hope you enjoy the problems and Chtholly’s story.
Good luck and have fun!
UPD1: The Scoring distribution is:
- Div. 1: 500 — 1000 — 1750 — 1750 — (1750 + 1250) — 3500
- Div. 2: 500 — 1000 — 1500 — 2000 — 2750 — 3000
UPD2: The editorial is out.
UPD3: Congratulations to the winners!
Div. 1 (subject to change):
Div. 2 (subject to change):
We would also like to congratulate the first solvers of each problem (subject to change):
- Div. 2 A: Forestmy17 00:01
- Div. 2 B: asterunee 00:04
- Div. 1 A / Div. 2 C: A_G 00:02
- Div. 1 B / Div. 2 D: maspy 00:05
- Div. 1 C / Div. 2 E: literalchild 00:19
- Div. 1 D / Div. 2 F: de1uxegg 00:23
- Div. 1 E1: __baozii__ 01:02
- Div. 1 E2: ABCaCaCa_ 01:10
- Div. 1 F: turmax 01:34
I hope this round doesnt become semi-rated
basta gona hoye.
As a participant, I hope to see high-quality problems
As a participant... Hope that Run-Twice problems will be in Div. 2 C-D.
As a tester, your rating delta after this contest will be a dirac delta.
Will I gain infinite rating for solving 0 problems?
No matter how many problems you solve, you will always gain infinite rating if you try your very best.
return of chtholly (tree?)
Secretly hoping for div1E to be AVXable again
What are you referring to with "again"?
896E welcome home chtholly
elite ball knowledge
As a tester I think the problems are interesting!
I see a *certain renowned problem setter who happens to be a red tester for this round. Looking forward to positive delta for us all on this round
orz Error_Yuan
Let me hit 1500 elo please <3
Nice communication problem
You mean: "Nice! Communication problem."?
Yet Another Chtholly Round!
Wow!!! Yet another Chtholly Round!
why aaa_Pigeon2?
As a tester,the problems are interesting.Good luck and have fun!
Finally an anime round!
yeaaaaaaaa she has returned
wow! another contest in such a short period of time!!!!
Chtholly round once again after 8 years, but no more ODT problems :(
8 years?
orz XG0000
orz XG0000
orz XG0000
Why
THE HAPPIEST GIRL IN THE WORLD!!
As a tester, I'm told by paulzrm that G is *800, and I have no comment about that.
upd: 1E
Note that there's no problem indexed G in both divisions.
As a tester there is.
I hope that I don't become the opposite of Chtholly ( The Saddest Man On Earth ) after the results of the contest
As a participant, I hope to see Chtholly.
Yea, I'm ready to pay (lose) my rating for this
+1
Oh I still remember another round from ODT many years ago. I found ODT so useful solving at that round.
this contest could be fire
WOW! a chtholly round again
Will the score distribution shown to us?
I hope I can solve div.1's A through C
chtholly is back ！
You really want me to read sukasuka huh....
CHALLENGE ACCEPTED
You can also watch the anime adaptation—it’s really good too XD
I watched it when it aired, but maybe it's time for a rewatch as well.
Why no cyan- testers
Wait is there a reason why d1C and d1D are both 1750? Is that supposed to mean they are supposed to be similar in difficulty
love your ngnl problem sir, hope this round is enjoyable!
Welcome home,Chtholly!
Chtholly is finally back after 8 years, and somehow I already feel like my rating is about to leave this world before she does
Welcome home,Chtholly.
I'm ready to solve 0 problem and 12 episodes in 150 mins
Why div2 is only up to 1900? Normally div2s are up to 2100.
If div1 and div2 is at the same time,div2 will up to 1900,otherwise they will up tp 2100.
“What Do You Do at the End of the World? Are You Busy? Will You Save Us?”
So Codeforces will be notorious (doge)
Just in case you didn’t know:
https://www.luogu.com.cn/discuss/61884
洛谷将会臭名昭著！————Unknown_Error
In my friend list, there is a orz guy among them. Guess who lol
greateric of course
(btw I hope I don't lose expert :sob:)
Bro how tf does D have almost the same number of solves as C. I literally stared at it for an hour and a half and got nothing
orz milky0002, KowoToma, scau_accepted, Khai2007, CryptoQuant, fIower, phantomas, asgardiann, :D
Chtholly is very cute,problems are interesting,but I am a fool.
I just had a generational run
Problem E was basically guessforces though i just assumed that
a suitable swap always exists after I realized that gcd = 1 means that we can compute the center of mass which behaves like a cell in every transformation
I wonder how it can be proved
Salam! how you solved D?
Turn the string into runs of 0s and 1s, so for example, 01101110100 becomes 1213112.
Then we have that:
number of ones and zeroes stays constant (obvious)
endpoints stay the same (because endpoints of substring stay the same in inversion since S[l] == S[r])
the number of runs stays exactly the same in every operation:
Suppose we inverted a substring [l,r] such that l lies in run ll and r lies in run rr. Then an inversion in the substring inverts the order of every completed run inside (ll,rr), which means the number of runs inside stays the same. Since S[l] == S[r], replacing the right side of run ll with the left side of run rr does not create any new runs. Thus the number of runs stays the same. So all reachable strings is at most all strings with the same number of 0s and 1s as the original string as well as the same number of runs and endpoints.
We can reach any such string by only picking substrings to invert that are 2 runs apart. In such an inversion, there is only 1 run inside (ll, rr) so it remains the same, the only difference is that the size of the runs ll and rr change, in fact, we can freely redistribute the size of ll and rr. This means that we can redistribute any 0 or 1 from any run to any other run, which reaches all strings above. The minimum size of a run is 1, so this is equivalent to counting the number of ways to put n objects into k boxes such that each box has at least 1 object, which is well known to be (n-1 choose k-1)
Thannnk Youuuu!!! I am a foollllllll
Suppose we need an adjustment of $$$(dr,dc)$$$ but there is no available pair. Then the grid can be partitioned into cycles formed by $$$(r+k*dr, c+k*dc)$$$, $$$k\in \mathbb{Z}$$$ for any $$$r,c$$$, where each cycle has the same size $$$s$$$, and each cycle is either all-white or all-black. This means $$$s$$$ divides $$$w$$$ and $$$n^2$$$, and since $$$\text{gcd}(w,n)=1$$$, we must have $$$s=1$$$, meaning that $$$dr$$$ and $$$dc$$$ are $$$0$$$ mod $$$n$$$; in this case we can choose not to alter the grid (i.e. swap $$$(1,1)$$$ with itself).
"Output your answer modulo 998244353" in D2B and "The game then lasts for k rounds" in D2C were super useful in solving the problems :-)
The time limits are sooooo tight (totally not tle63 crashout)
So many cheaters.
There are 5 Master in Top 7.
How to solve D2D?
Its a stars and bars problem among the 0s and 1s in the substrings of 0s and 1s.
you can see that you just need swap every adjacent digit to generate all string
So the problem is just: "If you add a head 0 and a tail 0, and you consider for each 2 adjacent zero is a child, so how many candies you can give to all (cnt0 + 1) children, which each candy is 1"
Does anyone have a simple idea for solving Problem B div 2 ? It seems really hard to me
The string is essentially fixed, it has to be a block of 2 0's or 2 1's alternating. EG: 00110011...
Therefore, once you fix the first two numbers, the rest of the string is forced. So you only have 4 possible starts to try. 00, 01, 10, 11.
Check if the start can create a valid construction, then +1 to your answer if it is.
Thank you so much! This was actually my first intuition too, but when I saw so many people solving it very quickly, I thought there must be some clever parity observation rather than just trying all the possible cases. Really appreciate the explanation!
for dominoes to have diff weights, the condition is $$$s_i + s_{i+1} \ne s_{i+1} + s_{i+2}$$$
so the condition for a row to be valid is $$$s_i \ne s_{i+2}$$$ ($$$1 \le i \lt n-1$$$)
There are only a few ways to get a valid row
READ THE HINT b4 reading this
$$$s_i \ne s_{i+2}$$$ and each char of string is either 1 or 0. So, if $$$s_i$$$ is 1 then $$$s_{i+2}$$$ is 0, $$$s_{i+4}$$$ is 1, and so on...
in other words, if we choose $$$s_2$$$ then $$$s_{4}$$$, $$$s_{6}$$$, $$$s_{8}$$$, ... are automatically assigned
similarly, if we choose $$$s_{1}$$$ then $$$s_{3}$$$, $$$s_{5}$$$, $$$s_{7}$$$, ... are automatically assigned
so, we have the option to choose for $$$s_1$$$ and $$$s_{2}$$$ only
number of ways = $$$2*2=4$$$
we can generate all 4 possiblities and check if we get to there from the given string
for example, for n=4 the possible strings are 0011, 0110, 1001 and 1100
for n=5 the possible strings are 00110, 01100, 10011 and 11001
Thank you! I really like this approach and the idea behind it.
Since this number may be large, output it moduloI guess the presence/absence of this phrase is a subtle tell (it's in Div2D and not Div2B)? Probably it should be avoided if this isn't desired.Yea its a red herring
What I mean is that since D2B omits "Since this number may be large", an observant person could notice the different phrasing and it gives away the trick. I'm suggesting that as a convention, "Since this number may be large" should be avoided, since its absence can be a hint. Similar idea to how 998244353 is often used in non-FFT problems.
Oh yeah, you're right, I didn't even read that sentence properly
Question on problem D:
After some experimentation on paper I realized you can shift move excess zeroes and ones to other blocks of zeroes and ones (respectively) as long as there is at least one zero in each block of zeroes and at least one one in each block of ones. So for example the string 0011010 has blocks of zeroes: [2,1,1] and blocks of ones [2,1]. This means you're able to transform the blocks of zeroes to [1,2,1] or [1,1,2] but not something like [0,1,3].
So at the end this effectively is a stars-and-bars problem, although is there a fast way to compute nCr with high n? I was considering log(n!) = log(1) + log(2) + ... + log(n) although I'm not really sure how you take a mod of exp^(log(n!) — log(r!) — log((n-r)!)) without overflow.
For large nCr precalculate factorials and inverse factorials upfront in $$$O(n)$$$. Then use the regular formula.
How do you compute n!/(r!(n-r)!) (do the division part) under mod?
Since division under mod isn't safe, you multiply by the modular inverse (which is the mod version of division). That's why you need inverse factorials.
Learn fermat's little theorem bro
Through Fermat's little theorem,a^(-1)≡a^(p-2)(mod p),so n!/(r!(n-r)!)=n!(r!)^(-1)((n-r)!)^(-1)
div1D is a very good hard problem disguised as an easy problem
As a participant, div1 C is absorutely need to be swaped with div1 D, It hard for me to construct a strategy
?
omega ultra super duper orz KowoToma only one to AK div1 :0
I love Chtholly!!!
subject to change indeed lol
that div 2B guy is in trouble
I got D2E's solution immediately, however I didn't realize the sample was wrong before the last 5 minutes ToT
that 's bad
Thanks everyone for participating in Codeforces Round 1116 (Div. 1, 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)
Gap between Div 1 D and Div 1 E is too long.
yeah
I want to report khoand25112007
There is different style code between B and D
oh there will a problem solved by chtholly tree?
What a well-designed problem! It covers a broad range of concepts, is grounded in a realistic context, and leads to a fairly natural solution. Kudos to the problem setter! More importantly, the data are essentially accurate, which is a fundamental hallmark of a good problem.
Absolutely brilliant div2E!!! Has similar COM based problem appeared in past?
It was a really interesting round specially Div 2 Gracefully thanks to prepare those problems to paulzrm and Error_Yuan
1B/2D and 1C/2E were great problems
这个时间对中国不友好
Dear codeforces team , my solutions are skipped as according to the system check the b question coincides with Neev_266.i don't know who this guys is , it's a pretty standard problem I used define int long long , he used define ll long long.i have used variable like even odd , he has used a and b, I have used bool possible he has used bool ok , I write return 0 while he has not written it.it was a standard question where only 4 strings were possible at max , moreover indentations are same as I use prettier extension on vs code . I hope you guys look into this matter as this code was solely written by me . Please review this warning and remove it from my account
I participated in the Div. 2 contest and my submission for 2256B is 386353383. I noticed that submission 386364747 is extremely similar to mine in both structure and implementation. I wrote my solution independently, without using or publishing any external source, and it was submitted earlier. Could the two submissions and their timestamps please be manually reviewed?
I would like to provide a clarification regarding the similarity detected for my submission [386377988] for problem 2256C.
First, I want to clearly state that I did not copy, share, or obtain the solution from any of the users mentioned in the warning, nor did I communicate with them regarding the solution during the contest.
The actual source code of my submission is not the same as the submissions mentioned in the warning. The similarity appears to be in the underlying algorithmic logic. For this particular problem, the solution is relatively simple, and once the key observation is made, the most direct approach naturally leads to the same or very similar algorithmic idea. Therefore, it is possible for multiple participants to independently arrive at the same logic without seeing each other's code.
I independently understood the problem, derived the approach, and implemented the solution myself. I did not use any publicly accessible submission, shared code, Ideone link, GitHub repository, or any other source containing a contest solution. There was also no intentional or unintentional communication with the mentioned participants that could have resulted in solution leakage.
I understand that Codeforces considers both intentional and unintentional leakage seriously, and I respect those rules. However, in this case, I believe the detected coincidence is based on the fact that the problem has a straightforward and natural solution rather than on copied code or communication between participants.
I kindly request that my submission be reviewed by comparing the actual implementations and considering whether there is evidence of code sharing or leakage, rather than relying only on the similarity of the high-level algorithmic approach.
I am willing to provide any additional explanation or information necessary regarding how I arrived at and implemented the solution.
Thank you for taking the time to review my clarification.
Thank You
I want to clarify regarding submission 386368793 for problem 2256B.
I solved this problem independently and have never shared my code with anyone, publicly or privately, before or during the contest.
I believe the similarity comes from the nature of the problem itself: once you realize the string must match one of two fixed alternating patterns for even-indexed and odd-indexed positions separately, the resulting logic is very constrained. You end up checking each character against i/2's parity to determine which of two fixed patterns it should match, tracking four boolean flags (pattern match for even positions x 2, pattern match for odd positions x 2), and multiplying the valid pattern counts. This is close to the only natural way to implement that idea, which likely explains why two independent solutions look structurally similar even with different variable names.
I'm glad to walk through my reasoning/thought process for this problem if that helps establish it was solved independently, or provide any other information needed.
My submission 386389459 for 2256C was flagged as coinciding with submission 386387229. I want to clarify that I independently solved and implemented the problem and did not copy this submission or communicate with the author during the contest. I understand why the solutions look highly similar: the implementation naturally consists of copying the circular string, iterating through adjacent positions, changing 10 to 01, and then counting the 1s at even/odd positions. My variable names and formatting are different, but the core implementation ended up being very similar independently. I would appreciate a manual review of the submissions, what to do right now not understanding
Thanks for the great contest! Problems A and B had very nice ideas. I managed to solve A during the round and upsolved B right after
Hello Codeforces team,
I am writing regarding the warning about my submission 386389925 for problem 2256E, which was reported as having significant similarities with submission 386364395 by user mxiao37.
I would like to clarify that I did not view, copy, or intentionally reproduce mxiao37's submission. I also did not communicate with this user or obtain their code in any way during the contest. I wrote my submission independently.
After comparing the two solutions, I can understand why the similarity detector may have flagged them. Both solutions use the same mathematical idea: counting the number of
#cells, calculating the sums of their row and column coordinates modulon, and using a modular inverse to find the required position/translation. Because of this, some parts of the implementation are naturally very similar.For example, my solution contains:
and I calculate the modular inverse of
wmodulon. In the first part, I use:while the other submission uses the algebraically equivalent form:
These are equivalent because
inv * w ≡ 1 (mod n). So if two people derive the same mathematical solution, it is quite natural for the resulting formulas and implementation to look similar.For the second part, both solutions also find the modular inverse using a simple brute-force loop and then multiply it by the row and column sums. This is a fairly direct way to implement the modular arithmetic required by the solution, so I think this may also contribute to the detected similarity.
However, I want to emphasize that this similarity was not caused by me accessing or copying the other participant's submission. I was not aware of their code when I submitted my solution, and I developed my solution independently.
I understand and respect Codeforces' anti-cheating rules, including the fact that code leakage or other forms of unintentional similarity can still be considered a violation. However, in this case, I believe the similarity was coincidental rather than the result of intentional plagiarism. I would therefore respectfully ask the contest administration to investigate the circumstances and the origin of the similarity before treating it as intentional copying.
If necessary, I am willing to explain my solution step by step, provide any evidence of my development process that I may have, or answer any questions about how I arrived at the implementation.
Thank you for taking the time to review my case.
I would like to provide a clarification regarding the similarity warning for my submission 386395367 for problem 2256E - Even If the World Turns, which was flagged as coinciding with submissions from LingLuo_Official, Lele_P4nggang51, iliya_mon, and snk_25
I want to clearly state that I wrote this solution independently. I did not copy, view, or obtain code from any of the mentioned users, nor did I communicate with them regarding the solution during or before the contest. I have also never published my code publicly before or during the round.
I believe the similarity comes from the fact that this problem has a very narrow solution space once the key observation is made:
gcd(n, w) = 1is a strong hint that the intended solution requires computing the modular inverse of w with respect to n, in order to recover the centroid position from the sum of coordinatesBecause of this, it is expected that multiple independent participants arrive at structurally similar code, even though variable names, macros, and specific implementation details (e.g. computing the modular inverse via extended GCD vs. brute-force loop) differ
Subject: Detailed Appeal regarding Similarity Warning — Submission 386386380 — Problem D (2256D) Dear MikeMirzayanov and the Codeforces Coordination Team, I am writing to formally appeal the similarity warning I received for my submission 386386380 in Problem D (A Ribbon for Tomorrow) during Codeforces Round 1116 (Div. 2). I understand that Codeforces maintains strict standards to ensure fair play, and I fully respect the anti-cheating policies. However, I firmly assert that this solution was written entirely by me, independently, during the contest duration. I have not shared my code with anyone, nor have I accessed any external solutions or communicated with other participants. To assist you in verifying my claim, I would like to explain my specific approach and logic for this problem: 1.Mathematical Derivation: My solution is based on the observation that the operation allows us to rearrange the blocks of consecutive identical characters. Specifically, I deduced that the number of reachable states depends on the number of runs (consecutive segments) of '0's and '1's. Let Z0 and Z1 be the total count of '0's and '1's. Let R0 and R1 be the number of runs of '0's and '1's. My formula calculates the answer as the product of two combinations: C (Z0 — 1, R0 — 1) * C (Z1 — 1, R1 — 1). This logic comes from the "Stars and Bars" method (or balls and bins), distributing the total count of characters into the specific number of runs required to maintain the alternating structure. 2.Code Implementation Details: If you look at my code, you will see a standard competitive programming template that I have used for a long time: I precompute factorials (fact []) and inverse factorials (inv_fact []) up to MAXN using Fermat's Little Theorem for modular inverse (power function with MOD-2). I have a helper function C (n, k) to calculate combinations modulo 998244353. In the main loop, I iterate through the string to count the total zeros/ones and the number of transitions (runs). The final output handles edge cases where R0 or R1 might be 0 (though logically impossible if counts are > 0, it's a safety check). The similarity detected might be due to the fact that this problem reduces to a standard combinatorial formula once the pattern is recognized. Many participants likely derived the same mathematical conclusion, leading to structurally similar code (precomputing factorials and calling a combination function). However, the variable naming (Z0, Z1, R0, R1), the specific structure of my precomputation loop, and the logic flow are unique to my coding style. I am confident that a manual review will show that my code was not copied from any specific source but derived from first principles during the contest. I kindly request you to review my submission and remove the similarity warning. I am happy to provide further explanation or solve a similar problem in a supervised setting if necessary to prove my skills. Thank you for your time and for maintaining the integrity of Codeforces. Sincerely, zhudaxia.
I want to clear up the warning about 386397026（F） and 386361260(D) being flagged for plagiarism. After this competition ended, I received warnings that my solutions for problems D and F were suspected of plagiarism. However, I’m very confident that I didn’t copy anything and didn’t receive any hints from anyone else. The system probably flagged my code as similar just because the correct solutions are very short, which increases the likelihood of similarities, and this time my ranking was also very high. This competition’s rating is very important to me, so I hope you can take care of this! If needed, I can provide my thought process during the contest to prove that I didn’t cheat: For problem D, we can notice that swapping doesn’t change the number of consecutive 0-1 segments, and any approach can reach the solution, so we just need to precompute factorials, and the answer is simply the product of two combinations. For problem F, I used a non-standard approach, basically doing a binary search on the answer and dynamically maintaining operations with a priority queue. The idea is that after no more than 30 operations, the sequence values become very small, and selecting x[j] in the i-th operation is equivalent to subtracting 2^i from it. Obviously, both my D and F solutions ended up being very concise, which eventually triggered the plagiarism warnings.
did they do an individual review or just skip the submissions?
Hello everyone,
My submissions for Codeforces Round 1116 (Div. 1, Contest 2255) were skipped with the message: "Your submissions in contest 2255 — Codeforces Round 1116 (Div. 1) were skipped because of a rules violation."
I solved the problems independently during the contest, without sharing code or using external help. Since no specific reason or flagged problem was mentioned, has anyone else experienced an unexplained skip in this round?
If any of the coordinators or authors could clarify which submission triggered the system flag or which rule was allegedly broken, I would greatly appreciate it. I am ready to explain my logic and implementation details if needed.
Thank you.
I am writing to state on record that my solution for Problem 2256B was written independently on my local machine using Sublime Text and pasted directly into the Codeforces submission form. I did not publish, share or leak my solution on any public platform or online compiler.
15
ww