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

hsr's blog

By hsr, history, 5 years ago, ,

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:

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

• +9

 » 5 years ago, # |   0 I experienced the exact seemingly mysterious behavior.
 » 5 years ago, # |   0 Same here: I am curious why this happens and how to avoid this in future contests.
•  » » 5 years ago, # ^ |   +7 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 →   -8 Can you explain why the above solutions are $O(n^2)$?
•  » » » » 2 months ago, # ^ |   0 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.
•  » » » » » 2 months ago, # ^ |   0 Thanks!
 » 5 years ago, # |   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 years ago, # |   0 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, # |   -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.