2122A - Greedy Grid
Solution
Bonus
2122B - Pile Shuffling
Solution
Bonus
2122C - Manhattan Pairs
Solution
2122D - Traffic Lights
Solution
Bonus
2122E - Greedy Grid Counting
Solution
Bonus
2122F - Colorful Polygon
Solution
Bonus
2122G - Tree Parking
Solution
Bonus
Thanks for the editorial. B gave me cancer.
hahaha. you are not alone.
I was hacked int last 2 minute becuase tle......
I'm sorry that I hacked you.
i also get cooked in b although just one thing i had left in a which helps me to not solve the problem
what are the hospital bills
Does this paper essentially solve F?
dang
thanks for quick editorial.. although I got cooked in this round by problem C
Thanks for the fast editorial :)
D is a good problem but it's too hard for a div.2 D.
yeah only around 500 people solved it even when div1 is included, if we see previous div2 contest .. more than 1000 people are able to solve D.
I have another approach and it wasn't not working, however it had a correct complexity. In my approach I had both MLE and TLE, and it was implementation heavy.
After solving G, I felt that it would be easier to use OEIS for the whole problem... I don't think it's good.
The induction part (or "OEIS part") in the editorial can also be replaced with a simple bijection: Consider the DFS order, visiting the larger child earlier. Then a leaf corresponds to a descent.
Yeah, I heavily dislike the fact that the main difficulty point of this problem can be resolved by simple OEIS search. But this was also educational in the sense that I should try to think less and brute force more when I see a counting problem.
Educational in the sense than even now, something like this can still appear as a final problem in a contest.
In problem B, why can't it be
$$$b[i]-d[i]+\min(a[i],c[i])$$$ Because we can definitely move the zeroes before the ones, or the ones before the zeroes.
we can do this , i did exactly this, dont forget to add contribution of zero transfers
Why is it ACCEPTED then ? This test case give different results for both approaches :
math is not mathing
initial zeros = 2+1 final zeros = 1+1
i.e, invalid testcase
I did exactly this way and it wasn't accepted, but a friend of mine did if(a[i] <= c[i]) { steps += a[i] } else { steps += c[i] } steps += b[i] — d[i] and it was accepted. I really want to know what is the difference between these two methods.
Yea you move a 1 only when there are least number of zeroes possible before it. If you can remove a zero before adding a 1 then do it, because the lesser the number of zeroes before a 1, the better. And if you have to add a zero, first remove the ones then add the zeroes.
I did this exactly way and my code was not accepted.
Yea I think you are not considering that if a[i] > c[i], then you remove all the zeroes and set a[i] = c[i], only then can you do the remaining operations. Check my code once, you'll get what I'm saying
see my solution once, its similar to your idea
How does the checker for F work?
If i am not mistaken, it is this https://cs.stackexchange.com/questions/64628/algorithms-for-counting-number-of-triangulations-of-a-simple-polygon (comment has link to paper with n^3)
Edit : i forgot that here we have a weird format of the number of needed triangulations. It is still doable with bigint in n^4.
Instead of bigint you can also do modulo a few random large primes.
Hilarious but I actually came up with problem D 3 years ago, proving that answer is $$$\leq 2n-3$$$, but during the contest I completely forgot about this, submitting some bullshit. Here is my original proof writeup translated from Ukrainian.
We can restate problem as follows: there is an initial message in node $$$1$$$; once node $$$v$$$ gets a message, it starts transmitting it to its neighbors in arbitrary order. What's the smallest time until the message reaches node $$$n$$$?
Answer: $$$2n-3$$$
Solution. Consider a path on $$$n$$$ vertices in which vertex $$$i$$$ is connected only to $$$i-1$$$ and $$$i+1$$$.
Let each vertex $$$i$$$ ($$$2\le i\le n-1$$$) first send a message to vertex $$$i-1$$$ and then to $$$i+1$$$ (if it exists).
Clearly, vertex $$$n$$$ receives the message at the end of second $$$2n-3$$$.
Now we prove that every vertex is reached within $$$2n-3$$$ seconds.
Let $$$S_i$$$ be the set of reached vertices after second $$$i$$$.
A vertex $$$v\in S_i$$$ is called alive if it has at least one edge leaving $$$S_i$$$.
For every $$$v\in S_i$$$ define $$$d_{v,i}$$$ to be the number of neighbours of $$$v$$$ that lie in $$$S_i$$$ and to which $$$v$$$ has not yet sent a message.
We maintain integers $$$\bigl[\ell_i,\dots,r_i\bigr]$$$ such that the multiset $$$( d_{v,i} | v\in S_i )$$$ is majorized by the sequence $$$\bigl[\ell_i,\ell_i+1,\dots,r_i\bigr]$$$.
Initially $$$\ell_0=r_0=0$$$. Let's update them as we transition to the next second.
Case 1. No new vertices are reached in second $$$i+1$$$. Every alive $$$v\in S_i$$$ uses one of its edges inside $$$S_i$$$, so $$$d_{v,i+1}=d_{v,i}-1.$$$ Hence the multiset is now majorized by $$$\bigl[\max(0,\ell_i-1),\,\dots,\,r_i-2,\,r_i-1\bigr]$$$
Case 2. $$$k\ge 1$$$ new vertices get message in second $$$i+1$$$. For a new vertex $$$v$$$, $$$d_{v,i+1}\le (r_i-\ell_i+1)+(k-1)$$$, while for an old $$$v\in S_i$$$, $$$d_{v,i+1}\le d_{v,i}+(k-1)$$$. Thus the new degree multiset of alive vertices in $$$S_{i+1}$$$ is majorized by $$$\bigl[\ell_i+k-1,\,\dots,\,r_i+k-1,\, (r_i-\ell_i+1)+(k-1),\,\dots,\,(r_i-\ell_i+1)+(k-1)\bigr]$$$ which itself is majorized by $$$\bigl[\ell_i+k-1,\;\ell_i+k,\;\dots,\;r_i+2k-1\bigr]$$$
Consequently, if $$$k_i$$$ vertices are added in second $$$i$$$ (either $$$k_i=0$$$ or $$$k_i\ge1$$$), the choices $$$\ell_{i+1}=\ell_i+k_i-1, r_{i+1}=r_i+2k_i-1$$$ preserve the majorization property.
Suppose not all vertices are reached after $$$2n-3$$$ seconds; then some vertices remain alive.
However, $$$r_{2n-3}=r_0+\sum_{i=1}^{2n-3}(2k_i-1)=0+2(n-2)-(2n-3) = -1$$$ which is impossible. Hence every vertex is reached within $$$2n-3$$$ seconds.
For a new vertex v, dv,i+1≤(ri−ℓi+1)+(k−1), while for an old v∈Si, dv,i+1≤dv,i+(k−1)I'm unclear on how we get to this...
Thanks for this btw when will be rating changes waiting...
it takes few hours.
I was curious to know that what is Problem Locked verdict on someone's submission. How's that achieved? If someone could share..
Rule no 5
thanks for sharing the blog, can you tell me, how can one lock his submission?
after getting accepted, you can lock problem by just clicking on the lock icon
cool, thanks!
im just curious you've been on CF for 2 years, how you don't know about it?
Ohh, i get that, it is so obvious to think, why i didn't know this. Actually, i noticed it many times but i was not getting any clue, how can i lock my problem, so i thought maybe its from the system that if a solution is too good that it cant fail on any pretest then the system locks it. So naive of me to think :) Also, i was not so active in comment section so far, so i never bother to ask but couldn't stop myself this time
can somebody please explain problem B?
The tutorial is well explained but I'll try to explain it clearly. You only have to count how many elements you have to remove, because you can put each element you remove in its final position. So, iterating though each pile, if in one pile you have more 1s than target, you have to remove all the 0s and the exceeded 1s, add that to the result. If not, check the 0s, if you have more 0s than target, add the difference between initial 0s and target 0s. I hope it's more clear now.
understand! thank youu
Wow, this contest made my brain TLE for sure
why complexity for B O(N^3)>>???
I solved D at 0:21 (and even got an intermediate result of global top-2!). It is hilarious that I spent literally less then a minute thinking about bounds and told myself: we can solve in $$$10\,000$$$ steps because after each step we wait no more than $$$deg(v)$$$ and we know $$$\sum deg(v) = m$$$ and we know $$$n\sim m \sim 5000$$$, right?
I feel I got really lucky. In retrospective it seems really not obvious why 10k is enough. Definitely kind of "I believe this should work" problem, idk if this is good for Div2D.
Same! in the contest I told me that I can randomly make a spanning tree then the answer is O(n), and firstly I dp for n times and got WA, then I changed it to 2n and got AC.
after the contest when I'm discussing the solution with my teammates, I found that my proof is totally wrong and feel very nervous until it passes system test.
Systests = Pretests.
why?
Systests = Pretests + Hacktests,
since Hacktests = empty
Systest = Pretests
B was just too unintuitive for me—I couldn't figure it out.
Can anyone give me a testcase why this code 329867964 for d fails?
50 mins to solve B by analyzing. 20 mins to solve D by guessing.
I saw a ~10% AC rate on D and I got scared so I didn't guess at once... turns out brute force is right and I don't know what's the main reason everyone is getting WA#2
Not sure what qualifies as Brute Force, but the solution doesn't seem like it to me.
Yeah I might have a wording problem :( It's just a straightforward approach of time complexity $$$O(nt)$$$ where $$$t$$$ is the answer but I'm not sure what $$$t$$$ is. However I can't think of anything else so I coded that anyway.
Can anyone explain me the solution of C in simple way?? The editorial went over my head :(
What I did: I sorted the points by the X and divided the points in 2 groups, the leftmost n/2 and the rightmost n/2. Then I sorted both groups by the Y and after that I paired the first point of the 1st group with the last point of the 2nd group and so on. I can't tell why that works but it was accepted.
How did you come up with that approach
I was trying to get the lines crossed each other, I thought that could be a way to do it. What you can't have are 2 lines (p1,p2) and (p3,p4) where both p1x and p2x are less than p3x and p4x (the same for Y).
it's actually right.
consider you have an sorted array a[] of length 2n. you want to pair them up so that sum(|a[p[i]]-a[q[i]]|) is maximum. this condition is equal to that there aren't two pairs (a[x1] a[y1]) (a[x2] a[y2) (x1<y1,x2<y2) that x1<y1<x2<y2.
if the p is a permutation of 1~n, q is a permution of n+1~2n, it's obviously that this condition is satisfied.
can you please simplify what you're saying. I don't see why would sorting by x first and then sorting both halves by y be optimal.
This is infinite iq approach (• — •)ゝ
Can anyone tell in B, if b>d why we do a+(b-d).. a is number of zeros but isn't it optimal to first give maximum zeros to other number possible that is reduce a to c(final state) and then do c+(b-d)?
But to remove 1, first you have to remove the total number of zero above it.
My point is why to remove all zeros if we can give zeros when a>c then reduce a to c and then give b
How will you reduce 1, without removing all the zeroes on top of it?
If a>c first we will give a-c zeros this leaves c zeros in pile which is obviously less than a now let's say we have b>d in same pile and we have to give 1's so shouldn't we shift c remaining zeros instead of a? That is c+(b-d)
So, removing a-c zeroes from top, will also cost a-c.
And then removing remaing c will cost c.
So, in total it is a-c+c = a.
In editorial we are separately doing a-c and then also adding a
I haven't seen the editorial.
For a[i]<c[i] or b[i]<d[i] what to do
If a[i] < c[i] and b[i] < d[i], then you have to do nothing, because the answer always exist as mentioned in problem, because for some other values where a[j] > c[j] or b[j] > d[j], you are going to remove the zeroes or ones, those zeroes or ones will compensate the first case where a[i] < c[i] and b[i] < d[i]
Is D too difficult for a D? The upper bound analysis of this problem makes me think it has the difficulty level of F.
its rating is 2300, definitely not F
Problem difficulty isn't based on how hard it's to prove, it's based on how hard it's to stumble upon the solution. In this case, guessing that it works is easier than proving, so that's taken as the difficulty.
For some reasons some contests are ordered by guess difficulty rather than by difficulty to actually solve (I guess it would be worse if such a guessable problem was at F, but it's not really that much better at D).
It would be better to use such problems on math contests rather than programming contests, but as it is I guess the meta on Codeforces really is just to guess...
In a math contest, it'd most likely be about finding a tight bound, which fundamentally changes how a proof can be approached. In a programming contest, it's very very common to make something that resembles a proof but isn't one because the objective is different — you don't need to know if the bound on time is $$$10N$$$ or $$$2N$$$, only that it should be low enough that your suboptimal code will fit into time and memory limits. You can start by writing a code and analysing it instead. You can generate many smaller graphs. Actual runtime is affected by cache efficiency here so maybe you need to optimise that, depending on your implementation — the time limit is kinda tight. You need to fit into memory. After experimenting a bit, getting rough insight into the problem, maybe you'd come up with a proof much easier.
proving the answer is O(n) also makes for a decent math problem (but easier). A lot, and I mean a lot of people did not even have any idea why the answer is O(n), or had a fake proof for their solution. You are one of the few exceptions.
I did not even read constraints on $$$M$$$ and just assumed it would be small too.
Please, calm down bro. You can't denigrate a problem only because you have not come up with its solution quickly during contest or lost rating.
You don't get it, I haven't talked to a single person that proved their solution during the contest. Some people did try but their proof is wrong.
Hi I proved it. Took me like 10 min.
The 3 people at around 2900 rating that I talked to didn't, maybe that's why they're doing that well.
That's basically coping on your skill issue. you can be 3500 and have problem solving something, people's mind work differently, there is no reason to disrespect. and also, a 2900 in the contest wouldn't care as much to prove it, maybe he just wanted to for fun or smth. why the disrespect
Why don't you come at me with your real account? I'm not disrespecting anyone.
thx for the editorial, C teach me some new things.
D was cool but I'm sad my python didn't go through even though the complexity seems ok-ish, why limits are not more lenient here?
I think O(N^2logN) wasnt meant to pass With C++ it TLEs in pretest 8
I also tried N^2 after the contest. I'd also say cutting n^2lgn is a bit too much
wtf is B bonus ?
in problem C this was my approach
So first lets simplify the expression using the formula for $$$max(a, b) = \frac{a + b + |a - b|}{2}$$$ after simplifying we get that we need to maximise this expression.
so our strategy can be to first sort all points w.r.t. $$$x$$$ after sorting we see that we pair 1st to last 2nd to second last, so the first part of the summation is taken care of, now we need to maximise the second part without rendering the first part useless. we notice that matching any $$$x_p$$$ before the median and $$$x_q$$$ after the median will only depend in the value of $$$x_q$$$ part and the sum can be same if we change the elements in any order before the median and after the median in their respective parts. so to maximise the second part we can sort the first part till $$$n/2$$$ w.r.t. $$$y$$$ and the second part w.r.t. $$$y$$$ independently.
Can u explain how the function simplfies to max(xp,xq)+max(yp+yq)
just substitute it you will get $$$\sum_{p, q}^{all pairs}2 \times (max(x_p, x_q) + max(y_p, y_q)) - (x_p + y_p + x_q + y_q)$$$ break these summations and the second part is always constant and same.
Loved the problems, B was too much fun!
lmao for problem d i just guessed something like: in the best way every "relax" operation that maybe make the first answer bigger (but can make the second answer smaller) will be done at most 20 times for every vertex. so anyone can hack? plzplz
What a great set of questions! The difficulty level is just right, covering a wide range of knowledge points. Moreover, the questions are based on practical scenarios, and the solutions are quite natural. A big thumbs up to the question setter!
题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞!
ps:This is irony.
This was a great round , B was nice , C was on an idea that i saw for the first time so got to learn something new from C itself . Looking forward for more rounds by Order Capital.
i think D is too hard that due i got a lot of "Wrong Answer On Pretest 2" :(
In problem A for m = n = 2 why cant we have a grid like
max greedy path has sum = 1 + 2 + 3 while max path is 1 + 900 + 3
therefore the answer should be "YES"
Someone tell me where I am wrong ?
greedy path is 1+900+3
why i couldnt understand
A path in a grid is called greedy if it starts at the top-left cell and moves only to the right or downward, always moving to its neighbor with the greater value (or either if the values are equal).so according to this unvisited neighbour of 900 is 3 which is neither greater than or equal to 900 so it cant go there if we follow the definition of greedy path.
greater neighbour among the neighbours, not greater than current value.
Holy moly, div 1~2 is different from div 2., with just solving 3 question I got +delta
Is there a solution for C, where the 2d coordinates are transformed into 1d form, and then the smallest and biggest are paired? (my thought process throughout the contest was to transform the coordinates somehow. But the transformations resulted in scaling the manhattan distance)
check this out. its not 1d but it explains how to solve clearly Here
Here is my solution for problem D which passed system tests, but I was unable to prove it. I hope either someone will hack it or provide the proof: Let's first try to minimize total time. I just have state (i, x) for being in vertex i and trying to go on x-th edge outgoing from i. After this my assumption was that in optimal solution (considering minimizing waiting time) you never need to arrive more than n minutes late compared to earliest arrival time in any vertex. But as I said above, I was unable to prove it. Any counterexamples or insights will be appreciated.
I wrote this exact same solution. I thought I proved it during the contest, but after the contest I realized my proof was wrong. I asked many 2600+s and none of them proved it. Maybe the answer is really small(<=2n-3) so there is no counter ex for the +n bound.
Hey can you tell me what you did in your code. We can prove that all vertices are reachable in maximum $$$2n - 3$$$ seconds. I understood that part, but I am unable to understand your implementation.
firstly, I calculated earliest arrival time for each vertex. Then, as mentioned above, I assumed that you don't need to arrive more than n minutes later than earliest arrival time for each vertex. Now graph states become (v, t) where v is the vertex you are currently and t is time passed relative to earliest arrival for this vertex. We need to calculate minimum waiting time. We have transitions from (v,t) to (v, t+1) with cost 1, and transition to (to, current_time — D[to] + 1) with cost 0, where to is vertex where we can go and D[to] is earliest possible arrival in this vertex.As costs are 0/1 we can use 0/1BFS
How to solve Problem C if the goal is to minimize the sum of Manhattan distances? Any ideas or approaches?
same solution , just group division will be different , like if the co-ordinates are : 2 5 7 8
divide them like :
2 7 | 5 8
instead of :
2 5 | 7 8
Idea
does same solution work for $$$C$$$ in 3D case?
No. It's not always possible to find a matching optimal for all three dimensions, for example
can you explain for the 2D thing the editorial says to match Xl∩Yl with a point in Xr∩Yr but how to implement this idea and also which point to choose from both the sets.
Any match is OK
In B,I wrote an O(n) solution in the contest.
submission
would it be possible to solve problem D with some kind of dijkstra approach?
https://codeforces.me/contest/2122/submission/329995334
Can someone help me with this.Its TLE on 9th test even though as per me i have a O(N) soln.
your solution is O(N) — not sure what is causing the TLE. Try to use '\n' instead of endl as it speeds up the output (endl is flushing the output buffer which is not a fast operation whearas with '\n' the buffer only flush when it's full or when the program terminates)
You are missing two critical lines
std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
never forget this in your C++ code
-
How to finish E in O(nk)?
For E，how to do it in O(nk)？
I can only come up with a solution in O(nklogk) though using convolution in state transition
Why convolution? The state transitions are just ("add anything between 1 and $$$K$$$" or "add fixed number") and ("subtract anything between 1 and $$$K$$$" or "subtract fixed number"). Prefix sums should be enough.
I'm so sorry,but I still don't know how to do in O(nk) though prefix sums.
I read your code(329839824) and my code(330058406).Such as your code,the
dp[i+1][j_nxt] = (dp[i+1][j_nxt] + dp[i][j] * cnt_dif[dif + (K-1)]) % MOD;//j_nxt=j+difseems like only using convolution. Could you help me? I sincerely thank you. Please forgive my worried English.There's no point in reading my code, I didn't overoptimise for that bonus.
Thank you all the same!I know that the cnt_dif is special so that we can cauculate the result in O(nk)
Our English teacher will cry after she sees your broken English.
Dear autumoon , I'm sorry .
Through further reflection, I discovered that for an $$$f(z) \times g(z)$$$, if each coefficient of $$$g(z)$$$ can be expressed by a $$$k$$$-degree polynomial, then it can be computed in $$$O(nk^2)$$$ time.
Specifically, consider the target exponent $$$s = i + j$$$. By replacing each indeterminate in the polynomial expressing $$$g(z)$$$'s coefficients with $$$s$$$, we obtain a coefficient polynomial for each power term. This polynomial should treat $$$s$$$ as the variable, with coefficients derived from the original polynomial. Ultimately, this can be transformed by incorporating the exponent into $$$f(z)$$$ and computing the result via prefix sums. The coefficients of each prefix sum are then determined based on the exponent of each term in the resulting polynomial.
For example, given $$$f(z) \times g(z) = h(z)$$$ where $$$g(z) = \sum (b + k i) z^i$$$, we have:
This can be computed by maintaining the prefix sums of $$$i \times f_i$$$ and $$$f_i$$$.
When $$$g_x$$$ is a linear function, this approach applies. Higher-degree cases can be handled similarly.
The translation was finished by Deepseek because my English is too terrible.
ahsoltan can you please add the implementations
Here is the solution to G-Bonus (solution using purely generating functions).
if we let $$$T_{n,l}$$$ represent the number of valid permutations on all labelled trees with $$$n$$$ vertices and $$$"l$$$ leaves, and let
then we have the following recurrence relation
where $C \left( n_1, \cdots , n_r \right)$ is the function that counts the number of partitions of $$${ 1,\cdots,n_1+\cdots+n_r+1 }$$$ into sets of sizes $$$1,n_1,n_2,...,n_r$$$ respectively (For example $$$C(2,1) = \frac{4!}{2!1!} = 12$$$ and $$$C(2,2) = \frac{5!}{2!2!2!} = 15$$$). In terms of generating functions, this becomes
Taking partial derivative w.r.t $x$, we get
Integrating w.r.t $$$x$$$, we get
Comparing coefficients of $x^0 y^m$ on both sides for all $$$m \geq 0$$$, we have that $$$c(y) = \frac{y}{1-y}$$$. Thus for $$$n \geq 1$$$, we have that
Expanding this further, we get
We must have $r=n$ and $$$r-m=l$$$ to get the required coefficient. Substituting this we get
Taking $$$k = n-m-l$$$, we can re-write the summation as follows
Now, since the coefficient in $$$t(x,y)$$$ is equal to $$$\frac{T_{n,l}}{(2n)! \ (n)!}$$$, we have that
Now, since the root is fixed, we must divide by $n$ to get only labelled trees having $$$1$$$ as the root.
Problem B is annoying.
These are my solutions:
1. Without I/O optimization which got TLE on test 9: https://codeforces.me/contest/2122/submission/330519530
2. With I/O optimization it got succeeded. Link: https://codeforces.me/contest/2122/submission/330520090
Is this kind of behavior expected for problems or is it just too strict test cases?
This means that we always need to have the I/O improvements!
Can anybody help me with my solution in problem D.
I dont know why it is failing on test case 2.
Problem Link: https://codeforces.me/contest/2122/submission/331618437
for the question C can we come up with some solution which first involves pairing the coordinates which have diagonally opposite quadrants, since for them the manhattan distance will just be the absolute sum of each coordinate, so pairing 1st and 3rd quad , 2nd and 4th, but I am not sure about the leftovers after this is done, atmax there will be coordinates left in the 2 quadrants.
Also can someone explain the tutorial of C in a better way
I think problem C is well-designed.. seldom see such clear and beautiful solution, even compared with problems with complex data structures