Hello Codeforces!
We are glad to invite you to Codeforces Round 1039 (Div. 2), which will take place on 27.07.2025 17:35 (Московское время).
The problems were created by I_love_Michel_Sardou, Richem, bestial-42-centroids, Yuuuuuuuuuuuuuuuuu and me.
We would like to thank:
Akulyat for coordinating our round and helping with the preparation of the problems.
antontrygubO_o, Adam_GS, JeanBombeur, Error_Yuan, Everule, prvocislo, KiKoS, Friedrich, mrthimote, Jasonwei08, arknave, mcfr, madlogic, kinnikuma, raphaelp, tibinyte2006, dssfsuper2, dazlersan1 and Thyl for testing.
MikeMirzayanov for the Codeforces and Polygon platforms.
You will have 2 hours to solve 6 problems.
Good luck!
UPD: The score distribution is 500 — 1000 — 1250 — 1750 — (1750+1750) — 4000.
UPD2: The editorial is out!
UPD3: Congratulations to the winners!
Div.1
Div.2
as a tester and fan of bestial-42-centroids, i encourage everyone to participate!
I also hope to Conquer Tourist (Jasonwei08 will get the joke)
as a fan of Jasonwei08 I am honored that he is a fan of me !
:blobhug: :blobhug:
undirected edge be like
As a Jasonwei08 hater, I will get downvoted.
wow what did i do :sob:
also to prove you wrong i upvoted
as a participant and "also" fan of Jasonwei08 I'm sure that everyone will do well in this contest
It feels illegal to be this early
Might be my favorite Div2 this year! Recommend everyone to participate!
Does that mean we need to brace ourselves for an ad hoc-heavy round?
No komments.
Gret grammer
why do u guys down vote low rated users like me :(
upvoted
was a very good round indeed
In fact very W div 2. E1 speedforce carries me.
As not a tester, I think I'm gonna enjoy this round!
ok so I got big negative delta last div2 round, hoping to get good news after this round.
and I hope problem statements are short and sweet like this announcement
short and to the point announcement 💚
Having a LGM tester is how you know the contest is going to be good
As a tester, I think you might want to check out this round!
"Yuuuuuuuuuuuuuuuuu and me"
Pun intended?
Score distribution??
I updated the announcement, sorry for the wait.
Hoping to get one step closer to Expert or even reach it!
Note that this Codeforces round is 100% french (even the coordinator now lives in France :D). We tried to write problems that represent our vision of what problemsolving should feel like. We hope that you will enjoy them :))
As a tester, I tested this round in France
what is the eiffel tower made of?
Better answer fast bestial-42-centroids or you will never write a contest that doesn't include cry
Bread ofc, duh
I haven't done much for the round but I still hope everyone will enjoy it :)
Let's hope this first contest on the first day in college is rewarding and hope to get a specialist soon!!!
oh wow... good wishes for your college.. salute to your dedication for taking part on first day of college.
Hope the train doesn't get late to drop me:)
I hope the problem statement will be as short as the announcement :)
As a participant, orz -firefly-!
hope not to see newbies or pupils winning this contest
looking forward to great problems and my brilliant solutions.(I am scared of falling back to specialist.)
I hope that problem statements will be short, simple and sweet like the announcement.
Is the French team ioi-25 the creator of this round?
Some of them are testers.
So the writers are ex-participants?
Mainly. We were all part of the Olympic preparation anyway.
WTF? Why G is 4000 pts!
WTF
How can U have the same name?
Billl(LLL)y & BiIII(iii)y
A fun fact is that in some websites because my current username (lucky_clover) has been used, so I use Iucky_clover, lucky_cIover or Iucky_cIover instead.
this is really interesting, How do you remember which site uses L vs I(i) ... huh ??
the I(i) is 1 pixel shorter then L
I do not remember, my broswer remembers.
yeah makes sense
chennie said that he can solve all the problems in just one hour
I can solve A in just one hour.
Lu Xun once said that pretending to be weak is a bad habit, chen
good luck!
Since F is 4000 points: new strat = first solve F, then A-E
What's the penalty of a wrong submission? 10 minutes or -50 points?
-50 points
Which scoring system hugopm?? Standard or extended ICPC?
Standard
good luck !
Is div4 no longer happening? This contest gives me a sense of power.
score distribution augur well
good luck, brothers and sisters!
Speedforces ABC yay
D and E1 are also 1750 so, I have feeling many people might reach E1
As a participant, i think i will get: 1) Downwotes to this comment 2) — Rating(because in other Div. 2 i do only 2 tasks)
Hope to get back to Expert :(
wish no longer to solve fake problem
I shall take this contest from my pillow fort
edit: bad contest, I should have just slept
requesting you a screencast of this round with your video. plz
gressforces
Loved the contest, but I messed up on both A and B.
Clutched(somewhat) soon after ¯_(ツ)_/¯
Adityadahiya went from being ranked 16k+ in last div3 to top 100 in this div2. Good stuff.
E1 is too classic
hint for c?
Superincreasing sequence
I don't have proof, but if for any element we have an element on the right which is greater than or equal to twice, then the answer is
NO.so i think it's guesswork during contest?
I am not proud but I guessed it so not sure if system test will pass..
they will pass, the proof is simple give it a try :)
bro its not guess work, very easy to prove. suppose any i<j arr[i]<=arr[j] then, for any valid x, we will choose to increase arr[i], thus, arr[j] will only be increased if arr[i]>arr[j]. now, for by how much can we increase arr[j], i.e., what x can we choose, x<=arr[i], because if x>arr[i], then i will be choosen instead of j. thus, arr[j]<arr[i] && x<=arr[i], arr[j]+x<2*arr[i] (sum both equations).
can you give me a brief hint, i know that we can pass lesser than or equal to the minimum element as k to the futher elements, so the range is [1,something] but why this something is 2*mini?
i edited with the proof.
I thought of setting each value from left to right. If we're simulating the process, we can set each value in 2 operations. The sample
5 6 1 1would have the operations (0,5), (1, 5), (0, 1), (0,1). Since the max you can add in one operation is the largest element on the left(otherwise we're editing that), the max would be 2*largest element. However, for a valuex, we can't addxontox(it has to be strictly greater) so the largest operation is(prefix max-1, prefix max).arr[i] <= max(0, prefix_min[i — 1] + prefix_min[i] — 1) should be true for all i>1
I took the idea that, for a given ith index (expect the first one), You need to construct the a[i] using the minimum of all the elements that occured till now. So Based on that you can maintain a set till the ith element. and then see if ~~~~~ // this is code auto it = *(s.begin()); if( a[i]<=2*it-1){ s.insert(a[i]); } else{ // failed as we cannot construct this element } ~~~~~
. Basically what we are doing is taht , for 5 6 1 1, we want to see for 5 0 0 0 , can we construct 6 or not , and given our set minimum is just 5, so we can construct next element up to 2*5 — 1 (till 11) . So , ussing this you can do this problem in O(1) per element, and overall O(n)
how does one find the actual ranges in E2? I know how to find the medians but not the corresponding ranges
I think we can work on all subarrays of size k and k+1. Then for each such sub array we would have a range of l to r. I think this would work but wasn’t able to implement until end
This is wrong. For $$$a = [1, 1, 2, 2, 2, 2, 1, 1]$$$ and $$$k = 6$$$, then $$$1$$$ is not a median of any subarray of length $$$k = 6$$$ or $$$k+1 = 7$$$, but it is a median of the whole array.
More generally if you consider $$$a = [2^x, 1^x, 2^{2x}, 1^x, 2^x]$$$ where $$$y^x$$$ is $$$y$$$ repeated $$$x$$$ times, then the length of the array is $$$6x$$$.
If you put $$$k = 2x+1$$$, $$$1$$$ is a median of a single subarray which has length $$$4x$$$ and this is close neither to $$$k$$$ or $$$n$$$ (so heuristics like trying a lot of random lengths wouldn't work).
Yes got that. Had no time to think more. Anyways very cool problem. I hope to upsolve it
For some (multi)set S with a range [l r] or medians, any set S' formed by adding or removing an element to/from S has a range of medians that intersects [l r], so if you find the minimum and maximum medians and their intervals [lmin rmin] and [lmax rmax], just walking from one interval to the other will give you a set of O(n) intervals whose union of ranges of medians is the entire range from the minimum to the maximum median achievable.
Read the editorial. I tried to make it as clear as possible but it's probably still not very clear, you can ask questions :)
Mental torture simulator contest
time to touch grass
MOTHER OF GUESSFORCES
guessed C,D,E1 without much proper analysis, hoping for a positive system test run.
also even after solving 5 questions, rank is around 1000 .. that doesn't make me happy.
E2 is wonderful, thank you!
nice div3
div 2.5 till E1 then switched to div 1.5
b>=c
Completely agreed
Nah i dont agree
I guessed B and C lol
haizzz, i hate this contest
brain cancer inducing C
Seriously! It's so hard to get intuition for these.
truly
Permutations of
[1 to n]forces...Unfortunately, I found E1<D and even E1<C for me when the contest almost end.
How did u solve E1? I had no clue. Just wrong guesses
The most important thing, we can binary search the value of submedian.(3sec Time limit also implies that)
When we fix the median, we can use sliding window along with prefix sum to check if any interval exists. Replacing all element with 1 and -1 is a classic trick.
Example:2103C and check the tutorial.
Hoping to reach Specialist with this contest :)
hint for c?
i couldn't guess its logic
you cant go past any element with a value greater than or equal to twice its value
does this work?
initiate a curmin that stores the minimum value seen in array so far . initialise it to a[0]. now note you can always make any element to its value if it is <2*curmin . if not you just output no Eg: to make 5 9 you do 5 0 -> 5 4->5 9 try making 5 10 ; you wont be able to
ah okay
will try and submit again when system testing is over
felt more like a div 2.5 edit: how did me and many more got system testing failed in A?!
I felt like div 1.5
E2 is Mo's Algorithm
is there a use for property given in problem D ie
max(a1, a2) > a3, my solution didn't use it but passed pretest.because of that constraint the LDS ending at ith element will always include one or both of $$$ a_{i-1}, a_{i-2} $$$
ok my solution felt simple enough .. but maybe this will simplify something more.. hope to understand better in editorial..
also hoping that my solution doesn't fail system test lmao.
yeap
let's look at p[i] < p[i + 1]
it obviously reduces the answer for the subsegment by at least 1
but since max(p[i — 1], p[i]) > p[i + 1] => p[i — 1] > p[i + 1], the answer will decrease by exactly 1
wtf was wrong with D? I'm still not sure where does the max(p1, p2) > p3 comes in play
You're not alone.
because of that constraint the LDS ending at ith element will always include one or both of $$$ a_{i-1}, a_{i-2} $$$
This makes the DP depend only on the last two items
$$$ max(p_{i},p_{i+1}) \ge max(p_{i+1},p_{i+2})$$$, so if $$$p_i \gt p_{i+1}$$$ or $$$p_{i} \gt p_{i-1}$$$, it's always optimal to take $$$p_{i}$$$. Such numbers will be in LDS of every segment they are in.
Fiddling with the stupid transition dp on D for the last 40 minutes, only to solve it 5 mins after the contest over.
if arr[i] < arr[i — 1] -> dp[i] = dp[i — 1] + (i + 1).
else dp[i] = dp[i — 1] + 1
yikes
yeah I did the same and this doesn't use the property given in the question, so I Was not sure if it is correct
Actually it does
The property gives the array a specific form that makes either i-1 or i-2 the best candidate for the last term of the decreasing subsequence otherwise you would have to look behind i-2 to see if you can find something better
so if you see the dp mentioned ... it doesn't use the fact directly as it only looks at one previous element.... is there a case where it fails ?
If the array didnt respect the condition,yes
ok I will try to check this tomorrow, thanks for sharing your thoughts.
It feels demotivating to not be able to solve anything after Problem A. :((
B in my opinion was much tricker than C. The edge case where the length of the array is odd was funky.
It was pretty easy to figure out you can just alternate using pairs and just keep removing either (LR) or (RL) depending on if your previous removal was increasing or decreasing. The only issue is when the array is odd, you can get a case where the final element in the middle screws you.
331167108
Did the same approach, got WA on pretest 2 :/
Correct, you didn't account for that edge case I was referring to. say you have at the end ( (4 1) (2, 3) (5) ) the 5 screws you. Your solution only works for even length arrays.
You can just check while the sz(array) >= 2, keep removing, then if there's 1 remaining, just append L or R. doesn't matter
can someone explain the idea of c ?
Lets build the array of length 2.
can we build the array [4, 8]?
No.
can we build the array [4, 7]?
Yes.
[4, 0] -> [4, 3] -> [4, 7]
Can you see now why we can't construct [4, 8]?
Build the array in order A[1]..A[N]. What is the MAX value that A[i] can be?
min(a[0:i-1]) * 2 — 1
Did I dazzle? I saw 11 greedy tags and 3 sorting tags in problem A
It was fixed
maybe, solution for e2 was not present in telegram or something
lol, E1 is very classical though, i knew the answer as i read the question. D was a good!
what the flow is this 331128282
I have some consideration about E2 but I dont know wether it is true，can sb. answer?: just like E1 , we can solve max and min submedians with its segment. guess: submediens is continuous and when change segement with one element insert or delete, the change of median is continuous as well. so we can translate from min-submedian-segment to max-submedian-segement by O(n) and update segement of all median between them. Is this true? I have not participated in this contest.
Seems the same way I thought of it.
Yes! This correct, strong :orz:
Good contest and clear statements. I'm glad that I eventually ended up solving D.
Decent and balanced contest, the participation was engaging. GJ.
contest ended right before I submit E1 :(
Thx for not having pretests for equality case in A (T.T)
Now 16+ pages of wa5 during system tests(
"strictly greater than c"
so I use smaller than. but it's exactly the opposite. :(
I just posted a comment about it here. We're really sorry about that :(
i gave up on first problem
We are extremely sorry for the hacks due to the equality case on problem A. This is so painfully obvious once we saw it, but for some reason it was unnoticed despite all our efforts in the preparation of the problems and the extensive testing we did :( We hope you still enjoyed the problems and we will do better next time!
1486D - Max Median and E1 are basically the same
I failed on pretest 2 for C, and I don't get how it could be wrong. Can anyone help me?
You're idea is correct, but you're breaking the loop as soon as you get x >= 2 * minimum, and it causes wrong inputs for next test cases. Remove the break statement, it will work.
Try long long instead of int. The problem is if minimum equals 1e9, then 2 * minimum occurs int overflow.
Nice tags on A, B, E1, and F lol
my first A,B,C best contest I have ever seen THANKS
Why is there no test in the first four tests that contains wrong forgetting the =?[problem:A]
I posted a comment about that. Once again, we're really sorry and we'll avoid this kind of mistakes in the future :(
It's not my fault, please fix the problem
I was able to solve A but what case are you talking bout?? Im a bit dumb to understand this.
in the solution of the problem you should but a statement <= c ,although i forget the equal sign i got accept because no enough tests in contest after contest i got wrong in test 5
Fast tests, fast editorial releases, great race. Except for the fact that A's pre-test data is not comprehensive enough, everything is so perfect.♪(･ω･)ﾉ
(Please forgive me for writing reviews using the translation plugin, my English is not good QAQ)
I'm glad you enjoyed the problems :) Sorry about the pretests of A, we'll do our best to not repeat this mistake!
no test for whether a number is strictly greater than c..... ;(
We're very sorry about this mistake D:
E1's idea is similar to 1486D - Max Median.
Somehow I solved 4 problems and only got +27 rating :(
because there are newbie accounts that still top the rankings:D
Thank you for such a weak pretest, I went from positive delta to -16
It was test 5, test 4 was still in pretest
@zeyd123
@sirkim21
this contest was too challenging and q3 also.
Twenty minutes ago, I received an email regarding code duplication. My submission for Problem D: [331148990][https://codeforces.me/contest/2128/submission/331148990]
was flagged as duplicate, even though I only needed less than 10 minutes to figure out the solution and solve it.
I was furious that code I wrote entirely on my own was flagged as duplicate. I reviewed some of the submissions mentioned in the email and found that most used the same variable names and nearly identical structure. My code is similar in structure and concept to the others.
But I don't understand: can these alone be used as a criterion for cheating? Remember, this problem only has three parts:
So, similar code is almost inevitable. Just like most div2A and div2B problems, everyone's code is very similar, with just a few lines of code.
So, I filed an appeal, hoping to have the erroneous flagged.
Dear Codeforces Team,
I received a code similarity notification for my submission in Round 1039. I believe this is a coincidence because:
in problem C: 1. Problem Logic is Straightforward
The problem's solution is based on a simple greedy approach with a
min_prefcheck, which naturally leads to similar implementations. Many participants likely used the same logic: — Check ifn == 1(trivial case). — Iterate through the array while tracking the minimum prefix (min_pref). — Compareb[i]with2 * min_pref.in problem E1: 2. Standard Binary Search + Prefix Sum Approach
The problem requires finding the maximum value
usuch that a subarray of length≥kmeets a condition. This naturally leads to: — Binary search onu. — A prefix sum check (with +1/-1 conversion) to validate the condition.This is a well-known technique (e.g., discussed in CP-Algorithms or USACO Guide).
No External Code Used
I did not refer to any external sources during the contest. The similarity is due to the problem's constraints favoring this standard approach.
Variable Naming Differences
While the logic is similar, my variable names (e.g.,
min_pref,min_pos) differ from others, indicating independent implementation.Could you please review my submission? Thank you for your time.
Best regards!
.
Thanks, bro.
And don't worry you'll grow eventually so don't cheat
Dear Codeforces Team,
I recently received notifications about code similarity issues in my applications for Round 1039. I assure you that I solved these problems on my own during the competition, using only my knowledge and without referring to any external sources, general materials or online platforms.
Regarding task B (2128B): The solution is based on a simple greedy approach.
My logic is natural for the constraints of the task. Given the simplicity, similarities in structure are expected for all participants, which is very similar to common solutions for Div2A/B tasks.
As for the E1 (2128E1) problem: The solution uses a standard methodology
My approach is well documented on competitive programming resources (for example, CP-Algorithms) and is the obvious choice for "maximum value with subarray constraints" tasks.
I understand the need to be vigilant about violations, but it seems to be a case of independent implementations converging due to problematic constraints. I kindly ask you to review my materials.
Thank you for your time.
tw20000807 orz