Glossary of Competitive Programming Terms

This glossary defines 35+ key terms used throughout this book and in competitive programming generally. When you encounter an unfamiliar term, look it up here first.

A

Algorithm A step-by-step procedure for solving a problem. An algorithm must be correct (give the right answer), finite (eventually terminate), and well-defined (each step is unambiguous). Examples: binary search, BFS, merge sort.

Adjacency List A way to represent a graph where each vertex stores a list of its neighbors. Space: O(V + E). The standard representation in competitive programming.

Adjacency Matrix A 2D array where matrix[u][v] = 1 if there's an edge from u to v. Space: O(V²). Use only for dense graphs with V ≤ 1000.

Amortized Time The average time per operation over a sequence of operations. Example: vector::push_back is O(1) amortized even though occasional doubling is O(N).

B

Base Case In recursion and DP, the simplest subproblem with a known answer (requires no further recursion). Example: fib(0) = 0, fib(1) = 1.

BFS (Breadth-First Search) A graph traversal that explores nodes level by level (all nodes at distance 1, then distance 2, ...). Uses a queue. Guarantees shortest path in unweighted graphs. Time: O(V + E).

Big-O Notation A mathematical notation describing the upper bound on an algorithm's time or space growth. "O(N log N)" means "at most c × N × log(N) operations for some constant c." Used to compare algorithm efficiency.

Binary Search An O(log N) search algorithm on a sorted array. Each step eliminates half the remaining candidates by comparing with the midpoint. The most important application: "binary search on the answer" for optimization problems.

Brute Force A naive solution that tries all possibilities. Usually O(N²) or O(2^N). Correct but too slow for large inputs. Useful for: partial credit, verifying optimized solutions, small test cases.

C

Comparator A function that defines a sorting order. Takes two elements and returns true if the first should come before the second. Used with std::sort.

Competitive Programming A type of programming contest where participants solve algorithmic problems within a time limit. USACO, Codeforces, LeetCode, and IOI are popular platforms.

Connected Component A maximal subgraph where every pair of vertices is connected by a path. Find components with DFS/BFS or Union-Find.

Coordinate Compression Mapping a large range of values (e.g., up to 10^9) to small consecutive indices (0, 1, 2, ...) without changing relative order. Enables using arrays instead of hash maps.

D

DAG (Directed Acyclic Graph) A directed graph with no cycles. Key property: has a topological ordering. Examples: dependency graphs, task scheduling.

DFS (Depth-First Search) A graph traversal that explores as deep as possible before backtracking. Uses a stack (or recursion). Good for: connectivity, cycle detection, topological sort. Time: O(V + E).

Difference Array A technique for O(1) range updates. Store differences between consecutive elements; range add [L,R] becomes diff[L]++ and diff[R+1]--. Reconstruct with prefix sums.

DP (Dynamic Programming) An optimization technique that solves problems by breaking them into overlapping subproblems and caching results. Two properties needed: optimal substructure + overlapping subproblems. See: memoization, tabulation.

DSU (Disjoint Set Union) See Union-Find.

E

Edge A connection between two vertices in a graph. Can be directed (one-way) or undirected (two-way). May have a weight.

Exchange Argument A proof technique for greedy algorithms. Show that swapping the greedy choice with any other choice never worsens the solution.

F

Flood Fill An algorithm (usually DFS or BFS) that marks all connected cells of the same "color" in a grid. Used to count connected regions.

G

Graph A data structure consisting of vertices (nodes) and edges (connections). Models relationships, networks, maps, etc.

Greedy Algorithm An algorithm that makes the locally optimal choice at each step, hoping for a globally optimal result. Works when the "greedy choice property" holds. Examples: activity selection, Huffman coding, Kruskal's MST.

H

Hash Map (unordered_map) A data structure that stores key-value pairs with O(1) average lookup. Implemented with hash tables. No ordering guarantee. Use when you need fast lookup but don't need sorted keys.

I

Interval DP A DP pattern where the state is a subarray [l, r] and you try all split points. Classic examples: matrix chain multiplication, palindrome partitioning. Time: O(N³).

K

Knapsack Problem A DP problem: given items with weights and values, maximize value within a weight limit. "0/1 knapsack" means each item used at most once. "Unbounded knapsack" means unlimited uses.

L

LIS (Longest Increasing Subsequence) The longest subsequence of an array where each element is strictly greater than the previous. O(N²) DP or O(N log N) with binary search.

LCA (Lowest Common Ancestor) The deepest node that is an ancestor of both u and v in a rooted tree. Naive: O(depth) per query. Binary lifting: O(log N).

M

Memoization Caching the results of recursive function calls to avoid recomputation. "Top-down DP." A memo table stores computed values; before computing, check if the answer is already known.

MST (Minimum Spanning Tree) A spanning tree of a weighted graph with minimum total edge weight. Kruskal's algorithm: sort edges + DSU. Prim's algorithm: priority queue + visited set. Both O(E log E).

Monotone / Monotonic Consistently increasing or decreasing. A function is monotone if it never reverses direction. Key for binary search on answer: the feasibility function must be monotone.

O

Off-By-One Error A bug where an index or count is wrong by exactly 1. Very common in loops (< n vs <= n), binary search, prefix sums (P[L-1] vs P[L]).

Optimal Substructure A property: the optimal solution to a problem can be built from optimal solutions to its subproblems. Required for DP to work correctly.

Overflow When a value exceeds the maximum representable value for its type. int max is ~2×10^9; long long max is ~9.2×10^18. Multiplying two 10^9 ints overflows int — cast to long long first.

P

Prefix Sum An array where P[i] = sum of all elements from index 0 (or 1) through i. Enables O(1) range sum queries: sum(L,R) = P[R] - P[L-1].

R

Recurrence Relation A formula expressing a DP value in terms of smaller DP values. Example: fib(n) = fib(n-1) + fib(n-2). Defines the DP transition.

S

Segment Tree A data structure for range queries and updates in O(log N). More powerful than prefix sums (supports updates). A Gold/Platinum topic.

Sparse Graph A graph with few edges relative to V². In practice: E = O(V). Use adjacency lists.

State (DP) The set of information that uniquely identifies a DP subproblem. Example in knapsack: (item_index, remaining_capacity). Choosing the right state is the key skill in DP.

Subtree All nodes in a tree that are descendants of a given node (including itself). Tree DP often computes aggregate values over subtrees.

T

Tabulation Building a DP table iteratively from base cases to larger subproblems. "Bottom-up DP." No recursion, no stack overflow risk.

Time Limit Exceeded (TLE) A verdict meaning your solution is correct but too slow. In USACO, most problems have a 2-4 second time limit. If you get TLE, optimize the algorithm — not just the constant factors.

Topological Sort An ordering of vertices in a DAG such that for every directed edge u→v, u comes before v. Computed with DFS (reverse post-order) or Kahn's algorithm (BFS-based).

Two Pointers A technique using two indices moving through an array, usually in the same direction. Converts O(N²) pair searches into O(N). Works on sorted arrays or when the condition is monotone.

U

Union-Find (DSU) A data structure supporting two operations: find(x) (which group is x in?) and union(x,y) (merge groups of x and y). With path compression + union by rank: O(α(N)) ≈ O(1) per operation. Used for dynamic connectivity, Kruskal's MST, cycle detection.

V

Vertex (Node) A fundamental unit of a graph. Vertices have indices (usually 1-indexed in USACO).

W

Wrong Answer (WA) A verdict meaning your program ran but produced incorrect output. Check edge cases, off-by-ones, and overflow.