Solution for VSN giving TLE in python 3 using the editorial approach

I used the same approach as mentioned in the editorial using python 3.
I am getting TLE for 6 out of 7 tasks.

The link for the code is:

  • https://ideone.com/IZ6ikK
  • Could anyone please check and see whats wrong with my code.
    I have been trying from many days but not able to understand why I am getting TLE.
    It will be of great help. Thanks!!

    I don’t think you are getting TLE because of an error in your code but more about this being a very computationally expensive problem. Note that if n=10^5 and all coordinates are 2*10^9 then that means that input is huge. You are also doing a lot of computations when doing the binary search(this is probably the thing that is the most expensive), so everything is going to take a lot of time. There is however a simple solution.

    One very important thing working with python, is to use pypy instead of python(cpython). They are both python interpreters and run the same code but pypy usually runs much much quicker, especially on these kind of brute force problems.

    Even though I’m a python programmer I almost never use python(cpython) as it is super slow, instead I use pypy. The only problem with using pypy on codechef is that codechef only supports pypy2 and not pypy3, but the difference between python 2 and python 3 isn’t that big, so it isn’t that big of a problem.

    When I tried running your code in pypy I got accepted with everything running under 1s.

    4 Likes

    Do Red Coders even use Python? That’s little strange because I remember reading an answer of Bohdan Pryschenko(i_love_tanya_romanova on Codeforces)on Quora where he said he hardly knows any Red Coder using Python as it’s extremely slow.

    I would believe that on codeforces, since there is no language handicap there at all. Here python gets extra time. Regarding python2 and python3 stuff, it’s not hard to make most python3 code run under python2. Essentially doing from __future__ import print_function,division, range=xrange and input=raw_input will cover most of it that matters. You can even put those last two assignments inside if sys.version_info < (3, 0): to make your code runnable under both versions. It’s my goto header when I realize python3 is too slow and need to use pypy.

    2 Likes

    Really appreciate the help :slight_smile: Thanks!!

    Also I tried the same with another problem(SHKSTR) of the same contest which was giving TLE. To my surprise even it passed all the test cases. I’m so happy , I found this.

    https://www.codechef.com/viewsolution/18919507