ko_osaga's blog

[GYM Training Contest] KAIST RUN Spring Contest 2019 (XIX Open Cup. GP of Daejeon)
By ko_osaga, history, 6 years ago, In English

Update 2019/06/12: Me and MikeMirzayanov managed to upload the Div.2 contest into Gym. Huge thanks him for the great system, and also a kind help!

However, I decided not to just open it, but to give a training contest. The contest is scheduled in June 14 Friday, 09:00 UTC. Even considering some obvious bias from the setter, I'm personally very proud of the Div.2 contest :D I hope you participate and share the same joy with us! (and of course, please don't cheat!)

.

.

.

.

.

.

.

.

Update 2019/06/05: I managed to upload the Div.1 contest into Gym. Have fun! https://codeforces.net/gym/102201

Open Cup GP of Daejeon is scheduled at 2019/05/05 Sunday, 11:00 MSK. Daejeon is a city where KAIST is.

Division 1 problem set is identical with MIPT PreFinals Camp 2019 Day 6. It was held on March 15.

Division 2 problem set is identical with KAIST RUN Spring Contest 2019. It was held on May 1 locally. Like last year, it was an IOI-style contest, but as we are doing in OpenCup, subtask will be disabled. Some problems between Div1 and Div2 are shared.

Problems were created by ainta, Konijntje, ko_osaga, kriii, kdh9949. Some problems in Div1 were borrowed by Diuven, imeimi.

Problems were tested by arknave, dotorya, Namnamseo, tzuyu_chou, .o..

List of relevant previous contests:

Enjoy!

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

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

Who all can participate? How can i request for Login authorization?

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

    You will solve 0 anyway, it is for 2000+

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

      I request CF community to think before replying such harsh comments! It hurts and some of us are here just to learn and not think about ratings!

      I am sure CF community will show their support by downvoting the deserving comment!

      Peace!

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

        You don't have to think about rating to have one. He just said that this contest is too hard for you, and this is absolutely true.

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

          I agree with him and you as well but his comment was not required in the first place. Hope you agree on this atleast. And there is always a human way of saying the truth without hurting someone. :)

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

I got TLE in J using bipartite matching (O(√N*M)). Is there any faster solution or was my implementation too slow?

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

    My Kuhn works in 444ms, lol.

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

      Thank you. I copied your implementation of bipartite matching and got OK...

      I tried also this but it was too slow too. I'm interested in library codes of people who got AC in J in the contest.

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

    The intended solution also uses $$$O(E\sqrt V)$$$ bipartite matching. My solution runs in 420ms out of 3s.

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

    Did you solve whole problem with flow or search for matching of size n-1, and than full solution without flow? Solving second part with flow too shouldn't work.

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

      I used just bipartite matching and construct answer based on it like as the intended solution.
      This is my TLE source code.
      My maxflow library is not optimized for matching and the graph has 2N+M edges. Besides, the graph is held in linked list. I guess these are one of causes of TLE.

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

    https://codeforces.net/blog/entry/17023

    The article is in Russian, but you can try Google Translate and also it contains the key part of the source code.

    I googled it using the words "codeforces, burunduk, Kuhn" because I remembered that a fast implementation by Burunduk1 exists that everybody use when I struggle with Dinic.

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

      Thank you. I didn't know that article. It was easy to understand for also non-Russian speaker :)

      I tried to use BFS instead of DFS in Kuhn and it became faster.
      Then I changed it to multi-source BFS, it became faster more.

      code

      It looks close to dinic so I'm not sure but I think It could be $$$O(\sqrt{V} E)$$$.

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

Thanks for the participation!

Problemsetter:

Solution for Div1

Solution for Div2

We also know that solutions are poorly written, sorry :( Thanks to xuanquang1999 for pointing out critical typos in Div2B solution.

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

    Btw, I think this beautiful Voronoi Diagrams by Konijntje deserves some attention, so I'll leave it here. This is used in Div2 problem set.

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

Would the problem set be available in Codeforces gym later?

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

Where do these contests take place?

Is there an email address that I can contact for creating a sector?

I tried messaging snarknews but his last visit was 2 weeks ago.

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

How to solve C and I?

I assumed C is some dp over components of two-connectivity and parity of cycles, but did not come to the final solution.

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

    C: The solution in pdf is written by Endagorion, so it might differ with my intended solution.

    For a permutation $$$p$$$ to contribute to the determinant, $$$(i, p_i) \in E(G)$$$ for all $$$i$$$. This means $$$p$$$ should cover all vertices with the collection of edges and cycles. If it's a cycle, it should correspond to some biconnected component in cactus. So you can run DP on each BCC, where you can decide whether you cover a cycle, or not.

    There is a catch, because every permutation actually contributes to the answer by $$$inv(p)$$$ mod 2. However, it is equal to the number of even cycle in the permutation $$$p$$$ mod 2. So if you add matchings or even cycles, negate it.

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

      Thank you very much for your explanation!

      P.S. I somehow missed the post with the editorial, now I see :)

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

We solved E (7 minutes after the end) using a bit different (maybe equivalent?) approach rather than the mentioned one in the editorial.

First, find the partition for N lunches and N dinners (sort by lunch-dinner difference). Second, solve problems in decreasing order of sizes (from N-1 to 1) using the solution for the previous one.

At each step there are three possibilities:

  1. Remove two heaviest dinners and move the lunch with smallest difference to dinners

  2. Remove two heaviest lunches and move the dinner with smallest difference to lunches

  3. Remove the heaviest lunch and the heaviest dinner

We used the same 4 mentioned sets from the editorial to do it in $$$O(N \log N)$$$.

P.S. it looks that the solutions are dual, but I can't prove it :)

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

    I think it's same, just the difference of removing or inserting?

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

      True, it uses path shortening instead of augmenting it.

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

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

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

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

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

"Some problems between Div1 and Div2 are shared."

So who have seen the Div1 problemset should not participate in the Div2 contest?

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

    As you pointed out, some problems from Div1 will appear. Just like virtual participation, please do not participate if you know the hints or solution of the problem!

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

30 minutes left~

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

For B, I think the answer is always $$$1$$$ or $$$2$$$. The former case is trivial to detect. For the later case, I thought about choosing random $$$100$$$ vertices and then check each of them in $$$O(n^2 / 64)$$$ using bitset. But seeing how many submission get TLE, I don't think this solution is correct.

UPD: I have just read the solution for B, but I think there are some typo in the proof.

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

    There were some "heuristics" which sampled 100 vertices with the highest outdegree and passed. :) We tested all kind of $$$O(n^3/64)$$$ and didn't manage to make it work, AFAIR.

    By the way, I really liked problem B. It's my favorite along with problem I. Hope you liked it too.

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

      I liked problem B, even though I spent about 2 hours on it and still cannot come up with the intended solution.

      Btw, how did you generate testcases against brute-force solution that iterate through student in random order?

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

        Yeah, we thought it was the second easiest problem, but it was one of the game-changers in the onsite round... It's always hard to estimate difficulties of ad-hoc type problems.

        Strongest generator.

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

        Thank you for enjoying problem B! At first, the test data was very weak. But Konijntje and other setters found out some heuristics and I was able to make counterexample for those solutions.

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

From Problem A editorial:

Observe that, A+=A is equivalent to B/= 2, and vice versa...

Why is this true?

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

    Roughly speaking, we are only interested in the ratio A/B.

    → Reply