Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

aim_to_mast's blog

PyPy 3-64 vs Python 3
By aim_to_mast, history, 5 months ago, In English

In a recent Div 3 contest, this D problem https://codeforces.me/contest/2236/problem/D , I solved and submitted my solution in PyPy 3-64, It got TLE ( https://codeforces.me/contest/2236/submission/378497496 ) but same solution I submitted using Python 3 got accepted ( https://codeforces.me/contest/2236/submission/378498806 ). I have faced this issue using python a couple of time also. Can any Python expert help me in this case ?

Thanks

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

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

Also the time difference is huge 234ms vs 2000+ms in Python 3 vs PyPy 3-64

In Usual cases PyPy 3 is faster as compared to Python 3

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

sometimes pypy is faster than python and sometimes not.
idk whats that good abt python, despite it being my first language.
just use c++ and u virtually never get TLE unless ur algorthm is flawed.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    sanae cross and color was tle hell and I also remember the intended solution for ioi 2008 regions was $$$n \sqrt{n} \log{n}$$$ for $$$n = 200{,}000$$$ and 8 sec TL lol

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

Hacked (though codeforces for some reason shows that it is in queue), now your solution also gets TLE using Python 3

Basically, the problem is using sets/dicts. Avoid them as much as you can, and if you can't then use special tricks to avoid getting TL

blog 1, blog 2

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

I just faced the same problem. I just submitted the same solution in Python3, and it got accepted, but in contest it got TLE after system testing in Pypy3. Python3 Solution: https://codeforces.me/contest/2236/submission/378523211 Pypy Solution: https://codeforces.me/contest/2236/submission/378415930

Generally, I saw this happen in interactive problems but never saw in the normal problems.

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

Learn how python maintains the dictionary and set... there's something know as perturbation probing. And it is deterministic, so easily hackable to get a TLE, basically your O(N) solution becomes O(N^2).

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

    simplest technique is to use a random variable (coz now nothing remains deterministic)

    So whenever u insert in a set, do

    s.add(x^rand)

    and whenever u query for x, do

    if x^rand in s:

    and whenever u access x, do

    for x in s: s = x^rand

    from random import getrandbits

    rand1 = getrandbits(32)

    rand2 = getrandbits(32)

    RANDOM = (rand1+rand2)//2-1

    This is my random variable...

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

Thanks everyone for helping me out.

→ Reply