ACM Competitive Programming Guide

Competitive programming and interview coding are different skills. Here's how to convert your contest experience to interview success.

I/O Templates

The biggest difference between ACM and LeetCode mode: you handle input/output yourself.

C++ Multi-test Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        // Process single test case
    }
    return 0;
}

Key points:

ios::sync_with_stdio(false) disables sync, 5-10x faster
cin.tie(nullptr) unties cin from cout
Clear global variables between test cases

Python Multi-test Template

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    # Process single test case

Note: Python's input() is too slow, must use sys.stdin.readline.

Java Multi-test Template

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            // Collect output in sb
        }
        System.out.print(sb);
    }
}

Key: Use StringBuilder to collect output, print once at the end.

Common Pitfalls

Data Range and Type Selection

Range	Correct Type	Common Mistake
≤ 10^9	`int`	None
≤ 10^18	`long long`	Used `int`
Involves multiplication	Check intermediate	`int a * int b` overflow

Typical error:

int a = 1e9, b = 1e9;
long long c = a * b;  // Wrong! a * b already overflowed

long long c = 1LL * a * b;  // Correct! Cast first

Graph Algorithm Selection

Scenario	Correct Algorithm	Common Mistake
Non-negative weights	Dijkstra	None
Has negative edges	Bellman-Ford / SPFA	Used Dijkstra
All pairs	Floyd	Ran single-source n times
Minimum spanning tree	Kruskal / Prim	Used shortest path

Typical error: Using Dijkstra on graphs with negative edges gives wrong results.

Multi-test Cleanup

Must clear global variables before each test:

int cnt[100005];
vector<int> adj[100005];

void solve() {
    // Must clear!
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= n; i++) adj[i].clear();
    
    // Then process current test case
}

Heap Dijkstra Pitfall

// Wrong: Not filtering stale states
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    for (auto [v, w] : adj[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

// Correct: Filter stale states
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;  // Stale, skip
    for (auto [v, w] : adj[u]) {
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.push({dist[v], v});
        }
    }
}

Contest Tips

Fast Input (10^6+ data)

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

Common STL

Container/Function	Use Case	Complexity
`priority_queue`	Heap, Dijkstra	O(log n)
`set` / `map`	Dedup, lookup	O(log n)
`unordered_set`	Hash dedup	O(1) avg
`lower_bound`	Binary search	O(log n)
`__builtin_popcount`	Count 1 bits	O(1)

Contest → Interview Conversion

Contest experience differs from interview requirements:

Aspect	Contest	Interview
Code style	Shorter is better	Readability first
Variable names	Single letter	Meaningful names
Comments	Almost none	Key steps need comments
Time limit	1-2 seconds	No strict limit
Communication	Not needed	Explain while coding

Interview Style Example

// Contest style (don't use in interviews)
int f(vector<int>& a) {
    int s = 0;
    for (int x : a) s += x;
    return s;
}

// Interview style
int calculateSum(const vector<int>& numbers) {
    int sum = 0;
    for (int num : numbers) {
        sum += num;
    }
    return sum;
}

Type	Core Algorithm	Typical Problems
Knapsack	DP state design	0/1 knapsack, unbounded
Shortest path	Dijkstra / SPFA	Single-source, multi-source
Segment tree	Range query	Range sum, range max
Union find	Path compression	Connectivity, MST
String	KMP / Hash	Pattern matching, palindrome