determinism's blog

USACO — Secret Code
By determinism, 9 years ago, In English

I was trying to solve this problem. I've found a solution whose complexity is O(N^4) (N = length of string). Since N might be 100, I've thought that it's not fast enough. Then I looked at the official solution, surprisingly, it is almost same with mine. Can someone explain the complexity of this algorithm and tell why it isn't TLE?

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

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

If N is at most 100, then O(N4) is fine, since 1004 = 100M.

As a rule of thumb, try to remember the approximate limits for different complexities...

  • O(N4): 100
  • O(N3): 500
  • O(N2): 10000
  • O(2N): 27
  • O(N * 2N): 22

Surely, it will depend on the time limit and the constant factor of your algorithm, but it's useful to remember those values.

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

Also you can precompute all string comparsions to reduce complexity to N^3.

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

    Can you explain how we can precompute? Wouldn't it be O(N^4) too?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      bool isEqual[N][N][N];
for (size_t i = 0; i < s.size(); ++i)
    for (size_t j = 0; j < s.size(); ++j)
    {
       isEqual[i][j][0] = true;
       for (size_t k = 1; k <= s.size() - max(i, j); ++k)
          isEqual[i][j][k] = isEqual[i][j][k - 1] && s[i + k - 1] == s[j + k - 1];
    }
isEqual[i][j][k] == (s.substr(i, k) == s.substr(j, k));
      → Reply