VERY NICE CONTEST SUPERB

It was a very nice contest. Thanks!!

1866D - Digital Wallet can be solved in $$$O(nm \log k)$$$.

The problem is equivalent to "find the maximum sum of a subset of elements such that, for each $$$i$$$, the number of elements taken from columns $$$[1, i]$$$ is in the range $$$[i-k+1, i]$$$".

Let $$$dp_{i,j}$$$ be the maximum sum of $$$j$$$ elements in the first $$$i$$$ columns (with $$$i-k+1 \leq j \leq i$$$). Note that $$$dp_i$$$ is concave, so we can try to use slope trick. Let's keep the $$$dp_{i,j}-dp_{i,j-1}$$$ in a multiset.

• The transition $$$dp_{i,j} = \max(dp_{i-1,j}, dp_{i-1,j-1}+a_{r,i})$$$ corresponds to inserting $$$a_{r,i}$$$ in the multiset.
• The constraint $$$i-k+1 \leq j \leq i$$$ can be handled by removing elements from the beginning and from the end of the multiset when necessary.

Submission: 221692181

HELP, Can anyone point out the mistake in C? 221727161 WA on the 6th test case.

Problem I is literally an easier version of 1458-E

It turns out that it can be solved in $$$\mathcal{O}(K\cdot\log{K})$$$, and even answer multiple queries for different values of $$$N$$$ and $$$M$$$ in $$$\mathcal{O}(\log{k})$$$ per query. Also, coordinates of all the values can be arbitrarily big (let’s say up to $$$10^{18}$$$).

UPD: in case someone is curious, here is my submission that solves the problem in $$$\mathcal{O}(K\cdot\log{K})$$$ with arbitrary big values of $$$N$$$ and $$$M$$$. If you add the two commented lines in the code, it will allow you to solve multiple queries, in $$$\mathcal{O}(\log{k})$$$ each.

