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!
Could you please explain this elaborately?
You can read the solution of a very similar problem here. The main transition is exactly the same. Please reply here if stuck!
Thankyou, I understood it!
HELP, 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:
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.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.me/contest/1866/submission/221741172)
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.me/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
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 toNK^2
using someprefix-max
calculation. 222054066Correct
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
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
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.