hsr's blog

TLE on Equivalent Strings
By hsr, history, 9 years ago, In English

I was solving http://mirror.codeforces.com/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://mirror.codeforces.com/contest/560/submission/12186813

TLE : http://mirror.codeforces.com/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.

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I experienced the exact seemingly mysterious behavior.

AC solution: http://mirror.codeforces.com/contest/559/submission/12188140

TLE solution: http://mirror.codeforces.com/contest/559/submission/12170145

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

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

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

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

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      Can you explain why the above solutions are $$$O(n^2)$$$?

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

        The run time is bound by the recurrence: T(n) = 4 * T(n/2) + O(n), where n is the length of the two strings.

        By the Master Theorem the running time is quadratic.

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

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply