ko_osaga's blog

[Gym] XXI Open Cup. Grand Prix of Korea
By ko_osaga, history, 4 years ago, In English

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

Special thanks to xiaowuc1 for revising our English.

List of relevant previous contests:

Enjoy!

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

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

What will be level of problems ,is it recommended for Div 2 participants?

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

    The problemset is designed for teams preparing ICPC Semifinals or World Finals.

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

Will there be a Div2 OpenCup contest?

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

    I sent it to Snark, but apparantly he didn't processed it. Div2 counterpart (KAIST 10th ICPC Mock Contest) will be uploaded to Gym shortly after.

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

      You mean shortly after the Div 1 starts today, or in a few days?

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

        I hope the former unless sth is broken.

        I can't guarantee, so if you want team participation, it's better to schedule later.

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

Is there Div 2 editorial?

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

I: Subtract version. Only master is to calculate subtree sum quickly.

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

How to solve F?

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

    Interval graph is acyclic if there are at most 2 intervals at each point. If this is true then you can divide these alive intervals into two sets of nonoverlapping intervals. Hence you can solve this using maxflow mincost, where flow has value 2 and there are edges $$$i \to i+1$$$ with capacity $$$2$$$ and cost $$$0$$$ and $$$s \to e+1$$$ with capacity $$$1$$$ and cost $$$-w$$$ for each interval. To speed things up you need to compute potentials with dynamic programming instead of Bellman-Ford/SPFA and you can do this since this graph is acyclic.

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

      Apparently you don't need to compute potentials quickly, we passed pretty comfortably with book SPFA.

      EDIT For reference, we just used https://github.com/ecnerwala/cp-book/blob/40b6ce3f17a5b917531b44404fbc7d9e0d1e4cd7/src/mcmf.hpp, which is based on https://github.com/kth-competitive-programming/kactl/blob/3e39f71e55fb414540d518b11dc40216fe22fe1a/content/graph/MinCostMaxFlow.h but supports sparse graphs.

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

        We didn't :(

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

        I would say that your implementation is quite far from book SPFA, for me it's unintuitive that abusing priority queues in such a way is even possible :)

        We tested all kinds of SPFA listed in Wikipedia, and any of them couldn't pass our data in <15s, which was in turn 100% random.

        Also, I'm convinced that yours could provably run in $$$O((n + m) \log n)$$$ time given that the underlying graph is DAG.

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

        Doesn't this shortest path algorithm works exponentially long on test like

        1 3 -2
1 2 -1
2 3 -2
3 5 -2
3 4 -1
4 5 -2

        and so on?

        I'm not sure if tests like this are constructible in min-cost-like problems, but seems to be strange. Anyway, it would probably be very fast on average.

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

          I haven't looked in a while, but I thought it is upper bounded by O(VE). It might not be though...

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

          Ah, I remember how it works. In SSPA, if all edges are initially positive cost, then we maintain a potential function which ensures they stay positive, so the runtime is just Dijkstra. If the edge costs can be initially negative, you should run a first pass of Bellman Ford to initialize the potential function (which I seem to be missing, but KACTL has).

          Our implementation adjusted the edge costs to implicitly choose a potential function of -x*10**12, just like Petr suggested.

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

            If all edges are initially positive, it's okey. I thought you are claiming your code to work with negative edges too, and was a bit surprised.

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

      We just set the initial potentials to -x*10**12, no need for dynamic programming :)

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

Thank you for your participation!

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

How to A properly? Our solution is:

For two vectors a and b the maximal number of things we can present is max flow of the complete bipartite graph with unit edges between the sides, and with edges from source to left with capacities $$$a_i$$$ and from right to sink with capacities $$$b_i$$$. Or, equivalently, min cut. If we take $$$k$$$ vertices from the left side into the mincut and $$$m - l$$$ vertices from the right side, then we need to check if the sum of maximal $$$k$$$ $$$a_i$$$-s plus sum of maximal $$$(b_j - k)$$$-s minus sum of all $$$b$$$-s can be greater than zero, or something. This is a segment tree with += on subseg and getmax on the whole tree. Did 46 teams implement the exact this? I think it's quite tricky to avoid mistakes here.

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

    I implemented that. It's not mandatory to interpret such as maxflow, but I don't know any other solution that has a different implementation.

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

      Our interpretation was something similar to the Erdos-Gallai theorem so the implementation wasn't as tricky, but we had a lot of failed submissions because of other reasons xD

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

    Quite standard problem and approach I would say. Moreover you can copy and paste this segment tree to E and L!

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

      Yea, today I've used the same segment tree in 3 problems xd

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

    This problem is almost the same as the bipartite graph realization problem. Our team googled and found out the Gale–Ryser theorem. It's not hard to prove that after changing the condition of $$$\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n b_i$$$ to $$$\sum\limits_{i=1}^n a_i \leq \sum\limits_{i=1}^m b_i$$$, the theorem works for this problem. The remaining part is just using a segment tree to keep track of the inequalities.

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

Where to find problems?

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

How could one upsolve div2 contest ?

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

E was nice, but almost identical to this problem: https://codeforces.me/contest/1109/problem/F

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

    I even have a TLE attempt on this problem, what a shame. Sorry!

    Actually, the problem had an underlying graph as a tree, but we have changed it after I remembered a problem in Ptz which was exactly the same. Though, the model solution was a complicated $$$O(n \log^2 n)$$$ one, and my solution was n^2.

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

I love this set, thanks!

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

Our solution in E was in $$$O(n\log{n})$$$ time, yet no link-cut or other fancy structures were required; the main part of our solution was to find such $$$r$$$ for each $$$l$$$ that the induced subgraph on vertices $$$[l, r]$$$ is a set of isolated paths and vertices; this is done by maintaining the paths as a set of treaps (each path is an in-order traversal of some treap) and then moving two pointers, after this some segment tree.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it +18 Vote: I do not like it

    300iq provided a fix to my idea. So we can use the Queue Undo Trick for this idea, by imagining that we insert and pop vertices, as here inserting vertices is $$$O(1)$$$ updates to dsu, but we cannot use this to replace the LCT in editorial.

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

The contest is ready in Codeforces Gym. Enjoy!

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

A set of interval covers each point at most K times if and only if it can be partitioned into K disjoint set of intervals. You can prove this by greedy algorithm or using the fact that interval graphs are perfect.

What does perfect mean in the editorial?

→ Reply