Блог пользователя ackounts

Автор ackounts, история, 5 лет назад, По-английски

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,

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +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.

»
5 лет назад, # |
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):

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 лет назад, # |
  Проголосовать: нравится +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 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 года назад, # ^ |
      Проголосовать: нравится +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)?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?