Объясните пожалуйста, почему в задаче A при создании одного массива со всеми значениями, сортировкой и подсчетом от a[0] до a[n/2], как за массив 'a' + от a[n/2] до a[n — 1] как массив 'b' ответ неверный на 1 тесте(3 пример)? Наверное я плохой математик, но так как у нас считается абсолютная величина — реверснутый массив не будет ничего значить. Так почему моё решение не прошло, а решения где алгоритм абсолютно тот же, но массив реверсится — проходят?

Мой код

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

I've also added 2 new features: Near real-time log streaming and Compressed Parameter editing without using tables.

• A: Array Balancing
• B: Getting Zero
• C: Water the Trees
• D: Progressions Covering
• E: Narrow Components
• F: Teleporters

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

My solution to 1661E - Narrow Components using persistent DSU and segment tree: 153317120.

For each node of segment tree I store a DSU containing nodes and edges in its range [Lx, Rx). When querying the tree, first I make save point, then I merge all ranges using edges between them and print answer, then I rollback updates (erase added edges in query).

Because of rollback function DSU operations take $$$O(logn)$$$ (there's no path compression).

Total time complexity: $$$O(H*(n+q)log^2n)$$$

Total space complexity: $$$O(H*nlogn)$$$

Where H is height of matrix. This solution will work for H > 3.

My English is too bad to explain the correctness of $$$f(x, k) - f(x, k + 1) \ge f(x, k + 1) - f(x, k + 2)$$$ in problem F.

But I have an ugly figure to prove it.

Thanks to Potassium to translate my proof into English as following:

Consider the case when $$$x = 5$$$, we draw a matrix as follows. When $$$i > 1$$$, all numbers in the $$$i$$$-th row from the bottom is $$$\frac{1}{i} - \frac{1}{(i-1)}$$$. For every square that touches the bottom edge, the sum of numbers inside that square must be $$$1$$$. This is because the sum of any square of length $$$n$$$ must be $$$((\frac{1}{n} - \frac{1}{(n-1)}) + (\frac{1}{(n-1)} - \frac{1}{(n-2)}) \ldots ) \times n = 1$$$. This means that if we draw $$$k$$$ squares to partition and cover the bottom edge, the sum of all numbers inside these squares must be $$$k$$$. Notice that the sum of areas of these squares will correspond to $$$f(x, k)$$$. We define the "optimal canonical partition" of $$$f(x, k)$$$ as the one which is obtained by removing the numbers starting from the top row and from the leftmost column. It is easy to see that we will visit the optimal canonical partition of $$$f(x, 1)$$$, $$$f(x, 2)$$$, $$$\ldots$$$, $$$f(x, x)$$$ in this order. In particular, $$$f(x, k)$$$ is visited when the sum of all remaining numbers is equal to $$$k$$$. The value of $$$f(x, k) - f(x, k + 1)$$$ is the number of numbers we are removing to obtain the optimal canonical partition of $$$f(x, k + 1)$$$ starting from the optimal canonical partition of $$$f(x, k)$$$. As the numbers we are removing are non-increasing, the number of numbers we are removing between each consecutive optimal canonical partition can only decrease. This proves that $$$f(x, k) - f(x, k + 1) \ge f(x, k + 1) - f(x, k + 2)$$$ as desired.

Are the contests getting tougher these days? every contest seems tougher than the last one

There is an $$$O(n + q)$$$ solution to E that involves Euler's formula. As Euler's formula for planar graphs states

$$$cc = v - e + f - 1$$$

$$$v$$$ is vertex count.

$$$e$$$ is edge count.

$$$f$$$ is face count.

$$$cc$$$ is the number of connected components.

Here we are solving for $$$cc$$$; $$$v$$$ is the number of while nodes; $$$e$$$ is the number of pairs of white nodes that are adjacent $$$f$$$ is the number of "blobs" that are composed completely of white nodes and have no white nodes inside of them.

a couple examples:

11
11

is 1 face.

111
111

is two faces.

111
101
111

is one face.

So we can use prefix sums to maintain $$$v$$$, $$$e$$$ (with two arrays, one for vertical and one for horizontal), and one for faces of $$$f$$$ that are a $$$2x2$$$ block of $$$1$$$'s. Then for each of the faces that are in the form of

11111
10001
11111

you also use an array but you also have to make sure not to count an unfinished face of such. It is also important to not overcount

11
11
11

as three faces.

Also, you have to count the area outside the queried region as $$$1$$$ face.

With this in mind you can use a few prefix sum arrays and some other arrays for the height 3 faces to solve this problem.

My terrible implementation of this idea is here.

nice problems B and C

in problem B I understand why we are checking all 15 combinations of 2's power. but can not understand the reason behind taking 15 possible additions. why cant the answer be in lets say (v+20) and then some 2's power in 15 range.

can someone explain? why we are adding 0 to 15 in cntADD

edit: ok i think i get it now. there is no (v+20) can be an answer because at most 15 steps are required. that is why even we add we can not go beyond 15 anyway. thus 0 to 15 range.

Can somebody explain why max+1 is better than max in some cases?

I have another solution for E using Segment Tree + inclusion-exclusion:

We can build a segment tree such that each node carries 3 pieces of information ($$$L$$$ : the left border of the segment, $$$R$$$: the right border of the segment, $$$CC$$$: the number of connected components in that segment)

When merging two nodes, we can simply add their corresponding $$$CC$$$ values, but then comes the problem of overcounting.

Some CCs in the resulting segment are counted more than once!

We can then use the inclusion-exclusion principle to count those common CCs.

We have at most 3 edges in all rows between the corresponding cells of two columns (The rightmost column in the left node and the leftmost column in the right node).

Every edge simply adds 1 to the number of common CCs, but then some CCs are over-counted (those shared by two edges) we need to subtract those now. and then add CCs shared by 3 edges.

Isn't it too complicated: the solution for A? We could use the following simple strategy-

for (int i = 0; i < n; i++) {
                if (a[i] > b[i]) {
                    swap(a, b, i);
                }
            }

Whoa, problem D's solution is so clever to resolve it with O(n) time complexity.

Thanks for the round!

Can anyone please explain the segment tree/lazy propagation approach in problem D?

Here is my clumsy proof for 1661C - Water the Trees claim that max or max + 1 is enough. I just tell how to transform filling of height (h + 2) into (h) with removal or replacement of moves.

In problem A I coded a solution just leaving the smallest numbers on $$$a$$$, just if $$$b_i > a_i$$$ then swap and it worked

Does anyone know why this works? I don't lol

I want to mention two things.

• In explanation of 1661D - Progressions Covering nothing said why this will work. And proof is simple. The only thing which can affect the last element is the last progression. And we can use it as much as required. Then, remove it from consideration and repeat.

• In explanation of 1661F - Teleporters nothing said why we talk about differences. And here is my explanation. Imagine you decided how many portals you would need to insert, it will cost $$$f(x, k)$$$. But we can think of it in a new way: there is list of "upgrades". Each upgrade $$$i$$$ costs $$$f(x, i - 1) - f(x, i)$$$. So first upgrade costs $$$f(x, 0) - f(x, 1)$$$. Next upgrade costs $$$f(x, 1) - f(x, 2)$$$ and so on. So if we do 3 upgrades, we have to pay $$$f(x, 0) - f(x, 1) + f(x, 1) - f(x, 2) + f(x, 2) - f(x, 3) = f(x, 0) - f(x, 3) =$$$ how much we reduced cost from the initial cost. So we can rephrase question into what minimum number of upgrades we need to have their sum cost $$$\geq$$$ difference how much we exceed the limit. Theoretical best way to do this is to pick most valuable upgrades. The only problem is... if we want to take upgrade $$$f(x, i) - f(x, i + 1)$$$ we also had to take all upgrades $$$f(x, j) - f(x, j + 1)$$$ where $$$j < i$$$. But the property $$$f(x, k) - f(x, k + 1) \geq f(x, k + 1) - f(x, k + 2)$$$ exactly implies that if we pick upgrade later, it means we already picked upgrade before, because it has greater or equal cost! So this property allows us to pick most valuable upgrades without violation of upgrades order.

I see Problem B has DP tag. How can this be solved by dp when there can be cycle?

Can anyone explain the BFS solution for problem B ? I have tried to understand the approach from SSRS submission but not getting the logic behind it.

Problem E description is absolute garbage. First of all why are the free cells denoted with '1' when the general convention in many of the problems we have solved is the other way around. Also it is not really clear from the description whether the whole component should be inside the interval or just need to have a cell in the interval. Believe it or not if you flip the 0 and 1 and consider the case where the whole component should be in the interval, the answer from the sample test checks out. Wasted like 2 hours trying to figure out what was going on.

My Segment Tree + Lazy Propagation solution for Problem D : 184339258 Make a difference array of original array, and make its use for adding AP in a range of original array.

Please fix this bug. It will confuse who solve this problem for practice.

In the tutorial of 1661F,

We have to find the minimum value of c
 such that g(c)≤ m

It should be "maximum" since in the solution code, we left lf = mid (the lower bound of the binary search) when we found a valid value of c (res.second <= w). In fact, the 'minimun value of c' will be 1 by the defination of g(c).

Alternate brainless $$$O((n + q)\log{n})$$$ solution for problem E using a segment tree and processing queries offline:

We will iterate over the rightbound $$$r$$$ of queries, and maintain a segment tree $$$S$$$ such that when we are at some $$$r$$$, $$$l$$$'th element of $$$S$$$ will hold answer for range $$$[l, r]$$$.

There is only one important observation: If we consider a single column, there is only case wherein two free cells are not reachable from one another ($$$101$$$). So now, we're only really interested in the places wherein the two disconnected $$$1$$$'s in the $$$101$$$ case get connected. It is pretty obvious that this will happen when a $$$111$$$ is adjacent to a $$$101$$$. We will now maintain at each $$$r$$$, a variable $$$last$$$ which is the minimal $$$l$$$ such that all columns in $$$[l, r - 1]$$$ are $$$101$$$ ($$$last = 0$$$ if no such $$$l$$$).

Using this observation, let us solve this problem. Assume that we have built a valid segment tree till position $$$r - 1$$$, now we move to $$$r$$$, how do we fix the segment tree?

Firstly, each connected component in column $$$r$$$ which is not connected to any cell in the previous column, will increase answer by $$$1$$$ for $$$[l, r]$$$ for all $$$l$$$.

For each connected component in column $$$r$$$ which is connected to some cell in the previous column, this increases answer by $$$1$$$ only for the range $$$[r, r]$$$,

Lastly, if the current column is a $$$111$$$ column and previous column is a $$$101$$$ column, notice that it might be uniting two ones of a $$$101$$$ in range $$$[l, r]$$$ which would have been disjoint in $$$[l, r - 1]$$$. Now there are two cases:

• The column at position $$$last - 1$$$ is a $$$111$$$ column. So here, the two disconnected components of $$$1$$$'s in the suffix $$$101$$$ columns get united at position $$$last - 1$$$. That means we need to fix only the answer for ranges $$$[l, r]$$$ ($$$ last \leq l \leq r - 1$$$). Do this by simply pushing a $$$-1$$$ update on this range in your segment tree.
• The column at position $$$last - 1$$$ is not a $$$111$$$ column. So here, the two disconnected components of $$$1$$$'s in the suffix $$$101$$$ columns get united only at position $$$r$$$. So we need to fix answer for all $$$l \in [1, r - 1]$$$. Do so by updating the segment tree.

Implementation: link