USACO — Secret Code

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

USACO — Secret Code

Автор determinism, 11 лет назад, По-английски

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?

usaco, algorithm complexity, tle

determinism
11 лет назад
5

Комментарии (5)

Написать комментарий?

tenshi_kanade

11 лет назад, скрыть # |

+14

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

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

O(N⁴): 100
O(N³): 500
O(N²): 10000
O(2^N): 27
O(N * 2^N): 22

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

→ Ответить

determinism

11 лет назад, скрыть # ^ |

Thank you!

→ Ответить

goo.gl_SsAhv

11 лет назад, скрыть # |

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

→ Ответить

determinism

11 лет назад, скрыть # ^ |

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

→ Ответить

goo.gl_SsAhv

11 лет назад, скрыть # ^ |

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));

→ Ответить