### Zlobober's blog

By Zlobober, 5 years ago, translation, ,

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).

• +248

 » 5 years ago, # |   +83 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.
•  » » 5 years ago, # ^ |   +13 And problem I — I believe it's not a good idea to try to separate MCMF and Hungarian. Both are O(n^3).
•  » » » 5 years ago, # ^ |   +3 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.).
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +7 Interesting fact: most of the people who had issues with MCMF fitting into the time limit never have issues with long long.
•  » » » 5 years ago, # ^ |   +3 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).
•  » » » » 5 years ago, # ^ |   +13 OK maybe my implementation was bad — is O(E log E) dijkstra faster than O(V^2) in practice?
•  » » » » » 5 years ago, # ^ |   0 With set: 1.2sV^2: 0.49s
•  » » » 5 years ago, # ^ |   0 MCMF with Ford-Bellman works 0.8
 » 5 years ago, # |   +5 " 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?
 » 5 years ago, # |   +33 where can see the problems?