Hello, Codeforces!
I am glad to invite you to take part in Codeforces Round 1045 (Div. 2), which will start on Aug/26/2025 17:35 (Moscow time).
You will have $$$2$$$ hours to solve $$$6$$$ problems. The score distribution is listed below.
There will be at least one interactive problem, so make sure to read the guide for interactive problems before the contest.
The round will be rated for participants whose rating is below $$$2100$$$, but higher rated users are also welcome to participate out of competition.
The problems were authored and prepared by me. I would like to thank:
- SSerxhs for coordination and providing great ideas to improve the problem set.
- Alexdat2000 for translating the statements to Russian.
- Our list of testers for providing valuable feedback: StarSilk, BurnedChicken, Misuki, __baozii__, _istil, A_G, SorahISA, shstyle., ub33, warner1129, lunchbox, PaperCloud, Ali_BBN, fr200110217102, AceIn, madlogic, daniel071292, polarbear03617, XiaoXia.
- MikeMirzayanov and KAN for the amazing Polygon and Codeforces platforms.
Good luck & have fun!
UPD: Score distribution: $$$500 - 1250 - 1250 - 2000 - 2250 - 2750$$$.
UPD2: Editorial
UPD3: Congratulations to the winners!
Div. 1+2:
Div. 2:
As a tester, I think the whole problemset is awesome! orz to author for making so much interesting problems!
As a tester, detset I.
[DELETE]
usually it's friends of author,
or something similar
As a tester, interesting problems and a really good contest.
sishtir baba hamatoon hamino migid
As a participate, I think we need less interactive problems (5 in a Row!)
I like them btw but my rating doesnt
As a tester, the problemset is one of my most favourite one. Good luck, hope you would enjoy it.
Look who I found!
Speedforces?
Prophet.
As a participant, i hate interactive problems.
Good luck!! :)
I think that interactive problems are overhated
I enjoy problems that give me +delta
they are fun bro..
Why all of downvotes bro said it's overhated
Practicing interactive problems would be beneficial, especially given the performance in the last two contests.
I think, Contest will be math related. Because author is from China.
The score distribution seems interesting
I prefer interactive questions, which are more interesting than regular questions and relatively easy to add points
Is there any proper approach for interactive problems
Just flush carefully
I think I am bad at interactive problems cause I never flush
avg indian.. they dont flush
kanglu detected , opinion rejected
why interactive problem why
this is my first contest,I'm so xcited!
As a tester, I like this problemset.
When was the last time problem B was an interactive problem in a Div2?
Are problems B and C hard or medium? What is the prediction for today?
B > C
Holy Lord Jesus Mother of Speedforces!
Problem $$$B$$$ is actual cancer.
problem B requires a lot of number theory intuition, which can be really tough for people not comfortable with those stuff
problem B was that easiest if I did not come very late as I did
i would say 99% of the difficulty of B comes from finding the solution, the implementation is trivial
Yeah. You just had to think of k==1 and k == 2 differently and for the rest k, just look at k-1.
Find reminder by (k+1), let's say it is r.. then add r times k to it.. so it will become r*(k+1), divisible by k+1.. :)
I want to submit a problem but I haven't registered :((
If the writer's for the contest can't properly control the difficulty gradient of your questions, please refrain from setting problems and harm others. These rubbish rounds are wasting every participant's time!
skill issue
A reasonable level of differentiation is essential for a good tournament. It's not only grandmasters who deserve to compete; every participant should have the opportunity to compete at their appropriate level.
It's very discouraging to see your rude words.
First of all, you didn't even solve a single problem from the contest — how can you just call it "trash"? Do you know anything about the problem qualities? Authors, coordinators, and testers put endless efforts to make this round possible, but you are just staring at standings and send offensive comments. Aren't you too rude?
Actually I found most problems enjoyable and interesting. The only issue is C being too easy — that's very hard to estimate difficulty for easy problems, so it is understandable for me. All the rest problems have nice difficulties. What are you complaining about?
On one hand, although I didn't submit, I attempted all problems except F but only solved A, B, and C. On the other hand, even without solving any problems, the gap in pass rates between C and D clearly shows this is an unreasonable difficulty span (7000 to 400). The difficulty of C didn't deviate excessively from the norm, but D far exceeded the typical difficulty of a Div2D problem (it would be more reasonable to place it in the E).
i'd be moved by your words if this contest wasn't this much garbage
I agree that he was way too rude. However:
You could get green performance to yellow performance by just doing ABC. At this point what is the contest actually testing? I think DEF were master+ level problems and it sucks that they were the only other problems in this problemset after C, because they are otherwise very interesting.
I'd argue the problems are really good despite the round being horribly unbalanced. Tbh rounds like this have been a problem since I've been blue and it really sucks that otherwise good problemsetters forget that the contests are made with a target audience in mind. A div2 contest should differentiate between cyans, blues and purples, not put everyone at 3 problems.
Have you heard of pigeonhole principle?
You're either
both of which sounds incredibly stupid, especially when solve count ratio doesn't even look bad in the first place.
Furthermore, why does having same number of solve count matter when ranking is based on sum of scores instead of solve count?
I'm suggesting that div2 contests have problems that focus on differentiating div2 participants. I don't think it's crazy to say that it is expected of an expert to do ABC as much as it is expected of a green to do ABC. My point is that it doesnt make sense for DEF to be on the same div2 contest. They would individually be good problems on different div2 rounds. I do not believe you need to be particularly accurate to notice there is a big gap between C and D.
C has 20x more solves than D. This is pretty significant since this difficulty range of most div2 participants.
If you have 3/4 problems that div2 are expected to solve and 5 div2 ranks, you are practically guaranteed to run into a speedforce situation. In this case it was particularly bad because 2/3 of these problems fell under the same pigeonhole.
Maybe you could argue that the only problem was that C was easier than expected, and otherwise the difficulty curve would be reasonable. However, it is expected that they would make the problem too easy, since there were only expert+ testers, and they are expected to do C every time.
You have a fundamental misunderstanding of problem difficulty. It's not a fixed number assigned to each problem. For today's D, this 20x number could easily fluctuate to 5x depending on whether there was an easy diameter-related problem on some recent round.
It's very hard to make sense of your argument when it revolves entirely around final solve count, which is not a number that is available to authors.
"speedforce" is a word invented for the purpose of some people getting validated on codeforces comment section. Speed matters on every contests regardless of difficulty distribution as long as the contest has finite duration.
Hi, I'm not sure if it's too difficult for rated participants. I just came here to state some of the facts.
I only meant to say just counting the number of testers for a round can't be enough reason.
Anyway thanks for the contest.
Hi, thank you for the comment. Trust me, it is also heart-breaking for me to see the results doesn't match my expectations.
As for the gap between C and D, I think I made a mistake here. Originally the problem only asks for the minimum number of operations, which doesn't raise any suspicion that it might be too hard from the testing results. A few days before the contest we added the first operation output to prevent it from being too guessable (also some testers think that it is too easy for its place). I thought the difficulty would be the same, but after the modification, there are few Div.2 testers tested the round. Now I learn that problem modifications can be really tricky, and we should value Div.2 users opinion more :(
500−1250−1000−2000−2250−2750
I am quitting cp now, no more
Great D
can you please tell idea in summary ?
find a diameter of the tree as the road
what about this . is this wrong https://codeforces.me/blog/entry/145775?#comment-1304346
emm I mean moving the diameter.
find a leaf node, then just moving the diameter as the sample of D.
in this: https://codeforces.me/blog/entry/145775?#comment-1304346 we can move 2 to 6.
oh i see
the worst contest ever
someone tell me what was the logic for c about time i quit cp
Greedy! For each even index element the prev element less than or equal to it. Now try to figure out how much you need to reduce the next element to satisfy prev + next <= current.
for c not b
solve windows of length 2 (just lower the odd index to match the even one).
Then solve windows of length 3 starting at an odd index. I chose to go on windows in increasing index, but prefering to decrease the higher odd index, so maybe i'll use less moves on the next window.
All other bigger windows should be a sum of solved windows
Can anyone tell why this is giving wrong answer https://codeforces.me/contest/2134/submission/335699285 It works on my VSCode :(
Is there any specific technique to solve D, or is it observation based only??
The tree is a path graph if and only if the length of the longest path is n-1 (counting length as number of edges). Each operation can only increase the length of the path by at most one. I claim that you can always increase it by one. Find an operation that does just that.
it doesnt increase only by 1. if the graph is a-b-c and b has another subtree that is a path of length x. doing the operation a b c will increase the length by x as it will append the path to c;
It increases the longest path by 1. In your example the longest path wouldn't be a-b-c it would've been a-b->path from b of length x.
in that case yes
how to solve E
find values from right to left, consider the parity of length of segment of twos after your position
Who felt that question C was easier than question B?
Is D something like: find the vertex with the longest chain going out of it (chain -> path connected to the vertex with no other vertices connected to that path) and let it be our c, and let our a be the vertex going into that chain from c
Additionally we need to consider a special case when there is only 1 vertex with number of children > 2
The problem was standered enough.
As a contestant i really enjoyed the problems though i could solve only 3
it was fun being purple again for two days i guess
Problem difficulty goes from PUPIL to MASTER , what's the point of these half-baked rounds,wait for one or more intermediate problem and make a proper round.
Guessforces. And great gap between C and D.
Problem $$$C$$$: 8.9k
Problem $$$D$$$: 493 lmaooooo
What the hell was B & how did 10k+ solved that question?
kinda spent more time thinking for B than C... saw C quite quickly ( if I am right )
It was easy
When k is odd -> You have to just add k once to all odd values, and the gcd of overall array will be 2
When k is even -> Just add k to a[i], (a[i])%(k + 1) times, the overall gcd will become k + 1.
How did you came to the solution when k is even?
Let's consider ai = 5, k = 2. If you add 2 two times, 5 will become a multiple of 3. Take any odd number and k = 2, either you will add 2 to it one time, then it will become a multiple of 3, or two times. In case of ai = 7, just add 2 once, and 9 is multiple of 3.
Try to generalize the idea, that we can make a number mulitple of k + 1 by adding k at most k times.
Let g be the final gcd of A, we must add 0 or multiple k to make A[i] divisible by g. In other word, let r = A[i] % g, c = number of k adding to A[i], for every A[i], we should guarantee that there exists a c >= 0 where (A[i] + c * k) % g == 0. This actually means every number within [0, g — 1] should be achievable by this g which implies gcd(k, g) == 1. You can find this g by brute force in just few iterations. You can see k + 1 mentioned by other people is just a special case since gcd(k, k + 1) == 1.
It's a bit easier if you first think about how you would solve it for k = 1; Obviously the best way is to make every element even. Then, you can try to solve the case k = 2, and even though you can no longer change the parity and make elements divisible by 2, you can note that it is possible to change the remainder when dividing by 3, and thus make every element divisible by 3. From there, you can generalize to all values of k, where for each k, you make every element divisible by k+1.
someone please tell me D was NOT re-rooting DP .. because then I will know I was not on right path and I will not cry :(
BTW <500 AC for div2D ... SPEEEDFORCESSS...
it's not
ok, thanks.
the div2 problem B is tooooo hard TwT
As a newbie apart from A I couldn't solve any other question :(
Ps: Got 4 wrong answers.
keep trying .. A was tricky IMO
I could only figure out a solution to E that uses $$$\frac{3n}{2}$$$ queries on average, but I couldn't find a worst case $$$\frac{3n}{2}$$$ query solution :(
Just realized the solution ... bruh I was so close T_T
Cool E! I really enjoy it.
First, the answers for $$$a_{n-1}$$$ and $$$a_n$$$ are straightforward to confirm. We only need to perform $$$\text{throw}(n-1)$$$, $$$\text{swap}(n-1)$$$, and $$$\text{throw}(n-1)$$$.
We compute $$$dp_i$$$ as the number of jumps starting from position $$$i$$$. Since $$$n \leq 1000$$$, we can update the $$$dp$$$ array using a brute force approach.
For $$$i$$$ from $$$n-2$$$ down to $$$1$$$:
If $$$dp_{i+1} \neq dp_{i+2}$$$, the situation is simple. We only need to check whether $$$\text{throw}(i)$$$ equals $$$(dp_{i+1} + 1)$$$ to determine $$$a_i$$$.
Otherwise (if $$$dp_{i+1} = dp_{i+2}$$$):
A key observation is that $$$dp_{i+1} = dp_{i+2}$$$ implies $$$dp_{i+2} \neq dp_{i+3}$$$. Therefore, we can use $$$\text{swap}(i+1)$$$ and $$$\text{throw}(i+1)$$$ to determine $$$a_i$$$.
However, the above observation is not sufficient, as the number of queries might exceed the limit. An important optimization is needed: before $$$\text{swap}(i+1)$$$, we can use just one $$$\text{throw}(i-1)$$$ to determine $$$a_{i-1}$$$. This way, we can determine two values with at most three queries, solving the problem.
AC code
As a newbie,I want to ask for help:How D?Thx.
problem difficulty
A — 1
B — 2.9
C — 3
D — TREE(3)
nice round, i tend to think that D is harder than E
Nevertheless, the quality of the questions in this competition is very high!
Why wasn't my E approach submitted? Clicking "submit" was clearly at least 2 seconds before the end time
.
I think is not correct ... because imagine .. a very long chain.. ( so this chain will be diameter) ... no if we add another edge to any node near center... we will not slide that edge towards end of diameter but one portion of diameter over that edge
like imagine 0-1-2......50....99-100 .. now if we have 50-101 as well
we will not slide
50-101to either side that will take 50 moves.. but we can slide one part of diameter over50-101edgeno, consider 1 6 1 2 2 3 3 4 4 5 3 6
Im not sure how to read this
Tree that has three chains from node 3, two of length 2 and one of length 1. The optimal operation is moving one of the 2 length chains to the end of the 1 length. The diameter would be 3 plus the 2 length chains.
I thought "find the diameter" then slide part of the diameter onto the node not in the diameter.
This gave me runtime error on test 7 (maybe it was bad implementation, as i didn't find a counterexample to this solution, i'm not sure)
Edit:I just read the editorial, definitely bad implementation
How in C just checking subarray of size 2 and 3 is enough.
Just consider the length of 3, and make a special judgment for length 2 when n=2.
Let's consider the array is a1, a2, a3, till an
If a2 >= a1 + a3 and a4 >= a3 + a5. Now if you take array of two size let's say a1 and a2, then we already made a2 >= a1 + a3, and the minimum value of a3 can be zero, so overall a1 will be greater than a2. Now if you consider 3 size array, then a2 >= a1 + a3. If you consider 4 size array let's say a1,a2,a3,a4. Here a2 >= a1 + a3 and a4 >= a3, so a2 + a4 >= a1 + a3.
i want atto round 2 with Hamed_Ghaffari
hard D boring E
3 solved people range is too wide, but regardless of it, i enjoyed round thx :)
good contest :) but it will be better if the writer swap(problem D, problem E)...
What was the reason for the unusual output format in problem D? I can understand not forcing us to write the full sequence of operations because the implementation would be quite annoying and the fact that the number of operations is O(n) somewhat spoils the solution, but I don't see why the output couldn't just be the minimum number of operations required. Is it really because the answer being
n-1-(diameter)
would be too easy to guess?
Double on that, at least it could have included both the minima and the operation too.
That just makes people think on some random operation that might be part of the solution not thinking on the actual problem, idk how such simple thing passes over coordinators and so many testers.
WA1 sent vs judged difference is probably too big.
Sent 2025-08-26 17:50:26
Judged 2025-08-26 17:54:32
https://codeforces.me/contest/2134/submission/335630967
what would you rate the difficulty of problem B? 1200? 1300? 1400?
ig, 1300 must be fine, it just requeires some basic number theory knowledge
Can someone explain why this weird solution passes for B?
trying to make it work for primes under 100
335688760
Similar code here only
primes <= 29needed to be precise. The idea is that you just need to find a prime number that does not dividek, so that you can keep increasing each number bykuntil the number becomes divisible by the prime chosen. Update: It seems any coprime number withkinstead of a prime will work as well.Great contest, thanks!
Need to ban:
akm19117012
RustyQuantPP
skebeb
ssnaik
Dudududududududud
TejasBharadwaj
humble.fool
for problem F, and it is only first page and I am lazy(sorry)
loved that D problem. The solution is incredible even though i miserably failed finding it!! (as always)
C was easier than B.. I wasted all my time on B did not even look at C.. so pathetic.. how can I avoid doing this in future? I mean can't just go through all the problems to determine which one should I solve..
should I read all the problems with same score then decide which one I want to solve first..
If more than one problems have same score then you should definitely switch after a couple of minutes
Can someone help with the last step of C?
But then I am stuck...
You can solve the problem using just this fact: Every even number must be at least the sum of its two neighbors.
First, lets solve the problem for the first number at an even index: $$$a[2]$$$. Notice that its always better to subtract from $$$a[3]$$$ first as that will affect $$$a[4]$$$, meanwhile subtracting from $$$a[1]$$$ won't affect $$$a[4]$$$. Now notice that when we move on to the next even number, $$$a[2]$$$ is satisfied. So again its better to subtract from $$$a[5]$$$ first.
In general, it is always better to subtract from $$$a[i+1]$$$ (where $$$i$$$ is even) before you subtract from $$$a[i-1]$$$.
In problem D, I am getting
"wrong answer given tree is not a path graph, but -1 found (test case 5)"for test case 2(truncated)But 5th test case which is the last one here, it is a path graph right? As per their definition written on the problem statement.
"A path graph is a tree where every vertex has a degree of at most 2. Note that a graph with only 1 vertex and no edges is also a path graph."5th test case is
the first test case is a graph with one node
Good Round
"Sometimes the issue is not taking something as an issue…" I was considering a case but didn’t realize it was the corner case missing from my test data! Finally, I’m happy to score 3 problems, Siuuu… #CodeForces
Lucky Contest.
To get exactly 1400 with +17 and become a specialist !!!
I don’t understand such hate for problem D. If you look from afar, it is obvious that the diameter of the graph should be included in your final bambuk. And since there is no longer route than the diameter, we should move points that are not in the diameter. It was my first thought after I read the problem.
So I agree with henotrix that just answering n-1-diameter would be kind of guessable. Yes, it might look a bit strange that the output is the first move, but for problem D, just giving the minimum number would be trivially easy and not really appropriate.
I am struggling in solving B. I am not able build any intuition can anyone help how they solved it. Please
You can make all the elements of vector divisible by (k + 1) by changing their value to x + k * (x % (k + 1)) where x is an element of vector. Do this for each element and gcd has to be atleast k + 1
Yes i understood the solution using K+1 but how to get the idea during contest. i am feeling helpless from yesterday as i think if i had not seen the K+1 solution i would ever come to the conclusion. How did u get that idea???
you need not do it with (k + 1) only you can do it with any number co-prime with k (k + 1 comes to mind the earliest as it is guaranteed coprime with k). After selecting a number you just have think mathematically what multiple of k has to be added for each element to make it divisible by your selected number.
and about the intuition, If you get odd k, you can make all elements divisible by 2. If you get k = 2, you can make all elements divisible by 3. thinking a bit more you can figure out the formula
okay thanks a lot. Will try bouncing back next contest
I hope you reach specialist in the next contest
It's funny to see how the difference between top 600 and top 7000 is only the speed ppl do the first 3 problems
yea there was a rating gap between 3rd and 4th problem, but generally if you go lower you will find more with same number of problems
I don’t know why it took so long to get the verdict on problem B. It showed 'Pretests passed' about 3 minutes after I submitted the code. Also, due to the Cloudflare verification after submission, I had to resubmit the code. Please try to fix these issues.
I counted and mine took exactly 4 minutes 34 seconds
Hello, My solution for Problem C ("Even Larger") was skipped for plagiarism detection. However, I want to clarify that I wrote the code myself by following the intended greedy approach described in the official editorial:
As explained in the editorial , only subarrays of length 2 and 3 need to be considered.
The correct solution is to use a greedy algorithm that decreases elements minimally so that the condition holds.
My code implements exactly this approach: at each step, I compute the minimal possible value to subtract (mini), ensure constraints for length-2 and length-3 subarrays, and carry forward a state (prev) to enforce correctness.
Therefore, my solution matches the standard editorial method, not any copied code. I kindly request that my submission be reviewed again. problem code link (335665812)
Thank you.
Attention!
Your solution 335622185 for the problem 2134A significantly coincides with solutions MASTER_RAFAT/335621768, wwwglll/335622185. 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://codeforces.me/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.
First of all, I don't know this person, and the time between his code submission and mine was less than a minute. Secondly, this is a relatively simple problem, and having similar logic in the code is quite common. You can check all my submitted code—it was entirely written by me.