jay__0208's blog

UNEXPECTED TLE !! is it ME ?? or is it PYTHON?? or is it CODEFORCES??
By jay__0208, history, 4 years ago, In English

Recently I gave Codeforces round #660 (Div 2) ============================================= ,

where i solved problem B in O(n) time complexity After doing the problem in O(n) I still get TLE !!! and its not only me I get to know many other also faced this problem

EVEN C++ O(n) SUBMISSION GOT TLE !!!!!

My submission : http://mirror.codeforces.com/contest/1388/submission/88472454

A C++ Submission : https://mirror.codeforces.com/contest/1388/submission/88470034

  • Vote: I like it
  • -48
  • 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 jay__0208 (previous revision, new revision, compare).

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

For 1, I think it's PyPy.

I tested the code in custom test. With Python 3.7.2 I got 124ms, but with PyPy 3.6 I got 2261ms.

For 2, It's $$$\mathcal{O}(n^2)$$$. string::operator= is $$$\mathcal{O}(n)$$$ and you used it $$$\mathcal{O}(n)$$$ times. The correct way is using string::operator+=.

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

The runtime of Python string concatenation is the length of the combined string, not O(1)

https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python

You code therefore runs in O(n2).

You will get familiar with Python data structures over time. Today I learnt how to call a function recursively in Codeforces.

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

    No actually loujunjie is correct , and the same code is running properly in python 3 where as not in pypy 3 but codeforces only says pypy is always faster than python

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

In python, strings are immutable.

When you concatenate strings then it creates a new instance. So every time you add a character to a string it creates a new instance of that string which takes O(n) time. And you do this n times so O(n*n). It's always better to use list instead of string in such cases.

alternative 1
alternative 2
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    It's not true. Python interpreter developers already added the optimization for this pattern back in 2004.

    += is slow (compare to join), but not so slow to be $$$\mathcal{O}(n)$$$ each time. But It seems PyPy doesn't have this optimization, leading to the TLE of OP.

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

      This makes sense. you are right they added optimization but it is very slow as compared to join. I tried same code with n = 10^7. And it took 7.8 sec with += and 1.5 sec with join. So asymptotically += is not O(1) (not even amortized).

      IMO, join is best practice.

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

https://mirror.codeforces.com/contest/1388/submission/88530339

https://mirror.codeforces.com/contest/1388/submission/88530040

Might help

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

Please don't shout.

→ Reply