angelg's blog

Estimated Time Complexity Of My Solution?
By angelg, history, 9 years ago, In English

Hello, today took place round #313. I have recently read some articles regarding hashing and how useful they can be to compare to strings really fast. When I read problem D (Equivalent Strings), I came up with a possible solution using DP and Hashing. It took me quite some time to get it to work properly, but sadly I got a TLE veredict after the final tests came through. This is my solution: http://codeforces.net/contest/560/submission/12189499.

After the contest, I managed to make it work slightly faster, but it only got AC after changing the recursion order, I know this in fact affects the running time of my solution. But I still haven't been able to figure the actual time complexity of this solution. I used four states representing the segment of string A and B we are currently checking if they are equivalent or not. I had to use a map, in order to keep a memo for the states already calculated. With the help of hashing, I believe the string comparisons could be done quite fast.

Cheers, Angel

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

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't think hashing and memoization in your solution improves the time complexity. In the worst case it will perform the obvious recursion 

solve(a, b) = (solve(left(a), left(b)) && solve(right(a), right(b)) 
          ||  (solve(left(a), right(b)) && solve(right(a), left(b))

Number of steps for such recursion can be described by similar recursive formula . There are formulas for solving such recursions, but in this case result can be easily guessed by writing first few terms.

f(1) = 1
f(2) = 4·f(1) = 4
f(4) = 4·f(2) = 16
f(8) = 4·f(4) = 64
f(N) = N2

It means that the time complexity is O(N2). In your solution it might be even worse due to the map and hashes, probably or more.

As discussed in this blog tests were weak, and such solution shouldn't have passed.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply, the Master Theorem link was very helpful to understand better the complexity of recursive solutions. I know my solution is even slower than the one most of people tried as it takes around 1 second. But, It's always a good to learn new things. Maybe, next time I won't waste my time coding solutions are not correct given the timelimit. Once again, thanks for your time.

    → Reply