Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

hsr's blog

By hsr, history, 5 years ago, In English,

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

TLE : http://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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I experienced the exact seemingly mysterious behavior.

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

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

»
5 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://codeforces.com/contest/560/submission/12188369 TLE:http://codeforces.com/contest/560/submission/12188347

  • »
    »
    5 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(n 2) solution when n ≤ 105.

    • »
      »
      »
      2 months 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)$$$?

      • »
        »
        »
        »
        2 months 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.

»
5 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I checked the editorial.I should have split and rejoined both strings according to lexicographic order.. then only one recursion call is required per length instead of the two like all of the solutions posted here are using. Nice question, it's not about luck .

»
2 months 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.