ovi_ivo's blog

Same code but python3's got an AC and PyPy3's got a TLE, why though?
By ovi_ivo, 5 years ago, In English

Hey there,

I solved 1214C - Bad Sequence of today's Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises) in Python3 and submitted it selecting PyPy3 as the compiler but I got TLE on test case 87. After the contest, I submitted the same code selecting Python3 as the compiler and got an AC.

Why so?

AC submission: 60028782; TLE submission: 60028578

Anyone care to clarify? Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Looks like this is how list.pop(0) is implemented. Try to run this code in Python 3 and PyPy3:

b=[]
for i in range(100000):
    b.append(i)
    #if i%5==1: b.pop(0)
print( len(b) )

Without b.pop(0) line Python3 and PyPy3 executes this piece of code in around 125ms. While uncommenting pop(0) line turn this time into 155ms for Python3 and into 560ms for PyPy3. And if it would be 200k cycle you would get TLE. Experiment! :)

→ Reply