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.
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
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
weak tests
don't send O(n2) solution when n ≤ 105.
Can you explain why the above solutions are $$$O(n^2)$$$?
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.
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.
Your TLE version could be accepted if you drop duplicate work as follows:
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.