D_coder22's blog

Uncertainty in Python Time of Execution
By D_coder22, history, 10 months ago, In English

Following is my code to the problem Link

I=lambda:[*map(int,input().split())]
rr=range
n,m=I()
a=[I() for _ in rr(n)]
# print(a)
dp=[0]*(n+1)
for i in rr(m):
    st=en=0
    for j in rr(1,n):
        if a[j-1][i]>a[j][i]:
            dp[st+1]=max(dp[st+1],en+1)
            st=en=j
        else :
            en+=1
    dp[st+1]=max(dp[st+1],en+1)
for i in rr(1,n+1):
    dp[i]=max(dp[i],dp[i-1])

q,=I()
for i in rr(q):
    x,y=I()
    print('Yes' if dp[x]>=y else 'No')

It gives TLE in some submissions while passes in others, to the fact that all have same code. Also sometimes for the same code Python 3 throws TLE and sometimes PyPy3. Is there any way to overcome this uncertainty, Or can anyone pls give reason for this

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sometimes it does happens that even after using Fast IO, the same solutions passes in some version of python and gives TLE in some other versions, And I would also like to know the answer for it. For Ex — https://mirror.codeforces.com/contest/1916/submission/239641018 , this codes gives TLE whereas https://mirror.codeforces.com/contest/1916/submission/239726913 , this gets Accepted. Like srsly how and how to know it before hand ???? It will be great If anyone can clear this doubt...

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Usually pypy3 is faster than python3. Usually the fastest way to get input in python (or at least the way that I've used that has worked pretty consistently) is using sys.stdin.readline(), your one submission that actually uses this to get input is significantly faster (311 ms).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Running time is nondeterministic. This is hardware limitation and there's very little we can do about it. This is why problems are recommended to set their TL at least triple of the main solution's running time.

→ Reply