### Pyqe's blog

By Pyqe, history, 3 weeks ago,

## 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

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
• +138

 » 3 weeks ago, # |   +18 VERY NICE CONTEST SUPERB
 » 3 weeks ago, # |   +11 It was a very nice contest. Thanks!!
 » 3 weeks ago, # | ← Rev. 6 →   +59 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
•  » » 3 weeks ago, # ^ |   +10 Ooo interesting. We didn't think of this approach at all!
 » 3 weeks ago, # |   0 Can anyone point out the mistake in C? 221727161 WA on the 6th test case.
•  » » 3 weeks ago, # ^ |   +11 hack： 5 4 2 1 3 0 4 0 5 1 0 1 5 0 0 0 Array Z is '10001'. Your output is 1, but the correct answer is 3.
•  » » » 3 weeks ago, # ^ |   0 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.
•  » » » » 3 weeks ago, # ^ |   +13 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.
•  » » » » » 3 weeks ago, # ^ |   0 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?
•  » » » » » » 3 weeks ago, # ^ |   +10 Acyclic directed graph in this problem can be generated by following: add an edge from vertex $1$ to all vertexs exclude vertex 1. for each vertex $u = 2 \sim n$, randomly choose some distinct vertexs $v_1,v_2,..,v_k$ (with $v_i>u$), add an edge from vertex $u$ to vertex $v_i$.
•  » » » » » » » 3 weeks ago, # ^ |   +8 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?
•  » » » » » » » » 3 weeks ago, # ^ |   +13 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;
•  » » » » » » » » 3 weeks ago, # ^ |   +3 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.
 » 3 weeks ago, # | ← Rev. 2 →   +58 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,....,1Querying for max on prefix and suffix cht.
 » 3 weeks ago, # | ← Rev. 2 →   +13 Problem I is literally an easier version of 1458-EIt 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.
•  » » 3 weeks ago, # ^ |   +18 Sorry, we weren't aware of the existence of that problem.
 » 3 weeks ago, # |   +3 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)
 » 3 weeks ago, # |   0 Hi, can someone please point out what's wrong in my code for problem c 221747021
 » 3 weeks ago, # |   0 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
•  » » 3 weeks ago, # ^ |   0 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 -> 41 -> 3 -> 4 your dfs path will be like this : 1 — 2 — 3 — 4 — 3 — 4
•  » » » 3 weeks ago, # ^ |   0 Oh, i get it thanks
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone explain or send me an example code for D? I didn't understand editorial
•  » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   0 Thank you!
 » 3 weeks ago, # |   +12 K can be solved by kinetic tournament, https://codeforces.com/contest/1866/submission/221756159
 » 3 weeks ago, # |   0 Can anyone show me the mistake when using greedy in D? 221764341 WA on test 18
•  » » 3 weeks ago, # ^ |   0 Not sure that greedy works in D
•  » » 3 weeks ago, # ^ |   0 1 4 3 10 1 20 1 
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Thank you very much bro, I saw my problem thanks for your test.
 » 3 weeks ago, # |   +5 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
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 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. 222054066
•  » » » 3 weeks ago, # ^ |   0 Correct
 » 3 weeks ago, # |   0 Has anyone talked about H question? I didn't understand the solution.
 » 3 weeks ago, # |   0 in problem C, how can we know Zx>Zy what is the condition ?
 » 3 weeks ago, # | ← Rev. 2 →   +13 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: $\forall 0\leq l < r \leq m, p_r - p_l \leq u_r - v_l$ $\Leftrightarrow$ $\forall 0\leq l < r \leq m, v_l - p_l \leq u_r - p_r$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  » 3 weeks ago, # | 0 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?  » 3 weeks ago, # | ← Rev. 3 → 0 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.  » 3 weeks ago, # | +8 Can Someone pls explain H , I didn't understood editorial very well  » 3 weeks ago, # | +1 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: herePriority Queues submission link: here •  » » 3 weeks ago, # ^ | 0 yes I think it's normal, PQs are faster for some reason  » 3 weeks ago, # | 0 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  » 3 weeks ago, # | 0 could someone please explain check function for problem G  » 3 weeks ago, # | 0 In problem H how to calculate g(e) function i can't understand can anyone explain it.  » 2 weeks ago, # | 0 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.
 » 12 days ago, # | ← Rev. 3 →   0 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 way if 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.