thecortex's blog

By thecortex, history, 8 years ago, In English

Hello,

I'm getting time limit exceeded on this problem; 710F - Операции над множеством строк

Any idea how to tweak my solution to avoid this quadratic runtime in method "count". I reviwed others solutions, and they are all quadratic, but why my implementation is just slower?

The nested for loop gives an asymptotic runtime of O(L^2) where L is input string length.

My solution; 20459110

Any hints would be truly appreciated!

Thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Your implementation of trie for counting procedure will take too much time. So, algorithm runs int O(L^2) , you also notice it. So, as the length could be of L=300000 ,So, Codeforces server could not run 90000000000 operations in 3 seconds. You may generally assume that codeforces server can run 10^8 operation in 1 second. You may solve above problem in O(N*sqrt(N)) by handling small and large queries separately. You may refer to my code for further details. 20158098