Zlobober's blog

By Zlobober, 23 months 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  

»
23 months 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.

  • »
    »
    23 months 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).

    • »
      »
      »
      23 months 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.).

      • »
        »
        »
        »
        23 months 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.

    • »
      »
      »
      23 months 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).

      • »
        »
        »
        »
        23 months 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?

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      MCMF with Ford-Bellman works 0.8

»
23 months 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?

»
23 months ago, # |
  Vote: I like it +33 Vote: I do not like it

where can see the problems?