TLE in Python 3.6

Hiii!! Everyone In recent contest Oct18 I solved HMAPPY with the same approach in python3.6 and C++ but I got TLE in python and accepted in C++. can anyone explain the reason why this happened?

Here my code in python:-
In c++:-

1 Like

Note: This may not answer the question.

Similar thing has happened with me in three problems in just last couple of days,

  • In October Long I got partial score in SURCHEES in python3.6, whereas now I can see similar solutions in c++ getting full score.
  • In Snackdown I got TLE in Graph on array, I used DFS, but exact same solution when translated to c++ got me 100 points.
  • In Chef and Strange addition of Snackdown, using brute force python3.6 code showed TLE, but brute force in c++ was partially accepted.

Python is almost 5 times slower than c++, that’s why it gets 5x time limit, But I think sometimes python performs even slower than 5x times of C++, This may be the reason of getting different results for similar approach.

1 Like

When data size increases, gap between Python and C++ also increases. When I first time implemented Segment Tree in Python, it was completing 10k query in 60 secs, but same code in C++ was doing 100k query in 0.9 secs. Too much array job is troublesome for Python.

But darpit_1234, your Python solution might have a problem, It might be an error in your binary search (I remember I had a similar problem). Here my final solution for same problem:

1 Like

The python program get’s stuck in the binary search loop.
with one of my own test cases I get the following values

l: 999999999999999872
r: 1000000000000000000
l+r: 1999999999999999872
(l+r)/2: 1e+18
mid=int(l+r)/2: 1000000000000000000

because the integers are getting large, python decides to put it in a float, which you cast back to an integer to get a different value than you wanted.
after the check, r get’s updated to mid which is the same as r already was.
this causes an infinite loop: TLE.

the fix for this problem is to replace /2 by //2
(python - Why does integer division yield a float instead of another integer? - Stack Overflow)

1 Like

C++ will never change a type if you don’t say explicitly that it should, that is why the C++ code does work.

1 Like

you’re right I made the changes and now it’s accepted. Thanks;)!! i will remember this.

1 Like