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).
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).
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 164 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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.
And problem I — I believe it's not a good idea to try to separate MCMF and Hungarian. Both are O(n^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.).
Interesting fact: most of the people who had issues with MCMF fitting into the time limit never have issues with
long long.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).
OK maybe my implementation was bad — is O(E log E) dijkstra faster than O(V^2) in practice?
With set: 1.2s
V^2: 0.49s
MCMF with Ford-Bellman works 0.8
Non-deterministic?
where can see the problems?