Блог пользователя Mastermind222

Same solution gave TLE during system testing but passed during practice.
Автор Mastermind222, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить