Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Zlobober's blog

GP of Ekaterinburg
By Zlobober, 9 years ago, translation, In English

GP of Ekateinburg has just finished. Let's discuss problems here. How to solve H?

(Russian version of the post contains my anger about statements).

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

»
9 years ago, # |
  Vote: I like it +83 Vote: I do not like it

Problem H: https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm

Well, is it allowed to use such tasks in contests? This task is just a copy of Schreier and Sims' idea and there is zero originality. I hope authors to come up with original tasks.

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

    And problem I — I believe it's not a good idea to try to separate MCMF and Hungarian. Both are O(n^3).

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

      MCMF worked 0.336 seconds in my case, not even close to TL (and I believe it can be still optimized a lot, by changing long long to int etc.).

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

        Interesting fact: most of the people who had issues with MCMF fitting into the time limit never have issues with long long.

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

      Were they actually trying to separate them though? I passed with Dijkstra on Set in my Min Cost Flow. So it was even O(N^3logN).

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

        OK maybe my implementation was bad — is O(E log E) dijkstra faster than O(V^2) in practice?

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

      MCMF with Ford-Bellman works 0.8

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • " If the number of points N ≥ 12, this set is divided using straight lines.
  • If the number of points N ≥ 12, then this set is divided into the set of 3 and N−3 points. "

Non-deterministic?

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

where can see the problems?

→ Reply