Thanks to you for participating!

My approach for E — There are $$$\sqrt{n}$$$ distinct values of $$$cnt$$$. Then fox $$$cnt_x$$$ and $$$cnt_y$$$ iterate over each $$$x$$$ and $$$y$$$ have those respective counts

I managed to upsolve D with annealing because my initial submit got unlucky amd FST'd 146160125

for the test case 3 2 1 2

why is answer YES not NO?

Can't we choose len = 2, array will become [1,2,2], which is sorted, thus answer should be NO.

UPD: Uphacked :)

Btw, there's a still some kind of motonocity: without caring about bad pairs, if we convert the postive side into a stair-shaped sequence as well, if we denote $$$optQ(i)$$$ as the optimal $$$Q$$$ for $$$P_i$$$, then $$$optQ(i) \le optQ(i + 1)$$$, which allows us to use divide and conquer optimization. Unfortunately, I don't know how to extend this solution to when we have bad pairs.

Well Balanced Round.

I understand continuation 1 of D editorial, but continuation 2 seems unnatural to me. Could anyone who solved it like that share their thought process? Maybe it can help.

Can someone hack my solution for D or estimate probability it passes under problem restrictions? 146133303

It is not intended solution, but some randomized algorithm. The general idea is (while possible) swap ($$$a_i$$$ with $$$b_i$$$) or ($$$a_i$$$ with $$$b_i$$$ and $$$a_j$$$ with $$$b_j$$$) if that improves score. Do that 5000 times and take minimum score over all trials.

Wrote it as did not come up with anything better...

1637E - Best Pair We going over all different values — O(n) and checking each different cnt O(sqrt(n)) and finding first pair O(m) Why complexity isn't O(n * sqrt(n) + m * log(m)) ?

Is there a way to solve Problem D in $$$O(N)$$$?

Hi , can anyone tell me why my solution for D does not gets MLE or TLE as i have passed 3 parameters in recursion, i know i have memoized the solution but still upper bound on memory in my solution can be (10^4)*(10^4)*(100). My solution : 146179358

In problem E, I found that if you only iterate non-empty vectors(you can use a array to find $$$\sqrt n$$$ vectors) and modify your code like this:

    for (int cnt_x = 1; cnt_x <= tot; cnt_x++)
        for (int x : occ[index[cnt_x]])
            for (int cnt_y = 1; cnt_y <= tot; cnt_y++)

Its complexity become $$$O(n\sqrt n\log m+m\log m)$$$, but it still passed every single test.

I tried to hack my code with a strong test(1~700 occur 1~700 times, and about 100000 random numbers occur 1 time) but codeforces returned "unexpected verdict". I guess that testers write the code I showed and they got TLE too. Can you help me to find out the reason of this unexpected verdict?

I don't know if this is a fact or something very obvious but I don't understand Iterating over all X and cnty <= cntx works in O(n) in Problem E. Shouldn't this be O(n√n)? Also, I don't understand how only iterating on cnty <= cntx is any better than iterating over all cnty

