Hello, Codeforces!
I am proud to invite you to Order Capital Round 1 (Codeforces Round 1038, Div. 1 + Div. 2), which will be held on Jul/19/2025 17:35 (Moscow time).
The round will be rated for everyone. You will be given 7 problems and 2 hours and 15 minutes to solve them.
All problems were authored by me.
I would like to thank:
cadmiumky and TheScrasse for coordinating the round,
Radewoosh, arvindf232, errorgorn, Adam_GS, Errichto, -XraY-, Marcin_smu, Rafi22, SergeiFedorov, Markadiusz, Dragos, VadymKa, freak93, Andrei_ierdnA, NemanjaSo2005, fwitt, ToxicPie9, madlogic, Porumb, ivgechu, stefdasca, tibinyte2006, lIlIlIlIIll, trraian, Buek, larush, lev1106 for testing,
Alexdat2000 for Russian translations,
MikeMirzayanov for Codeforces and Polygon.
Score distribution:
| $$$500$$$ | $$$1000$$$ | $$$1500$$$ | $$$2000$$$ | $$$2500$$$ | $$$3250$$$ | $$$4000$$$ |
And now, a few words about today's sponsor!
Order Capital is a team of engineers and researchers with a deep passion for algorithms, clean code, and well-crafted solutions. Many of their team members have a competitive programming background — with roots in ICPC, IOI, IMO, Code Jam, and Hacker Cup — so hosting their own Codeforces round is a particularly exciting milestone. They specialize in building high-performance systems for algorithmic trading, where every nanosecond matters.
Here’s the founder’s welcome post in case you missed it — plus info on current openings.
Considering joining the team or doing an internship? Hit the link and fill out the form — they’d love to hear from you!
🏆Prizes & Surprises:🏆
- 1st–4th — 1000 USDT
- 5th — 800 USDT
- 6th — 700 USDT
- 7th — 600 USDT
- 8th — 400 USDT
- 9th — 300 USDT
- 10th — 200 USDT
But that’s not all.
Top 10 — guaranteed, plus 20 lucky participants ranked between 11 and 200 will also get our surprise merch boxes!
Good luck, have fun, and don’t forget to apply if you're looking for your next challenge!
UPD: Editorial is up.
As a tester, congrats cadmiumky on his first coordination!
As a tester, I recommend 👍
that's what testers always say...
Test
.
i need merch
As someone who never buys shirt, I hope the merch is shirt
wow problem difficulty curve will be very steep if there are only 7 problems, hopefully not a speedforces round
We're flying with this one
order a -Cap1taL-
is there a certain cutoff one needs to perform upto in order to be considered for the intern offer?
After 2 years, Polish round!!!
is it just me who saw that the logo seemed like a woman instead of a whale like it looks just like a French woman.
edit I didn't mean it as an offense just that it was like an illusion or something. Like the Olympic logo but sideways IDK
2095H - Blurry Vision
I've been trying to see it differently for the past $$$10$$$ mins, but all I see is a whale. Can you please describe/outline the French woman?
Like you are watching her from the side and the white color are the hair and the black color is the face shape, it’s not that much of a resemblance but it looks a head.
Honestly it does kind of look like an old woman. I'm not sure how you see a French woman there, unless you think that French women are not very attractive.
I hope that this is what you were talking about. I have drawn in a few features to make it easier to see. I'd suggest everyone reading this to rotate the actual image, as the original is much more terrifying.
No no I said French because it was like the Olympic logo in Paris By the way you locked in fam 2000 elo gain in 2 years is crazy.
Well, i don't see the whale, all i see is the woman lol
Score of problem D is 2000, is this mean that D would be more difficult than usually?
seems like that...
yayy!! a div 2 contest after such long gap
Hoping some positive delta after few drawback.
hoping to reach specialist again
As a nontester, I hope I will become a pupil again!
I have never given a div.1 + div 2 contest before. How is it different from a standard div.2?
Me too
I think you don't need to think about it .. just treat it like a normal div2 contest from your side .. the only thing is that the scoreboard will have div1 people also, so your rank might be a little lower than normal overall if you look at it mid contest.
But as a div2 coder we do our normal stuff, nothing changes.
yeah
div.1+2 is just basically a global round where div1 people also participates...
what is the expected difficulty rating for problem c and d
Check clist.by/problems you can find the expected ratings of the problems there.
Is it going to be speedforces?
Not ready but let’s see how it goes. Hope it’s not a speedforce lol
I think so
Hoping to perform well and break into Specialist.
good luck
Hope to get IGM. Just 23 points away.
Upd: Failed to debug E and is getting -ve delta. :(
oh wow good luck. I can only dream to reach there one day.
I'll get rated today. How exciting is it!
Hope to solve at least 2 problems. Good luck everyone!
pathforces
greedyforces
Loved the problems
nvm
oh wow... how do you know this is going to happen ?
use carrot chrome extension.
upd: for you it's showing -98 man :'(
Hello friend, i am using carrot extension with google chrome, but it is not working for me, it always show an error on the extension
What kind of browser you are using? upd: it worked with me for 3 years maybe, but now it is not
it was also not working with me but i tried removing and again installing ..then it worked for me
guessforces
people need to learn this isn't discussion space before contest ends.
Speedforces?
How to solve D?
Edit: The proof is wrong
You will have to wait at most $$$d$$$ seconds at a node of degree $$$d$$$ to move to a specific adjacent node of your choice, so the max possible time is sum(d) = 2 \cdot nSo just solve as dp[current time][node] = min time spent waiting. There are only 2 transitions from each state so this runs in O(n ^ 2) time.Code — 329875705Isn't the max possible time $$$n \cdot (n - 1)$$$ then?
Hmm, you're right, my proof doesn't particularly make sense but it passes pretests so either they're week or through some optimal magic there always exists a path which uses at most $$$2 \cdot n$$$ even when the degree increases.
To be absolutely honest, I came up with this proof after getting AC lol. I managed to get AC by guessing that the answer would be bounded by number of edges / total degree (after being unable to think of a way to solve it otherwise). So when time upto $$$n$$$ got WA, I just re-submitted with $$$2 \cdot n$$$ which passed pretests, lets see if it passes system tests :P.
So your solution works in $$$O(ans1 * n)$$$. Assuming that $$$ans1$$$ is quite small than this solution works
So we can find $$$ans1$$$ with BFS then we can find $$$ans2$$$ with dp described above
Code: 329882266
if that's the case wouldn't the solution be O(n^3),
Idk who is right though.
I am not sure I understand your explanation. $$$\sum n = n^2$$$, not $$$2n$$$? My explanation involves considering the shortest unweighted path from $$$1$$$ to $$$n$$$ and observing that no two non-adjacent vertices on this path could share a neighbor (and thus the sum of degrees on such a path is at most $$$2n$$$). I will be happy to learn whether there is a simpler way to see this.
Could you explain it in a bit more detail, like if the path looks like this a-b-c, then a and c have a common neighbor?
Fair. I meant common neighbours except for the ones on the path itself. Let me phrase it in a different way: every vertex in the graph is a neighbour of at most two vertices from this path.
If it's not too hard, can you tell me if I understood you correctly: the shortest path then should at most consist of 2n changes of vertices? For example if a path was a-b-a-c, then the changes would be 4
(the editorial for the problem corrected me. it is actually not $$$2$$$ neighbours but $$$3$$$.)
the shortest path clearly cannot contain the same vertex twice so i don't know what a-b-a-c is. let $$$F$$$ be the set of vertices on the shortest path from $$$1$$$ to $$$n$$$. i am saying that for every vertex $$$v$$$ in the whole graph, $$$v$$$ has at most $$$3$$$ neigbhbours in $$$F$$$. it is true that otherwise $$$v$$$ would be a shortcut, and the path wouldn't be the shortest. from this claim, it follows that the sum of degrees of all vertices in $$$F$$$ is at most $$$3n$$$.
Umm in the 2nd example we go 1-2-1-3-1-4? Or did I misunderstood something again
i am not talking about the answer. i am just talking about the shortest path in the graph (like found by bfs).
Thank you for your patience and clarifications:DD, sorry for such bother
Did this exact thing and got MLE.
You can replace with 32 bit ints which take ~200MB and get AC.
If we always have to wait d seconds at a node of degree d, then wouldn't the max possible time be bigger, i.e. M? Or am I missing something?
is D ad-hoc?
aaaahh !! couldn't figure out C ... I will get negative delta..
how to solve it? I tried to find farthest point and remove them ... but I am not sure if I was correct.
Real. Got cooked so hard on C ;-; Someone who solved, please tell how to solve?
The idea is this:
start with 1-D, what do you observe?
the left half can only connect with the right half
expand the idea to 2-D, there are 4 quadrant
bottom left <-> top right
bottom right <-> top left
no need to worry about how many in each quadrant,
with some proof I forgot already it will balance.
noooooo !! I had this idea but I couldn't prove that it will balance out :(
What happens if the input contains points from only one quadrant, or if we run out of pairings across quadrants and are left with points in just one quadrant?
it means you chose your quadrants wrongly, you need to move the x-axis or y-axis to make it balanced. it should divide x into 2 groups, and y into 2 groups, it will be balanced.
I think it's best to wait for editorial, I'm not sure how to explain my idea.
If you're still confused give me counterexample, I'll find the balance.
The general idea is that you have to pair all points with the "high" x values with all the points with "low" x values (where high are the upper half and low are the lower half), and do the same for y. It can be proven that such a separation is always possible because of symmetry of low and high points (there are as many low y points as high y points) and you just have 4 groups: low x low y, low x high y, high x low y, high x high y, and you map low x low y to high x high y and low x high y to high x low y.
This is the best solution because if you write out the result as a sum all points with "high" x will be added, all with low will be subtracted and analogically for y
aaaahhhh !! I had a similar idea but couldn't prove it .. darn it.
Lets say we have 2n points, we sort them by x. Then if in the first n points we have k "high" y points (ones that are in the first half of the sorted array when sorted by y), then we have n — k "low" y points in the first n. But since there are n "high" points total, the second n points have n — k "high" y points and k "low" y points so it always pairs perfectly as a result.
Here is a general outline of the proof that it works. It turns out that the sum of differences will be actually the same as if we solved the problem on x and y independently which is quite cool in my opinion.
ok, thanks for the explanation.
No problem :)
How does this work with duplicates? For example if the highest low x value and lowest high x value are the same.
they can be both in the same group or in different group, doesn't matter
if you divide the coordinates sorted by x in half, and only make pairs between the first half (with lower x values) and second half (with higher x values), no matter how you pair between the sets, the total amount of x distance is fixed. if you make any changes within these constraints, the amount of x distance you lose from doing one pairing is gained by another pairing, so the total is constant. then you have complete freedom to pair by y extremes, as long as you make pairs between coordinates of each set.
so are you saying sort by
xand just pairiwithn-i??sort by x and split the list in half. then pair the extremes of y.
if you agree that after you sort x and split in half, the total x distance is fixed for any pairing, it becomes clear that the best solution is just to pair the extremes of y as it gets reduced to a 1D problem.
It's 1D case. In 2D case we divide this into 4 groups and match the opposite
yeah it is mind blowing to me that it works ... I tried to think in this direction but couldn't make it work :'(
I tried a bunch of methods like different metrics, choosing first and last, first and half, in pairs, nothing works. I have no idea what's the solution
same lmao :(
I literally was trying batshit and then submitted in last 5 min another random solution wanting to atleast pass first test and passed everything :|
oh wow!!!
B did me bad.
I got very confused too.. but then I was able to work with the assumption that transfer is possible, so I only worked with piles which had excess items
Thank you for the contest!
The problems are fun.
Though some statements seem a bit too terse.
This was my first contest here! it was a good experience.
Cancer contest.
In problem B, I misunderstood "the top element of any pile" as "any number of the top elements of any pile" and lost Master :( Is this new problem solvable?
lol i made the same mistake
All I know is the upper bound will be lower
Uncalibrated difficulty, poor statements, poor test case. Unfortunately, I did not enjoy it
In problem C, how can we prove that generating quadrants by dividing at the middle x and y coordinate individually will result in an equal number of points in diagonally opposite quadrants?
did you get AC with this.. I was thinking about this but couldn't prove that it will give clean division as you mention.
Passed pretests at least — 329822824
Note that points with x / y coordinates at the quadrant axes may need to be moved in either direction to ensure we have an equal number of points on both sides.
ok, thanks... hope editorial will make it clear for me.. I will upsolve this tomorrow.
good luck for your system test.
There are $$$\frac{n}{2}$$$ elements in the lower 2 quadrants. Similarly for the 2 left quadrants. Say there are $$$k$$$ points in the lower-left. Then there are $$$\frac{n}{2}-k$$$ in the lower-right and $$$\frac{n}{2}-k$$$ in the upper-left. The counts match so you can match the opposite quadrants. Similarly for lower-left and upper-right.
Lets say we have 2n points, we sort them by x. Then if in the first n points we have k "high" y points (ones that are in the first half of the sorted array when sorted by y), then we have n — k "low" y points in the first n. But since there are n "high" points total, the second n points have n — k "high" y points and k "low" y points so it always pairs perfectly as a result.
If you divide them into quadrants, then if you pair points with opposite quadrants, you can see that the x moves as much as the x coordinate of the middle x and the same for y, for all points, which gives maximum overlap.
Because, if you pair points in corresponding opposite quadrants, then distance between the two points would be |x1| + |y1| + |x2| + |y2|, which is maximum possible for any given point.
Cool problem G, my differential equations exam was only a month ago, didn't expect to need it so soon
However, what's with the tight time and memory limits for problem D? You make one too many $$$n^2$$$ size arrays, and it's over, and for some reason I had to rewrite deque as a static array to get into time limit (though changing compiler also could've sped up my code, but still, that is not something the contestants should think about). With ML it's as if someone didn't bother to change the default 256MB in polygon, which is rarely used now
I think the ML was intended to cut away O(N^2) memory solutions (at least I hope so, otherwise it is in a really bad spot)
You just do the standard trick of maintaining only 2 dp states and look at "active" edges for each vertex separately.
I see. My solution didn't look like a dp, but it can also be implemented in linear memory. But ML is still enough for 2 $$$n^2$$$ size arrays of ints and then a bit more, so it did not actually cut away anything, just made life more frustrating.
"Tight" limits on D probably just mean the authors had a more efficient solution. E.g. if you have solutions like the one below, you would not think that the TL/ML are tight.
(memory usage is O(N + M))
I think it's the problemsetter's job to think of different solutions and make it so that each one either can't pass and it's clear from the constraints that it can't pass, or can pass comfortably.
Here I didn't notice the memory limit (which is my bad, true), since in most tasks it is either enough for everything or it's explicitly stated in the statements that ML is lower, than usual. If the authors intended for only linear memory to pass, it would've been easy to make $$$n \le 10^4$$$, which is less normal to see for problems with $$$n^2$$$ memory
Actually, nevermind my complaints about D, I just realised that my proof of my solution was incorrect. I assumed that there is never a need to enter any vertex $$$n$$$ seconds after the first possible time to enter it.
Now I think that it's just incorrect, if anyone can hack my solution, I'd be very greatful
Successfully hacked :)
Thanks a lot!
Yeah, the intended solution should be super simple, straightforward DP. You're right that 5000 x 10000 x 2 ints don't fit into 256 MB, but I think optimising O(memory) is an ok part of programming problems just like optimising O(time), as long as it's taken into account as part of problem difficulty.
why frozen?
Bro, I was only a specialist for one day XD.
Can anyone explain C? How can we sort?
first sort by x
then 1-n/2 sort by y
n/2+1 — n sort by y
pair i with n-i-1
proof??
1 Every optimal solution pairs left–right. Sort points by $$$x$$$. Call the first $$$n/2$$$ points L and the rest R; for all $$$p\in L,\;q\in R$$$ we have $$$x_p\le x_q$$$. If an optimal pairing contained $$$(p,q)\subseteq L$$$ and $$$(r,s)\subseteq R$$$ with $$$x_p\le x_q\le x_r\le x_s$$$, swapping to $$$(p,r)$$$ and $$$(q,s)$$$ (or $$$(p,s),(q,r)$$$) strictly increases the $$$x$$$-distance sum while leaving the $$$y$$$-part non‑negative—contradicting optimality. Hence every pair must take one point from L and one from R.
2 Ascending + descending maximises the $$$y$$$-part. Let $$$y_{L_1}\le\dots\le y_{L_{k}}$$$ (ascending in L) and $$$y_{R_1}\ge\dots\ge y_{R_{k}}$$$ (descending in R) with $$$k=n/2$$$. For any bijection $$$\pi$$$, consider
If two indices $$$i \lt j$$$ violate the “asc–desc” order—i.e. $$$y_{R_{\pi(i)}} \lt y_{R_{\pi(j)}}$$$ swapping $$$\pi(i),\pi(j)$$$ never decreases $$$Y$$$ (triangle‑inequality exchange argument). Repeating swaps yields the asc–desc matching, which therefore maximises the $$$y$$$-sum (rearrangement inequality with absolute values).
3 Combine: overall maximum. All cross‑half matchings share the same $$$x$$$-sum $$$\sum_{i}(x_{R_i}-x_{L_i})$$$ (non‑negative and fixed). Step 2 gives the largest possible $$$y$$$-sum among them. Therefore the pairing $$$(L_i,R_i)$$$ with L ascending, R descending maximises the total Manhattan‑distance sum, completing the proof.
My English isn't very good. I used AI translation to organize my thoughts. I hope it's helpful. Please point out any issues.
Will we get lightning fast editorial??
guys is it possible to solve D using BFS + priority_queue?
priority_queue has a log factor which will give TLE due to really tight TL/ML
very poor statement in A
took a lot of time to understand
i also think so
+1, i didn't understand around 20 minutes
Hello! Will the solutions to the problems be posted?
I thought d was easy until i see sample test cases
very Nice and short problems E was very nice but shit D and C
How to solve C?
editorial is out, we can check there.
ok, thanks for reminder!
D was great, dk how to solve it tho ToT
How do you solve B?
if there are too many 1s in one of the stack, the amount of extra 1s AND all of the 0s above it need to move. if in a stack, there are too many 0s, AND the 0s above it were not already forced to move because there were too many 1s in the stack, we need to also count the amount of 0s we need to move.
keep track of the total for every stack. we do not need to consider cases where a stack has too little 1s or 0s because this stack will receive 1s and 0s from another stack having too much
because it is given that solution is possible you only look at piles which have excess of values
so if we have excess 0 ... we can transfer all of them in 1 move each
if we have excess 1.... wee need to bring that excess on top .. to do that we need to shift the 0s on top to bottom ( the decision we make here is to choose state of 0s on top when it is minimum like if need extra .. we first push all zeroes to bottom then shift 1 .. and then bring in extra 0s because other wise we will do more steps to bring up one )
we can ignore piles which have less than required number of values because it is give that problem is solvable that means one of the steps we did in previous states will fill the required values.
https://mirror.codeforces.com/contest/2122/submission/329877188
I got WA for not caseworking 5 vertices out at the end of loop :(
Does author have better solution than 332 vertices, or is the constraint supposed to be super tight?
Most submissions use under 320, some even close to 300.
I somehow deluded myself that the points couldn't be paired perfectly in C and the contest was doomed afterwards. I need to get more sleep...
Same, I tried pairing points in opposite quadrants with respect to x-axis and y-axis. But, of course there was no guarantee that there wouldn't be leftovers, so eventually changed this approach.
Bro exactly my first apporach was this to pair w.r.t to x and y axis and when found this is incorrect then completely left this idea and moved to greedily solve this question
grrrr and it turns out that E was completely free since it doesn't have a hard-to-find proof like D!! (not that I actually found it lmao)
rip my GM :((
C was very bad to me.
How to do G? It seems like it's an OEIS problem..
Yes, if you generate the answer sequence and then divide by some factor depending on $$$N$$$ you'll get:
https://oeis.org/search?q=1+26+66+26+1&go=Search
Wow, those actually are just eulerian numbers again. I wonder if there is a combinatorial way of showing that
Someone tells me that the answer to problem D <= 3n. Is it true? Why?
Is there a precedent classic problem that uses similar solution to C? If not, I would think this is the most disgusting problem I have ever written. Do you really think that to guess such conclusion is interesting?
This is a good problem. Plus, I proved before AC...
To prove that the upperbound is always possible, sort all points by $$$X$$$ coordinate. Change their respective $$$Y$$$ coordinate to $$$0$$$ or $$$1$$$ depending on if that $$$Y$$$ coordinate is in the first or second half of the array if we sorted by $$$Y$$$ coordinates instead of $$$X$$$. We can do this since we don't care about the actual values. Now, we essentially have a binary array $$$A$$$ of length $$$N$$$, and we must create $$$N/2$$$ pairs of indices such that for each pair $$$(i,j)$$$, the following conditions are satisfied(assuming 1-indexed), $$$i \le N/2, j \gt N/2, A[i] \neq A[j]$$$.
This is always possible because the number of zeroes and ones in the array are equal. Say we have $$$X$$$ zeroes in the first half of the array, then we know for a fact that $$$N/2-X$$$ ones are in the first half, and therefore $$$X$$$ ones and $$$N/2-X$$$ zeroes are in the second half. So we can easily match them.
Hoestly speaking, it's not about proving. I have to come up with an idea or a solution before I prove it correct. But this idea is based on what? Is it a classic trick or an intuitive reasoning? I don't think so. So this idea just comes from nowhere, and most likely I will never apply it in the future, but yeah, it definitely ruined my whole day. So, FUCK THIS PROBLEM
It's a common trick in competitive programming to think of obvious upper or lower bounds and try to prove (possibly with some intuition) that it could be achieved (something like wishful thinking or extremal principle maybe).
For example, my natural thought process to this problem: "What's the best possible answer? It's when the X and Y coordinates are solved independently. This is just 1D version and I can solve that easily. Trying some few examples it seems I can always match in such a way that I get that upperbound. Now how to prove that it's always possible...".
What I'm trying to say is that a good intuition (sharpened by solving lots of problems) will take you far in CP, and now you know for example that this method of solving could be used in future problems so this problem wasn't a waste : )
Thanks for your reply. yeah, i will try to do more codeforces problem especially math type lol
I remember solving some problem on Manhattan distance earlier. Some of them get really intuitive and easy if we just think in 1D! That's exactly what I thought here. If I completely ignore y, then I can simply sort according to x and pair them up like 2 pointer(e.g. x[1].p with x[n].p, x[2].p with x[n — 1].p and so on...) to make the distance maximum. I think it's a pretty good idea to start with. At least, helped me to think 2 dimensionally!
I though of 1D first but I realize that in 1D, for example, if there are n number and I sort them, x[1] with x[n], x[2] with x[n — 1]... is the same to x[1] with x[n / 2 + 1], x[2] with x[n / 2 + 2] ... becasuse the distance between x[1] and x[2], the distance between x[n — 1] and x[n] are calculated both once, and the distance between x[2] and x[3], the distance between x[n — 2] and x[n — 1] are calculated both twice, and so on. So I gave up transfrom from 1D to 2D. I try to calculate the contribution of every distance difference in X / Y respectively, but it's too complicated. I try to relate to quadrant, like 1 with 3, 2 with 4, but didn't work. I notice that |x| is noly 1e6, and think maybe I can do something about it. But obviously it's not a big thing. I can't even think of a method that enable me to pass the testcase#2. I even try to think something like bipartite graph, starting from the closest pair and divide them into two different groups. Perhaps it's because I haven't solved enough math problems so I can't think of such idea. Recent contest didn't go very well for me so this problem really makes me frustrated. Still thanks for you guys' reply, I will try to do better.
..
Can someone hack my O(n * m) for D. 329857388
Someone please tell me why o(n) solutions are TLE for q(b). I got it accepted only with fastio, how stupid is that supposed to be
No it doesn't (mine is O(n))
remove fastio, it will fail mp
C needs a mathematician to solve it, not a Competitive Programmer :(
Real
haha，guessforces...
Yeah, I got 4 "Wrong Answer on pretest 1" and had no idea so I gave up.
Maybe Problem C isn't really friendly to Newbie. :(
C isn't friendly for a CM also
Thank you for F! And for the contest in general.
And for G I guess, but I was too bad at math apparently
I have a doubt regarding problem A. I gave a submission which basically prints no if the matrix is 2x2 or if n or m is 1, but if the matrix is 1x4 and the values are 2 3 1 100 then the greedy path would be 2 > 3 and stops there because 1 < 3. But the maximum value path extends all the way, so my submission is wrong, but it got accepted anyway. Can anyone explain to me what's happening?
At first, I thought so too, so I got wa. But in fact, the greedy path will extend all the way to 100 because it actually takes the larger value of the two optional positions, that is, comparing the values on the right and below rather than comparing the current position and the values on the right. So when n=1 or m=1, the greedy path will cover all the grids.
For problem C if it was 3D points, the maximum manhaten distance , is
we sort array X we sort array Y we sort array Z
then catch maximum n/2 element from each of them and substract minimum n/2 elements from each of others?
No, here is a counterexample:
$$$(0, 0, 0), (1, 1, 0), (0, 1, 1), (1, 0, 1)$$$
Ideally you would want to add the 1s and subtract the 0s, giving you $$$6$$$ in total. But no matter how you pair up the 4 points, 2 of the last 3 will be paired up, and their common 1 will cancel out, making the answer $$$4$$$.
I hate programming. I hate CP. I hate Codeforces.
have some trouble for problem A: when the grid is 2 * 2:
1 5
3 4 the max is 1 -> 3 -> 4 = 8, but the greed path should be 1 -> 5 = 6, why the answer is NO?
it has to end at bottom right, so 1->5->4 = 10
I see. I misunderstood the problem statement, thinking it had to be a value greater than the current position. lol. thx
why i am not able to see my rating
Hi, thank you for the great contest — I really enjoyed it! However, could you please clarify why the time limit is being exceeded for this code(problem B)? The code was accepted during the contest, but now I see it's getting a Time Limit Exceeded verdict. It feels a bit too strict for what seems to be a reasonable approach. Is there something specific expected in terms of optimization?
Use this ios::sync_with_stdio(false); cin.tie(NULL);
Same issue.
You can try changing vector to just a single int.
and use std::ios_base::sync_with_stdio(false);
11
I was too scared of the job application to participate
Disappointed my python solution to D didn't make it link. I don't think anything would suffer if the timelimits were a bit more lenient.
D is a very good problem if you have to prove it. But this is GuessForces :(
The proof is hard but wonderful, I think it's about *2600 (please tell me you have an easier way). But I just guessed the answer won't be too big and then got the accepted result. I think a lot of people guessed the solution correctly, but they weren't sure if it's right or not, so they didn't submit it.
Maybe it will be a nice problem in MO?
You don't have to guess it and it's not that hard. You need to intuitively understand that more edges tend to give shorter paths and set out proving from there, or generate many smaller graphs and observe the worst-case on them with a slower solution, or you can even "hope that tests won't be too strong" which happens surprisingly often with such hard to achieve facets of problems. Seems you just got stuck overthinking.
Here's one simple enough proof: a rough upper bound on time is min(sum of vertex degrees over any path). Let's take a path that achieves this minimum and split it into 3 parts with large (greater than $$$N$$$) degree sums. The left and right part have a common neighbour; we can replace the middle part by this neighbour and improve the degree sum this way.
That's great, thank you!
1199 twice now :cry:
gamegame = taeyeon_ss.
Proof:
Same templates, same coding style
Non-intersecting active participation in div1 contests in last year
use of the unusual variable "frog" 273190195 328043527
Please ban one of the accounts.
Which one should be banned?
Thats upto staff, not me. The rule I believe is the lower rated account however.
Seems he frogot to follow the rules!
I have returned from 1596.
Please if someone could tell where i went wrong in my approach for D? i got the min time correctly but not the wait time. thanks!
(got cooked so hard in B and C that i decided to move to D altogether)
Although it is too hard for me, buts the problem is really good
yayy another speedforces round, became specialist
who can tell me how to solve B question
If I could have been the first, how wonderful it would have been for me.
Question C was the one for the majority population to get rating booster or be where you are
No
how to participate ?
in Problem B when i submitted my solution without adding below two lines i got tle why its so?
Subject: Appeal for False Plagiarism Detection — Problem 2122C (Submissions 329867017 & 329877332)
Dear Codeforces Coordination Team,
I am writing to formally appeal the plagiarism verdict against my submission 329867017 for problem 2122C, which was flagged for significant similarity with user Devesh7701's submission 329877332. I respectfully request a reconsideration of this decision based on the evidence and arguments presented below and make the contest rated for me and reroll any kind of rating changes.
Summary of the Issue
My solution was flagged as matching with another user's code, despite being developed independently using standard competitive programming approaches. The similarity stems from the elementary nature of the problem's solution path, not from any form of collaboration or code sharing.
Evidence of Independent Development
1. Submission Timing Evidence
2. Code Analysis — Standard Algorithm Implementation
Problem 2122C requires a straightforward sequence of operations that naturally leads to similar code structures:
Required Steps: 1. Read points into a vector with index tracking 2. Sort by x-coordinate 3. Split into two equal halves 4. Sort each half by y-coordinate
5. Output pairs in the specified manner
My Code: ```cpp
include <bits/stdc++.h>
using namespace std;
struct Point { int x, y, ind; };
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while (t--) { int n; cin >> n; vector<Point> coor(n); for (int i = 0; i < n; ++i) { cin >> coor[i].x >> coor[i].y; coor[i].ind = i + 1; } sort(coor.begin(), coor.end(), [](const Point &a, const Point &b) { return a.x < b.x; }); vector<Point> left(coor.begin(), coor.begin() + n / 2); vector<Point> right(coor.begin() + n / 2, coor.end()); sort(left.begin(), left.end(), [](const Point &a, const Point &b) { return a.y < b.y; }); sort(right.begin(), right.end(), [](const Point &a, const Point &b) { return a.y < b.y; }); for (int i = 0; i < n / 2; ++i) { int ind1 = left[i].ind; int ind2 = right[n / 2 - 1 - i].ind; cout << ind1 << " " << ind2 << "\n"; } } return 0;} ```
Other User's Code: ```cpp
include <bits/stdc++.h>
using namespace std;
struct Point { int x, y, idx; };
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while (t--) { int n; cin >> n; vector<Point> points(n); for (int i = 0; i < n; ++i) { cin >> points[i].x >> points[i].y; points[i].idx = i + 1; } sort(points.begin(), points.end(), [](const Point &a, const Point &b) { return a.x < b.x; }); vector<Point> L(points.begin(), points.begin() + n / 2); vector<Point> R(points.begin() + n / 2, points.end()); sort(L.begin(), L.end(), [](const Point &a, const Point &b) { return a.y < b.y; }); sort(R.begin(), R.end(), [](const Point &a, const Point &b) { return a.y < b.y; }); for (int i = 0; i < n / 2; ++i) { int a = L[i].idx; int b = R[n / 2 - 1 - i].idx; cout << a << " " << b << "\n"; } } return 0;} ```
3. Key Differences Indicating Independent Work
Despite the algorithmic similarity, our implementations show clear evidence of independent development:
indvsidx,coorvspoints,left/rightvsL/R4. Why This Algorithm Convergence is Inevitable
Standard Competitive Programming Pattern: This problem follows a textbook sorting-based approach that any experienced competitive programmer would naturally implement. The constraints of the problem leave virtually no room for algorithmic creativity:
struct Pointios::sync_with_stdio(false)andcin.tie(nullptr)5. Simple Template Structure
Both solutions use a minimal, standard competitive programming template without complex or personalized headers. This lack of distinctive template features contributes to the similarity, as we both: - Use
#include <bits/stdc++.h>(standard in competitive programming) - Use basicstruct Pointdefinition - Apply conventional fast I/O setup - Follow standard main() function structure6. Consistent Coding Style Evidence
My previous submissions demonstrate a consistent coding style that matches this submission: - Consistent variable naming patterns (
indrather thanidx) - Similar formatting and spacing preferences- Comparable struct definition styles - Standard template usage across multiple contests
Declaration of Independent Work
I solemnly declare that: - I developed this solution entirely on my own using local development tools - I did not share, publish, or leak my code through any online platform (Ideone, GitHub, Pastebin, etc.) - I have never communicated with user Devesh7701 or any other participant during the contest - I did not use any AI assistance, code generation tools, or external help - I can provide additional verification materials if required (local environment screenshots, browser history, etc.)
Request for Reconsideration
Given the evidence presented above, I respectfully request that the Codeforces team:
The similarity between our codes reflects the elementary and standard nature of the required algorithm, not collaboration or cheating. In competitive programming, especially for problems with straightforward algorithmic requirements, such convergence is not only possible but expected.
Supporting Documentation
I am prepared to provide additional evidence upon request, including: - Screenshots of my local development environment - Browser history logs showing no access to code-sharing platforms - Detailed explanation of my problem-solving approach - Analysis of my historical coding patterns
Conclusion
This case represents a false positive in plagiarism detection — a well-documented issue in competitive programming where standard algorithms naturally lead to similar implementations. I have provided substantial evidence of independent work and request fair reconsideration of this verdict.
Thank you for your time and consideration. I look forward to your response and the opportunity to resolve this matter fairly.
Respectfully submitted, [DIAMONHEAD13] SANKALP JAIN
--- *This appeal is submitted in accordance with Codeforces policy as outlined in http://mirror.codeforces.com/blog/entry/8790*
As a tester, congrats ntherner on his first coordination!
Congratulations to winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.
Very nice c . Nice concept
DIV 2
Great contest, thanks to the authors!
Why do I get TLE on test 9 although it seems O(n). Also is muy logic incorrect and if yes then why is it passed on first 8 tests.