Hello, Codeforces! Or, as we like to say in Romania: Poți să îmi dai link la rundă în privat să testez?
We are proud to invite you to Codeforces Round 1051 (Div. 2), which will be held on Sep/17/2025 17:35 (Moscow time).
The round will be rated for participants whose rating is below 2100, but higher rated users are also welcome to participate out of competition. You will be given 6-7 problems, one of which will be divided into a subtask, and 2 hours to solve them.
The problems were authored by anpaio, tvladm, MateiKing80 and by yours truly.
We would like to thank:
rolandpetrean waipoli Turcavid tibinyte2006 _istil Tudy006 mircea_007 madlogic Non-origination AlanSkarica ToniB andrei_C1 AleXutzZu __baozii__ cherryk -firefly- Andrei_ierdnA NemanjaSo2005 KALARRY chromate00 octa_bos A_G CatsAreCool Proof_by_QED khba InRainbows wuhudsm usuyus and welleyth for testing,
Orzify for orzing the round,
Alexdat2000 for Russian translations,
MikeMirzayanov for Codeforces and Polygon,
You for participating in the round.
Score distribution: $$$500 - 1000 - 1500 - (1750 + 1000) - 2500 - 3000$$$
Good luck & have fun!
UPD: Editorial is published: https://mirror.codeforces.com/blog/entry/146526
UPD2:
Congratulations to all the winners!!!
Div. 2
Div. 1
As participant, Hope everyone positive Delta
expert now?
ayda, expert olub qurtarammadin de sen de. xD
Doesn't this clash with CodeChef Starter contest?
I wonder if there is a positive side effect of having fewer cheaters in the CF round because of that.
I think cheaters will give both rounds at the same time. Hoping for -ve delta for them.
As a tester, I tested one more round (other than this) that is in the current contest list.
just one?
brooooooo
As a tester, it's my first time testing!
As a tester, it's my first time being a tester.
As a tester, I did NOT commit several warcrimes in the former Yugoslavia. I think the contest is really fun and the problems are really well-made.
easy one
As an author, I was told to farm contribution
As an author, we got carried
As a tester, the problems were so nice, I had to solve them twice
after getting negative delta in previous rounds, I am here with hope of getting good performance and getting back to expert.
best wishes to all.
good luck to you!
thanks !!!
First wednesday usual time rated contest in years?
As a participant, I hope there aren't any math problem
Bruh, if you have a pen, or pencil, and a paper list, then you can solve math, i know that TOOOOOO hard to get pen and paper, but if you want to get + rating and be Pupil like me, you should learn. And, the school giving you a "base" in math, so that not like "EZ!!!!!", but not hard like two-dimensional DP.
...Plz don't downvote my comment, i don't want to be with -60 contribution :(((. And don't disilke because i say: "DP hard" :(((((
This is just not my strength. I struggle everytime a math pb append, but I can solve easily more complex DP problems (btw, I was pupil, It's just a div2 full of maths pb that downgraded me)
To be fair, you have 30 problems solved total. You should probably try to practice math problems between context if you hate them so much, then you will get used to them (especially since, for pupil, you don't really need to solve ABC, just AB)
Yes exactly bro! If you have learnt it and know the basic implementation then math based questions seem easy, I can even do a few 2DDP Questions but when it comes to Binary Search I will quietly sit in a corner and cry like a child.
omg Romania mentioned!
Drum bun, drum bun, toba bate, drum bun, bravi români, ura! Cu sacul legat în spate, cu armele-n mâini, ura!
As a participant I hope Real Madrid wins UCL this year Hala Madrid!
uefa chopped league? anyday
mes que un club
Visca Barça, visca Catalunya
"Can you give me the link to the round privately so I can test it?"
Hope I will reach pupil in first time.
i hope you will!
All the best to everyone
It’s really tough when Codeforces and CodeChef schedule contests at the same time. Can’t participate in both properly
orz guest_ducbao_
Still looking for a contest without __baozii__. He's a great tester, yes but damn I don't think anyone has tested this many rounds in a row.
By the way is Orzify an account created SPECIFICALLY for this post?
As a tester, I'm totally sure that participating in the contest is better than playing FACEIT
Can someone help me with dp problems, what would be the best resources to learn from and any specific problemset to practice from. Thanku
cses.fi This one has great problems, and there are tutorials online to help them solve:
Tutorial 1
Tutorial 2
already mentioned
cses problemsyou can look at
atcoder dp contestbut dp problems on
leetcodeare very good for getting in lot of practice, you can filter problem based on tag and then sort them based on difficulty ... you should start with problem with editorial so that you can upsolve if you can't do it yourself.thanks a lot for guiding .
after today's D1 and D2 I should also practice DP .. :( :(
Hoping for fun problems and reaching specialist :)
anpaio is it hard__?(yes or no)
romania number one in coding
hard contest
Two things:
1) How so many submissions on C man wtff
2) How so many submissions on D1 man wtff
EDIT: WTF MY RANK DROPPED BY 600 IN LAST 7 MINUTES?????!!!!(2816 -> 3400)
Three letters — GPT
Problem $$$D$$$ is a beautiful problem but it cost me a headache and a half to get the DP transitions right.
Good problems and good contest, thanks for the round LucaLucaM anpaio tvladm MateiKing80 and all testers.
do we need fenwick tree to solve D2?
what was the idea for Di got we need to avoid subsequences with lds>=3.
yes, any subsequence with ids >= 3 is illegal.
and thats all? all the subsequnes avoiding it is good or any more condition
yes, I wrote a O((2 ^ n) * (n ^ 3)) brutal force to check it and it's correct hahaha.
It's iff. Consider a graph on n vertices and an edge between i and j iff it is an inversion in the array. You can even be brave and direct the edge i->j if i < j and vice verse.
Observe first that the graph is transitive (if u->v is an edge and v->w is an edge then u->w is an edge). Since this creates a conflict, 321s are not allowed.
Hence 321 => inversion graph is not 2-colorable. Now suppose there are no 321s then clearly there are no larger odd-length path skips either. (Since any odd length path skip has a 321 by transitivity) so the graph IS 2-colorable in this case.
Your sequence is good iff it has no 321 subsequence.
My idea was to DP the number of subsequences with LDS 1 and 2.
Sadly, I ran out of time :(
Good contest Overall , Don't know why I stucked on B for long although it was so easy after it clicked , C was simple topo qeustion , D was good literally took so much time .
Hope getting blue in next contest.
How C?
here , you have to arrange edges according to ( x , y) if (x>y) then v -> u otherwise u -> v .
and then traverse according to indegree if indegree is zero then that particular node doesn't have to take tension of any node so assign maxm remaing val to this position .
1->2 -> 3 | | 4 5
here 3,4,5 have indegree 0 so we can put any value at this positions according to their parent and (x,y) . decrese indegree at also after processing nodes . finally you will have your ans . // this is text
A question cooked watermelons today
Bro why couldn't I complete A holy hell
WA pretest 6 in D1 (╥_╥)
couldn't even solve problem A, submitted 6 wrong submissions, all failed on pretest 2.
real
How to do C?
Think of topological sorting. Try to create a directed graph with the corresponding x and y values for each edge.
yeah tell how edges form according to x and y ??
if x > y, an edge forms from u to v
otherwise, an edge forms from v to u
if x>=y then edge is from u to v
If the value of x > y, then create a directed edge from u to v. Else create directed edge from v to u. Apply topo sort then.
Notice that it is always better to take the largest one from x or y. In lieu of this,
Construction 1 : If i < j, then we add a directed edge from i -> j if the corresponding x is equal or higher else we add a directed edge j -> i;
Now, notice that if we perform a topological sort, and always assign the node with indegree = 0, the maximum number(multiple indegree = 0 can be assigned in any order), then we obtain the optimal sum. This is supplemented by the fact that the resulting directed graph must be directed acyclic, while simultaneously always achieving our above stated fact.
Since it always exists and achieves our fact through construction, we are done.
For each edge $$$(u,v,x,y)$$$:
Since the original graph is a tree (no cycles), these constraints form a DAG.
We can then do a topological sort and assign values $$$1 \dots n$$$ in topo order.
Yeah
deleted
How to Approach Problem C ?
Use the idea of topological sorting. The core idea is : the graph is undirected and it's a tree, hence acyclic. So, u can sort it topologically in a way that gives the maximum answer.
so 1st idea is you can always choose max number from the pair ..
so you can create a directed graph from the tree.. edge direction is decided by which number from the pair you choose
now toposort order of that graph gives you the answer, just assign 1 to n in order of topo sort.
Thanks for your reply.
At this rate I should stop giving contests and just study until I can solve C
Same man, I am struggling with C in every contest, don't know how there are so many submissions for C, its so demotivating...
Screencast with commentary
D1+D2 = 2750, E = 2500, F = 3000 is an insane scoring distribution. E is amazing though.
No way 6k ppl know topological sort. I haven't even heard of it before this round. GPTforces man
Damn, it was topo sort?
Also, you DP looks like a a jumping goat if you dont focus.
Another comment said topo sort, idk fs cus I didn't get it My dp for D was bad, but I don't get D anyways
Did u do C without topo? the 6k would make more sense then
I couldn't solve C. So don't know, I was conjuring a DP solution for C. Failed miserably after 40-50 min and gave up.
I was talking about your profile picture looking like a goat not question D.
Oh yea when it's small it looks like a goat, I see a bunny though
It's my cat, but it uploaded upside down for some reason and i'm not bothered to fix it
You can solve it without topological sort, if you do an "inorder traversal" on the tree by visiting all of the children with lower value than the current node, then the node itself, then all of the children with higher value than the node. Then the nodes are ordered from 'smallest' to 'largest'. Still surprised that 6k people solved the problem, I found it pretty hard.
I guess that makes a bit more sense then thanks
You just basically described the way of finding top sort)
You're right... lol but maybe some people who don't know topological sort, could still come up with the solution I used?
I really loved today’s contest! It wasnt too easy or too difficult. Also, it’s my first time solving Problem C in a Div 2 contest! :D :p
Very unlucky round for me. But the problems are good.
The round was good overall. I was curious what it would be given such a good Romania performance at IOI.
can you please share neat observation for A, I struggled with it a bit... ( actually I didn't read input was a permutation, then I was able to do something based on maximum in each step )
I kinda just counted the number of peaks, if you have more than 1 postive peak, you cant transform. And if you have even 1 negative peak, you cant transform. I just check for both these conditions.
oh cool ... thanks for sharing this observation.
not sure why I am struggling with div2A lately :(
Simpler solution for D.
D is to count subsequences without 321.
Blog
Vedio
How to solve D1 & D2?
for D1 find number of subsequences with lds<=2
Yeah, okay. So I found the number of subsequences with LDS = 1; But, how do I find the number of subsequences that have LDS = 2?
ok thanks
arent you a tester?
yes, but i didn't really looked through chats about solution :)
here is my idea for D2(I finished my code 1 minute after the contest). here is my submission: 339160589
A subsequence is good if its inversion graph is bipartite, which is equivalent to saying it can be split into two increasing subsequences. This means that when we build subsequences element by element, each new element can either join the red chain or the blue chain, but always respecting increasing order within each chain. The dynamic programming transition is simple: if we put the new element in red, it must extend a subsequence whose last element in blue is smaller, and vice versa if we put it in blue. To count these efficiently we use two Fenwick trees, one for subsequences ending in red and one for those ending in blue, which allow us to query how many subsequences can be extended with the current value and then update with the new states. Starting from the empty subsequence, we process all elements this way and the final accumulated total (taken modulo 10^9 + 7) is the number of good subsequences.
do you need to construct the tree for C to get $$$O(n\log n)$$$?
It can be done in $$$O(n)$$$ with by constructing the tree.
The key idea of this problem is to decide, for each edge, which endpoint should receive the larger value in the permutation in order to maximize the contribution. For an edge $$$(u, v)$$$ with values $$$(x, y)$$$, if $$$x \gt y$$$, then we want $$$p_u \gt p_v$$$ so that the edge contributes $$$x$$$; otherwise, if $$$y \ge x$$$, we want $$$p_v \gt p_u$$$ so that the contribution is $$$y$$$. This naturally creates a set of directional constraints between vertices: when $$$x \gt y$$$, vertex $$$u$$$ must be assigned a larger number than $$$v$$$; when $$$y \gt x$$$, vertex $$$v$$$ must be assigned a larger number than $$$u$$$. Once these constraints are set, the problem reduces to finding a topological ordering of the tree that respects them. The topological sort guarantees that for every edge the endpoint required to be “greater” appears later in the order and thus receives a larger permutation value. Finally, we simply assign values $$$1$$$ through $$$n$$$ along this order, ensuring all constraints are satisfied and the sum of contributions is maximized.
here is my submission: 339111975
D is literally this if we can identify it
Count subsequences that do not contain a strictly decreasing subsequence of length 3 or more.
Can anybody help me debug my code for B. It failes in pretest 2. I used greedy solution to sort cost array in descending order and voucher array in ascending order. Than I pick the smallest voucher and jump to the smallest element with the cost in the group.
You need long long for ans.
oh no I have doen #define int long long so all my ints are long long
This may be wrong when $$$n \lt k$$$.
But k has a constraint that 1<=k<=n so that won't be a problem
Wait. Where did you find that constraint.
Oh no my bad. There was no such constraint. I confused the other constraint for b[i] with this one.
sigh...I come up with logic of an answer quite nicely but when I go to code it why do I f*ck up so much? Should I do implementation practice.
Implementation is important. To gain rating, you need to code correctly and fast. But I'm not sure if some specialized training on implementation is needed, there are rarely problems with heavy implementation on Codeforces. Maybe the best way to avoid making mistake is to make them, and be careful when facing similar situation next time.
Between, your solution for B will be correct if you change this line.
Is there any way to solve D2 with a standard segment tree implementation? I had to copy-paste the fenwick tree implementation from cp-algorithms with 20 minutes left on the contest, because I couldn't find any other way to avoid the TLE.
Just build segment tree for each row and each column. $$$O(n^2\log n)$$$ should be fast enough. Your solution with fenwick tree sounds like $$$O(n^2\log^2 n)$$$.
I wrote a segment tree implementation just like that(https://mirror.codeforces.com/contest/2143/submission/339133001), but it didn't seem to work even after optimizations. I'm pretty sure both of my submissions had time complexity O(n^2 log(n)), though.
The time limit is really tight, we'd better not use modulor here. My segment tree finally passed with some optimizition. code
if u build 2 diff seg trees for row and column how do u synchronize them ?
All updates are for single points, so we can update on both its column and its row.
oh noooo T____T
For $$$C$$$, I just guessed that it's always possible to take $$$max(x, y)$$$ for every edge and did $$$BFS$$$ from leaf nodes and did some casework on $$$u, v, x, y$$$ and assigned values greedily and it passed lol. I have no idea what topological sort is :)
whatever you did, you discovered topo sort !!!
Yay!
noooo !! didn't see C is topological sort..so tried to code it myself and made 1 WA ..
also D looks like nice DP which I couldn't figure out. I think we need to find
count of subsequences with longest decreasing sequence having length < 3you don't need to topo-sort. You can kind of start on any node , but just reverse the constraint on edges if your going in opposite direction
if u -> v then x,y
if v -> u then y,x
i think I understand what u saying, because it is a tree..
shouldn't we start with a node which as 0 in-degree ?
This works because its a tree.
Greedy proof: You can always assign some value to a node to take best of (x or y) of an edge. This decision will not affect other nodes ( because its a tree ).
If lets say i give some value to a node 1 . I can always give values lesser or greater to my neighbors to get the best from these edges .
This works because what ever value I give to my neighbor wont affect each other (might not be the case for a graph)
For the start assume you can give any value to a node , later normalize it to bring it under the permutation constraint
ok normalization in the end will make it correct, thanks for sharing the idea
is there a simple $$$O(n ^ 2)$$$ solution for D2? I had to use fenwick trees for half of my transitions from D1, and it was painful to implement
I did implement a O(n^2) code(2 mins after the contest ended lol), but couldn't submit it. Not sure if it's correct.
Half of your transitions need fenwick, but all of my transitions need fenwick :(
Enjoyed solving A,B,C, but I feel super sad knowing I’m going to get a huge negative delta -_-
if you solved 3 problems why negative delta..were you very slow in submission ?
Only C was slow, but I’m using an extension called CorrectIt, and last time it showed –56
oh ok ... best wishes .. it seems I might also get small negative delta :( :(
Thanks bro, good wishes for you too. The main reason C was slow is that I solved it in a really weird way, so I spent a lot of time while debugging
C >> D1
The pattern a_i > a_j > a_k is not real. It can't hurt you.
The pattern:
Plz give solution of A I am a absolute beginner
if you can find index such that it is less then both of its neighbours then ans will "NO" else "YES". (a_i-1 > a_i && a_i+1 > a_i)
Tight constraints for D2. In contest Segment tree solution gets a TLE but passes by Fenwick tree (used gpt generated conversion) code
E is the easiest problem I have ever seen for a while... However I don't know why my rank always decreases :(
Loved this round, I'm an Expert again!
C was great
It was great
Dear Codeforces administrators,
Regarding my solution 339112959 for problem 2143C: I would like to clarify that I independently implemented a standard topological sort (Kahn’s algorithm) for this problem.
The similarity with other submission arises because: – The algorithm is a well-known, standard approach for such graph problems. — All input variable naming is taken from question itself and from standard algorithm (n, u, v, x, y, din, g) – The graph construction (by comparing x/y values and assigning edge directions) follows directly from the problem statement, so many solutions naturally look alike.
I did not share my code with anyone, nor did I use any public online compilers or platforms that could have leaked my solution.
I kindly request you to reconsider this flag, as the resemblance is a consequence of the common algorithmic approach and not due to intentional code sharing or plagiarism.
Thank you for your time and understanding.
Regarding Similarity Allegation on Submission submission:339093124
Hello everyone,
I recently received a plagiarism warning regarding my submission 339093124 for problem 2143A in Codeforces Round 1051 (Div. 2). It was flagged as being very similar to another submission by [user:Anurag_2314] submission ID 339128344). I would like to clarify my side and provide some context.
1. About the Other Submission It was mentioned that the code by Anurag_2312 339128344 looks very similar to mine. I would like to point out that: That user first submitted a different version of the solution, which was accepted. Later, they submitted another version whose implementation looks closer to mine. The resemblance is a result of the straightforward nature of the problem, not copying.
2. No Intentional Sharing or Copying I want to make it clear that: I did not share my solution with anyone. I did not copy code from anyone. I have never uploaded my contest solutions to public platforms like Ideone (with public access) or GitHub during/after contests. Any similarity is due to the simplicity of the problem and the limited number of natural ways to implement it, not due to collusion or leakage.
Final Note I respect Codeforces rules and contest integrity, and I am always careful not to engage in any form of unfair play. Given the above explanation, I kindly request the moderators to reconsider this plagiarism strike and remove it from my account, as the similarity arose only from the straightforward nature of the problem’s implementation.
I kindly request you to reconsider this flag, as the resemblance is a consequence of the common approach and not due to intentional code sharing or plagiarism.
Thank you for your understanding.
Dear Codeforces administrators,
Regarding my solution 339126451 for problem 2143C: I would like to clarify that I independently implemented a standard topological sort (Kahn’s algorithm) for this problem.
The similarity with submission [339149501] arises because: – The algorithm is a well-known, standard approach for such graph problems. - All input variable naming is taken from question itself and from standard algorithm (n, u, v, x, y, p, adj) – The graph construction (by comparing x/y values and assigning edge directions) follows directly from the problem statement, so many solutions naturally look alike.
I did not share my code with anyone, nor did I use any public online compilers or platforms that could have leaked my solution.
I kindly request you to reconsider this flag, as the resemblance is a consequence of the common algorithmic approach and not due to intentional code sharing or plagiarism.
Thank you for your time and understanding.
`2143A - All Lengths Subtraction it is purely coincidence that mine and someone else's solution got matched. I haven't used any compilers like ideone(where code is publicly available) too and also I didn't even know the other person with whom the solution got matched. also I have submitted the solution earlier. This is a mere coincidence, I understand that it is not ethical to provide code for someone else or use someone else's code. Please reconsider the flag. Thank you.
Hello,
My submission 339093124 for Problem 2143A in Codeforces Round 1051 (Div. 2) was flagged for similarity with [user:Anurag_2312]’s submission 339128344. I would like to clarify:
No Sharing or Copying – I have never shared my code with anyone, nor copied from any external source. I also do not use public compilers/platforms (like Ideone) where my solutions could be exposed.
Order of Submissions – I submitted my solution earlier. The other user’s later submission resembled mine only because the problem is straightforward and naturally leads to similar implementations.
Pure Coincidence – Any similarity is coincidental and due to the limited number of ways to solve the problem, not plagiarism.
I respect Codeforces rules and contest integrity, and I kindly request reconsideration of this strike.
Thank you for your understanding.
Hi there, I want you all to see the following 3 submissions which I found on Question C solution of many accounts.
339121255 339118543 339119152
I saw complete similarities in all these codes so I am letting you know if you also think there might been some kind of plag or any thing similar kindly take appropriate actions