Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 63 ยท Getting Started with Contests

Python for Contests

Use Python in contests: fast input idioms, reading ints and grids, joining output, the recursion limit, speed tips, and knowing when Python is too slow.

Python is a perfectly good contest language. Its short syntax means fewer bugs and faster writing, big integers are built in, and its standard library has a heap, a deque, bisect, itertools and more. The price is speed: plain Python loops are roughly 30 to 100 times slower than C++. This lesson shows how to read input quickly, how to write output efficiently, how to avoid the classic recursion trap, and how to recognise when a problem needs something faster than pure Python.

On a real judge your program reads from standard input. The in-browser examples here cannot read a real stdin, so we build a small stand-in that behaves like input() over a prepared string. The code you write inside functions is identical to what you would submit.

Reading input

The standard tool is input(). It reads one line, without the trailing newline. A typical test starts with a line of numbers:

Python
n = int(input())
a = list(map(int, input().split()))

input().split() cuts the line at whitespace into strings, and map(int, ...) converts each one. For small inputs this is all you need.

For big inputs, input() is slow because it does extra work per call. The idiom contest Pythonistas use is to rebind it to the faster sys.stdin.readline:

Python
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

Two cautions. sys.stdin.readline keeps the trailing newline, but int() and split() ignore it, so numbers still parse. If you read a string you want to compare or index, strip it: s = input().strip().

An even faster style reads the whole input at once and walks through the tokens. It is robust against odd line breaks, because only whitespace matters:

Python
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))

Here sys.stdin.buffer.read() returns bytes, and int() accepts bytes tokens directly. This pattern is shown read-only because the page cannot supply a real stdin; below we simulate the same behaviour.

Python An input() stand-in and the usual parsing patterns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stand-in replaces input with a function that returns the next prepared line, so the three parsing patterns behave as they would on a judge. Every later lesson in this tutorial that needs input uses the same trick or just passes data into functions.

Reading shapes you will meet

Python
# many test cases
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    # ... solve and print

# n pairs, one per line
pairs = [tuple(map(int, input().split())) for _ in range(n)]

# a matrix of integers
matrix = [list(map(int, input().split())) for _ in range(n)]

# a graph: n vertices, m edges (1-based labels)
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

Keep a habit of converting to 0-based indexes when it makes the code simpler, and say so in a comment.

Writing output

print is also slow when called hundreds of thousands of times. Collect the results and write once:

Python
out = []
for _ in range(t):
    out.append(str(solve()))
print("\n".join(out))

To print a list of numbers on one line, use print(*a) for moderate sizes or " ".join(map(str, a)) for large ones. Both avoid a loop of print calls. Remember that " ".join needs strings, so convert with map(str, ...).

Python Output joining and why it matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions produce the same text, but joining first usually wins by a clear margin. The exact timings depend on the machine, so the demo prints only the facts that do not.

The recursion limit

Python limits recursion depth to about 1000 frames by default. A recursive depth-first search on a path of 100,000 vertices would crash with RecursionError, which the judge reports as a runtime error. There are two usual answers.

  1. Raise the limit with sys.setrecursionlimit(10**6). On some judges you must also run the recursion in a thread with a bigger stack (threading.stack_size) to avoid a real stack overflow crash. This works but is fragile.
  2. Iterate. Replace recursion with an explicit stack. This is safest and is how most strong Python contestants write graph code. We return to it in DSU and Tree Problems.
Python Recursion versus an explicit stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first call fails with the default limit, the explicit stack has no such limit, and raising the limit helps for moderate depths. Prefer the stack for anything near the maximum input size.

Speed tips

  • Put the code in a function. Local variable access is faster than global access. Call main() at the end.
  • Use built-ins. sum, max, min, sorted, len, any, all and slicing run in C and beat hand-written loops.
  • Prefer list comprehensions over appending in a loop where the logic is simple.
  • Avoid repeated work inside loops: hoist len(a) and attribute lookups such as out.append into local names for hot loops.
  • Use the right container. Membership in a set or dict is O(1), while x in some_list is O(n). Use collections.deque for queues, since list.pop(0) is O(n).
  • Do not build big strings with += in a loop. Collect pieces in a list and join.
  • Use heapq and bisect instead of re-sorting repeatedly.

The next demo compares a loop with built-ins and a list membership test with a set. Timing differs from computer to computer, so we check which one is faster rather than quoting seconds.

Python Built-ins and the right container

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When Python is too slow

Sometimes the intended solution is correct but the constant factor kills you: about 10^7 or more basic operations in nested loops, or a tight inner loop in a dynamic programming table with 10^8 cells. Options, in order:

  1. Check the algorithm first. A better complexity beats every micro-optimisation.
  2. Vectorise with NumPy if the judge allows it (many do not; check).
  3. Use built-ins and bit tricks to process many items per operation: for example, Python integers as bitsets.
  4. Submit with PyPy instead of CPython if the judge offers it. PyPy often runs loop-heavy code several times faster, though its recursion and memory behaviour differ slightly.
  5. Accept it. If every serious solution is O(n^2) with n = 5000 and a 1-second limit, the problem may simply be a C++ problem. Move on and solve something else; that is a legitimate contest decision.

In short, use Python's strengths (readability, big integers, rich library) and do not fight its weakness on problems that need 10^8 loop iterations.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which line makes input() faster on large inputs?

    sys.stdin.readline avoids the extra per-call work of the built-in input(). Remember that it keeps the trailing newline, so strip strings before comparing them.
  2. 2. You must print 200,000 numbers, one per line. What is the best approach?

    A single print of a joined string is much faster than many print calls. Repeated string += also performs poorly.
  3. 3. A DFS recursion on a 100,000-vertex path gives a runtime error in Python. What is the most reliable fix?

    An explicit stack has no depth limit other than memory. Raising the recursion limit may still crash the real call stack.
  4. 4. Why put the main code inside a function?

    Access to local names is faster than to module-level names, which matters in hot loops.

Summary

  • Read with input = sys.stdin.readline or read all tokens from sys.stdin.buffer.read().split().
  • Convert with map(int, ...), and strip strings you plan to compare.
  • Collect output in a list and print once with "\n".join(...).
  • Avoid deep recursion: use an explicit stack, or raise the limit cautiously.
  • Use functions, built-ins, sets, deques and heapq for speed.
  • If the intended solution still cannot fit in Python, try PyPy, bit tricks or NumPy, or move to another problem.

Next: Verdicts and Debugging