## 1866A. Ambitious Kid

Author: Pyqe

Developer: nandonathaniel

**Tutorial**

## 1866B. Battling with Numbers

Author: KokiCoder

Developer: nandonathaniel

**Tutorial**

## 1866C. Completely Searching for Inversions

Author: Pyqe

Developer: gansixeneh

**Tutorial**

## 1866D. Digital Wallet

Author: CyberSleeper

Developer: CyberSleeper

**Tutorial**

## 1866E. Elevators of Tamem

Author: FreeJinG

Developer: Pyqe

**Tutorial**

## 1866F. Freak Joker Process

Author: nandonathaniel

Developer: Pyqe

**Tutorial**

## 1866G. Grouped Carriages

Author: ArvinCiu

Developer: ArvinCiu

**Tutorial**

## 1866H. Happy Sets

Author: Edbert.H

Developer: Edbert.H

**Tutorial**

## 1866I. Imagination Castle

Author: CyberSleeper

Developer: CyberSleeper

**Tutorial**

## 1866J. Jackets and Packets

Author: asteriskzie

Developer: Pyqe

**Tutorial**

## 1866K. Keen Tree Calculation

Author: nandonathaniel

Developer: Pyqe

**Tutorial**

## 1866L. Lihmuf Balling

Author: gansixeneh

Developer: gansixeneh

**Tutorial**

## 1866M. Mighty Rock Tower

Author: ArvinCiu

Developer: ArvinCiu

**Tutorial**

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.

Submission: 221692181

Ooo interesting. We didn't think of this approach at all!

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

hack：

Array Z is '10001'. Your output is 1, but the correct answer is 3.

Can you explain how you found out the Wrong Answer/hack to the submission? I find it very difficult to find the WA test case even in my solutions, let alone understand other's solutions and then hack theirs. Also, for some reason, I find it very hard to understand someone else's solution/logic in the solution, until and unless their logic exactly overlaps with my thought process.

The test case was just randomly generated by the other code I wrote. I ran the submission and an AC solution, then I found their ouput different. Of course, this process may have been carried out many times.

Did u stress test the solution or just manually entered the test cases? I thought of stress testing my solution with my brute approach, but couldn't figure out a way to generate random acyclic directed graph. Is there any way to do so?

Acyclic directed graph in this problem can be generated by following:

all vertexsexclude vertex 1.Thanks. Finally, I figured out I forgot to put a %M while performing an operation.

Also, in your solution, you don't seem to be using any %M while performing the calculations, rather you are using some template Z=Mint<>, which seems to be performing the modular operations.

Can you explain what that Z is, or some blog relating to that, or where you learned that from, OR made it on your own?

Mint is basically a custom data structure unlike int, long long it has some extra features Once you declare a variable in mint, you can forget about mod operations and can use in a normal way. modular Uncomment required mod. and can declare as modular var;

You are welcome. In fact,

`Modular`

class is common in codeforces. For example, tourist uses it recently in this submission.The class "MInt" in my solution was made by myself after refering other's code. I think you may understand the logic in the code and just not understand the grammer about "template","operator+" and "operator*" etc. Please refer information related to it. And this blog mentions

`Modular`

class.My soln of K is simpler than editorial.Diameter is max of (tree diameter, sum of farthest 2 vertexes from Xi)

We can do it offline.

First, find the farthest vertex using CHT.

We can also maintain the vertex in CHT, so we know which vertex it is along with the farthest distance.

Let

`v_1,v_2,v_3,....,v_k,....,v_m`

be the order of adjacency list.Let

`v_k`

be the farthest vertex.We need farthest vertex in CHT of

`[v1,v2,...,v{k-1}]`

and`[v{k+1},....,v_m]`

We can run two loops from 1,2,...,m and then m,m-1,....,1

Querying for max on prefix and suffix cht.

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.

Sorry, we weren't aware of the existence of that problem.

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.com/contest/1866/submission/221741172)

Hi, can someone please point out what's wrong in my code for problem c 221747021

Can anyone please let me know why do we need DP for Problem C. Why does my solution exceeds Memory Limit if anyone could answer? TIA 221696430

since you can visit each node more than one time u will cross the edges more than one time like in this example :

1 -> 2 -> 3 -> 4

1 -> 3 -> 4 your dfs path will be like this : 1 — 2 — 3 — 4 — 3 — 4

Oh, i get it thanks

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

Let's say that you were to fix a set of elements of the grid that you want to take. An algorithm that could determine if you can actually take them would go from left to right and always pair the first element to the first interval (it's better to, in the future, have intervals that reach further to the right available, rather than shorter ones). The really important observation is that at any given moment, intervals that are not paired (and could be used in the future) form a suffix of all of the intervals (when sorted by their endpoint). This is because if the set of not paired intervals is 4 5 7 8 9 (without 6) we can swap the paired elements of 4 and 6. If 4 can't be paired with what we paired to 6, that means it can't be paired to anything else to the right of what was paired to 6, so it's useless to remember it in the future. This means that at any given moment we only need to remember that we didn't pair 0, 1, 2, 3 . . . or K of the rightmost intervals. Transitions are similar to the idea behind the greedy I mentioned at the beginning.

Thank you!

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

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

Not sure that greedy works in D

Thank you very much bro, I saw my problem thanks for your test.

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

Really Nice Approach Because If we just try to think about the same Problem in 1D then the order in which we are taking element doesn't matter only what elements we take hence, we can really just take the elements in a sliding fashion and extending the same approach to 2D gives your solution. Please correct me if I got it wrong!!

Upd:

My submission: Although I got

`NK^4`

running idk how but I am pretty much sure that it can be optimised to`NK^2`

using some`prefix-max`

calculation. 222054066Correct

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

in problem C, how can we know Zx>Zy what is the condition ?

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

yes I think it's normal, PQs are faster for some reason

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

could someone please explain check function for problem G

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.

Hello Pyqe, can you please clear my following doubt. In question 1866J - Jackets and Packets can we think of the DP in the following way . dp[i][j][k][l] -> minimum time if there are i jackets removed in total and have been into j packets and k is the topmost remaining element in left stack and l is the topmost remaining element in the right stack ; How we are going to make transitions -> dp(i,j,k,l) -> i think it is not possible because how we are going to know the remaining elements left in the stack. or

can there be a wayif yes, can you please tell ; It will be very helpful . I have just asked this because i have been thinking for a long time that why this approach will fail or may work after some clever modifications.Because i just wanted to tell my thought process to someone superior and experienced person. If you can help in this regard then it will be very kind of you. As then it will be more convincing to understand the editorial and the reason behind combining it into a single array.