You are not logged in. Please login at www.codechef.com to post your questions!

×

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!!

    asked 16 Jun, 17:50

    zymbio's gravatar image

    4★zymbio
    212
    accept rate: 0%


    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.

    link

    answered 16 Jun, 22:05

    gorre_morre's gravatar image

    7★gorre_morre
    2723
    accept rate: 44%

    edited 16 Jun, 23:13

    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.

    (17 Jun, 02:58) sorb19974★
    2

    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.

    (17 Jun, 09:39) algmyr6★

    Really appreciate the help :) Thanks!!

    (17 Jun, 19:40) zymbio4★

    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

    (17 Jun, 20:50) zymbio4★
    toggle preview
    Preview

    Follow this question

    By Email:

    Once you sign in you will be able to subscribe for any updates here

    By RSS:

    Answers

    Answers and Comments

    Markdown Basics

    • *italic* or _italic_
    • **bold** or __bold__
    • link:[text](http://url.com/ "title")
    • image?![alt text](/path/img.jpg "title")
    • numbered list: 1. Foo 2. Bar
    • to add a line break simply add two spaces to where you would like the new line to be.
    • basic HTML tags are also supported
    • mathemetical formulas in Latex between $ symbol

    Question tags:

    ×14,441
    ×662
    ×193
    ×165
    ×59

    question asked: 16 Jun, 17:50

    question was seen: 186 times

    last updated: 17 Jun, 20:50