For problem F, if we enumerate one of the biggest height node, then the contribution of node i (i is not the biggest node we determine） is max(0,h[i]-(the maximum h of the node except the node in the subtree of the biggest node when the root is i and i itself). We first determine the root of the tree, then my solution is to calculate up[i] and down[i], it means if the biggest node in the subtree of i, what the contribution will be for node father[i] and if the biggest node not in the subtree of i, what the contribution will be for node i. Then we can easily calculate the answer.

problem E: weak pretests, there're no number occurs more than $$$\mathcal O(\sqrt{n})$$$ times (maybe just random tests). I write sort wrongly and passed all the pretests, but failed system test later :(

I replace my code

sort(adj[idx].begin(),adj[idx].end(),[&](int x,int y){
    return diff[cnt[x]]!=diff[cnt[y]]?diff[cnt[x]]<diff[cnt[y]]:x>y;
});

with

sort(adj[idx].begin(),adj[idx].end(),[&](int x,int y){
    return cnt[x]!=cnt[y]?cnt[x]<cnt[y]:x>y;
});

then passed all tests.

Weak main tests for F. Simple memorization passed...

https://codeforces.me/contest/1637/hacks/785940

I have a different solution for D. At first we simplify the cost function, \begin{align} &\sum_{i = 1}^n \sum_{j = i + 1}^n (a_i + a_j)^2 + (b_i + b_j)^2 \newline &= \sum_{i = 1}^n \sum_{j = i + 1}^n a_i^2 + a_j^2 + 2a_ia_j + b_i^2 + b_j^2 + 2b_ib_j \newline \end{align}

Notice that $$$ \sum_{i = 1}^n \sum_{j = i + 1}^n a_i^2 + a_j^2 + b_i^2 + b_j^2 $$$ is constant, so we only need to minimize \begin{align} &\sum_{i = 1}^n \sum_{j = i + 1}^n 2a_ia_j + 2b_ib_j \newline &= 2\sum_{i = 1}^n \left(a_i \cdot \sum_{j = i + 1}^n a_j\right) + \left(b_i \cdot \sum_{j = i + 1}^n b_j\right) \end{align}

Let $$$A$$$ and $$$B$$$ be the final arrays $$$a$$$ and $$$b$$$ respectively after applying all swaps. Notice that, for some $$$i$$$, if we fix $$$\sum_{j = i + 1}^n A_j$$$, then $$$\sum_{j = i + 1}^n B_j$$$ is also fixed, because $$$\sum_{j = i + 1}^n B_j = \sum_{j = i + 1}^n a_j + b_j - \sum_{j = i + 1}^n A_j$$$

Now we can do, $$$ dp[i][sum] = \text{minimum cost for the suffix starting at }i\text{ such that } sum = \sum_{j = i}^n A_j $$$

Let's also store $$$ p[i] = \sum_{j = i + 1}^n a_j + b_j $$$

Transitions are simple,

If we do not apply any swap at position $$$i$$$,

If we apply swap at position $$$i$$$,

This dp can be done in $$$O(n^2 \max a_i)$$$. Then, the final answer is just

Here is my implementation.

quite thankful for beautiful problems and fast editorial with hints :)

In problem D, how did you derive the second item of "cost", Σ(a[i]*(s-a[i]))?

For B's dp based approach, in editorial are the transitions wrong since I got AC with dp[l][r] = max(1+mex(v[l],v[l+1],....,v[r]),max over c = [l,r)(dp[l][c] + dp[c+1][r]))

Can anyone share O(n^3) dp based solution for B?

The autor's solution for problem C outputs wrong answer for test 1 4 1 5 0 1 The code returns 3 but the shortest way is 1 5 0 1 -> 2 3 1 1 -> 3 1 2 1 -> 3 2 0 2 -> 4 0 0 3 that takes 4 operations. (Update — It's not true)

In A. Sorting Parts, for 2 1 4 5 3, what will be the output?

Hi Mangooste!

Thank you for the nice round!

There is a wrong statment in the last but two paragraph for Problem H's Editorial:

Note that the number of points to the left and below i equals to pi−1−si, and the number of points to the left and below i equals to (i−1)−(pi−1−si)=i−pi+si. So di=(i−pi+si)−(pi−1−si)=i−2pi+2si+1. So ci=di−2si=i−2pi+1.

Here $$$i−p_i+s_i$$$ might be the number of points left and above $$$i$$$.

I have an alternate solution for E.

First, let's group all values by their frequency. Let's say that has_ct[f] is a list of all values $$$x$$$ such that $$$ct_x = f$$$, and this list is sorted in descending order.

