Блог пользователя allllekssssa

Автор allllekssssa, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

M is the same as this problem.

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve G?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Did 16 teams really write link-cut tree?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        P.S. Copy-paste, not write.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +16 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve L?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

How to solve I?

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