Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 1040 (Div. 1) and Codeforces Round 1040 (Div. 2), which will start on 31.07.2025 17:35 (Московское время).
You will be given 6 problems and 3 hours to solve them in both divisions. Some problems will be divided into subtasks.
The problems were authored and prepared by me.
Some problems may be interactive. So please refer to the guide on interactive problems if you are unfamiliar with them.
We would like to thank
- TheScrasse and errorgorn for the coordination;
- Alexdat2000 for Russian translation;
- BurnedChicken, who impressively solved $$$15$$$ problems, for VIP++ testing;
- StarSilk, liympanda, irmuun, irkstepanov, nifeshe, Error_Yuan, Akulyat, sevlll777, FairyWinx, IceKnight1093, Kaey, -firefly-, TopazDragon89, misteg168, DAleksa, n0sk1ll, nicolasalba, AbduSaber, masa.dobric, reirugan, raresh30, chromate00, gleb.astashkin, dimasik06 for testing;
- MikeMirzayanov and KAN for creating Codeforces and Polygon.
Good luck and have fun!
Score distribution:
Div.1: $$$500$$$ — $$$1000$$$ — ($$$750+750+750$$$) — $$$2000$$$ — $$$3000$$$ — ($$$2500+2500$$$)
Div.2: $$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — ($$$1500+1500+1500$$$) — $$$4000$$$**
UPD 1: Editorial
UPD 2:
Congratulations to the winners!
Div.1:
Div.2:
As a tester, I solved strictly fewer than 15 problems during testing.
As a participant, I also solved strictly fewer than 15 problems during testing.
deleted, cause got downvoted for no reason ;(
off topic, but the contest you made was fire!
As a random guy, i dont know what to say
Nice problems! I recommend the Codeforces community members who haven't participated yet to give it a try.
yes really i enjoyed man!!
My first compulsory div 1. contest, guess who's going back to expert.
As a tester, I upvoted this blog.
Wishing everyone a great performance!
As a tester, I wish everyone an amazing performance.
As a non-tester, -firefly- tested.
As a tester, I could not hear any negative feedback from other testers. Besides, I decided to not tell my opinion about this, as I have seen people believe the exact opposite as I tell them my opinion.
As a tester, I pretend to test.
As a VIP tester, the contest is completely different than when I tested.
That's for sure, considering you solved 15 problems for 2 sets of 6 problems (which ig will overlap, giving total of ~10 unique problems in a set). So even in the best case it's only $$$\frac{2}{3}$$$ similarity to your experience :)
Pretty short and to the point announcement.
Finally a Div.1 only contest! As a participant, hope that the problems are interesting and may it be cheater free!
Interactive problem ,oh no
Interactive problem, oh yes, free rating
can you explain what is this interactive problem
There is full explanation
arigato
Wish this round is better than CodeForces Round 1000(Div. 2)!
Anyway, where's the score distribution?
There is no score distribution and thank God there isn't any because the score distribution ones are the hardest ones
they all have score distribution except for div 3-4s and educational rounds
Why Downvotes?
i upvoted
Really excited for Codeforces Round 1040! Huge thanks to the authors and testers for their hard work. Best of luck to everyone—let's enjoy solving together!
As a tester, I'm in Bolivia.
are u participant of ioi?
Mongolia team.
Hope for short problem's statements like the announcement
Hope to reach specialist
Hope this round goes well for me!
Interactive problems are the most fun ones, but also the hard ones :(
wuhudsm orz!
Hoping to reach Specialist with this one :)
I hope everyone does good and reach where they want to :)
Congratulations bro! I also got a rank increase after this contest :D
Thankyou so much :)
Congrats to you too, hope you also reach higher ratings
Like ho w many interactice can be there and also i am excited for this contest. Hope it is easy!!!
As a tester, I really enjoyed the problems. Recommend to participate.
As a tester, I completely forgot about this round
Looking forward to it
As a tester, all the best to everyone.
This will be my first div 2 !! Hope i will give my 100%
Will do my first contest!
Oh, Interactive problem?? Free rating for me. 😁 or WA/TLE/MLE hell 😭 💀
Hope to reach pupil in this round.
score distribution ??
does score distribuiton mean that e1 will be easier than d?
no
Yes
it wasnt i guess
Oh!! very interesting score distribution for div2D and div2E-1
Hope I can Skip Speicialist and got Expert :(
Hope to get back to expert :(
I like contest held by wuhudsm!
Is the comp recommended for a beginner
Thanks for the hard work behind this.
i miss gf ;-;
Oh no I know nothing about generating function please no
Also I hope interactive is not 1A/2C
do u miss her like me :?
Ok,carry on
I know u miss her like me :heartpulse
Thank you to all the authors, testers, and coordinators for this great contest! I
you're joking right? D is so stupid
really? took me an hour. i wonder if there's an easy solution. or if you did prove the solution.
It's about D Div 2, I think
Another great problemset by wuhudsm. Best CF round I've done in a while!
Fun problems. Struggled worse on B than D crew.
I think i had the solution for E, but too slow to implement.
My idea was if we have a known opening bracket '(' and known closing bracket ')', we can check up to 9 indices to see if they are '(' or ')'.
The idea is this we query in this format ('(' + index_to_check + '('). It will be 0 if its closing or 1 if its opening.
Now we expand this idea. for the second index we run the same query twice! and for the third 2^2. Now we receive a bitmask of the values that are ')'!
I had same idea. But notice: you can better. Just use format
'((' + index_to_checkSo, you can check 8 indexes by query. Length of query is3 * (1 + 2 + 4 + ... + 128) < 1000I couldn't solve div2D .. I don't deserve to be an expert.
Someone please share the idea behind it.
go from right to left and pick choose greedily. (try to prove it).
hmm our idea is different
oh no I had this idea but didn't pursue / analyze fully ... aaaaahhhhh !!!
this felt like linear and looking at constraint I thought correct solution has to be
n*nFunny advice: if you're unsure of the complexity, check the submissions for the problem! I failed to solve D too, but I knew that the complexity had to be n or nlogn since all the passed submissions were <100 ms
yeah, smart !!!
my solution was n^2 and passed
Here's my analysis. lets say we have 3 pairs (1, 6) (2, 5) (3, 4). We notice the first pair(1, 6) is either the largest or smallest element in the permutation.
(2, 5) pair does not affect your choice on (1, 6) because if you chose 1, its smaller than both 2 and 5, and if you chose 6 its greater than 2, 5.
This means we can process the permutation in order, start with 1 and process up to n. maintain a set of indices that have been removed, and greedily decide whether to choose small n, or large n.
thanks, I will try to upsolve it today.
you solve from value 1~N
O(N^2) is acceptable
don't get discouraged, sometimes I also only solve 2 probs in div2.
thanks for your kind and supporting words ... yeah I will keep giving contests
Basically, you store the indices for every number 1..n. Then, for those indices, you can count the number of inversions(regardless of future choices), if you chose either i or 2*n — i. For every index, I used i or 2n — i, depending on the number of inversions. To count inversions, I used order statistics tree, but I later realized, it could also be done using whole array pass(as the constraints allow it). Sorry, if my explanation is not that clear. You can see the code: 331840665
no worries, thanks for sharing your idea,
I should have given more effort to this problem... so many people solved it.
I also struggled a lot with it. Idea is that if you don't flip number in position, you will add as many inversions as there are bigger numbers before current number. If you flip, you will add only those bigger numbers which are after, because all inversions with numbers that are flipped before and were smaller before flip are considered calculated already, and all numbers which are after and greater will cause +1 inversion (regardless they will be flipped in future or not). So for each position greedily decide to add count of bigger nums before or after this position
just needed 10 more minutes! for c2!
How to solve div2E1? Please please please
My solution was to find an index that I am sure is a '(' and ')' (call the former bra_index, the latter ket_index), this can be done with binary search.
After finding these indices, query the other indices two at a time (call them i and j):
? 8 i ket_index bra_index bra_index ket_index bra_index j
Essentially, it is asking what f("s_i ) ( ( ) ( s_j") is:
so you can identify what those two characters are with one query, and in total it would take less than 1000 / 2 + 2 * log(1000) < 550 queries.
And actually by making the template 's_i ) ( ( ) ( s_j' longer you can identify 6 characters at a time! I think this is the solution to E2 (probably).
Just saw the editorial, it's pretty much the same idea but they did a better job explaining lol
Thank you. I thought this way but I forgot that I can use same index more than once per query. And all the variants of (i, j, bra, ket) did not give me enough information.
hint for E?
Could not understand how to get the correct answer in that few queries
How to 1D
I'm pretty sure dp[l][r][center][increments] should work?
It represents the number of ways you can fill [l, r] where [center] is the first element that gets painted black in the range, and it has been incremented [increments] times by stuff outside of the range. To transition, you just iterate on the next element to pick from [l, r] (resulting in the range getting split into 2) and [increments] is at most like 12 or something, so I think it might run in time (?)
I couldn't properly implement this in ~30mins though :((
(edit: I don't think this works 🤣)
I failed with one of the samples but that sounded good to me:
Actually I found my bug and now it just works so I still have to submit but I'm more or less confident in this one.
Damn, was so close, forgot to copypaste $$$\times \binom{r-l}{i-l}$$$ once. It would be a get to GM round for me
D was quite nice, really felt good when I finally got it.
In Div1B, how can we prove that the greedy approach of just iterating right to left and moving a position up if it improves the answer is correct?
I guessed that greedy would get AC after seeing the solve count go up that quickly but can't actually prove its correct >.>
Even solving Div1C3 feels significantly easier than proving this to me.
If u look at inversions as value (1, > 1) + (2, > 2) ..
u can see relation between (i, > i) pairs is either i is below them or above them.
I thought of it differently. Consider the number 1 in the permutation -- if I keep it as it is it will always form an inversion with all digits to the left of it but no inversion with any digit to the right of it, and if I flip it then it will be vice versa.
So, I can greedily choose what to do with 1. Now that all inversions including 1 are taken care of, we can effectively remove it from the array..and now 2 becomes the new 1 and so on..
Why remove 1 and moving forward with 2 and so on works?
I thought like this
Say u move from right to left and at some index i, u see that the no of numbers bigger than a[i] on the left is more than the no of numbers bigger than 2*n-a[i] on the left, now changing a[i] to 2*n-a[i] is definitely better
But what about the numbers in the right -> if those were smaller then those are still smaller so no change else let's say they were smaller but then they were also changed by 2*n-itself so those are now bigger but now even after doing 2*n-a[i] to index i, those number will still remain bigger hence no change again.
Edit: ok i missed the case where the right number is bigger but then it was made 2*n-itself
See my comment above. You can prove this by showing that as the number increases, whether you choose i or 2n-i has NO effect on your previous selections. (1,6),(2,5),(3,4) if you choose 1, it will be the smallest value in the array. If you choose 6 it will be the largest value in the array. This means you only need to consider the indices of the elements with a larger N, because your choice has no effect on previous selections.
Actually, you can iterate through the array in arbitrary order and it can be easily proven.
ABC great, D guessforces, E cancer
fr D was just guessforces. so hard to prove why it works
If you consider them in order from 1 to n, you will find it surprisingly simple.
F STD
I SOLVED D IN THE LAST MINUTE
i cant believe div2D was so guessable lol, idk how the solution works, but its so easy to guess it. hope it passes system tests
also for me... B >>>> C ... I had template for MST so C was easy peasy.
mst? bruh overkill much
wait what ... what did you do ? ...
coz I had template for MST it was not much effort
i just sorted + O(n) pass
pseudo_code
oh I see , how it will also avoid the cycle.... noooo!!!!
now I am worried about system tests lol
Could you explain your approach for C? Struggled with C quite a bit.
oh I actually observed that there shouldn't be any cycle in the graph formed so it has to be a tree.. so I just found MST... but
M is maximumso made all edges have negative weight...weight = r-l+1but negative.i dont think you need MST. you just had to keep adding edges to a component. if adding current edge formed a cycle, just dont add it. i used DSU to keep track of cycle similar to kruskals algo but there was no need to keep track of weights, any tree would work as there will be path from smallest node to largest node
yeah I see it now, but I didn't spend too much time thinking of alternate ideas as MST came first to me.
simply throw away all the segments that are subintervals of other segments
oh wow !!!
For every ai, chose the max bi, throw away everything else. Because cycle can only be formed if for a given ai, you have two bi, bj, which can form a cycle, so it can be avoided if we just chose the max.
oh man I didn't think like that.. that is really nice adhoc problem solving.
if u have a cycle say a-b-c-d-a where say b is largest and d is smallest then u can just keep b-c-d and remove a-b or d-a or both
As this will not decrease F(s) (since the numbers covered are still from the smallest b to largest d) but this will decrease G(s) as the cycle doesnot exist now
Ultimately F(s) does not decrease by anything but G(s) decreases to 0
yeah, thanks. I was overthinking lol
Trash round! Every time you put these ad-hoc problems my friend will do them faster than me, otherwise this won't happen. Can't you just involve more algorithms???!!!
I really liked Div1C, its such a fun problem to think about and optimize.
Also thanks for not making the constraints unnecessarily tight.
Here's how I solved div2 E1.
First, let's call the query answer Q. The given string in parentheses is s (i.e., we're looking for s). Let the first character of s be s[1], the second character be s[2], and so on. The length of s is given as n. First objective: Find the index that exactly corresponds to ). If we query a string of length 2 and Q = 1, the string must be () . We'll use binary search to find this.
There are two main cases for string s. 1. Q(s) = 0. That is, the RBS is not in s. In this case, s must be in the form )))....(((. That is, s[1] = ) and s[n] = (. Therefore, we can achieve our first goal. In this case, we achieve our first goal. 2. Q(s) > 0. That is, the RBS is in s. In this case, we can find out using binary search. Let the length of the current string be k. I. Let's query from 1 to k//2. If Q > 0, select 1 to k//2 as a new string and perform binary search again. If Q = 0, II. Let's query from k//2 + 1 to k. If Q > 0, select k from k//2 + 1 as a new string and perform binary search again. If Q = 0, Clearly, Q(s) was greater than 0, but both Qs are 0. This means that the RBS has been truncated by the part. That is, it has been divided into k//2 and k//2 + 1, so s[k//2] = ( and s[k//2 + 1] = ) .
This binary search is repeated until the string length becomes 2. If the Q value is 1, then () is confirmed, and we can use that to determine the indices of (and ). Since it's a binary search, n is at most 1000, so it should take less than 50 attempts to obtain the index. Let the positions of the characters (and) be a and b in the indices obtained this way.
Secondary Objective: Finding the Entire String s Now, we need to find the remaining characters, excluding the already known s[a] and s[b].
We can easily find them by pairing them like this.
The query can be as follows: For s[i] and s[j], whose characters are unknown, The query is as follows: i i j j i j i j i j b
If Q = 7, then s[i] = ( and s[j] = ) . If Q = 6, then s[i] = ) and s[j] = ( . If Q = 1, then s[i] = ( and s[j] = ( . If Q = 0, then s[i] = ) and s[j] = ) .
This way, we can find all strings with a single query, so we can find all strings with at most 500 queries.
After finding all strings in this way, we can combine them and output the answer as !
For n = 3, we need to split them using special logic. First, let n be e, f, and g when n is 3. Q(e,f,g) is used. If If Q(e,f,g) is 0, then g = ( , and e = ). To find f, solve Q(f,e). If Q(f,g) is 1, then f = ( , and if Q(f,g) is 0, then f = ). If Q(e,f,g) is 1, then solve Q(e,f). 1. If Q(e,f) is 1, then e = ( , and f = ). To find g, solve Q(g,f). If Q(g,f) is 1, then g = ( , and if 0, then g = ). 2. If Q(e,f) is 0, then f = ( , and g = ). To find e, solve Q(e,g). If Q(e,g) is 1, then e = ( , and if 0, then e = ).
This allows us to obtain the answer when n = 3. Here it is.
Now, next, let's consider the case where k = 3. That is, when the binary search encounters a case where the length is 3. So, instead of using other logic, let's use this logic. Let e, f, and g be e, respectively. Do Q(e,f,g). If Q(e,f,g) is 0, there's nothing more to do in this interval. Move on to the next interval. (If the current interval was from 1 to k//2, move on to the interval from k//2 + 1 to k. If the current interval was from k//2 + 1 to k, set s[k//2] = ( and s[k//2 + 1] = ) and follow the original logic of terminating the binary search.) If Q(e,f,g) is 1, do Q(e,f). 1. If Q(e,f) is 1, then e = ( and f = ) is . Since we have found the indices of ( and ), we terminate the binary search. 2. If Q(e,f) is 0, then f = ( and g = ). Since we have found the indices of ( and ), we terminate the binary search.
damn, was close to getting this and knew binary search was involved yet wasn't confident enough to write up a solution
thanks for explaining!
That was my exact idea with slight difference at the i i j j i j i j i j b part, but my solution keep getting stuck at testcase 8, and I see many other people stuck at testcase 8 too. thus I added this part of the code before my main solution to test something out
The result I got was TLE on testcase 8 while passing the first 7 testcase, my idea was that if the string s consisted of atleast one "(" and one ")", then s[1],s[2]...s[n],s[n-1]...s[1] will consisted of atleast one pair of bracket, but in testcase8 it contains returns 0.
can someone explain to me why this might have happened? Thanks
My tle submission: https://mirror.codeforces.com/contest/2130/submission/331853802
Was trying to hack some solutions (D2B) but it kept giving me invalid input —
Validator 'vali.exe' returns exit code 3 [FAIL there is no 1 in a! (test case 1)]Fixed: Just realized there should be atleast one 0, one 1 and one 2 in the array.
Me? ^_^
Anyone know why so loose constraints on Div1A/B? Made me suspect my solution for a while lol.
$$$O(n ^ 2)$$$ makes Div1B nicer to implement in several ways by allowing you to just iterate over all positions before / after while applying the greedy as well as trivially calculating the total inversions.
More cynically (or tbf saltily) speaking, it allows you to think about $$$O(n ^ 2)$$$ dp approaches till you go insane :)
Does anyone know why this TLEs on pretest 5 for div1E? I spent the last 90 minutes of contest crashing out over this and got nowhere
https://mirror.codeforces.com/contest/2129/submission/331856028
Condiser a graph with many nodes with degree $$$0$$$. Some testers and me also make the same mistake at first ;)
Bruh cannot believe i threw rank 40 like that, especially considering the headsolve was extremely simple and took about 5 minutes
From score distribution I thought to myself that three subproblems is a bad sign. Surprisingly it was quite reasonable, like you definitely have some advancements to do and it's good to be rewarded gradually here.
Good round. Was really close to solve D,but couldn't figure out one of the samples on the paper in last several minutes — wasn't counting one of the cases.
div2 B impossible
I could not prove B ,i just guessed it and wrote the code and boom ,it worked like magic
I've also passed pretests, but I know that my solution is incorrect. Hope, they'll share tutorials soon, with proper explanation :)
can you share your code..
https://mirror.codeforces.com/contest/2130/submission/331796924
It took me a long time to conclude that Div2C was just cycle removal.
Can anyone explain the logic behind Div. 2B? Banged my head for over 2 hours but couldn't do it :/
To go from start to end, Alice has to traverse every element atleast once so required sum should not be less than the sum of the elements. If it is you don't have to rearrange just print the array. If the required sum is equal to the sum of elements no matter how you rearrange, Alice will go from start to end to achieve the sum. Now, if the required sum is greater than total sum, find the difference. The array always contains 0, 1 & 2. If 0 & 1 are neighbors, Alice can go from 1 -> 0 -> 1 to gain extra 1 so it can cover any diff. Only arrangement left is all 0s at the start then 2s then 1s. With 2 -> 0 -> 2, Alice can get extra 2 and with 1 -> 2 -> 1, Alice can get extra 3. Only positive integer which cannot be formed using 2 and 3 is 1. So only if, the required sum is one more than the total sum this arrangement will be sufficient to prevent Alice from getting the required sum. So only two cases:
C > D ?
why Question D doesn't come, yoink
turns out i am really bad solving only 2 problems out of 6. And i am to go to university next year... hope to find the sacred secrets of solving with TheScrasse's divine guide until Judgement Day (next summer)
B is beated me... D is so strange by its simplicity, i hope i guessed right greedy strategy and pretests are strong
For Div2 C ( Div1 A), why is taking the longest segment starting form a point , wrong ?
Eg. {(1,2),(2,5), (1,5)} then answer can be { (1,5) , (2,5) }
Yes, I did the same. My solution is passing all pretests: 331814465
[submission:331855822]Why is this incorrect?
What could be the possible problem if Div.1 C1's pretest 1 got TLE (neither Idleness Limit Exceeded nor Wrong Answer, it's Time Limit Exceeded) and checked that
cout << endl;/cout << '\n';thencout.flush()aren't the issues (https://mirror.codeforces.com/contest/2130/submission/331854284)Approaching 1C3 gradually is a great experience.Thanks for the author!
Can anyone explain why my div2 E1 doesn't work?
https://mirror.codeforces.com/contest/2130/submission/331855065
My idea was same as editorial where you find one '(' and one ')' and my query was s1)(s2))
In E3 div2, during the last 15 minutes I received multiple denial of judgement verdicts, even though nothing was wrong with my code and I had no idea what's wrong. After the contest, the verdicts changed to WA on 8. How can this be explained? I could have solved E3 during the contest if not for this issue...
Solved D using Order Statistics Tree in O(nlogn). The constraints really made me doubt my solution, but thankfully it passed!
Why was problem E approved, and survived testing phase? I'm quite sure both part of the main idea appeared on codeforces and atcoder before.
How to solve B?
Can someone please explain how to do B? I feel so frustrated that I was able to do A,C but not B and I know I would have been able To solve D but got stuck at B. B was a nightmare. Please can someone help me with the approach.
Div 1 or 2? I gave only div2 so ill explain div 2 B If the sum of the array is greater than s then alice won't be able to find any sequence so output will be the array itself . If sum = s => whatsoever the arrangement she will always be able to cover the array by traversing once so o/p = -1 Now if sum < s and the array has 0 and 1 side by side she will again be able to traverse the array as she can go from 1->0->1 adding 1 each time so she can cover any target s . So we try to put 0s then 2s then 1s and now 2->0->2 adds 2 and 1->2->1 adds 3 and we can make every no. Using 2 and 3 except for 1 so if and only if s=sum+1 alice won't be able to make it else she would so we print all 0s and 2s and 1s if sum+1=s else -1. Hope you get it:)
Shit thanks a lot!! I was able to figure out till the point that the final answer will be of the form 0s->2s-1s but was never able to understand the condition of getting -1, I come from leetcode and for some reason I get stuck more on B than C maybe because B is usually greedy or constructive and that is quite weak point gor me since such problems are rare on leetcode. Thanks a lot for the help!!
let the sum of array be "sum", if sum == s then regardless of the permutation Alice can just go through everything once and win, if sum > s then regardless of the permutation Alica can't get a final sum smaller than "sum" since there's no negative number. now let's condiser the case where sum < s. remember that all 0, 1, 2 appear at least once int he array, so let's consider the 3 adjecent cases: between 01, 12 and 02. if some 0 is adjecent to some 1 then 0 -> 1 -> 0 adds 1 to the final sum, so it doesn't prevent Alice doing anything. let's assume Bob wants to prevent this form happening, so no 0 can stay next to 1, then there must be some 0 and 2 adjacent to each other (otherwise the array is all 0s), and there also must be some 1 and 2 adjacent to each other (otherwise the array is all 1s). so notice that 0 -> 2 -> 0 adds 2 to the final sum, 1 -> 2 -> 1 adds 3 to the final sum, which means that every even number and ever odd number >= 3 is addable to the final sum by doing the previous 2 operations repeatedly, the only sum not addable is 1, so in this case Bob can prevent Alice from winning by putting all 0s on the left, all 1s on the right, and all 2s in the middle, avoiding Alice to add only 1 to the final sum, and that's all possible cases
weak constraints C,D div2
why n^2
you did D better than n^2?
I used n^2 only to count the number of inversions in the greedy array, since the constraints allowed it https://mirror.codeforces.com/contest/2130/submission/331813442
But this can easily be replaced O(nlogn)
fair enough
Div1B appeared on CF 12 years ago. And I wrote an editorial for this problem, for some reason.
Done anyone have an idea what could the probable rating of D be? Can't believe my weird solution passed pretests :D Couldn't solve C tho :(
1400-1500
1500-1600 not less than 1500, no more than 1600
ah.. now i feel bad that it took more than 1.5 hrs to solve it lol :')
i really can't believe that i figured out D 3 minutes before the end, but couldn't implement, then found out my solution was correct...this feels much worse than if i had not figured it out at all bruuuhhhh
I could not find the greedy solution for Div2D/Div1B problem.
Instead, my solution is: iterate elements by value from 1 to n. For each value
v, let's say its position isi, then count (using a segment tree) how many positions on the left that have values larger thanv. Call this count asL. Similarly, count how many positions on the right that have values larger thanv, Call this count asR. IfL>R, then keepp[i] = vas it is, otherwise updatep[i] = n*2-v.After we have the final array, count its number of inversions using merge sort.
The idea behind this is:
When considering a current value
v, if there are more numbersv'>von the left than on the right, it's better to keepvas it is, otherwise, updatevton*2-v.After visiting
v, updating or not updatingv',v'>v, does not affect to their comparison: bothv'andn*2-v'are larger thanv, and smaller thann*2-v.Wow, I overlooked the constraint for the problem. I thought it was
10^5.With the problem's constraint, segment tree or merge sort is not needed.
While everyone solving Div2B fast and correct with O(n), I'm bricking Div2B with O(n+s)...
Back to pupil boys. CF expert is too hard for me, I'll be happy at specialist and that's enough.
This is my proof for the greedy solution of
Div2DFirstly, the number $$$p_i$$$ will always be as it is or it will increase to ($$$2*n - p_i$$$), it will never decrease
Let $$$1 \lt i \lt = n$$$ going from right to left
And let all the items right to $$$p_i$$$ be in the optimal case
For the left items of $$$p_i$$$, increasing $$$p_i$$$ will make the number of inversions lower or at least it will keep it the same, so for the next left items, it's always optimal to increase $$$p_i$$$. Let the decrease in inversions be $$$x_i$$$ ($$$x_i$$$ is positive)
For the right items of $$$p_i$$$, increasing $$$p_i$$$ may increase the number of inversions by $$$y_i$$$. But if $$$x_i \gt y_i$$$, the total number of inversions generated by the current item and the previous right items will decrease
So increasing $$$p_i$$$ is optimal for any value of the left items (so, changing them will not affect our choice for $$$p_i$$$), and it's optimal for the current values of the right items (which are optimal in the current case)
my rating graph is going to become a triangular wave now :( disheartening.
Did everything right in Div2(B). But it didn't click to me that we can make any number using 2 and 3 except 1. So was only able to solve A :|.
why is system test not starting?
Div 2 E1 mistake? ~~~~~
void b_n(int l, int r, int i) { int ans = -1; int left = l, right = r; while (left <= right) { int mid = (left + right) / 2; cout << "? 2 " << i << " " << mid << endl; cout.flush();
int response; cin >> response; if (response == 1) { ans = mid; left = mid + 1; } else { right = mid - 1; } } if (ans == -1) { for (int j = l; j <= r; j++) { a[j] = '('; } } else { for (int j = l; j <= r; j++) { a[j] = (j <= ans) ? ')' : '('; } }}
int solve() { cin >> n; bool found = false;
for (int i = 1; i < n; i++) { cout << "? 2 " << i << " " << i + 1 << endl; cout.flush(); int k; cin >> k; if (k == 1) { found = true; a[i] = '('; a[i + 1] = ')'; for (int j = i + 2; j <= n; j++) { cout << "? 2 " << i << " " << j << endl; int k2; cin >> k2; if (k2 == 1) { a[j] = ')'; } else { a[j] = '('; } } if (i - 1 >= 1) b_n(1, i - 1, i); break; } if (i == n - 1) { a[n] = '('; b_n(1, n - 1, n); } } cout << "! "; for (int i = 1; i <= n; i++) { cout << a[i]; } cout << endl; return 0;}
~~~~~
Nvm am dumb af
$$$B$$$ was kinda annoying. I had to think for a long time (40 min) before I got the solution. $$$D$$$ was a bit of a guess lol.
Overall good problems, thanks for the round wuhudsm and all testers!
Sub_acc001 is a cheater 331818606. Please bun this shit
how did u understand it? I dont see anything illegal
I won't tell you how I did it because it might help other cheaters, but the authors know why he is a cheater.
oh that makes sense. You can use personal messages, i swear i'm not cheater haha
When testing start??
Very well
Good
did tons of reading errors, rating took a drop but loved the questions
Can you make a contest before 7 Aug... please! Iam really wanna 20 point to get pupil
my random dividing got fst in C3 :angry:
Great contest! I especially enjoyed solving versions of problem C one by one. If I didn't get stuck on D for so long I would get more rating XD
(Though, it seems that most participants were confident about their skill and hopped to C3 at once, which could be a better strategy)
Editorial for C3 isnt clear enough, how did you get this sequence in your code? (1,2,3,5) Like the thinking behind it. Max I could figure out was powers of 2
The only important thing regarding "powers of 2" is that the weight of the current one should be larger than sum of previous ones. However, the construction to reach exactly "power of 2" requires too much characters and does not make good use of nested substrings, so we need an alternate construction.
The construction
k * (s[i] + ')') + ')'will result in a weight of $$$\dfrac{1}{2}k(k+1)$$$ with a length of only $$$2k+1$$$. So I just greedily find the longest sequence with such weights and the array in my code are the indices $$$k$$$.So the construction with your k values will result in a distinct and non overlapping count for each k (similar to pows of 2), correct?
Yes.
couldn't solve a single one, got close to D but my only idea was to generate all subsequences and that's exponential time complexity.
I'm cooked
I finally became Pupil φ(゜▽゜*)♪
Nice problems
wuhudsm How are you checking for that thing in D2D?
why don't they give me 1200 so I will be pupil :(
gon be my first contest yessirr lesgo
As a tester, I enjoyed testing and IOI
Contest is not that easy for beginner but i learned one thing to not submit without you are 100 percent sure
Hello Codeforces team,
I have received a notice about coinciding solutions for problem 2130B. I want to clarify that I have always used the same personal template for every question I solve. You can check the submission timestamps: I submitted before the other users listed in the email.
I have not shared my code with anyone nor used any public platform like Ideone with default (public) settings. I’m also an old user on Codeforces, whereas some of the other accounts seem to have been created just recently—I do not know how this coincidence happened.
Kindly review the submission times, account histories, and other details—I assure you I have not engaged in any unfair practices.
Thank you for your understanding.
Attention!
Your solution 331834642 for the problem 2130B significantly coincides with solutions singhshaurya520/331834642, Priyavrat_02112004/331837134, AdarshSharma2501/331839408, Adarsh_Yadav_07/331840348. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. 2130A too now it looks like those accounts were created just recently, and this was their first contest. I truly don’t know how this coincidence happened, but I want to assure you that I did not intend to break any rules.
Kindly review the submission times, account histories, and other details—I promise I have not engaged in any unfair practices.
Thank you very much for your time and understanding.
There is no mistake here, your solutions for A and B looks just the same as codes from massive leaks: 331748569, 331759096.
.
It was an accident, and I have some evidence for my innocence. Please read my claim carefully. Coinciding with my submission? Of course, it was just a mere coincidence. You have given me Plagiarism with the participants which I don't know. This is really unfair to me. Being beginner, I want my rating back as this was my best ranked contest where you gave Plagiarism with unknown participants. It might be such that they have used same logic and variables as for 33k participants, we can't have that much solution.
I don't know any of the participants with whom my code matches. Please understand my feeling and review me my rating as soon as possible. It matters me a lot. I didn't have copy code. Please help me
Dear Codeforces Administrators,
I recently received a notification alleging that I was involved in cheating, stating that my code is highly similar to another participant's submission: cly312/331768451 and cybercondor/331828373. After reviewing some of our submissions, I would like to present the following reasons why I believe I should not be penalized:
I submitted my solution 90 minutes earlier than him. After solving the problem, I did not share my code anywhere nor use any online code debugging tools.
In his other submissions in this contest, the code consistently begins with the following segment:
However, this segment is absent in submission 331828373. I believe this indicates that he copied my code.
Therefore, I believe I should not be deemed guilty of cheating. Could you please consider revoking the penalty?
Vladosiya, Hello,could you please consider revoking the penalty?Thank you very much.
Hi, as I see system message mentions submissions 331768451 and 331828373, it's also very similar to the way AI solves this problem.
Hello, I think that g(S') is 0 when S' is acyclic, which reduces the problem to maximum union coverage under forest constraints. Solving it using DSU is very natural, and this is indeed the approach most people take. This is my Luogu Account, where you can see that I won first prize in CSP-S. This may demonstrate that I am capable of independently solving this problem. If there are other ways to verify that I am not an AI, please let me know. Thank you.
My username is singhshaurya520, and I am writing to respectfully request a review of the skipped verdict applied to my submissions in Codeforces Round 1040 Div2, specifically for Problem 2130B and the 2130A flagged problem.
I would like to bring to your attention the following points:
The other users involved appear to be newly created accounts. Upon checking their profiles, it seems this was their first Codeforces contest, while I have been an active user for a long time. I do not know how such a coincidence occurred, but I can assure you it was not intentional on my part.
I never shared my code. I work in a private, secure environment and do not share my code with others or use any public IDE with open visibility. I strongly value fairness and integrity in contests.
Request:
Based on these facts, I kindly request:
A review of the submission timings.
A check of the involved accounts' activity and histories.
If validated, the removal of the skipped verdict and restoration of the contest rating.
I truly respect Codeforces as a platform for competitive growth and would never knowingly violate its rules. I hope this appeal can be reviewed fairly.
Thank you very much for your time and understanding.
Hello Codeforces team,
I received a plagiarism notification stating that my solution (ID: 331843163) for problem 2130C, and was told to comment to appeal this.
I want to clarify that I did not share my code with anyone, I did not use public platforms like ideone.com or pastebin during or after the contest, I wrote the solution independently on my personal system.
Let me know if there's anything else i can do to to prove my innocence.
Dear CF admin, "Your solution 331781967 for the problem 2130C significantly coincides with solutions andy_dahiya/331781967, hacker1909_2/331851332. Such a coincidence is a clear rules violation." I have been flagged by the plagiarism checker for my code matching with some stranger. The code accused of being copied is this->https://mirror.codeforces.com/contest/2130/submission/331781967. It is the solution for the Div2 C, it was standard DSU implementation and it was auto completed by my Co-pilot which is allowed by the Codeforces AI policy (https://mirror.codeforces.com/blog/entry/133941). There was almost nothing that you can write differently in this code. This matching is purely co-incidental and completely out of my knowledge. Moreover, the other person's submission is about 2 hours later indicating that my code has no relation with his. Thus, I request you to not take any action against my account and withdraw the skipped judgment.
So you tell me this 331781967 and this 331851332 look almost identical (and similar to this AI/leak 331770349) just because nothing could be done differently (it obviously could 331749239)?
More than that I see your D solutions differs in weird places, as if you rewrote main() from scratch.
My C solution (331781967) is pure DSU boilerplate—there’s very little you can change—autocompleted by Copilot under your AI policy. I submitted it nearly two hours before the flagged code, so any similarity is coincidental. If you’re now questioning my D solution, please also review my E1 (331840111); you’ll see it’s entirely genuine.
Dear Codeforces Administrators,
I am writing to respectfully appeal the plagiarism flag on my submission for problem 2130C. I want to assure you that I completed this contest independently and did not share my code with any other person or consult any other participant's solution during or after the contest.
My solution is based on a standard Disjoint Set Union (DSU) data structure with path compression, which is a very common approach for this type of problem. The implementation of fundamental algorithms like DSU is often highly standardized across various educational resources and competitive programming templates. I believe any similarity detected in my code is purely coincidental and arises from the standard, boilerplate nature of the DSU implementation itself, rather than any form of academic dishonesty.
I kindly request that you review my submission again in light of this explanation.
Thank you for your time and for maintaining the integrity of this platform.
Sincerely,
varad17
Use the 3rd party code blog post
Also, DSU is overkill and especially should not be used by a 1200 on a C. Save your time and don't cheat next time.
Woow!
Great contest. Love interactive problems!
Standings page(https://mirror.codeforces.com/contest/2127/standings) is down/not opening for me.
I believe there is a missing test case in Problem 2130B - Pathless – Sum on the Subtree, which leads to incorrect solutions being accepted. Consider the following input:
5 9 0 2 2 2 1 This input represents a tree with 5 nodes and a total required sum of 9. The array specifies the desired subtree sums for each node. In this case, the configuration is already valid, and the correct output should be:
0 2 2 2 1 However, submission 342216799 incorrectly returns -1 for this input, yet it was accepted by the system. This suggests that the test cases do not cover such scenarios where the input is already a valid configuration, but the solution fails to recognize it.
$$$i=[1,2,1,2,3,4,5]$$$ is a counterexample to your configuration
yes I got it . Thanks
nice job