blackSnek's blog

Need help with a PyPy3 submission
By blackSnek, history, 3 years ago, In English

Problem — 1539C

My O(N*log(N)) PyPy3 code got TLE verdict for N — 2e5 (worst case)

Can someone explain what operations are being heavy in my code? and how can I optimize them?

Here is the submission link — submission

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Who the fck said you to use pypy...use c++ and you're never gonna get these types of complaints.

Switch to c++ and thank me latter.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Why don't you comment with your real account?

    :)

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Same thing happened with me ..when I used python it gave me accepted..but for pypy tle...why are these problems with python and pypy...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Specific in this case pure Python is faster, but idk how to explain it

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

One problem is that in pypy3 it's faster to read as bytes instead of string. If you replace input = sys.stdin.readline with input = sys.stdin.buffer.readline it should pass. Another alternative is to read the entire file with a single os.read() or sys.stdin.buffer.read() at the beginning with something like input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline. Or just use the fast i/o template from pyrival: https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

But the other problem is that integers larger than 32 bits will switch to a slow big integer implementation and sorting that is slow. I don't know of any good solution for that right now (EDIT: apparently pyrival has an long_ordersort, pajenegod orz!!!). It might get better if we get an option to submit in 64bit pypy in the future (see pajenegod's post: https://codeforces.com/blog/entry/90184)

EDIT2: I tried out the long_ordersort implementation from pyrival (it needed one bug fix to work in pypy3) and it was around 650ms: 120134673. I noticed some submissions which were faster by casting to floats, but that trick only works up to around 2**53 so they are hackable: 120130807

→ Reply