punk_tech's blog

Is it possible to use complicated algorithms such as Hopcroft-Karp for t test cases? [SOLVED]
By punk_tech, 3 years ago, In English

I was trying to solve problem D from past tourist's contest using Hopcroft-Karp's algorithm. Here's my code

Yeah, I know that this problem has an easier greedy solution but I just want to check if it is possible to solve such a problem with a complicated algorithm at all. I've done some randomized tests for my code and they showed that on test cases where t = 1 and n = 2e5 my submission would get AC 62ms but on test cases where t = 1e4 and n = 20 my code exceeds 15 sec.

I don't know what the problem is. Time complexity of Hopcroft-Karp is O(E*sqrt(V)) which is O(t * N*sqrt(N)) in my case. I have a suggestion that it can be explained by high hidden constant of the algorithm.

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

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Yeah, why not? Here's my in-contest submission using hopcroft.

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

I solved it using Dinic's algorithm, and Hopcroft Karp should perform at par, if not better. Here's my submission: 122817211

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

=putin(layer); You are using memset on an array of size 1e6 for 1e4 times. It is bound to give TLE.

→ Reply