Mastermind222's blog

Same solution gave TLE during system testing but passed during practice.
By Mastermind222, history, 4 years ago, In English

This is in regard with Codeforces Round #660-Div 2 Problem B. I submitted a solution to this problem in O(n) time complexity. It passed all the pretests but gave TLE in system testing but later during practice the same code was accepted.

Solution submitted during contest: https://mirror.codeforces.com/contest/1388/submission/88486803 gave TLE.

Solution submitted for practice: https://mirror.codeforces.com/contest/1388/submission/88530257 passed all the test cases.

Can anyone explain me why it happened? Thanks in advance!

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

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

Auto comment: topic has been updated by Mastermind222 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Change the line where you wrote

s = s + '9'

to 

s += '9'

writing s = s + '9' makes your algorithm 0(n^2) because you duplicate the variable s every time

Hope this helps :p

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

This code is $$$O(n^2)$$$:

for(int i=0;i<n;i++)
s=s+"9";

But can easily be fixed to be $$$O(n)$$$.

for(int i=0;i<n;i++)
s+="9";

Also personally I think the indentation is a bit confusing, at least indent the inside of the loop and/or add braces:

for (int i=0;i<n;i++) {
    s+="9";
}

My guess is maybe the compiler was able to catch this and optimize it the second time? P.S. you never used cin fastio.

→ Reply