Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

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(n2) solution when n ≤ 105.

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