Fix two particular values of $$$ct_x$$$ and $$$ct_y$$$; let's call them f1 and f2. What we want now are $$$x$$$ and $$$y$$$ such that x in has_ct[f1], and y in has_ct[f2], and $$$(x, y)$$$ is not bad, and $$$x + y$$$ is maximal. We will iterate over all (f1, f2) pairs, and let our final answer be the maximum $$$x + y$$$ across all (f1, f2) pairs.

We use the fact that we sorted has_ct[f1] and has_ct[f2] in decreasing order. Draw a 2D grid. For some $$$(i, j)$$$, let x = has_ct[f1][i] and y = has_ct[f2][j]. Then, define grid[i][j] = x + y. Because each list is decreasing, note that each horizontal and vertical slice of the grid is also decreasing. Naturally, the maximal value of the grid is attained at the top-left corner, when $$$(i,j) = (0, 0)$$$. But, if their $$$(x, y)$$$ is bad, then we need to explore the rest of the grid for the next largest value. But the shape of the grid tells us that the next largest values are the ones attained by taking one step right, or one step south.

In general, let $$$dp(i, j)$$$ be "the largest value in the grid that is attainable from $$$(i, j)$$$ using only right-down motions". If the corresponding $$$(x, y)$$$ is not a bad pair, then $$$dp(i, j) = x + y$$$. If not, then $$$dp(i, j) = \max(dp(i+1, j), dp(i, j+1))$$$, which is just like the classic standard grid dp.

We note that this DP is much faster than $$$\mathcal{O}(n^2)$$$, because we only explore the grid further if $$$(x, y)$$$ is bad. So actually, the combined work of our DP across all (f1, f2) pairs is just $$$\mathcal{O}(m)$$$.

Finally, note that there are only $$$\mathcal{O}(\sqrt{n})$$$ different frequency values possible, because $$$1 + 2 + 3 + \dots + k = \mathcal{O}(k^2)$$$. So, iterating over all (f1, f2) pairs does $$$\mathcal{O}(\sqrt{n}^2) = \mathcal{O}(n)$$$ work.

There are also some miscellaneous log factors scattered about because of how I grouped by frequency, how I identified bad pairs, and the fact that I used a map to handle the DP memoization, but those aren't really too important.

Link to submission: https://codeforces.me/contest/1637/submission/146196644

I made video Solutions for A-E in Case someone is interested.

If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com

Problems added: "A, B, C, D, E, F, G, H".

Can anybody please explain in problem B how the contribution of zero is i*(n-i+1) ?

Can someone explain simplification of cost in Problem D

Hi, I want to share my solution for D with 1d dp.

Problem D: Can someone please explain to me in more mathematical detail how to get the simplifaction for the cost, more specifically the following relation: $$$\sum_{i = 1}^n\sum_{j = i + 1}^n2*a_i * a_j = \sum_{i = 1}^n(a_i * (s - a_i)) $$$ ?

Some solution for problem E now gives TLE which passed during contest system testing. Will there be any System testing now after rating changes

Did AlphoCode participate this contest?

What's with this test case 79 for E . Older AC's also getting TLE'ed

Slightly different approach to 1637F - Towers

In Problem C, do the positions of the elements other than the ends not matter at all? Since the final solution is somehow independent of it.

Can someone also explain a little beyond the editorial? I'm unable to convince myself what is explained above.

I like the approach for problem E! Are there other problems that can be solved with the same technique?

Is it possible to do D in O(n)? If someone has done it can you please describe your approach.

By Pisinger’s balancing algorithm for subset sum, problem D can be solved in $$$O(n\cdot \max a)$$$. here is an implementation.

In problem E you can check if the edge is bad in O(m + n) total if when iterating over x you'll first mark all bad pairs bad in an array (and then mark it not bad again when going to vertex x + 1)

So you need log factor only for initial sorting/coordinate compressuring

The alternative solution for F is very nice. I got up to most of it but couldn’t see that rooting the tree at the max value would deal with all issues regarding how to choose the second endpoint for each path. Hopefully some day I’ll be able to make these types of smart optimizations on my own.

