Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 1064 (Div. 1) and Codeforces Round 1064 (Div. 2), which will start on Nov/16/2025 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them in both divisions.
The problems were authored and prepared by le0n and me.
We would like to thank:
- Sugar_fan for his coordination;
- Alexdat2000 for Russian translation;
- liqingyang, ZhouYuHang for providing problems that were ultimately not used;
- Tobo, _istil, zhoukangyang, wenhao801, baka24, zhaohaikun, xcyle, _RedWine_, Bossusuprem, mzen, phir., dXqwq, songhongyi, SubgraphCounting, Seg_Tree_, Brooksx, A2_Chaos, jhgfds, Crystally, Um_nik, Friedrich, qbf, sunzihang, EvenImage, Arpa, Adam_GS for testing;
- TheScrasse, Error_Yuan and others who were invited but unable to test for reasons;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution:
- Div. 1: $$$500-1000-1500-2500-3000-4000$$$
- Div. 2: $$$500-750-1000-1500-2000-3000$$$
We hope you'll enjoy the problems!
UPD: Congratulations to top $$$5$$$ in Div. 1 and Div. 2.
Div. 1:
- maroonrk, achieving perfect score at an astonishing 01:18:30!
- JDScript0117, with an outstanding comeback at 01:55:46!
- Benq
- ksun48
- Nachia
Div. 2:
- __lucailie, with a final solve at 01:59:15!
- weertyu
- su_da
- Axiom_
- WangYuanyi
First solves:
Div. 1:
A: ksun48
B: Benq
C: OrangeEye
D: Benq
E: Benq
F: maroonrk
Div. 2:
A: f___off
B: Animesh--__--
C: lemmec0de
D: Doraemon-_-
E: Shakhzod_Toshpulatov
F: kyUUKoU
UPD: Editorial is out!
not counting this one, 5 of the last 6 div-1 rounds have had an LGM as one of the setters (and there wasn't a single LGM setter in rounds 1013-1047 before these)
Hello from the only one of the last 6 Div. 1 rounds
Round 1058 and Global 29 both had no lgm authors
Both um_nik and mindeveloped fell off i think i have a new favourite shitposter
Tested 3 months ago and almost forgot everything, can I participate?
Tested, I
Didn't test 3 months ago and almost remember nothing, can I not participate?
Help me reach -99 in contribution
how can u get that contribution?
Against all odds... he embraced the dark side of the happiness force
oh I tested
Hoping for an easy B than C this time.
As a tester, why can't I remember testing it?
hope everyone gets positive delta <3
is it possible ??
who knows???
Wow, I just saw an announcement (it poped in the middle of the website, as usual round announcements). If I'm not mistaken, if somebody missed it, it's only possible to see it after the round starts. Is that correct and if so, is that intended?
In case anybody is interested, this announcement is as follows.
General announcement
Hacking is disabled in problem A-D (in div. 2). In problems A-D, system tests are equal to pretests; in problems E-F, system tests are equal to pretests plus hacks.
I think I saw it about div1, so I guess there are 2 of those. Mine said A-B has hacking disabled and everywhere pretests = systests (+ hacks if possible).
I think DIV2C is same as DIV1A based on Score distribution
My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064.
Wow I can see PinkieRabbit
hi
Best of luck everyone!!! Hope you increase your rating :) !!!!
Vote up if you think the problems are nice.
can someone check div2 B, simulate the test case 1 iteration number: 6,7,9. upon simulation answer comes out as 6,5,6 yet in the answer of the testcase it shows differently.
Same for me, simulation showing different answer then the actual answer for 5 5 6.
u should close the page from the back
You can click on any tab
The order of the variables change. In the input, it is a, b, n. On the simulation it is a, n, b.
I have mastered the art of speedforces
wow you solved in around 20 min... so fast ... what rank you got ?
I got rank 800+ 15 minutes before end, after contest end it's already systest.
It said 900+, but that might be wrong.
ok, congrats for top 1000 and being so fast !!!
$$$C$$$ is such a shit problem. 4k solve difference between $$$C$$$ and $$$D$$$ in Div2. Speedforces Shit round.
Nah the implementation was fun
div2B is a strange problem for me, it cost me 20min to solve it :(
30 mins for me :/
In my opinion, D2C / D1A was way to easy to guess
can you please tell wat did you guess ?
I just took the sum of every consecutive pairs and subtract it by the pair w/ the largest max and it passed, no idea why tho
ok, cool, hope editorial will give us more insight
so D2C is a DP ?from a worthless mid schooler-_-!
no its greedy
greedy
no, you just take away the pair with the smallest maximum every time, can be done with sets/priority_queues
how do we know this is best .. I guessed same but without proof
Consider x < y < z, if we first take (y, z) with a cost of z then we will have to take another (x, z) with cost of z which makes the answer 2 * z, but if we take (x, y) and (y, z) that makes x + z which is smaller than 2 * z, basically we want to remove smallest numbers using smaller maximums
ok thanks
You can prove it by comparing the process to the Kruskal algorithm.
The only weird thing is that when you add an edge and remove it from the graph, a new edge is created (so the graph is "changing"). But this edge has a weight greater or equal to all the weights you have already added, so you are still adding them in the right order and you get a MST.
oh wow!! what a creative way to look at it ...
thanks for sharing
The general approach is to first prove that the answer is no less than a certain value, and then construct a valid scheme to demonstrate that this value can be achieved.In this problem, we first disregard the cyclic condition and define b[i] = max(a[i], a[i+1]). The answer cannot be less than the sum b[1] + ... + b[n-1], because the larger of any two adjacent numbers must contribute at least once. Then, we can construct a sequence of operations to demonstrate that this value is indeed achievable.My code
ok, thanks for sharing your ideas !!
I'm like the only person that uses linked_list in the server.
really? only can use ai and ai+1,the priority_queue would shuffle the order
I forgot that we also have to delete additional pairs so priority queue won't work efficiently, I used set in the end, but the point was that we keep pairs of those, not individually
You can also maintain $$$\text{left}[i]$$$ and $$$\text{right}[i]$$$. Initially, $$$\text{left}[i] = i-1 \mod n$$$ and $$$\text{right}[i] = i+1 \mod n$$$.
Then you can handle deletion of index $$$i$$$ by setting $$$\text{left}[\text{right}[i]] = \text{left}[i]$$$ and $$$\text{right}[\text{left}[i]] = right[i]$$$.
When merging $$$a_i$$$ with $$$a_{i+1}$$$, you delete the index of the minimum value and insert the new edge into the priority queue.
I did that too! I think that it is the easiest way.
I used divide and conquer + Sparse Table to find the position of the maximum element
us but segtree
I spent a lot of time on this problem during the competition but still couldn't solve it. In fact, I overcomplicated it. All I needed to do was calculate all the expenses first, get a total expense, and then subtract the largest one. There was no need for a priority queue or anything else. I felt like crying when I realized the truth. (╥﹏╥)
I actually ended up finding an O(n) solution — since its a ring you can just rotate the array so that the maximum is on the side and then just find the sum of the maximum of all adjacent pairs in your rotated array: 349299008 (In the comment where I wrote "max of difference" I meant "max of pairs")
speed forces ... so many quick solves till
div2Cbut thendiv2Dhas less solvesI like the visualization for
div2BI don't think 1B/2D is that easy.
I got no ideas for D .. need to work on counting I guess!!!
For D I had an idea, but it was already too late to implement it :(
Get an array with the amount of occurrences of the numbers and sort it decreasingly. a1 >= a2 >= ... >= ak What I got is that for each i, we can get the following amount of multisets that exclude elements which would come from a_j, j < i:
a_i * (Choices(a_{i+1},...,a_k) — (#choices with < a1 — ai elements))
Then, the sum would be the answer. For the testcases it seemed to work, at least.
I don't know about others, but for me personally, problem E was obvious, I came up with it after reading it, and I spent some time on problem D, but I couldn't pass it during the round (although I came up with a rough solution).
Undoubtedly, E is far easier than D.
idk if only I felt it but problem B was way too tricky..
yeah felt same... I guessed that answer can't be more than 2 ... only then I made some progress.
Yes, implementations are easier than thinking the logics.
D2E uses very similar idea to 2147E - Maximum OR Popcount
explanation for d1, sir
Problems are great but why not 3h duration? I don't think 2h is enough for this round.
Personal complaint: I can pass 1C if I have 3~5 more minutes...
3 hour contests are usually div1/div2 contests with 8 problems, not contests with 6 problems, and at least in my case, the extra hour would probably just end up with me staring at 1D with no ideas whatsoever for one more hour.
Is D1D a Kuhn-like algorithm?
I tried my best on D but couldn't come up with an approach, can someone hint it please.
Div 1 D reminded me of this recent problem + solution. Took me some time to make sure this is similar enough to apply a similar algorithm.
why the hell did it not remind ME of that solution? :(((((
You guide others to a treasure you cannot possess
Thanks for gifting the solution to us kind sir, it was literally my fastest solve today all because of you.
at some point i will have to stop posting comments to start gaining rating…
I actually have you in my friends list and when I saw that was the first problem you solved I got more confident (:
Thank you for "getting me to red rank"
To me, d2E is quite easy but d2d is a little bit harder:(
Can you provide a hint for D2E? Please put it under a spoiler tag.
My observation was:
Only the largest 30 elements of $$$a$$$ were relevant.
Intuition: We need to look at the highest bit and use a number to satisfy this highest bit. We use the biggest number to achieve this somehow.
Let query be $$$q$$$. Iterate those biggest elements $$$e$$$ starting from the biggest:
See 349330720.
Thanks! I had a very similar solution, except instead of putting
e ^ (1 << firstbit)back into the queue for reconsideration in case 2, I was trying to find the largest submask of $$$q$$$ that is $$$\le e$$$. 349323998Can't agree more
approach for C , hint ?
I just simulated the process by eliminating the smallest remaining element, and merging it into its smallest neighbor. Note that since the element getting eliminated in the current round is the smallest, its neighbors will be greater than or equal to it.
how to do index as if one value is deleted it stays in vector : 4,1,1,1,5 -> 4,1,5 but in vector its 4,-1,-1,1,5
Maintain two arrays of length n:
You can reason about why $$$prev$$$ should be initialized with $$$[n-1, 0, 1, \dots, n-2]$$$, and $$$next$$$ with $$$[1, 2, \dots, n-1, 0]$$$. When processing the element at index $$$i$$$, we can eliminate it by doing 2 reassignments: $$$next[prev[i]] := next[i]$$$ and $$$prev[next[i]] := prev[i]$$$.
You can see my implementation.
ohk similar to doubly linked list.
solve the problem for a linear array first, then your answer will be the linear solution ignoring the largest interval (cost is largest element) of the circular array.
There is a 1 for-loop solution for this problem dsu isn't needed
hint for linear solution: consider the minimum contribution any element can have to an optimal solution
A, B, C resembles a Div. 3 problem
2D(1B) was an awesome difficult problem. It took me so long to reduce the problem into a knapsack variant tho.
Same for me. It was very satisfying to get the correct output on the first run. I reduced it to:
Find the sum of product of all the subsets of the freq array such that the sum of the subset is >= max freq. Here freq is an array of frequency values of distinct elements in $$$a$$$.
My approach is pretty much a negated version of your solution.
How does D1C/2E make it to the contest?
What's wrong with it? My only complaint is that D1B and D1C should be swapped, but that's a placement issue, not a problem issue.
Does that imply it was overrated for its difficulty? I think D2D is too easy to be a D2E.
How to solve problem D? Couldn't clearly understand the problem, like what does modes mean?
I wonder how many AC 1C would have if the same idea didn't appear in a recent round (https://codeforces.me/contest/2147/problem/E )...
As an author of that round, the first thing I did was to open my code from that round to see what ideas I could reuse, but it is not that similar.
Estimated time for the rating to roll out?(I'm quite excited)
amazing round! I spent around 45 minutes on B (lmao), then i solved greedly C using dsu, and I came up with an idea for E literally 2 minutes after the end
There is a possible wrong test case in Problem B — Tab CLosing.
In test cases 6, 7 and 9 the output given is 1, 2 and 2
Whereas the output according to the visulaizer given in the problem is 6, 5 and 6 respectively.
The output of my solution is also 6, 5 and 6 for these test cases respectively.
349309302
Problem link — https://codeforces.me/contest/2166/problem/B
The answer cannot exceed two, first close the right tab without moving, then close the left tab without moving
Love the efforts you all make to create such high level questions :)
cant authors see ritesh_3822 submissions time... bro submitted till E in 39 mins with codes like huge submitted in 2mins.. do authors even see submissions of top people or people who are writing in their blog..
did authors cant see who are they putting in their blogs like many of div2 first solvers or div2 5 top participants are cheaters .. they can see their submissions.
Is it only me or 1C is much easier than 1B?
I agree, solved C much faster than B
Agreed, the conclusion in 1C that "only the top 30 are useful" is immediately obvious, whereas it took me a while to figure out the conclusion for 1B.
I want a rollback… maybe it will turn my 1996 into 1200 points
I solved div2(C) using a decreasing Monotonic Stack. First time I've gotten to implement this in a live contest!!!
guys i am in love with div2 C(div1 A problem)(cyclic mereging) i also made a video on that go check it out (not here for views(i mean i do but) literally i loved that problem so i wanted to make https://youtu.be/hcCuCJHx_OY ;).
thnx to (leon) and all the problem setters.really enjoyed it:)
User ajmahim2020
During today’s contest Codeforces Round 1064 (Div. 2), the system skipped your submission for 2166A - Same Difference.
"It seems that you didn't understand the logic of the problem. In your first submission, your answer was skipped. After 3 minutes, you sorted the string and submitted it again, which wasn’t necessary. If you had written your first submission by yourself, you wouldn’t have done the sorting."
The reason i am writing because you did the same in Codeforces Round 1061 (Div. 2) in 2156A - Pizza Time.
You are copying code from somewhere or something like that in contest. you breaking contest rule and destroying the fairness.
If you submit 2 correct submissions to the same problem the system will skip the first one automatically.
In my opinion I think its pretty reasonable that someone might do this and I wouldn't say its conclusive evidence for cheating.
if you check you would see both of my code is correct.so focus on your pregress.get a life bro.
Wow Speedforces and I got +42 delta
A hint for 2F/1D?
Try to firstly match the smallest numbers with it+1
is your idea different from reducing the problem to bipartite graph (as some comments above and in editorial) ? could you give more hints ?
I believe that user weertyu is an AI cheating user. The variable names in his code are very similar to those of AI. They are composed of both lowercase and uppercase letters, and the variable names are long and complex.
He weertyu has different I/O methods for each problems solved in the contest.
Problem A — Uses builtin normal scanner with no custom made template.
Problem C — Uses buffered reader and print writer but no helper methods of template, parsing the values each time taking input
Problem D — creates custom class FastReader as in template to read input but uses builtin System.out.println() to print the output.
Problem E — uses custom FastReader input but uses PrintWriter for output.
In a single contest, using 4 different I/O methods is suspicious.
i love codeforces
I love codeforces
Is Problem C genuinely difficult, or does it only seem hard to me?
It's not difficult, it's just tricky. If you get the approach, you'll do it; otherwise, you won't. I also couldn't solve it but I believe it's still easy.
After seeing the solution, it feels like the question was really easy all along.
Kinda late to the party but I would like to add my two cents on div2(c) solution. My idea is if we look at the maximum element in this array than the element to the right of it has no choice but to make the pair with its right one. Because if it were to choose left one the anser would always be non optimal as the left one is the biggest. Now if we have the array as:
a1, a2, a3, a4, a5....an
and let a1 be the largest than a2 makes pair with a3. Now the smallest of both is replaced. Our answer will always contain max(a2, a3) because at some point a2 has to pair with the one at its right. If a3 < a2 than cost a2 will happen. Even if a3>a2 than cost a3 has to happen as only someone bigger can remove a3. I think this part is a bit fuzzy so I would appreciate if someone can complete my proof of why this actually works.
Can someone tell how can one comeup with the solution to problem c div2 from scratch like what things should one try after looking at such a problem.any general problem solving principles that turn out to be handy (please dont tell go practice,i know that is important but there is more to it than just practice)
After looking at problem I realized that to get the minimum sum, I would have to make sure to merge the largest element at the end. I thought that it would require graphs or linkedlist where I have to recursively solve the question but if you just add all elements before the largest element in reverse order and then all the elements after the largest element in reverse order, you would get a list of elements in an anti clockwise cyclic order. Then just compare every 2 elements and add the maximum of the two to the sum and at the end add the max element.
for the example:
7
1 1 4 5 1 4 1
we exclude 5 and then have a list which is [4,1,1,1,4,1], sum=4+1+1+4+4=14 and add the max element and we get sum=19
Solution when？
Everyone is saying that C was very easy , but I am still not able to understand the main idea behind the solution . The n.log(n) solution specified in the editorial is using linked list which we usually avoid in cp and also I am not too comfortable with data structures as I am still new in CP. I saw another solution where we store max of all possible adjacent values and then sum the smallest n-1 of those which does give the answer. But the prove behind that is still unclear and also how will one intutively think about it.
Also I have been practicing CP from usaco guide and cses , are these resources sufficient to excel in CP and particularly on CF.
where is the tutorial ?
https://codeforces.me/blog/entry/148452
The editorial for Problem Div2D/Div1B is unclear. Can anyone explain, plz?
In the Second question of Div2, add this testcase a = 10, b = 25, n = 2 and check how many would have got wrong submissions.
I was cheated by divccc,he sat nearby and copy my code when I go to the toilet,NOW my score has been DNF
[deleted,idk who stole my account]
for problem C
If two adjacent x and y are equal can we choose where we merge x and y? for example 1 2 2 2 1 -> 1 2 2 2 or -> 2 2 2 1
For Div2C, does anyone know why working in reverse does not work? For example, greedily building the input array from the maximum element.
https://codeforces.me/contest/2166/submission/361319091