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

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

Update 2019/11/07. The contest is now in Gym. Thanks to MikeMirzayanov for uploading it. Have fun!

Hello! I'm happy to announce XX Open Cup. Grand Prix of Korea.

List of relevant previous contests:

Enjoy!

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

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

I can't wait to solve them

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

Best sentence of the problem-set: If you know about “cardinals,” please assume that “infinite” refers only to “countably infinite.” If you don’t know about it, then you don’t have to worry.

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

How to solve I?

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

      We almost removed I due to that issue (apparently it's well known in China), but I just decided not to. Hope you enjoyed our contest anyway.

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

        Yes, other problems were pretty nice.

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

        That's a beautiful problem but I've seen it so many times already... It's well known in Poland as well and I guess everywhere else too

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

          I initially made an easier problem, but .o. lately discovered that it was solvable for a general graph, hence the current form.

          I don't think it was known in Korea (at least no testers knew), so it was nice to use for local contests. For OpenCups, I agree that it's not enough to please top-level contestants since the topic is pretty general.

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

          Also it was in Jagiellonian U Contest, at winter ptz camp 2013 (Problem H. Hunt).

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

    I thought it was something like we can find all pair shortest distance between all the vertices. Let, the maximum distance d be between u and v. These will be our two ends of the diameter. After that, we find a path between u and v, of distance d. We then add the rest of the vertices in a greedy manner so that our diameter remains unchanged. Can we approach the solution like this?

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

So, is it possible to solve J faster than O(nlogn) with Treap? Our solution is still getting TL 13.

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

    You can maintain $$$dp_i - dp_{i-1}$$$ in heap.

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

      Can you explain please? I don't think we can change Treap in our solution without getting O(nlog^2n).

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

    You can use std::priority_queue instead of treap. I claim that the complexity would still be $$$O(n \log n)$$$. Indeed, unlike the more common situation, when we merge things that have size $$$O(\text{subtree size})$$$, here we merge things that have size $$$O(\text{subtree depth})$$$. It is quite well-known that we will do only linear number of operations in that case (and each of them takes $$$O(\log n)$$$ time).

    The solution is not particularly quick even with heap (the implementation below took ~0.5s on Yandex.Contest), so it is unsurprising (though unfortunate) that using treap may give TL.

    Code

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

      Oh, std::priority_queue is probably much faster than the nonsense I was doing with std::multiset.

      Our solution ran in 1.161s during the contest, but strangely runs twice as fast when I resubmit the same code now at ~0.5s.

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

How to solve I and J? We wrote the solution of J using heavy-light ,, but I think it has a simple solution :( Can anyone explain ?

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

    How to solve J using heavy-light?

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

      I proved for my opinion , if for $$$k$$$ we take some set of vertices , for $$$k + 1$$$ we need only add some vertices to that set. Now we can solve problem only for $$$k = 1$$$. After we find set of vertices for $$$k = 1$$$ , we can delete vertices of that set and do it again for the new tree.

      For vertex $$$v$$$ we take difference $$$dif[v] = (val[v] - \sum_{to}{dp[to]})$$$ where $$$to$$$ is the child of $$$v$$$ , $$$dp[to]$$$ is the answer for subtree of $$$to$$$ for $$$k = 1$$$ and $$$val[v]$$$ is the value which is given in the statement.

      Now for $$$k = 1$$$ , how we find vertices that we need? The vertex $$$v$$$ is in the set if and only if $$$dp[v] = val[v]$$$ therefore we need that $$$dif[v] >= 0$$$ (We can find this with simple segment tree). After we take this vertex we delete that vertex (give the value of $$$dif[v]$$$ $$$-infinite$$$ in the segment tree) and doing update $$$dif[x]$$$ $$$+$$$$$$=$$$ $$$dif[v]$$$ , for any vertex $$$x$$$ from $$$root$$$ to $$$parent[v]$$$ (update this with heavy-light decomposition).

      P.S. We got WA7 during the contest.

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

Congratulations to Polish Mafia (mnbvmar, Radewoosh, Marcin_smu) for the first place by a huge margin, and also being very close to all solve!

Here is the solution.

I hope you enjoyed the contest!

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

    I think time limit for problem F was very tight, we did the segment-tree variant and it was impossible for us to squeeze it in time.

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

      I have got TL 46, but it wasn't related to the segment tree speed. Try checking maxtest with $$$O(n)$$$ add queries with $$$k = 0$$$ and $$$O(n)$$$ third type queries with $$$x = 0$$$.

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

    I really enjoyed the problemset, thanks for it!

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

    In K I also built centroid decomposition for one tree and reduced problem to $$$\min_{u \neq v}(a_v + d(v, u) + a_u)$$$ on the compressed second tree. But for some reason I thought that the fastest way to solve it is also centroid decomposition, so I wrote 2-dimensional centroid decomposition. It's $$$O(n\log(n)^2)$$$ with huge constant, but passed in 9.5 seconds.

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

    An alternative solution for D:

    Consider only positions of 2. If you move all 2s into the correct position, then 1s are in the correct position automatically.

    Let's assume the assignment of 2 are fixed (matching of starting positions and ending positions). Let d_i : |start position of i-th 2 — end position of i-th 2|. Then, the lower bound of the cost is (the sum of ( (d_i/2) * (C+1+1+2) + (d_i%2) * (C+1+2) ) ) + (number of inversions in assignment).

    And, surprisingly, it is always possible to do (you can find at least one optimal move in each situation)

    So, we can use dp[][] for each parity. The time complexity is O(N^2) and you can find the actual order of operations by topological sort.

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

Contest was good, big thanks to authors

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

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

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

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