Fork512Hz's blog

[1968G2 — Division+LCP] Need help: desparate 3200ms TLE41, KMP worse than Z-func by constant?
By Fork512Hz, history, 2 weeks ago, In English

I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $$$>\sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

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

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

My KMP passed by memoising it 260210442

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OK. To recover from this I went to learn Aho-Corasick Automaton this evening and it went out pretty funny, 25/26 test cases passed on the template.

→ Reply