Pyqe's blog

By Pyqe, history, 14 months ago, In English

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
  • Vote: I like it
  • +138
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

VERY NICE CONTEST SUPERB

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

It was a very nice contest. Thanks!!

»
14 months ago, # |
Rev. 6   Vote: I like it +59 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain this elaborately?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You can read the solution of a very similar problem here. The main transition is exactly the same. Please reply here if stuck!

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

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

            1. add an edge from vertex $$$1$$$ to all vertexs exclude vertex 1.
            2. 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$$$.
            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              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?

              • »
                »
                »
                »
                »
                »
                »
                »
                14 months ago, # ^ |
                  Vote: I like it +13 Vote: I do not like it

                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;

              • »
                »
                »
                »
                »
                »
                »
                »
                14 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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.

»
14 months ago, # |
Rev. 2   Vote: I like it +58 Vote: I do not like it
My soln of K is simpler than editorial.
»
14 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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)

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like 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.