Блог пользователя determinism

USACO — Secret Code
Автор determinism, 10 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится 
      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));
      → Ответить