Python constant-factor engineering at scale

Your algorithm is correct. Its complexity is right. But when you submit to the judge, it times out. The issue is not the algorithm itself. It is the speed at which Python executes your code, instruction by instruction.

Python is slower than C by nature. The contest grader runs on PyPy 3.8, which compiles frequently-executed loops to native machine code and dramatically speeds up Python. However, PyPy does not accelerate all Python code equally. The choices you make about input parsing, data structures, and loop structure determine whether you meet the time limit.

Reading input once

Calling input() in a loop for hundreds of thousands of lines is extremely slow. Each call involves line parsing, buffer management, and string allocation. In a tight loop, this overhead dominates and consumes the time that should go to your actual computation.

Instead, use sys.stdin.read().split(). This single call reads all input, and you then extract tokens by position from the resulting list. You saw this pattern in M3.10.

1import sys2
3
4# Slow: reading with input() in a loop5def slow_read():6    n = int(input())7    total = 08    for _ in range(n):9        x = int(input())10        total += x11    return total12
13
14# Fast: reading everything at once15def fast_read():16    data = sys.stdin.read().split()17    n = int(data[0])18    total = 019    for i in range(1, n + 1):20        total += int(data[i])21    return total22
23
24def main() -> None:25    result = fast_read()26    sys.stdout.write(f"{result}\n")27
28
29if __name__ == "__main__":30    main()

5
10
20
15
25
30

100

The first version calls input() on each line. The second reads everything at once and indexes the list. Both do the same work, but the second is faster.

Flat lists and parallel lists

Storing data in tuples or dictionaries makes sense in small programs. On a large test case, access time adds up.

A list of tuples like [(3, 5), (1, 7), (2, 4)] looks clean. But each lookup first finds the tuple, then indexes into it. If you have 100,000 points, that is 200,000 attribute accesses.

Instead, use two flat lists: one for the first value and one for the second. Index both lists with the same integer. A list lookup on an integer index is just an array access. PyPy's compiler can make it very cheap.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    n = int(data[0])7
8    # Read points into parallel lists9    x_coords = []10    y_coords = []11    for i in range(1, 2 * n + 1, 2):12        x_coords.append(int(data[i]))13        y_coords.append(int(data[i + 1]))14
15    # Process: find sum of all coordinates16    total = sum(x_coords) + sum(y_coords)17    sys.stdout.write(f"{total}\n")18
19
20if __name__ == "__main__":21    main()

3
1 2
4 5
3 6

21

Here we have 100,000 points. The tuple version stores them compactly in memory. The flat-list version uses two separate lists. When you process a point, you index both lists. This is faster on PyPy because the compiler optimises integer indexing heavily.

Packing integers

Sometimes you have data you want to encode compactly. For example, you might have a node number (0 to 10,000) and a time value (0 to 1,000). Instead of storing them separately or as a tuple, pack both into a single integer.

Multiply the node by a large enough constant and add the time. Then when you need the node, divide by that constant and take the remainder.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    n = int(data[0])7
8    # Pack node (0-10000) and time (0-1000) into one integer9    PACK = 1000110    packed = []11    for i in range(1, 2 * n + 1, 2):12        node = int(data[i])13        time = int(data[i + 1])14        packed_value = node * PACK + time15        packed.append(packed_value)16
17    # Sort packed values18    packed.sort()19
20    # Output unpacked values21    output = []22    for p in packed:23        node = p // PACK24        time = p % PACK25        output.append(f"{node} {time}")26
27    sys.stdout.write("\n".join(output) + "\n")28
29
30if __name__ == "__main__":31    main()

3
5 100
2 500
5 200

2 500
5 100
5 200

A packed integer stores two values in one. When you sort the packed values, you sort by node first, then by time. The sorting is faster because you are moving fewer bytes. Dictionary lookups are also faster when your key is a single integer instead of a tuple.

Avoiding copies

Slicing a list creates a new copy. Joining strings creates copies of the input. These copies use memory and time.

