### ackounts's blog

By ackounts, history, 12 months ago,

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://codeforces.com/blog/entry/72415?#comment-566810) but I don't know in practice how often that actually happen.

Thank you all,

• +17

 » 12 months ago, # |   +1 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.
•  » » 12 months ago, # ^ |   0 Thanks Not-Afraid, but that problem has indeed a Pypy solution: https://www.codechef.com/viewsolution/29131078Did 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?
•  » » » 12 months ago, # ^ |   +1 Well, look carefully the solution you mentioned it is partially accepted.
•  » » » » 12 months ago, # ^ |   +3 You are absolutely right. Thank you so much for your answer, that was exactly what I was looking for.
 » 12 months ago, # | ← Rev. 2 →   +6 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): from sys import stdin, stdout def read(): return stdin.readline().rstrip() n, m, q = [int(x) for x in read().split()] a = [int(x) for x in read().split()] b = [int(x) for x in read().split()] while q: arr = [0]*4001 l1, r1, l2, r2 = [int(x) for x in read().split()] for i in range(l1-1, r1): arr[a[i]] += 1 for i in range(l2-1, r2): arr[b[i]] += 1 result = 0 for i in range(4001): if arr[i]%2 == 1: result += 1 stdout.write(str(result)+"\n") q -= 1  import java.io.PrintWriter import java.util.StringTokenizer fun main(argas: Array) { _writer.solve(); _writer.flush() } fun PrintWriter.solve() { var (n, m, q) = readIntArray(3) val a = readIntArray(n) val b = readIntArray(m) while (q != 0) { q-- val arr = IntArray(4001) val (l1, r1, l2, r2) = readIntArray(4) for (i in l1-1 until r1) { arr[a[i]] += 1 } for (i in l2-1 until r2) { arr[b[i]] += 1 } var result = 0 for (i in 0..4000) { if (arr[i]%2 == 1) result += 1 } println(result) } } /** IO code start - Spheniscine template */ @JvmField val INPUT = System.in @JvmField val OUTPUT = System.out @JvmField val _reader = INPUT.bufferedReader() fun readLine(): String? = _reader.readLine() fun readLn() = _reader.readLine()!! @JvmField var _tokenizer: StringTokenizer = StringTokenizer("") fun read(): String { while (_tokenizer.hasMoreTokens().not()) _tokenizer = StringTokenizer(_reader.readLine() ?: return "", " ") return _tokenizer.nextToken() } fun readInt() = read().toInt() fun readIntArray(n: Int) = IntArray(n) { read().toInt() } @JvmField val _writer = PrintWriter(OUTPUT, false) 
•  » » 12 months ago, # ^ |   +11 I bet pajenegod can solve it in python.
•  » » » 12 months ago, # ^ |   0 farmersrice you were right, he did it!
•  » » » » 12 months ago, # ^ |   +3 All hail pajenegod, king of python!!!!!!!!!
•  » » 12 months ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » 12 months ago, # ^ |   -23 pajenegod from today on, you are my personal hero. Thank you so much for your answers, they really encourage me to keep using Python instead of switching to a different programming language!
•  » » 12 months ago, # ^ |   0 As a reference, here is my AC solution using the bitwise operations suggested by pajenegodhttps://www.codechef.com/viewsolution/29859435 from sys import stdin, stdout range = xrange input = raw_input def read(): return stdin.readline().rstrip() def readints(): return [int(x) for x in read().split()] _, _, q = readints() A = readints() B = readints() for _ in range(q): arr = [0]*4001 l1, r1, l2, r2 = readints() for i in range(l1-1, r1): arr[A[i]] ^= 1 for i in range(l2-1, r2): arr[B[i]] ^= 1 result = sum(arr) stdout.write(str(result)+"\n") 
 » 12 months ago, # |   +15 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 exampleI'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.
•  » » 7 weeks ago, # ^ |   +3 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)?
•  » » » 7 weeks ago, # ^ |   +2 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.
•  » » » » 7 weeks ago, # ^ |   0 Ok thanks a lot!
 » 12 months ago, # |   -8 The danger with Pypy is you don't know how long the JIT compiler takes to warmup. I've had relatively simple code take 1+ second to just start executing. That is not something I want to deal with. FlakeLCR tells me that sometimes standard python actually runs faster.