Interesting to come up with heuristics. 146448463 seems to work pretty well, though it's clearly fundamentally wrong. Main idea is to take 150 of the best ones wrt to $$$x$$$ and 50 of the best ones wrt $$$cnt[x]$$$.

My solution to G is similar to the editorial but works on sequences $$$2^k, 2^k+1\cdot2^l, 2^k+2\cdot2^l, \ldots$$$ with $$$l \ge k$$$. We split that into an "even" subsequence divisible by $$$2^{k+1}$$$ and a non-empty "odd" subsequence that's only divisible by $$$2^k$$$. The "even" part is solved recursively, the "odd" part solved by gradually pairing up elements into powers of two and smaller sequences just like in the editorial. When only powers of $$$2$$$ are left:

• if all powers smaller than the answer occur only once and there are at most two such powers, we fail but that never happens — easy to check all possible inputs
• if all powers smaller than the answer occur only once and there are at least three such powers ($$$2^a$$$, $$$2^b$$$, $$$2^c$$$ with $$$a \lt b \lt c$$$), we keep doubling $$$2^a$$$ and $$$2^b$$$ till we get $$$2^c$$$ twice; doubling two values takes two operations
• once there's some power $$$2^c$$$ smaller than the answer occurring at least twice, we get $$$0$$$ and $$$2^{c+1}$$$ and change the $$$0$$$ to the smallest remaining power
• once the smallest $$$2^c$$$ occurs at least twice: we can change $$$(2^c, 2^c, 2^c) \rightarrow (2^c, 2^{c+1}, 0) \rightarrow (2^c, 2^c, 2^{c+1})$$$ or just double two values $$$2^c$$$, which gives us a way to simply change all $$$2^c$$$ to $$$2^{c+1}$$$; we repeat while it's necessary

The only significant thing about this is the bound: $$$\le 4n$$$ in all my testing with much greater $$$n$$$ and it seems to be asymptotic. It also seems A081253 is the sequence of the only values of $$$n$$$ that tighten the bound if we keep increasing $$$n$$$.

Can someone look at my code, It is giving runtime(array out of bounds) error with c++17 and wrong answer on test 5 with c++20, though it is working on my local system(using c++ 17).

c++ 17 : https://codeforces.me/contest/1637/submission/146466246 c++ 20 : https://codeforces.me/contest/1637/submission/146466291

Edit : There was a problem with 2d vector thing, I changed it to a normal 2d array and initialised it to 0. Now it works.

I learnt new things in problem B.

In problem E if we fix x and iterate over cnty>=cntx rather than cnty<=cntx still the time complexity must be the same but making this change gives a TLE on test 79. Mangooste can you please explain this.

here are the submission links cnty >= cntx and cnty <= cntx

The time complexity of the solution for F should be nlog due to sorting

Thanks for the great round and complete editorial :)

For D, by Jensen's on $$$x^2$$$, $$$\left(\sum_{i=1}^n a_i\right)^2+\left(\sum_{i=1}^n b_i\right)^2$$$ is minimized when $$$\sum_{i=1}^n a_i$$$ and $$$\sum_{i=1}^n b_i$$$ are as close together as possible. So instead of calculating the sum for any $$$dp_{n,s}$$$ that are true, we can instead iterate through all true $$$dp_{n,s}$$$ and find the $$$s$$$ that's closest to $$$\frac{S}{2}$$$, where $$$S=\sum_{i=1}^n(a_i+b_i)$$$, and calculate $$$s^2+(S-s)^2$$$. It's probably not faster at all (both seem to take 15ms on c++), but it feels a bit smarter.

Edit: of course, Jensen's is not the only way to arrive at the conclusion: expanding $$$(S-x)^2+x^2$$$ and using properties of quadratics works too.

Petr's accepted solution for E:best pair using pair hashing now giving tle for test case 78/79.
I m curious if there any better approach to hash pairs without getting hacked.