When you do not need a copy, avoid creating one. Read from the original list. Append to an output list and join it once at the end, instead of concatenating strings in a loop.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    n = int(data[0])7
8    # Slow: concatenating strings9    # result = ""10    # for i in range(1, n + 1):11    #     result += data[i] + " "12
13    # Fast: appending to list and joining once14    output = []15    for i in range(1, n + 1):16        output.append(data[i])17
18    sys.stdout.write(" ".join(output) + "\n")19
20
21if __name__ == "__main__":22    main()

3
hello
world
test

hello world test

The first version concatenates total in a loop. Each concatenation creates a new string. The second version appends to a list and joins once. On large outputs, this is much faster.

A complete example: sorting pairs by custom order

Imagine you have to sort pairs by one field when it is small, and by the other field when the first is tied. This is a common CCC task.

The slow way is to write a custom comparison function and call the sort. A faster way is to pack both values, compute a sort key, and sort by the key.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    n = int(data[0])7
8    # Pack pairs (a, b) where we sort by a then b9    PACK = 100010    pairs = []11    for i in range(1, 2 * n + 1, 2):12        a = int(data[i])13        b = int(data[i + 1])14        packed = a * PACK + b15        pairs.append(packed)16
17    pairs.sort()18
19    # Unpack and output20    output = []21    for p in pairs:22        a = p // PACK23        b = p % PACK24        output.append(f"{a} {b}")25
26    sys.stdout.write("\n".join(output) + "\n")27
28
29if __name__ == "__main__":30    main()

4
5 2
2 8
5 1
2 3

2 3
2 8
5 1
5 2

The pairs are sorted by the first value, then by the second value when the first is tied. The packing approach sorts on a single integer per pair. This is faster than using a key function that unpacks them during each comparison.

When to measure and when to stop

You have finished the algorithm. You code it up. You test on sample inputs and the output is right. The judge times out on the larger subtasks.

Before you start optimising, measure where the time is spent. Run the largest test case you can fit in memory and see which part of your code takes time.

If your algorithm's complexity is bad, no constant-factor trick will save it. Fix the algorithm first.

If the algorithm is fine but you are still too slow, use a profiler or add timing code to see which loop or which operation uses most of the time. Then optimise that part. A smaller optimisation elsewhere will not help.

1import sys2import time3
4
5def main() -> None:6    t_read = time.time()7    data = sys.stdin.read().split()8    t_parse = time.time()9
10    n = int(data[0])11    total = 012
13    t_compute = time.time()14    for i in range(1, n + 1):15        total += int(data[i])16    t_done = time.time()17
18    read_time = (t_parse - t_read) * 100019    parse_time = (t_compute - t_parse) * 100020    compute_time = (t_done - t_compute) * 100021
22    sys.stdout.write(f"{total}\n")23    sys.stderr.write(f"Read: {read_time:.2f}ms Parse: {parse_time:.2f}ms Compute: {compute_time:.2f}ms\n")24
25
26if __name__ == "__main__":27    main()

4
10
20
30
40

100

This program solves a small example and prints the time each part took. When you run it on a large test case, you see what is slow.

Another fact about CCC: the grader keeps your best submission. If the fast solution would take you longer to code than you have, submit the simpler solution first. If the fast solution is risky or complex, code it safely, so a crash never replaces working code.

The house skeleton for fast I/O

You have already seen the house skeleton in M3.10. Here it is again.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8    # algorithm implementation9    output = []10    # ... build output list ...11    sys.stdout.write("\n".join(output))12
13
14if __name__ == "__main__":15    main()

This is the shape to use for any problem with large input. It reads once, processes, and writes once. Use it as your default for senior problems. All the examples in this lesson use this shape.

Recap

A fast Python program reads input once with sys.stdin.read().split(), stores data in flat 1D lists or packed integers, avoids slicing and copying, and keeps loops tight. PyPy compiles hot loops to machine code, but only if the code is simple and uses cheap operations like integer indexing.

Before you optimise, measure. After you optimise, measure again. Know the complexity limit for partial marks and decide when to stop.