Typing templates from memory

In a contest, you cannot open notes or search the internet. You type everything from memory. After you solve several problems, certain patterns become automatic. You type them without thinking.

This lesson teaches you to build that muscle memory. You will practice typing common templates until your fingers know the shape. Unlike memorisation for a test, this is functional memory: your hands remember how to type the code, not your brain.

The house skeleton

The fast-I/O template is the foundation of every senior CCC solution. You have typed it in M3.10 and every module since. By now, it should take you 30 seconds to type without thinking.

Type it again without looking:

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8    # algorithm implementation9
10
11if __name__ == "__main__":12    main()

When you type this in a contest, you are setting up fast I/O before you solve the problem. It becomes reflex. On your first line of code, you write import sys. Before you write any algorithm, you read the whole input once. This habit saves you from the time-limit trap: calling input() in a loop on large inputs.

Practice this until you can type it without hesitation. Time yourself. Can you type it in 20 seconds? If it takes longer, you are still thinking about the syntax. That thinking time costs you during the contest.

BFS on a grid

Many contest problems ask you to search a grid. Flood-fill, shortest path, connected components: these all use BFS. The template is always the same. Here is the shape:

1from collections import deque2
3grid = [[0, 0, 1], [0, 1, 0], [0, 0, 0]]4rows, cols = len(grid), len(grid[0])5start_row, start_col = 0, 06
7queue = deque([(start_row, start_col)])8visited = {(start_row, start_col)}9
10while queue:11    r, c = queue.popleft()12    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:13        nr, nc = r + dr, c + dc14        if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:15            visited.add((nr, nc))16            queue.append((nr, nc))

This explores all reachable cells. The key parts you must type correctly are: the four directions in the order they appear, the bounds check that uses both < and <=, and the visited set update before appending to the queue. If you append before marking visited, you can add the same cell multiple times.

In a contest, when you see a grid problem, you do not think about BFS. Your fingers type this loop. You fill in the starting cell and the row/column bounds, and the rest flows automatically.

Prefix sums

Prefix sums answer range-sum queries in O(1) time after O(N) preprocessing. For a 1D array, you build this:

1arr = [3, 1, 4, 1, 5]2n = len(arr)3prefix = [0] * (n + 1)4for i in range(n):5    prefix[i + 1] = prefix[i] + arr[i]

The key detail: the prefix array is one element longer than the input. This handles the edge case where you want the sum from index 0 to j; you compute prefix[j + 1] - prefix[0], and prefix[0] is always 0.

Then the sum of elements from index i to j is prefix[j + 1] - prefix[i]. You use this formula hundreds of times in contests, so the indexing must become automatic.

For a 2D grid, the formula is more complex:

1grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]2rows, cols = len(grid), len(grid[0])3prefix = [[0] * (cols + 1) for _ in range(rows + 1)]4
5for i in range(rows):6    for j in range(cols):7        prefix[i + 1][j + 1] = (grid[i][j] +8                                prefix[i][j + 1] +9                                prefix[i + 1][j] -10                                prefix[i][j])

The 2D formula is: current cell plus the cell above plus the cell to the left, minus the cell diagonally above-left (to avoid double-counting). When you type this, you recite the formula to yourself: "cell, above, left, minus diagonal". After ten practice runs, you type it without reciting.

The sum of a rectangle from (r1, c1) to (r2, c2) is:

1prefix = [[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21], [0, 12, 27, 45]]2r1, c1, r2, c2 = 0, 0, 1, 13total = (prefix[r2 + 1][c2 + 1] -4         prefix[r1][c2 + 1] -5         prefix[r2 + 1][c1] +6         prefix[r1][c1])

The pattern mirrors the inclusion-exclusion principle: you include the rectangle, exclude the top strip, exclude the left strip, and add back the top-left corner that was excluded twice.

Circular array indexing

When you have a circular array (like a queue or a ring buffer), use modulo to wrap the index:

n = 5index = 0index = (index + 1) % n

To step backward:

n = 5index = 0index = (index - 1) % n

To jump by k steps:

n, k = 5, 2index = 0index = (index + k) % n

Python's modulo operator handles negative numbers correctly, so (index - 1) % n always gives a value between 0 and n-1, even when index is 0.

Union-Find template

Union-Find is a data structure for tracking connected components. It supports two operations: union (merge two sets) and find (return the representative of a set). Keep it as two plain lists and two functions, the same shape as every other template here:

1n = 62parent = list(range(n))3rank = [0] * n4
5
6def find(x):7    while parent[x] != x:8        parent[x] = parent[parent[x]]9        x = parent[x]10    return x11
12
13def union(x, y):14    px, py = find(x), find(y)15    if px == py:16        return17    if rank[px] < rank[py]:18        px, py = py, px19    parent[py] = px20    if rank[px] == rank[py]:21        rank[px] += 1

find(x) walks up to the root, flattening the path one hop at a time so future calls are shorter. union(x, y) finds both roots and, if they differ, attaches the shorter tree under the taller one, using rank as an estimate of tree height. Call union(a, b) to connect two nodes and find(x) to check which component x belongs to.

Common typing mistakes

Off-by-one in modulo: Use (index - 1) % n not (index - 1) // n for stepping backward in a circular array. The double-slash is integer division, not modulo. Easy to confuse when typing fast.

Missing initialisation: When using prefix sums, initialise the first row and column to zero. The prefix array is always one element larger than the input. If you forget this, all your queries are off by one.

Forgetting bounds in BFS: Always check 0 <= nr < rows and 0 <= nc < cols before adding to the queue. Forgetting the bounds check or checking only one dimension causes out-of-bounds errors.

Swapping x and y: In a 2D grid, use (row, column) consistently. If you define the grid as grid[i][j] where i is the row, then when you use (nr, nc) in BFS, nr is the new row and nc is the new column. Do not swap them mid-code.

Why memory matters

In a contest, you have limited time. You cannot open notes or search the internet. You must rely on memory. The patterns you have typed a hundred times come out of your fingers automatically.

When you practise typing templates, you are not memorising. You are building automatic recall. Your brain and fingers work together. By the time you sit for a contest, you are faster because you do not hesitate.

A good contestant does not think about BFS. They see a grid and their hands start typing. There is no conscious decision-making in the template; the decision-making is in what comes after: how to modify the template for the specific problem.

Practice strategy

Spend 5-10 minutes a week typing these templates from scratch. Start with the house skeleton. Move to BFS. Then prefix sums. Then circular arrays. Finally, Union-Find. Do not worry about speed in the first week. Type carefully, paying attention to the exact syntax. Notice where you make mistakes and why.

Over time, your speed will increase naturally. After a month of practice, you will type these patterns without conscious effort. You will be faster in a contest.

When you sit down at the judge on contest day, your fingers already know what to type. When you encounter a problem, you type the template instantly and spend your mental energy on the problem-specific logic, not on recalling syntax.