ackounts's blog

By ackounts, history, 5 weeks ago, In English,

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,

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Well, look carefully the solution you mentioned it is partially accepted.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You are absolutely right. Thank you so much for your answer, that was exactly what I was looking for.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

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

Kotlin: https://www.codechef.com/viewsolution/29851255

import java.io.PrintWriter
import java.util.StringTokenizer

fun main(argas: Array<String>) { _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)
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I bet pajenegod can solve it in python.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      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!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a reference, here is my AC solution using the bitwise operations suggested by pajenegod

    https://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")
    
»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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.