Spheniscine's blog

By Spheniscine, history, 4 years ago, In English

A – Repeat ACL

Spoiler

B – Integer Preference

Spoiler

C – Connect Cities

Spoiler

D – Flat Subsequence

Spoiler

E – Replace Digits

Spoiler

F – Heights and Pairs

Spoiler
  • Vote: I like it
  • +57
  • Vote: I do not like it

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

Thanks for the detailed explanations!

Unfortunatly I still do not get F at all, I am out before the interesting part. Here are my questions:

The term "matching" does mean... a pair of two persons, or the set of pairs in one permutation?

I think I understand the definition of $$$pairs(n)$$$. Is there a difference to $$$pairs(N)$$$?

The function $$$f(k)$$$, what exactly is the meaning of $$$f(1)$$$, it is the number of permutations with one... what?

How do you come from $$$f(k)$$$ to $$$BAD(x,y)$$$, there is the term "seed"?

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

    Matching means a state where all the people are paired up (and some might be bad pairs)

    $$$pairs(N)$$$ simply means the $$$pairs$$$ function called on the $$$N$$$ given in the input

    $$$f(k)$$$ is the number of sets of exactly $$$k$$$ bad pairs, such that within a set, no person appears twice; i.e. the cardinality of $$$F_k$$$. It's used to "fix" $$$k$$$ bad pairs before matching the rest using $$$pairs$$$.

    The rest is just a way to tie the set-theoretic definition of the inclusion-exclusion principle to the counts we are interested in. There might be room for improvement there

    edit: Oh I noticed a use of "matching" when defining a bad pair, thus being inconsistent, I shall fix it

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe try reading the "counting derangements" example in the Wikipedia page for the inclusion-exclusion principle; it's an analogous but simpler example of the application in this problem. When counting derangements of cards, you count the number of permutations fixing one matching card, two matching cards, etc., same applies here with fixing one bad pair, two bad pairs, etc.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D:

There is also a way to solve this using only an ordered map.

Can you explain it a bit?

  • »
    »
    4 years ago, # ^ |
    Rev. 10   Vote: I like it +3 Vote: I do not like it

    Problem D, and E much more transparently, can both be reframed as what I call "segment painting" problems. They're basically like the "junior" version of lazy-segtree where a range query is always followed by an assignment in the same range, thus destroying or truncating ("painting over") any old segments in the way.

    The method is as follows — use an ordered map of entries $$$r \rightarrow (l, s)$$$, denoting a segment in the range $$$[l, r)$$$ (half-open ranges are convenient here) with metadata $$$s$$$ (e.g. the length of the longest subsequence in D, the digit in E). On each update, you have a new segment $$$(l_{new}, r_{new}, s_{new})$$$; iterate through the map starting from $$$l_{new}+\varepsilon$$$ (using e.g. upper_bound in C++ or higherKey in Java). Then you may do something with each overlapped segment (in fact you may even decide $$$s_{new}$$$ with this step), and remove them from the map. If the old segment isn't completely covered, it should be replaced with a smaller segment (truncation); in fact this may split an old range into two, in the case of $$$l_{old} < l_{new} \wedge r_{old} > r_{new}$$$. Stop when you either reach the end or find a non-overlapping segment, then add the new range to the map.

    This works in $$$O(n \log n)$$$ because each operation adds a maximum of $$$3$$$ range entries to the map, and only iterates through and immediately removes older entries.

    E is quite straightforwardly solved this way, but D requires a transformation where points $$$A_i$$$ are replaced by segments $$$[2A_i - k, 2A_i + k + 1)$$$. Funnily enough I found this solution before the segtree solution (and only after solving E), due to how brains work sometimes...

    (Food for thought: is there a problem that can be solved this way that lazy-segtree can't, due to greater flexibility?)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you provide link to your submissions, in case you solved using an ordered map?

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

      Thank you for your solution. Pretty cool technique. For those who want to check out C++ solution for Problem E

      Link to submission : https://atcoder.jp/contests/abl/submissions/17139903

      But I am still not clear about the complexity part. What I understood so far :

      1. Data Structure will always hold non overlapping ranges
      2. While adding a new range at most 3 entries needs to be made (if it overlaps with some other range i.e 2 after breaking old range and 1 for new range)
      

      What I didn't understand is "and only iterates through and immediately removes older entries.". Can you please elaborate it a bit more, because I guess this the crucial part for calculating complexity.

      Can you please explain why there is bound on number of elements that we will be iterating over in our data structure?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Iterating through the map takes $$$O(\log n)$$$ per entry, but you delete entries right after iterating through them (except for the one that tells you to stop, but that's only one per step), so you can amortize that cost into the cost of the step that placed that entry into the map.

        It's analogous to the analysis of stack-based problems. A single step may iterate through and remove many older entries of the stack, but those entries must have already been added by a previous step, and once an entry is removed they won't be accessed anymore.

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

Auto comment: topic has been updated by Spheniscine (previous revision, new revision, compare).

Necro-edit to problem F with a new explanation of PIE. Hopefully this is easier to understand than the previous revision.