Fork512Hz's blog

By Fork512Hz, history, 3 days 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

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

My KMP passed by memoising it 260210442

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm taking a look

»
3 days 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.