Hello, Codeforces!
eren__, sweetweasel, and I are glad to invite you to Codeforces Round 1024 (Div. 1) and Codeforces Round 1024 (Div. 2). Both rounds take place at May/11/2025 17:35 (Moscow time), and have a duration of 2 hours and 30 minutes.
The Division 1 contest is made up of $$$6$$$ problems, and the Division 2 contest is also made up of $$$6$$$!
We would like to thank:
- maomao90 for his wonderful coordination and huge help in preparing the round.
- Alexdat2000 for the Russian translations.
- Our testers: mmdrzada, N_z__, Hamed_Ghaffari, Shahrad_Mirzaei, RSAMSD, -this-is-obd-, AmShZ, AlefHeKaaf, beny_kh, Nariman_MT, sohsoh, Shayan86, Nimazare, Amoo_Safar, _R00T, Um_nik, AriaH, KiaRash24, AmirAli-Asgari, RadRah, NK_, FrontMan., Ali_BBN, AustinJiang, dshfjka, aram.hosna, arvindf232, larush for testing the round and providing valuable feedback.
- MikeMirzayanov, KAN for the amazing Polygon and Codeforces platforms.
- You, for participating in the round and gaining a positive delta!
This is our first (and hopefully not the last) contest on Codeforces, so we really hope you will like the problems. Don't forget to have fun!
The score distribution of the rounds is as follow:
Division 1:
Division 2:
In the end, here’s a behind-the-scenes photo of the authors putting in the effort to bring you a fun round!
UPD1: The contest is now over. Congratulations to the winners!
Div. 1:
Div. 2:
UPD2: The Editorial is now out.
As a tester, I wish the authors would win the IOI.
As a tester, I wish the authors would win the IOI. (and, of course, two of the testers :D)
LOL
Thanks a lot
wow are they IOI participant ?
I hope they get good results
Thanks my sweet student
take me as your student
why not ! of course.
do you take newbies?
yes.
So does that mean I can be your student?
yes again.
Thanks, Teach!
One can confirm by looking at the photo, that the authors are smart and good-looking.
As A participant I hope Enjoy.
A power of two round can't miss it, the next one will be 1024 rounds later
And the power is a power of 10, next time that happens will be 2^100, and universe might end by then
orz
as a none tester, I can confirm this contest will be epic
This would be my 100th rated round...Excited for this !
Hey bro quick tip: between rounds work on problems that are 200–400 points above your current rating so (1800 to 2000) for 50–100 of them until you can solve them quickly. This helped me a lot during my IOI and ICPC training when I was stuck at ~1700. Hoping for a +delta for both of us
thanks this was helpful!
Try maybe solving alot of CSES Problems too their is only 300 of em i did it all in a couple of months helps alot.
Thank you for your suggestions :)
i hope the round is strong strong
Yay, my first Div1 contest. I'm so excited!
As a participant, I hope solve three questions and become a specialist.
Me, too.
And I hope everyone can enjoy the round with a rare index!
As a failed cyan, it's inspirational to see a lot of newbie prodigies AKing the contest I am sure that future of CP is in right hands ...
But I don't see 720 problems in the Div 2 round...
Wow 1<<10th contest
wish to have non-negetive rating change :)
I wish to hit pupil :D
I solved 3 problems on a div 2 twice now and couldn't hit pupil. Better solve 4 next time....
Damn your crazy, you got 4
tyty, gl on reaching pupil soon!
As a potential participant, 720 problems in Div. 2 is kinda scary. Good thing it's 2:30 and not just 2 hours long.
Let's take out our horses for the cowboy round.
1024 is a very meaningful number，This contest must be very exciting ！！！
I used to think top coders were nerds, but the image in the blog changed my mind.
The one in the top right looks like Berlin from Money Heist.
Bella Ciao
EL Classico or this contest? Hmm...
My first div 1 :) !
Codeforces Round
1<<10!Looking forward to a Wonderful Round :D
I think this is gonna be a speedforces round for Div. 2
What score actually is? Is it connected to the problem's rating?
Please don't get me wrong.
The score distribution will be very helpful if you actually care about the details:
But I'd suggest you to focused solve problems in order and ignore the hairy details for best practice atm. You might want to revise the details later, once you starting to getting good at it.
Is it forbidden to ask anything if I don't know something? Like, why am I getting dislike just for asking a question?
Probably because this question gets asked under every contest announcement, even though it's easy to understand what it is by searching it up
Well. I guess I'm a reverse nutella now.
@ of the guy in sunglasses?
Shoo
will i be green ,who cares i am from a warrior race
this is the second div 2 in a row where we have 250 on problem A
Congurats!It's round 1024!
oh! the contest number 10000000000 -__-, i cant wait for it fr <3
CF round $$$10^{1010}$$$.
let us give this contest
1<<10upvotes to celebrate nice number for the round.Good luck, guys! I'm sure you've cooked a great contest.
I'm gonna cook inshallah
As a non tester, i was supposed to test but forgot, wish you a good contest
there's 720 problems in the div2???
edit: oops i just realized two people commented this before me... i'm unoriginal :(
Round 10000000000 is here!
Time to ready my a+b template because A is 250 points
But you're in Div. 1 :)
Got me there...
Very nice LOL
Yeah,finally it's round 1024.And when will round 2048 come
Probably in 15 years =))
Just out of curiosity, why some rounds have unrated option but this one doesn’t?
Icpc style contests: div 3,4, Edu rounds do, Cf styles dont
Thanks! I wanted to participate in this round but I am 100% confident I won’t perform my best tomorrow; so unfortunate I will miss 1ll<<10
Thats not the round 1024, thats round 2^10
2^10 = 8, what do you mean??
I see what you did there!
the ^ is the exponential sign, not the bitwise xor operation
Thanks, I wouldn’t be able to tell otherwise!
That first photo straight up looks like Dagon's Domain Expansion — ocean vibes , domain expansion pose and all Gotta be Toji Fushiguro to clear it all up with zero cursed energy but max smoke
"The Division 1 contest is made up of 6 problems, and the Division 2 contest is also made up of 6!"
Why is the Division 2 contest made up of 720 problems??
.
But 6! = 720 ヾ(•ω•`)o
ha ha !!! noice.
from the score distribution of div.2, it seems the speed to solve first three problems would be a major differentiator, and if solved 4th it would give much edge over other participants
i myself fucked up C! should have gone with instinct from the very beginning : (
I knew it so didnt give it :)
what problem rating should i expect for the first 3 of div2?
and hope to reach pupil in this contest..
A : 700 — 1000 B : 1000 — 1200 C : 1400 — 1600
You can check the rating of problems on Clist
First time participating in a 1 << x contest >:)
2^10 congratulations!
As a participant, seeing Um_nik as a tester means useful algorithms.
Do testers decide problems ? That is the job of authors right?
As a tester, haji ajab cantesti !!!
eshgh kardi ???
asan benazam:)
KiaRez orz
eshgh
as a tester, i know problem A
and this is the answer of problem A:
cin >> q; while(q -- ){ cin >> n >> m ; cin >> r >> c; cout << max(r — 1 , n — r) + max(c — 1 , m — c) << endl; }
why would you say something like that?
It's not a good joke.I hope you're not a real tester.
bro he's on the list
Oh,it's bad.
No I have seen it, what should I do?! Should I give up A?
ig writer have many spare A problems
Sometimes I really hope my complain and downvote would make the comment disappear.
What was that. Very poor behavior. I hope its just a joke.
Happy round
0b10000000000！will manhandle this contest
Failed
I will forever in shame
Again 250 score for problem A!
I hope to not get minus on that.
Why are the scores so strange today?
How long does it usually take for someone to reach candidate master on average? I've been participating in contests since the beginning of 2025, but I feel that I'm still far away :(
Hope to solve today's ABC as fast as possible.
Lets call this contest "The 10th bit"
Failed to start like Mbappe in todays contest...**Hala madrid**
rainboy orz
last submission 5s before the contest ends!
aaah!! couldn't solve div2 D... got messed up in case work. is there a simple solution ?
Fill the first $$$n-3$$$ places greedily
yeah, did that; but how to decide the order of nth and n — 2th term?
Parity of the permutation is invariant, so just compute it for the original permutation and one of these $$$2$$$ potential answers and using that, figure out which of them has the right parity.
this is brilliant, thanks.
someone else also mentioned this, I wish I could figure it out.
spent 1h30 searching for an invariant, didn't find one..
Ahh, I knew there had to be some invariant. I was stuck for almost 2 hours trying to "guess out" the most arbitrary property of the swap operation...
Could you please explain what do you mean by parity of permutation ?
It means the parity of the inversion count.
exactly one ordering among the two ordering of $$$nth$$$ and $$$n-2 th$$$ element is possible so if we keep filling in first $$$n-3$$$ places by continuous naive swapping; the array that remains in the end is the answer , but issue is how to keep track of the changing array within time limit , thing is I have figured out it is safe to assume that in one operation it is possible to swap $$$a[i]$$$ and $$$a[j]$$$ ,$$$a[i+1]$$$ and $$$a[i+3]$$$ where $$$j$$$ is any $$$index \gt i$$$ with the same parity as $$$i$$$
the sum of number in inversions in individual even and odd arrays % 2 before and after the rearrangement remains the same so if the sum of inversions in odd array and even array is odd then the smaller number will come at nth place else vice versa
yeah I figured that I just have to handle last 3 places.. and at max one inversion will remain in odd and even places total
but it seems in some cases you can still sort remaining positions by doing some swaps initially ( I think ).. couldn't figure out in what all cases it is possible to sort both odd and even position completely.
Hmm good point but I think the last three elements are already uniquely determined (not sure)
oh your pretest passed so I think you are right.. did I make a silly mistake.. nooooo!!!
Total count of inversions will remain same modulo 2 (For one operation it can change by 0/-2/+2/+4/-4 etc.). If we get a different modulo 2 for the greedy complete sort approach, just swap nth and n-2th positions.
Could you please provide the proof/intuition behind this ?
Proof of Inversion Parity
Consider a b c d -> c d a b
For element 'c', inv += (c>a?1:-1) + (c>b?1:-1) = {0 or -2 or +2}
For element 'd', inv += (d>a?1:-1) + (d>b?1:-1) = {0 or -2 or +2}
Proof of Greedy Selection
Position parity of every element remains the same (i.e. you can only move an element among the odd positions if it is initially at an odd place, likewise for even)
Further greedy selection possible for 1 to (n-3)th element
n-1th element already decided(greatest of its parity) so all that is left to to determine (n-2)th and nth elements(Among the two greatest values), which can be thus chosen to satisfy the inversion parity.
Note that say the two candidates for n-2th and nth values are x, y (x<y), then (x z y) and (y z x) would lead to always different parities of inversion, hence answer uniquely determined.
Could you please elaborate?
You can sort the even and odd groups by just greedily moving the minimum in the suffix to this position. You know everything is sorted right now except positions n and n-2 because you couldn't do the greedy strategy on them. If n and n-2 weren't in sorted positions (in their group) you know that group has 1 inversion and the other group has 0 inversions. Otherwise, you know both groups have 0 inversions. Notice when you're doing the swaps, the relative parity of the inversions in both groups never change. If they're different parities, they will always be different parities. If they're the same parity they will always be the same parity. So, if they have the same parity initially, you can never get 1 inversion in 1 and 0 in the other (the only possible choice is 0 inversions in both even and odd group). If they're different you can never get 0 inversions in both.
oh I see... I think I get some idea.. thanks for sharing this.
In the end I think whole trick was can you sort those last two elements or not.. and I think your idea is a very simple way to figure that out.
guessForces in C... no idea why spiral printing starting at center passed pretest LMAO.
we would want 0 to be present in most of the subgrids as any subgrid without it would mex to 0, therefore we put 0 at the centre as this pos has the most occurrence of among all. now comes 1, we would like to put 1 such that the subgrid containing 1 and 0 are maximised, this would be subgrid 0 1, now comes 2 ,now we want number of subgrids containing 0 1 2 to be maximised, this can be achieved by enclosing 0 1 2 in a 2*2 grid, using this logic we can prove why spiral printing was the optimum sol'n.
oh wow.. I think this makes sense.. so it was kind of for any cell count how many subgrids this is going to be part of .. sort it .. and then put number in reverse order or something.
whoa thank you for sharing this .. I am sad that I didn't get any ideas for this.
yeah, say our pos is (i,j), number of subgrids this would be present in is i*j*(n-i+1)*(n-j+1), this is because we have "i" choices from top to i, (n-i+1) choices from bottom row, w.l.o.g we can say the same for j.
wow, so cool that you were able to think all this during contest time..hope you get positive delta and become higher rated than me.
Didn't think of spiral printing specifically, but that example input, even for n = 3, was a massive hint.
guess work=accepted in C for me
what did u guess
I think printing as spiral starting at center works on pretests
first time I've seen a nice constructive problem :O
Great problems. Thanks
Can someone please explain C , i thought 0 should come in middle and 1 should always follow it
but kept getting wrong answer on pretest 2
this was my try :319285532
how to do div1C?
Say the elements that occur at least twice are integers from 1 to x.
The first occurrence of each i, i<=x should be in a prefix,
and the last occurrence of each i, i<=x should be in a suffix that doesn't intersect with the prefix.
Now we start building the answer from an empty prefix and suffix and each time we extend one of them based on whose x is smaller.
The indices of the elements taken in the prefix should be subtracted from the answer.
The indices of the elements taken in the prefix should be a added to the answer.
for each iteration we say ans = max(ans, cur_ans)
I've done the building of the answer using a segment tree.
lemma: In an optimal pairing, $$$max_j$$$ such that j is the left of a pair $$$\lt$$$ $$$min_k$$$ such that k is the right of a pair.
For each index, we define $$$L_i$$$ as the biggest number $$$t$$$ such that you can label $$$a_{1,\dots, i}$$$ with $$$1, 2,\dots, k$$$.
for $t$ to be valid, you need every $$$1 \le k \le t$$$ to have at least $$$t - k + 1$$$ eligible elements, so $$$cnt_k \ge {t - k + 1}$$$ thus $$$cnt_k + k - 1 \ge t$$$, so maximum $$$t$$$ is the minimum value of $$$cnt_k + k - 1$$$ over all numbers from $$$1, \dots, n$$$. this can be handled using a segment tree, initialize the segment with the array $$$b = [ 0, n-1 ]$$$ and then loop from $$$1$$$ to $$$n$$$, when visiting $$$a_i$$$, add +1 to $$$b_{1, \dots,a_i}$$$, and let $$$L_i = min_{i = 1}^{n} b_i$$$.
Calculate $$$R_i$$$ the same from the suffix.
$$$T := max_{i = 1}^{n-1} {min(L_i, R_{i + 1})}$$$. The numbers of the pairs will be from $$$1$$$ to $$$T$$$.(This is reached from the first lemma, where $$$i$$$ is the splitting point)
Now start greedily pairing, add all indices with values $$$ \gt T$$$ to a set, and for $$$i$$$ from $$$T$$$ to $$$1$$$, add every occurrence of $$$i$$$ to the set, match the minimum and maximum elements in the set and remove those 2 from the set(they will have the value $$$i$$$ in the optimal array), and calculate the answer.
Instantly borrowed my own code at problem 2036D - I Love 1543 and saved implementation time at div2C.
why make us think so much in problem div2 A, we want to be happy while starting the contest please
I got 94 points at last,humorous
I was able to solve it fast, but still I felt a bit more effort than I expected :(
who else skipped C to solve D and then stuck at D and lose a lots of points ...
any second i felt im closer to answer of D but stuck after 1hr, realized i could solve C in less than 10 minute...
how to solve C .. did you figure it out or you guessed printing the spiral way ?
actually for any cell (x,y) i calculated how many subgrids exists which doesn't contain (x,y).
because you know if we set positions of 0 to be (x,y), we should have most subgrids containing this cell ( otherwise their MEX would be zero )
after finding how many subgrids exclude (x,y) minimized it using parabola's minimum formula.
then you get x = (n+1)/2 and y=(n+1)/2.
so i realized zero should be at center always, moreover, its subsequent numbers are better to be close to it, to maximize MEX for those subgrids containing zero cell.
its not really a proof but it was my intuition, then i guessed spiral would be the best solution. submitted and it worked
very nice, thanks for sharing your thinking .
Exactly, every moment i felt i am close to solving D but i was yet too far away, and exactly opposite for C, it seemed too complicated but was really simple
for D i only had 1 uncertainty about a[n-1] and a[n-3] ( zero indexed ). if i could somehow find them i could solve it. there was only two possibilities....
You count inversions to determine the ordering of those two elements
Oh it makes sense. Thank you
In D I declare the BIT array globally for fenwick tree and wasted 45 min to debug.
You could've also used alternative methods like merge sort or ordered set
Solution is fine but the problem was declaring an array globally and not making clear cause obvious WA as we have different cases in single testcase (t>1)
Can someone give a hint for problem E?
Say the elements that occur at least twice are integers from 1 to x.
The first occurrence of each i, i<=x should be in a prefix,
and the last occurrence of each i, i<=x should be in a suffix that doesn't intersect with the prefix.
Oh, I got it! Thanks!
What does the author wants to test by giving problems like Div 2 C .......
I personally find it a nice problem.. It was intuitive to have a spiral matrix because that's how MEX would be maximised. Though; it also took me long time and various other guesses to come up to the idea..
And this is not a coding test but a problem solving contest (nothing to be tested by the author). So, author wants to make an interesting problem not the one testing knowledge.. That's why guess work is also crucial at times !!
guessing abilities T_T
Why do you announce results even though it is before systests xD?
hello, how can i improve to solve the problems? im new here
Try to solve the problems from the easiest one.
constructiveforces
C was the worst problem I have ever solved.
where tutorials?
Fun fact: the solution of 1693D - Decinc Dividing gets Wrong answer on test 2 in 2101D - Mani and Segments.
Can you provide a case where avoiding
3,1,4,2
3,4,1,2
2,1,4,3
2,4,1,3
wrong?
UPD( fails on 2 5 3 1 4)
in fact 2 5 1 4 is 2 4 1 3, and you can avoid it, see 319312314.
i was SOO distracted i +1 A and B :sob: but in the end i think i did alright, great contest!
In B of div1 and D of div2 why is my submission failing, i try to get the smallest number to front, and then recursively keep making the array smaller and smaller until no more operations are possible, I want to know my mistake before seeing the editorials answer.
it seems you can still sort last remaining 3 positions if you do some swaps before doing the whole process you are doing.
how come we have winner list before system tests have finished ?
I wrote 3.24KiB for 1C :(
How did you solve this problem?
rainboy orz
I like the problems, quality is standard div1 level.
One of the best CF problemsets I've seen in a while, huge congrats to the authors! <3
D глина, еле заслал
D https://judge.yosupo.jp/problem/static_range_lis_query sorry
Thanks for sharing, I forgot that this existed. :P
How to D
bubble sort maybe.
I wouldn't. You do eventually have to sort, but the constraints suggested a complexity of O(n log n). So I just pulled out my trusty mergesort where I needed it.
Answer will be sorted arr(resp of odd and even position) just need one extra swap for odd number of inverions
Ama go volunteer back in the army cause WTF is the solution for Div 1 C lol?
What is the intended time complexity for Div1E? I implemented $$$O(N \sqrt{N} \log{N})$$$ solution with sqrt decomposition but narrowly TLE, so I think that there may be more efficient solution.
I had $$$O(N\log^3N)$$$ running in 3374ms. Basically running https://judge.yosupo.jp/problem/vertex_get_range_contour_add_on_tree $$$O(\log N)$$$ times (though I was somewhat slow since I wasn't familiar with the solution code).
Also, it shouldn't be hard to remove a log factor since in this problem all adds are happening before gets, and the adds are on prefixes only.
319295559
I was able to solve problem B but not A.. Can someone please help with problem A!!
Think of this, say n is not divisible by p, now the sum of the entire grid would be (n/p)*q plus the sum of remaining n%p elements. You can clearly see we can achieve any sum of n is not divisible by p by having desired values of last n%p elements . Now take the case when n is completely divisible by p, here we don't have a choice, is (n/p)*q doesn't add up to m we cannot possible get this sum, as here we don't have the freedome to assign values to last n%p elements.
Notice that the constraint on the segment sum essentially means that the values loop throughout the array over a period of p.
Now, if n is not divisible by p, there will be only part of that loop (segment) at the end, which can carry the total sum to m, and the rest of the segment can compensate and bring the segment sum to q, so it's always YES. If n is divisible by p, then you don't have that extra flexibility, and the segment sum times number of segments must match the total sum. In other words, YES if q*(n/p)=m and NO otherwise.
My first time reaching the 1st page of the final standings omg
I'm so happy
I don't mean to be mean but how does a guy with best perf top 1700 do ABCDF? There's no way you didn't use AI / do account sharing
ABCD are all not really hard and at least 1000 participants worked them out, right?
As for F, I don't think AI is so boring to make this silly solution actually, this is just simple binary search. If you want more details what have I thought:
First, I found that all the cute subarrays has partial order under the inclusion relation. So in this case, one may notice that it's only needed to search all the maximal cute subarrays, using two-pointers.
Second, still the property of partial order, you can use binary search to find the maximum right border when fixing the left border.
After finding these 2 properties, I tried binary search. After passed the examples, I tried $$$n = 200'000$$$ random shuffled permutation (you may notice that there's a comment in
main()that usedfreopen). But it resulted TLE. All the next things I did is just try something that may speed up, like recording low high array to speed up the inserting process, still using binary search for the deletion process. And it just happened that it worked, I can't even believing why it worked lolCongrats, you are insane! GM when?
I'll try my best! Thank you \('w')/
You can see 319236013 clearly states
// Extra vector added to reduce plagiarism.Ban shubh1211
1C is much harder than 1D and 1F. that makes me have no time to solve 1F
I finished debugging my E one minute post-contest and it passed... :(
Same here... :(
Nice round over all!
Thanks to the all the staff who helps to hold this round.
Is ternary search nlog^2n is one of the intended solutions for 1C? Then why the harsh time limit, I'm so tilted rn
I also use the same time complexity in this. I use set and run 1140ms main test
Eyyy!! +60 for solving 3/6! Yeah!
Read 1D as 1693D, worked on it for 1.5h, and finally wrote the full code, until realizing I've read it wrong.
I totally forgot that, three years ago, I solved it during contest!!
Furthermore, my today solution, and the one that I wrote three years ago, are completely different!!!
I have used an ai tool to generate code for printing spiral matrix for div2-C. I am not sure if it's within the guidelines. I got the logic by myself then i used an ai tool to write the code for spiral matrix.
Its mentioned here that
If you're unsure whether a particular AI use violates the rules, please consult the competition organizers.I want to know if this use is permitted or not.
It is scrictly forbidden to use AI during a live contest for any purpose,all accounts for plagiarism
if you check the link, its mentioned that
Using AI to generate simple boilerplate code (e.g., input/output functions) is allowed.Input/output functions. As if one couldn't have them prepared before the round.
That probably counts as cheating. There is a world of difference between boilerplate code for IO (that just gets the input in a manageable form for the algorithm) than using it for the implementation of the algorithm itself.
Seeing at you submissions, it took you 30min to submit your first wrong program for C, after which you used AI (as you said in your comment) to get a correct implementation. Seeing that you found the implementation of your solution a challenge, you cannot argue that it's just meaningless boilerplate code. This is Competitive Programming, not Competitive Thinking: even though it's important to find the correct algorithm(s), finding a way of implementing them in a concise and fast way is part of the challenge. Using AI for that is, thus, cheating.
Here is a solution for Div1C / Div2E, which uses trenary search (seems to be alternative approach to what most people used).
To find optimal k, ternary search can be used. Submission: https://codeforces.me/contest/2102/submission/319299542
Can someone help me why the solution which i submitted using Set fails but one which i submitted using priority queue passes. Set — https://codeforces.me/contest/2101/submission/319668536 PQ — https://codeforces.me/contest/2101/submission/319668295
Shouldn't both take similar timings as both have TC of O(logN).
I think it's expected behavior. My solution with set got 3781 ms result and the one with priority queues — 1092 ms. I see you use 2 sets (I used 1), so it will probably need something around 7500 ms. Priority queue is much faster than a set, it's a known fact, explained by how the elements are stored (vector versus a tree, where adding nodes require frequent memory allocation). Instead of using 2 sets you can use one: remove the "back" set. Instead of
use
etc. It still gets TL (on test 9 instead of 7). I managed to get AC with another optimization: golden section for ternary search. It passed in 3200 ms: https://codeforces.me/contest/2101/submission/319685824
So, there is no bug in your solution with set. Red black tree is just generally much slower than a heap.
Just found a Random hustler the-raja who gave todays contest just for fun ,and above that he proudly boasts about in on his linkedin ,when I asked him about his apporach in D ,he replied with an AI generated response . The guy's post link on linkedin
hey_twin
damn bro
damn
Bashed 1D with sqrt + bitset: 319301576. I had like 6 bugs, so I didn't make it to the time...
Hope you reach GM soon bhai
Thanks, I hope it too...
I have $$$O(n)$$$ solution for D1.
Observation: if $$$p[1...n]$$$ is cute, then $$$p[1...{n-1}]$$$ and $$$p[2...n]$$$ are cute as well. So, we can use two-pointers to calculate intervals $$$(i, r_i)$$$, where $$$(i, r_i)$$$ is the longest cute subarray starting at $$$i$$$.
To do so, we have to maintain LIS and LDS in deque (to simulate two pointers), but notice that $$$(i, r_i)$$$ is cute, meaning that LIS + LDS $$$ = r_i - i + 2$$$ (this fact simplifies problem).
Since, we only considering cute subarrays adding $$$p_j$$$ to the back of the deque is easy, since LIS or LDS must extend by element $$$p_j$$$, and non-extending longest subsequence can only change its last element.
Deleting $$$p_i$$$ from the front of the deque is a bit harder, since it is possible for $$$p_i$$$ to be a beginning for both LIS and LDS. In this case, we can proof that after erasing $$$p_i$$$ we always can extend LIS/LDS in the front by the first element of LDS/LIS.
And the last case occurs when LIS = 1 or LDS = 1 (but not at the same time), in this situation the one having single element must change it to the last element of the other one.
My solution: 319304301
I have a different $$$O(n)$$$ solution for 2101D - Mani and Segments.
All this is possible using next greater element and prefix / suffix min / max. My submission (319283002) is $$$O(n \log n)$$$ because I calculate next greater element with a set, but it can be optimized to $$$O(n)$$$ with a stack.
It seems like there is quite a large variance in judging time that can happen; during pretests my solution for C passed in 3840 ms, in system testing it got TLE on test 9, right after system testing finished i submitted it 2 more times and it got TLE on test 9 both times, now i submitted it again and it got AC in 3718 ms. A variance of 50 ms is something I'd expect but I had no idea there could be a difference of over 300 ms...
It happened to me so. My solution to div1E(https://codeforces.me/contest/2101/submission/319279543) got TLE on pretest 97(after waiting 10mins..), but when I submitted exactly same code after systest(https://codeforces.me/contest/2101/submission/319301076), it runs in 5656ms.
MFW Problem D
OMG same!
This is for 1D or 2D? I don't see how this could be related to 2D.
Div $$$2$$$D. Just implementation of selection sort, which is $$$O(N^2)$$$
But then you throw in TREAP, and wooosh, magic magic $$$O(N \cdot log(N))$$$
For 1B, I forgot to use
long longs for counting inversions but it still ACed because overflow preserves parity :)I think several people still got WA because of this. I think they use %2 directly so for example -1 and 1 will get different result, thus they got WA.
Using
if (inversions % 2)should still AC though (since both 1 and -1 will result in true)Got wrong answer on Div1A due to wrong Spiral Printing Code on GeeksForGeeks. Somehow it prints the correct matrix for n = 2 and 3 (the sample test cases), and gives ridiculous output on n = 4 :(
maybe don't rely on others' code to solve contest problems :D
I mean it is allowed to do that. Also it was not trivial to implement so I thought, might as well take it from the internet
I found printing the spiral backwards, starting from one of the corners, somewhat easier.
Here are some of the top cheaters : [2ky], [LuOH3_] . Know more??? Add them to the list — justice awaits...
Hey what are you talking about here?
I'm talking about you. Just look at your rating graph — How is it even possible to reach Specialist in only 2 contests? And You reached Specialist in just 2 contests and solved only 11 problems in total ???
Did my code look AI generated or what?
Okay Well. But How it is possible being a Specialist in only 2 contests..??
I don't want to be rude but... Practice hard and get better I think? I can just be lucky in this case. Getting first place is unexpected for me.
I think you should just get gud, instead of wrongly accusing others for cheating.
Who knows, you might be the cheater here.
When is editorial coming out
For div1C, is $$$O(nlog^2n)$$$ not allowed? I realized we can do it in $$$O(nlogn)$$$, but this $$$O(nlog^2n)$$$ submission passes in 4.5s while the time limit was set to 4s.
use scanf or fast IO may be helpful. I passed it with $$$\log^2$$$ in 3.8s.
My $$$\mathcal{O}(n\log^2{n})$$$ solution with
std::set+ binary search (1.1 s): 319296499Using DSU instead of
std::set(125 ms): 319298390I see, basically my code calls the function twice in the binary search. Single call passes within 4s. Thanks
When solutions?
solution plz ToT
Dear Codeforces, Hello, I am jitesh66, and my solution (ID: 319249391) for problem 2102C has been flagged for similarity with another user's submission.
I want to firmly state that this is completely my original work. The logic used — spiral traversal of a 2D array — is a well-known and standard technique. It's quite natural for different participants to arrive at similar-looking implementations when solving such problems, especially when the approach is straightforward and commonly used.
It is deeply concerning that such a basic and commonly taught method has been flagged as a violation. Just because two people wrote similar code for a standard idea doesn’t mean either one copied the other. How can it be assumed that I didn’t write my own code, especially when there’s no evidence of any unfair activity from my side? Even the editorial suggests spiral traversal, and I independently figured out and coded the logic on my own.
I did not collaborate, copy, or leak any part of my code. If similarities exist, they stem from the nature of the problem and the algorithm required to solve it — not from any violation.
I request a fair and thorough review of this case. Penalizing users for applying standard techniques undermines the spirit of the competition.
Thank you.
All three of my problems for this contest have been skipped. I literally handwrote all the code and thought about the logic, investing a lot of time in it. My multiple solutions were incorrect on pretest 2, which I further debugged myself. Why were these solutions skipped? It undermines the effort I put in, and in return, I am told I copied someone else's code. Moreover, I received a notification for my problem C, but all of my codes have been skipped. It makes sense that, given the nature of problem C, implementing a spiral matrix can turn out to be a standard code; hence, it can be flagged, which is again incorrect but somewhat understandable. However, skipping the other two problems too literally makes no sense to me; that is a really wrong decision.
Kindly look into the matter. I have genuinely tried to perform well, and I don't want to be flagged as a user for no reason.
Three legendary coder for all time...
Dear Codeforces, Hello, I am deepiit.gupta, and my solution (ID: 319251371) for problem 2102C has been flagged for similarity with another user's submission.
I want to firmly state that this is completely my original work. The logic used — spiral traversal of a 2D array — is a well-known and standard technique which also has a question on leetcode (problem — 59) . It's quite natural for different participants to arrive at similar-looking implementations when solving such problems, especially when the approach is straightforward and commonly used.
I did not collaborate, copy, or leak any part of my code. If similarities exist, they stem from the nature of the problem and the algorithm required to solve it — not from any violation.
Regarding Plagiarism Flag on Submission 319255450 (Handle: Athk_0312)
Hi Codeforces Team,
I'm writing about the plagiarism verdict on my submission 319255450 for Problem C from Round 1024 (Div. 2). My handle is Athk_0312.
I want to clarify that I didn’t copy anyone’s code or cheat in any way during the contest. The solution just involved filling the matrix in spiral order, which is a very common pattern. In fact, it's the same approach used in well-known problems like Leetcode 59 (Spiral Matrix II), so it's quite natural for different people to come up with very similar-looking code.
Since the logic is straightforward and widely known, it's likely that my code ended up looking similar to others. But I can assure you it was completely my own work.
Regarding Plagiarism Flag on Submission 319274770 (Handle: agrawalheyramb)
Hello Codeforces team and reviewers,
I am Heyramb Agrawal (handle — agrawalheyramb), and my submisssion for Probblem C (Mex in the grid) is flagged for plagerism. I firmly believe that this is false positive, as I independently wrote the solution on my own. This problem can be easily solved using the standard spiral traversal of matrix. In fact, I had previously solved the spiral-matrix problem on LeetCode, which clearly predates the contest.
I am also attaching link and screenshot of my previous LeetCode solution of spiral matrix traversal. Link to Leetcode problem
I humbly request the codeforces team to reconsider this flag.
[user:agrawalheyramb][submission:319274770][problem:C Mex in the grid][contest:2102]
three legendary coder in the world for all time...!
Subject: Clarification on Solution 319260324 for Problem 2102C
Dear Codeforces Team,
I hope this message finds you well. I recently received a notice regarding my submission (ID: 319260324) for problem 2102C, which is said to significantly coincide with another solution.
Regarding this ,I would like to clarify that I did not copy any code. After i got the idea that we should take the elements in a spiral, I took that code template from GFG.. This is the reference — _ https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/_ i just modified a bit and submitted this. The approach I used is a well-known and standard method for filling a spiral matrix, which is also commonly used in LeetCode Problem (I practiced it while solving Takeyouforward sheet).
I assure you that my solution was written independently. I kindly request you to reconsider the plagiarism flag, taking into account that the approach is based on a widely known algorithm.
Thank you for your time and understanding.
My Handle : "_Hadwik_"
eren__ can you share the checker code for d1A, Mex in the Grid
Read the function f.
thanks! having a check for more than 1 occurence before counting helps