allllekssssa's blog

OpenCup — Grand Prix of Moscow
By allllekssssa, history, 6 years ago, In English

Hello,

Grand Prix has just finished!

Can anyone tell us solution for problems F and M? Can you tell me proof for solution of problem J?

  • Vote: I like it
  • +31
  • Vote: I do not like it

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

M is the same as this problem.

Can anyone tell me how to resolve the terrible precision issue for problem B?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's an LP of three variables. Nested ternary search worked for me without much trouble, but I don't know why it's precise enough.

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

      Sorry, I use binary search and reduce it to a half-plane intersection problems. I need to check whether the intersection is empty.

      And now the precision issue becomes out of control because the range of coordinate can be greater than $$$10^{13}$$$ now and the half-plane intersection problem itself is quite precision sensitive.

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

        I’ve used simplex, our implementation required only good epsilons here, but I’m not very good in this topic, I just think that the implementation is good.

        → Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

M: Let's work with the inverse permutation, then for each $$$S$$$, elements of $$$S$$$ should lie on a consecutive segment. Among sets that are not contained in other sets find the set $$$S$$$ that could be the leftest segment. It must satisfy the property that for each $$$A, B$$$ that are not contained in $$$S$$$ either $$$A \cap S \subseteq B \cap S$$$ or $$$B \cap S \subseteq A \cap S$$$.

After that we can split permutation into 2 segments $$$T_0 = S, T_1 = { 0, ..., n - 1 } \setminus S$$$. If some set $$$S'$$$ splits $$$T_i$$$ into two nonempty subsets, we know in which order they should be. So we split $$$T_i$$$ until each $$$S'$$$ is either a union of some $$$T_i, T_{i+1}, ..., T_{j}$$$ or contained in some $$$T_i$$$. After that we can solve recursively for each $$$T_i$$$.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

F: Choose $$$i$$$ and $$$j$$$ such that $$$s_i = s_j$$$ and $$$i < j$$$. There are $$$2^{j - i - 1}$$$ ways to choose something between them. We also need to choose some $$$k$$$ and choose $$$k$$$ elements to the left of $$$i$$$ and $$$k$$$ elements to the right of $$$j$$$. Choosing the same amount of elements from two sets of sizes $$$a$$$ and $$$b$$$ is the same as choosing $$$a$$$ elements from the set of size $$$a + b$$$. So each pair $$$(i, j)$$$ adds $$$2^{j - i - 1} \binom{i + (n - 1 - j)}{i}$$$ to the answer. We can split it into product of 3 parts: $$$2^{n - 2} (i + (n - 1 - j))! \cdot \frac{1}{i! 2^{i}} \cdot \frac{1}{(n - 1 - j)! 2^{n - 1 - j}}$$$. The first part depends only on $$$i + (n - 1 - j)$$$ the second on $$$i$$$ and the third on $$$n - 1 - j$$$. So we can count it with FFT.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Could you tell a bit more details about counting these values with FFT?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I forgot to mention that we do FFT for each character separately. Fix character $$$c$$$. Let $$$a_i = \frac{1}{i!2^{i}}$$$ if $$$s_i = c$$$ and $$$0$$$ otherwise and let $$$b_i = \frac{1}{i!2^{i}}$$$ if $$$s_{n - 1 - i} = c$$$ and $$$0$$$ otherwise. We calculate convolution $$$a * b$$$, multiply its $$$i$$$-th element by $$$2^{n - 2} i!$$$ and count sum for $$$i = 0..n - 2$$$.

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

        Cool. Looks like it's quite universal approach, which I didn't know about. Thank you!

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Choosing the same amount of elements from two sets of sizes $$$a$$$ and $$$b$$$ is the same as choosing $$$a$$$ elements from the set of size $$$b$$$.

    Of size $$$a+b$$$! Here is a related puzzle: you are blindfolded and in front of you lie a hundred coins — ten heads and ninety tails. You cannot identify the coins by touch, but you are allowed to flip them arbitrarily. You need to separate the coins into two sets (possibly of distinct size) containing the same number of heads each.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    For each element with value X we store the link to the closest element to the right with value X or X+1. Only O(1) links are adjacent to each element, so we can recalculate them when the value changes.

    We store the links in a link-cut tree with a special added sink vertex to the right. If the element has no link to the right, we link it with sink.

    To answer the query we fing the leftmost occurrence of $$$k$$$ on the segment, expose it and the sink and answer some standard query like "rightmost element in a binary tree with value less than something".

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

      Did 16 teams really write link-cut tree?

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

        I also wonder. Still, why else the time limit is 20s?

        P.S. Copy-paste, not write.

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

          Actually we wrote Link-Cut Tree for this problem. And it seems we need about 15s to pass some cases. I think it is because of the constraint is very large in this case.

          PS: According to what I've been told, the author tried very hard to generate data to prevent some O(nsqrt(nlogn)) to pass this problem...

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

        You can solve it with sqrt decomposition instead of link-cut

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

          What is your complexity for SQRT decomposition? I have solution with one extra log when I am answering to queries, Update is classic $$$O(\sqrt N)$$$ per query. So for me solution has around $$$5\cdot 10^9$$$ operations, for optimal block size.

          If you remove log, please explain me your idea :)

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

            You can solve it without extra logs, just follow ifsmirnov ideas, but for linkcut use sqrt decomposition

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            we also had O(n sqrt n) without logs as far as I understand but we had hard time to pass TL

            → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Can you explain this sentence a little bit more:

      Only O(1) links are adjacent to each element, so we can recalculate them when the value changes.

      As I understood each element can be right for many other elements, maybe I misunderstood sentence.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I think you misunderstood the part of "value X or X+1". It's not "and", so every node have one outdegree (and two indegree).

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here is a very short sqrt-decomposition which does the job. link. The point is to not batch over arrays, but to batch over queries and solve the problem in $$$O(N + Q^2)$$$ time. Really liked this problem (or maybe I was too stupid).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The answer is $$$n^{n-2} - \sum_{i=\lceil \frac{n}{2} \rceil + 1}^{n-1} n \cdot \binom{n-1}{i} \cdot i \cdot (n-1)^{n-1-i-1}$$$. In other words, you calculate number of all labeled trees and subtract all trees having one vertex with too large degree. The subtracted value is obtained using generalized Cayley's formula which already appeared in previous Opencup contest.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Note that we need only the position of the shift, not the number of inversions itself.

    What happens if we shift the whole permutation once? Consider the left element. Let it be $$$X$$$. It currently takes part in $$$X$$$ inversions, and will take part in $$$n-X-1$$$ inversion when moved to the last position of the array. So the change is $$$n-2X-1$$$ no matter where other elements are.

    To find the shift with minimum value we replace each element with $$$n-2X-1$$$ and find the prefix with minimum sum. It is done, for example, with a treap.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I misread the statement to find the number of inversions :(

      → Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

J: For every value, calculate the distance to its destination and sum these distances. In a single swap, this sum can not decrease for a 'free' swap and can decrease by at most two otherwise. So $$$sum/2$$$ is a lowerbound for the answer.

Furthermore, it is easy to see it is always possible that you can always choose two values to swap so that the either sum decreases by two, or the swap is free and the sum stays the same (choose a value that is in the wrong place, see what direction it needs to go, if the value in that direction needs to go in our direction or is in its final place, we found a valid swap, otherwise it needs to go in some other direction and continue searching from that value). We cannot keep making free swaps indefinitely, so eventually we will make a swap that decreases our sum by two, which proves that the lower bound can be attained.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

How to solve I?

K can be solved with a simple DP. Maybe Nash equilibrium is a scaring word.

→ Reply