We can avoid the extra logN in the algorithm if we make sorting not in bin search. The total solution will work in $$$O(N * (log N + log max(A))$$$. My solution began to work not in ~1000 milliseconds (with sorting in bin search), but in ~400 milliseconds (https://codeforces.me/contest/1866/submission/221741172)

Can someone explain or send me an example code for D? I didn't understand editorial

K can be solved by kinetic tournament, https://codeforces.me/contest/1866/submission/221756159

Can anyone show me the mistake when using greedy in D? 221764341 WA on test 18

My approach for problem D :

$$$dp[i][x][y]$$$ denotes I have to do $$$ith$$$ operation, and can only take elements starting from $$$xth$$$ row and $$$(i+y)th$$$ column, now I have two options either to take the current element or go to the next element. Next element will be $$$(x+1,y)$$$, if $$$x+1 > N$$$, then make $$$x = 1$$$ and increment $$$y$$$ by $$$1$$$.
Some base conditions will be $$$y$$$ cannot be greater than or equal to $$$k$$$, etc. This approach seems much simpler than the intended solution mentioned in the editorial.

My submission : 221780386

Has anyone talked about H question? I didn't understand the solution.

I want to share another alternative solution of 1866D — Digital Wallet, which works in $$$O(nm\log (nm))$$$.

Observe that the problem is a matroid structure, where I think the correctness of both the downward-closed property and the independent set exchange property is straightforward.

Since the problem is a matroid structure, let's greedily pick the $$$nm$$$ elements from large to small by their value. Once a picked element causes the currently picked elements to be unselectable by the operations, we discard it.

But how to verify whether a set of elements is selectable? My approach is to regard it as a matching problem that matches the elements and the operations and then use Hall's Theorem.

A set of elements $$$\mathcal{S}$$$ is selectable if and only if:

For any subset $$$s \in \mathcal{S}$$$ of it, the number of operations that can select at least one element in $$$s$$$ must not be less than $$$|s|$$$.

If you are familiar with the application of Hall's Theorem to interval matching problems, I think it is not difficult to simplify it to the following form:

A set of elements $$$\mathcal{S}$$$ is selectable if and only if:

For any range $$$1\leq l \leq r\leq m$$$, the number of elements in it is not greater than the operations that intersect the interval. We say an element $$$A_{x, y}$$$ is in a range $$$[l, r]$$$ when $$$l\leq y\leq r$$$.

Let $$$p_i$$$ be the number of picked elements in the range $$$[1, i]$$$. Let $$$u_i$$$ be the number of operations intersecting with the range $$$[1, i]$$$. Let $$$v_i$$$ be the number of operations fully inside the range $$$[1, i]$$$. Both $$$u_i, v_i$$$ are easy to pre-calculate.

Then the above condition can be rewritten into:

Maintain two segment trees. One maintains the maximum of $v_l - p_l$, and the other maintains the minimum of $$$u_r - p_r$$$. A picked element $$$A_{x, y}$$$ will cause a suffix subtraction. The condition will fail after the subtraction if and only if there exists $$$l<y$$$ and $$$r\geq y$$$ fail the condition. You can verify it using the segment trees.

The total time complexity is $$$O(nm\log(nm))$$$ (sorting) + $$$O(nm\log m)$$$ (segment tree operations for each element) = $$$O(nm\log(nm))$$$.

Though the above approach somehow overkills the problem (and is slower than the earlier $$$O(nm\log k)$$$ solution), I think it might be an exercise for practicing the applications of Hall's Theorem. Or maybe we can solve a more complicated version of the problem. For example, for each operation, you can do it $$$t_i$$$ times.

Submission: 221787757

Can anyone explain why the transitions are done that way in D? I thought that we should add f0[y] to f0[x] so that x's parent knows the amount of zeroes after x, but why would it need to know how many ones came after x?

Isn't the solution for problem E of time complexity $$$O(Q^4)$$$? Though there are $$$O(Q^3)$$$ states, each one has up to $$$O(Q)$$$ transitions.

Upd: Oh right, you don't want to "skip over" any people, so you can only transition from the $$$O(Q^2)$$$ previous states where there is an elevator that served the previous person.

Can Someone pls explain H , I didn't understood editorial very well

G gives TLE on test case 18 if we use multisets. But it gets AC if we just replace multisets with priority queues. Is this normal?

Multisets submission link: here

Priority Queues submission link: here

It's weird, can someone explain the wrong point of my code in problem D, I got WA at test case 27

my submission: 222034318

In problem H how to calculate g(e) function i can't understand can anyone explain it.

I have a question about problem G. I tried to solve it using Hall's theorem at a contest. At first I tried to use binary search on the answer(suppose it is $$$x$$$). Then we create a bipartite graph where on the left side we have carriages where we will start and on the right side we have carriages where we will finish. On the left side we create $$$a_i$$$ copies of the $$$i-$$$th vertex and on the right side we create $$$x$$$ copies of $$$i-$$$th vertex. Then we try to find a counterexample to Hall's theorem. We should find such a subset $$$i_1, i_2, ..., i_k$$$ of vertexes from the left side such that $$$a(i_1) + a(i_2) + ... + a(i_k) > x * $$$(size of union of segments which correspond to the chosen carriages). I tried to use dp then -- $$$dp(pos, r)$$$ means the minumum difference between the left and the right parts of the unequality above where we are now on the carriage number $$$pos$$$ and the rightmost segment from our union have it's end equal to $$$r$$$. It seems that we can optimize it with the segment tree but it seems to hard since we have to deal with something like adding an arithmetic progression on a segment. I understand that it is an overkill for this problem but I think that idea(binary search + hall's theorem + dp + data structure to optimize it) is very nice. Can this still be solved using this method? Maybe there is an easier way with Hall's theorem to solve this problem? Can we reformulate this problem in a more harder way so that greedy becomes impossible and we should solve it with Hall's theorem? And do you know some other problems which use Hall's theorem in a similar way? Thanks in advance.