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

TLE on Equivalent Strings
Автор hsr, история, 9 лет назад, По-английски

I was solving http://codeforces.me/contest/560/problem/D

No matter how much I tried, I could not get pas testcase #91, it was always TLE for that one.

Then I tried switching the order in which the recursive function is called and then the programs passed within 31ms (program had 2s timelimit)

Here are the 2 solutions:

Accepted : http://codeforces.me/contest/560/submission/12186813

TLE : http://codeforces.me/contest/560/submission/12186933

Is there any reason why it failed or is it by pure co-incidence that the test cases broke my program.

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

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

I experienced the exact seemingly mysterious behavior.

AC solution: http://codeforces.me/contest/559/submission/12188140

TLE solution: http://codeforces.me/contest/559/submission/12170145

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

Same here: I am curious why this happens and how to avoid this in future contests.

AC: http://codeforces.me/contest/560/submission/12188369 TLE:http://codeforces.me/contest/560/submission/12188347

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

    I am curious why this happens

    weak tests

    and how to avoid this in future contests

    don't send O(n2) solution when n ≤ 105.

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

Same here. 12188567 vs. 12188586. You can't really prepare for stuff like this. Those who had the right order in their recursion got very lucky, I guess.

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

Your TLE version could be accepted if you drop duplicate work as follows:

bool eqs(const char* a, const char* b, int n)
{
    if (n % 2 != 0)
        return strncmp(a, b, n) == 0;

    n /= 2;
    return eqs(a, b, n) && eqs(a + n, b + n, n) || eqs(a, b + n, n) && eqs(a + n, b, n);
}

In other words, you compare strings at the beginning of the call and do the same with the halves on every next recursive call again. After eliminating this the solution should pass the tests, I believe.

→ Ответить