ackounts's blog

By ackounts, history, 5 years 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://mirror.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

| Write comment?
»
5 years 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 years 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 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years 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 years 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 years 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.

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

    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)?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?