Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Fork512Hz's blog

By Fork512Hz, history, 10 months 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 >n and 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

»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

My KMP passed by memoising it 260210442

»
10 months 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.

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

https://mirror.codeforces.com/contest/1968/submission/301727963 I have also encountered the same problem. Can you help me see why this kmp cannot pass this question. I think the complexity of KMP is correct.

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

https://mirror.codeforces.com/problemset/submission/1968/303781322 Hello my friend, just now I was inspired and discovered a very effective optimization method that can reduce the time from 3.2s to 0.6s. My friend, you can notice that many prefixes of length i are repeatedly calculated many times during the binary kmp process. We can optimize these repetitions by using a memory array. The optimized efficiency is as high as 80%, which is astonishing! The code I have modified will be marked with//#############################################################