Hi Codeforcers!
I haven't seen yet a problem that gives Time Limit Exceeded when using Python (Pypy) instead of C++. I would like to know if anyone has encountered such kind of problem in the past. I am especially concerned by instances of expert competitors like Egor Kulikov switching from Java to C++ because of performance issues(https://mirror.codeforces.com/blog/entry/72415?#comment-566810) but I don't know in practice how often that actually happen.
Thank you all,
No. You can find many problems that do not have any solutions accepted in python. See this one. You can find more div 1 problems too.
Thanks Not-Afraid, but that problem has indeed a Pypy solution: https://www.codechef.com/viewsolution/29131078
Did you experience an event where you coded the solution in Python (pypy) and it didn't pass, but after translating it to C++ it did?
Well, look carefully the solution you mentioned it is partially accepted.
You are absolutely right. Thank you so much for your answer, that was exactly what I was looking for.
EDIT: My implementation was not optimal and pajenegod was able to provide a working solution in Pypy!
Thanks to Not-Afraid for finding a problem that can't be solved using Pypy, but it can using other languages. Here is the code I used both for Pypy and Kotlin (identical algorithm):
Python: https://www.codechef.com/viewsolution/29847892
Kotlin: https://www.codechef.com/viewsolution/29851255
I bet pajenegod can solve it in python.
farmersrice you were right, he did it!
All hail pajenegod, king of python!!!!!!!!!
Brute forcing a problem with a Q * (N + M + 4000) solution, with N = M = Q = 10^5, really isn't PyPy's strong side. Also this is clearly not the intended solution. However I was still able to make a brute pass with PyPy https://www.codechef.com/viewsolution/29856065 . The conclusion is simply that the test cases were no where near max tests.
I usually use PyPy to solve problems on cf. I would say that it is noticably slower than C++, but it is not unbareable. Cpython however is often far too slow to be used.
The big thing with PyPy is that depending on how you implement an algirithm, you can get anything from really good times to certain TLE. For example not handling the input/output in a good way will many times cause TLE. Sorting tuples is also another good example
I've been training competetive programming using a bot on the AC discord server that gives me random 2100 — 2300 rated problems from cf to solve. Out of hundreds of problems I haven't had to skip a single one. (Many times my submission is the first AC with Python.) However I sometimes really have to work to get AC.
Is there a way we can avoid sorting tuples? For example in questions involving dijkstra's algorithm, is there an alternate way to solve without sorting tuples(assuming it is equivalent to appending tuples to a priority queue)?
In the special case of Dijkstra, I've been using a segment tree instead of a heap (in order to avoid tuples). I've had a lot of success with it, especially when it comes to avoiding TLE. There are problems on CF where all heap based Python solutions TLE, but my segtree Dijkstra easily survives. I've been thinking of putting it up on Pyrival, but I haven't gotten around to do it. Usually I just code it from scratch which takes me a couple of minutes.
As for how to sort tuples in general. You can get around directly sorting tuples by using a stable sort and sorting one component at a time. I usually do this with a radix sort for maximum performance.
Ok thanks a lot!
By sorting tuples do you mean sorting list of tuples ie. [(1,2), (2,3), (3,4)] etc? Can I avoid it using [[1,2],[2,3],[3,4]]? Why is sorting tuples slow in pypy?