Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 1053 (Div. 1) and Codeforces Round 1053 (Div. 2), which will start on Sep/24/2025 14:35 (Moscow time). You will be given 7 problems and 3 hours to solve them in both divisions.
Note the unusual starting time.
- One of the problems will be divided into two subtasks.
- One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.
The problems were authored and prepared by Dominater069, satyam343 and me.
We would like to thank
- Dominater069 for his 😎 💀 😅 🙃 coordination;
- Alexdat2000 for Russian translation;
- Geothermal and jtnydv25 for VIP testing;
- isaf27, fextivity, maomao90, Adam_GS, A_G, SmolBrain, lethan3, IceKnight1093, cadmiumky, zeemanz, Sana, kshitij_sodani, Sugar_fan, Darren0724, guagua0407, efishel, satyam343, blue, CatsAreCool, chromate00, Non-origination for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution:
- Div. 1: $$$500 + 1000 + 1750 + 2500 + (2000 + 1750) + 3250 + 4250$$$
- Div. 2: $$$500 + 1250 + 1250 + 1750 + 2500 + 3250 + (2750 + 2500)$$$
We hope you'll like the problemset!
UPD: Congratulations to top $$$5$$$ in Div. 1 and Div. 2.
Winners
UPD 2: the editorial is out.
almost all the authors & testers are RED
As a tester, I highly recommend the interesting problems in the round!
It was a horror show :)
Will be fun fs
testers OR!Z
Cant wait for another satyam round orz
Contest of my favourite coders!
Where is __baozii__? Does he want to reach IGM?
Satyam343 round omg
Satisfactory contest time for Chinese participants huge W
As a participant, hope the contest has great problems and may it be cheater free!
Satyam343's round omg!! Already scared.
If your rating_range<=1600 then the 3 hour contests is not for you , it's for those cheaters.
1899
Please note the unusual start time
As not a tester, I highly recommend the interesting problems in the round!
So what is a ":smiling_face_with_sunglasses: :skull: :grinning_face_with_sweat: :upsidedown_face: coordination"?
Where __baozii__ went?
my first div1
Math contest is about to happen
return of the mathforces
why math?
500 to 1250.... damn. and C is also 1250
Why the unusual timing on a weekday?
This round is based on an onsite contest.
Makes sense. Sad I will miss it :(
where is __baozii__.. Hope he will regain HIS Streak soon
orz
That's a hell of a coordination.
Here , Everyone is my favourite coder, especially Dominater069.
Looking Forward to it!
Hope to reach CM :)
Participating in this contest. My target for this contest to solve three problems. Best of luck to all participants.
Hope I can get a good grade
How high the average rating of testers are...
excited
Quite sad because I’ll probably miss this contest since it’s happening earlier than usual.
The time is really really wonderful！Finally no more staying up late!I would also like to thank the experts who set the questions and conducted the tests; your hard work is appreciated.
As not a participant, I will not participate
I love java! console.log("hello world");
Codechef admin coordinated a round on Wed. and clash with the Codechef round by 5 minutes :(
Would've changed to :) if it intersects for more than 1 hour.
True
As a tester of the round based on OII 2025, I must show you this meme.
Sad that I got classes on that time but best of luck to all other participants
Highly praise the friendly starting time!
The time is very kinds for Chinese OIer.I can play the contest but don't have to Staying up late.
Is Div1 rated for everyone or just above master
Like can I register to Div1 today and be rated?
Add time
zur
Div.2 => Div.(1.5)Forces
why my friend's account creative2024 be banned during the contest. He wonders how can he appeal under this situation.
why and how can he solve this problem ?
if you codeforces.com think he occupied the runner resources caused the judging problem, how can you simply regard someone who was stuck in interactive problem as the chief culprit !!! he is really angry and needs a explanation for this situation.
I think your friend is actually Oscaryang?
is creative2024, my friends who participated codeforces the first time.
Jaw dropping Contest!!!
The queue is now over 10 minutes long, what happened?
Why in queue?
One of the servers (called Floyd) just rebooted. It looks like it has some hardware issues :-( This is the first time it has happened.
ok
please tell me it won't unrated for this reason :'(
Excuse me,may I ask if it is going be unrated?
obviously no , they gave us 15min extra time too
It’s been a long time since a Div. 2 B problem made me think this much.O_o
I hope everyone is enjoying.
Well,at least 123 hope didn't enjoy.
Any intuition to Div2E?
Was D that easy? How so many people solved it? How to solve it?
example image helped a lot in guiding my thoughts in correct direction.
i think i got the pattern but wasnt able to implement it properly ... although i need to prove that that pattern is universal and then implement :((
You can prove (by induction on the rows) that the black squares aren't under the left and right diagonals. After that, iterate from the center of the square row $$$i$$$ by row $$$i$$$ and pick which $$$a_i$$$ black squares you want to keep in row $$$i$$$ out of the $$$n - \sum_{j \gt i} a_j$$$ you have remaining.
You also need to check that $$$a_i$$$ add up to $$$n$$$ and that none of the ones after the middle are nonzero. All of this is relatively straightforward to prove.
disaster! can someone please give hints for Div 2 B (the contest is over)?
you can do greedy solution.. the main thing that you have to observe is that looking for next white cells by brute force does not actually give TLE.. cause at some point next cell will be out of range of the existing set. at least i passed the pretest with it.. don't know what will happen in system testing
Beautiful solution. I used some data structure to find next white cell, and it was painful to code.
thanks
It can be done greedily in one pass. The only time a next person is gonna be at different cell than where current person ended while following command 'B'. Since ending at command 'B' makes the cell black, and for the next person, he must be at next white cell when following the B command
Sooooooo Hard B and C TAT. I'm not good at them,but I learned a lot.Thanks for the contest
It felt like hard ,I was stuck at B for so long.
The problems were exciting. Nearly solved 3 this time, couldn't figure out how to optimze O(n²) to O(n)
problems B and C are consisted of pretty simple ideas, but finding out it took to many time for me...
Any hints for B?
brute force will work. hints:incremental path:your answer will always increase.
Gottem, thanks.
whoa!! I didnt find C simple, is there an observation which makes the implementation simple ?
Why were the hacks disabled for Div2B $$$?$$$
Spent a lot of time thinking on E, but couldn't formulate anything. Can someone explain?
If for some $$$i \lt j$$$, Alice doesn't take $$$a_i$$$, and takes $$$a_j$$$, then Bob must prefer $$$a_i$$$ to $$$a_j$$$. Otherwise $$$a_j$$$ is also taken by Bob.
Honestly I have no idea how my E12 passes, how to calculate random shuffles fail probability?
How shuffling work? So if a problem is hack-free then likely it is probability-based? Only saw one other problem like this before. And isn’t the proper way of solving recursively dividing the array into 2 and ask to see the single value appear in which part? Although that gives the wrong guess for version 2.
Usually when the problem has fixed number of tests, you might consider writing some randomized algorithm. Probably there are another cases where problem needs fixed number of tests while not using randomized algorithms, I don't know them tho.
You can use shuffled indexes for queries while dividing the array into 2. This should reduce number of queries, but i am not sure how much it reduces.
Also your code finds correct guess for version 2, but just uses too many queries i guess
Thanks! I will have to see the editorial. The reason for the wrong guess was because wrong implementation during optimization. Overall it was still too many queries.
Div1 E1 is kind of problem that makes people submit the worst ideas they've got. My local stress started passing on 3:14 and it was not enough to fix minor stuff and submit :cry:. Not sure what was the purpose and intended approach of the problem, need editorial.
Div1 BC are sweet, F is interesting (like I dont even understand how one can solve bamboo in 2 rounds). I definitely had some troubles with the way some problems were formulated — maybe this is even good against LLM's understanding problems but unfortunately it's also against me understanding problems.
hints for C? didnt have to time to find C since spent so much time for B
You want to delay people from leaving for as long as you can; how can you do this?
Only make people leave when you're absolutely forced to.
(((...()()()...))), $$$k-1$$$ people at the start, then alternating leaves and stays.Note that the proof is pretty nontrivial compared to the actual observation (which, at least I, just guessed), however it's not that bad. You can prove that this works with either an exchange argument, or with two constraining inequalities after forcing both conditions.
I got the observation in first go but somehow couldn't code it. Can u give me some hints on how to go about implementing it?
You need to be able to:
You can easily do 1 and 2 with a regular prefix sum. For 3, you'll need to calculate two prefix sums (or notice that $$$\text{psum}_1 = -\text{psum}_2$$$ and just negate), one for $$$[a[0], -a[1], a[2], -a[3], ...]$$$ and one for $$$[-a[0], a[1], -a[2], a[3], ...]$$$. Once you have these, you can just use them to calculate the middle part.
I still don't understand it.
Can your share your code and tell what happened in each step and how you think of this solution.
Compute an array of segments seg[i] = a[i+1] — a[i], then build two prefix sum arrays: pre_odd for odd-indexed segments and pre_even for even-indexed segments. For k=1, take the sum of all odd segments. For k>1, exclude the first and last k-1 segments of the relevant parity (odd if k is odd, even if k is even) and use the prefix sums to quickly calculate the sum of the middle segments. Keep counters of how many odd/even contributions have been used so far, and iterate this process for all k.
for n=6, the signs will go like this. find a way to add this pattern
k=1 [ -ve +ve -ve +ve -ve +ve ]
k=2 [ -ve -ve +ve -ve +ve +ve ]
k=3 [ -ve -ve -ve +ve +ve +ve ]
Thank you everyone (◕‿◕✿)
UPD: I finally got AC. My submission
my proof for c: any two consecutive segments would differ by 1 in contribution, as the point between them would be used as entrance or exit to already entered visitor. to prove why the said construction works, we can see that parity of contribution of an segment remains same so 4 contribution segment couldn't do 5 contribution(). now we greedily chose maintaining contribution<=k.
today, maybe I'm spcialist
div2 a is fun, but what's the meaning of div2 b and c, and c is so typical!
I have a max flow solution for Div2E is it supposed to pass
Maybe you need simulating cost flow.
It was intresting lol
I worked out CTS2024D1T3 so I know the solution of 1F but I forgot there is T in 1E so I have no time to finish 1F
This was my hardest contest so far, maybe I’m too used to quick A/B solves :)
Why Foredawn is not banned even he is unrated and solved 7 problems
Hey is it rated
Anyone give me some hint how to approach the problem B div2 i was unable to do that...
so you can simulate the whole process in O(n*n) .. but the observation which I made was if you process
i+1character, only thing which matter is what you did withi-thcharacter ... so you don't need to start from the beginning again ..try to work with this hint ...
bro i also in confuse that how do i know the next Black cell
so store all black cells in a set ( in cpp ) and if you just increment the position and check if that position is black .. this will not time out.. because in one operation you can only make once cell black. so you will not check more than
2*10^5cells in worst case.That's neat, how did you come up with this intuition?
I think it is just practice but also constraints tell me that it can't be
O(N*N)so I tried to think of something faster.but the fact that you only paint 'ONE' cell in your last step helps .... because when you start next time all that portion before the cell colored last time will be same.
Any editorial for E div2?
Define $$$p_a(i)$$$ and $$$p_b(i)$$$ to be the positions of element $$$i$$$ in the preference arrays of Alice and Bob respectively.
Let's say that the set of elements Alice takes is $$$i_1, i_2, \dots i_m$$$ where $$$p_a(i_j) \lt p_a(i_{j +1})$$$ ($$$j \lt m$$$).
How exactly can we get Alice to take exactly this set of elements?
.
.
Notice that when taking $$$a[p_a(i_j)]$$$, it must obviously not already have been taken by Bob.
We therefore derive a necessary and sufficient condition for a subset of elements $$$S =[i_1, i_2, \dots i_m]$$$ to be attainable by Alice:
This motivates the following naive dp formulation:
Define $$$\text{dp}(i, x)$$$ to be the maximum score of some Alice-attainable set $$$S$$$ from the prefix $$$a[1, i]$$$ wherein $$$\max_{k \leq i, k \notin S}(p_b(a[k])) = x$$$. The transitions take the following outline:
This runs in $$$O(n^2$$$) and it's trivial to optimize the transitions to $$$O(n \log(n))$$$ using segment trees.
Thanks a lot ❤️
There is a n^2 dp solution where dp[i][j] — maximum value of first i items Alice has taken when Bob has taken j of his first items.
Let p[i] — position of element i in Bobs list
The transitions from i to i+1 when someone takes item a[i].
For each j:
if Bob has already taken this item dp[i+1][j] = dp[i][j]
if Bob hasn't taken this item dp[i+1][j] = dp[i][j] + v[a[i]] (Alice takes the item)
Bob can take the item if not taken yet dp[i+1][p[a]] = $$$\max_{0 \leq k \leq p[a[i]]}$$$ dp[i][k]
This solution is n^2 but it can be optimized by saving this dp in a lazy segment tree.
This is my solution, don't know if intended
Oh now i understand better
thanks ❤️
It was a horror show...!
Amazing problems , enjoyed Div 2 B...
I got a solution of D1E with expected $$$3.5n+2\log_2 n$$$ on average, and failed both E1 and E2.
Then I improved the solution to $$$2.75n+2\log_2 n$$$, passing E1 and E2 at the same time, despite that $$$35$$$ of $$$10^6$$$ local tests failed. (which seems to be too bad, as E1 has around $$$3.2\times10^5$$$ testcases.)
No idea of why did it get accepted, and why are the boundaries $$$4n+2\lceil \log n \rceil$$$ and $$$925$$$.
Your solution seems actually slightly better than what you stated (see the editorial). It's intended for E2 but not for E1. Maybe it passes on E1 as well because TLE submissions on Codeforces are rejudged.
For E1, your asymptotics don't matter on small tests. If you're not guaranteed to fit in the small query limit for small $$$n$$$, you're out of luck.
Well, it turns out that I was too sleepy last night and I made a typo in the local tests. I set the bound to $$$4n+\lceil\log n\rceil$$$ instead and that caused a slight chance of failure. Now it failed $$$1$$$ case among $$$10^7$$$.
My bad, thanks anyways.
same problem
The round I reach GM.
Felicitations, good job.
Thank you!
Lost the opportunity to jump over IM in somewhat amusing way...
What do you guys think of problem B and C's rating?
I learnt that I need to practice more greedy/implementation/construction problems in a similar range :(
it was hard for me because i'm newbie
Appeal for Flag on My Submission 340186188 for Problem 2151E
Hello Codeforces team, I would like to appeal the flag on my submission 340186188 for problem 2151E in this contest.
I would like to assure you that I wrote my code independently and did not share it with anyone or view anyone else's solution during the contest. The similarity in the solutions is only coincidence due to the nature of the problem itself.
My Logic for Problem E I solved using a dynamic programming approach, but to make it more efficient I also optimised my data structure. As you may know, this is a standard technique in competition programming. The logical steps to think of this solution are quite constrained, which could lead to similar code from my peers. Here are my steps: 1. My primary thought is to process Alice's preferred items one by one. It is natural to maintain dp[j] to represent the maximum value of Alice's items after Bob has picked his j most preferred items.
A naive O(n^2) dp solution would be too slow. As I notice that we must update range and point between states, I decide that a Segment Tree is the fastest data structure to optimise the program to O(nlogn). My code uses a segment tree and lazy propegation to handle the range additions faster.
When I am processing Alice's i-th preference A[i], I let its position in Bob's list be p. The logic inside the loop is divided into cases:
My segment tree code is a standard template I used for many problems. Data structures have common structure, using function names like build, push, add, and query. Variables like mx for maximum and lz for lazy are also common. Maybe this is one more reason why my solution looks similar to my peers.
In conclusion, as this specific dynamic programming method is the most efficient way I could think to solve the problem, it is maybe also that other contestants who are familiar with these methods would think of the same logic and similar implementation.
Proof of Innocence
I wrote my code within my local Visual Studio Code environment and did not use any public IDEs like ideone.com. I am not sure how to find the cache/logs or file histories, but if you would inform me on what details you would like to verify, I can try providing. To avoid this in the future, I will use a local Git repository.
Thank you for your time. I am just a mathematics and computer science university student trying out the Codeforces platform. I have read the rules and understand them very seriously. I hope this explanation clarifies my solution and shows that it is my own independent work.
Sincerely, ComplexBulb
Appeal for Plagiarism Flag on My Submission 340173657 for Problem 2151D
Hello codeforces team, I am writing again to appeal second flag I received from same contest. This appeal is for my submission 340173657 for problem 2151D. Once again, I want to say that my submission is my own work. I did not teamwork with anyone, nor did I find external solutions during the contest. The similarity I guess comes from the mathematical and algorithmic type of the problem.
Explanation of My Logic
This problem is a combinatorics and counting problem.
The problem's constraints on black cells can be reduced to a known problem of counting permutations with restricted positions (such as placing n rooks on an nxn board without attacking each other). My solution uses a formula derived from this.
The number of valid grids can be calculated with the following steps, which my code implements directly:
As the solution is a direct implementation of a mathematical formula, most people who correctly solves the problem will produce code that is similar with me in logic.
Same as my previous appeal, I wrote this code in my Visual Studio Code local development environment. I am fully prepared to explain my thought process and the derivation of the formula in more detail to prove that my understanding is my own.
Sincerely, ComplexBulb