This guide covers essential algorithms, data structures, and mathematical concepts frequently encountered in competitive programming.
A crucial piece of advice: Merely understanding how an algorithm works is only the first step. True mastery comes from applying these concepts to solve problems. You must practice implementing these algorithms and adapting them to new challenges on your own. There is no substitute for hands-on problem-solving.
Note: Some problem descriptions linked here are in Chinese. You can often use an online translator or ask an LLM for assistance if you get stuck.
This section lists highly recommended platforms, books, and tools for practice and learning. For most of the topics below, you can find excellent tutorials on sites like CP-Algorithms or Wikipedia.
- Luogu: A Chinese OJ platform with a vast collection of problems from informatics olympiads.
- AtCoder: A popular Japanese platform known for high-quality, math-oriented contests.
- Codeforces: The most popular platform for competitive programming, hosting regular contests for all skill levels.
- SPOJ: A classic online judge with a large number of problems, often used for practicing specific, well-known algorithms.
- LeetCode: Excellent for practicing specific topics and preparing for technical interviews.
- Introduction to Algorithms - Thomas H.Cormen/Charles E.Leiserson/Ronald L.Rivest/Clifford Stein
- Competitive Programmer’s Handbook - Antti Laaksonen
- Algorithms Illuminated - Tim Roughgarden
A powerful search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
An optimization technique that solves complex problems by breaking them down into simpler subproblems, storing their results to avoid redundant computations.
A programming language feature that allows you to define custom behavior for operators (like +, -, <) with your own data types (e.g., structs or classes). This can make code for concepts like vectors, matrices, or modular arithmetic much cleaner and more intuitive.
An efficient, stable, comparison-based sorting algorithm that works by dividing an array into halves, sorting them recursively, and then merging the sorted halves.
A specialized tree-based data structure that satisfies the heap property. It's perfect for efficiently finding and extracting the minimum or maximum element.
A technique that converts a string into a numeric value (a hash) to allow for fast comparisons. Polynomial rolling hash is a common and powerful method used to solve many problems involving string matching and palindromes.
An efficient string-searching algorithm that preprocesses the pattern to skip unnecessary comparisons, achieving linear time complexity.
Creates an array (the Z-array) where Z[i] is the length of the longest common prefix between the original string and the suffix starting at i. Useful for various pattern-matching problems.
A tree-like data structure that stores a dynamic set of strings, enabling fast retrieval and prefix-based searches.
A string-searching algorithm that can find all occurrences of a set of keywords in a text simultaneously. It combines a trie with failure links, similar to KMP.
Two fundamental graph traversal algorithms. DFS explores as far as possible along each branch before backtracking, while BFS explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
A DFS-based algorithm that finds the strongly connected components (maximal subgraphs where every vertex is reachable from every other vertex) in a directed graph.
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
A linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.
A versatile tree-based data structure that allows for efficient range queries (e.g., sum, min, max) and point updates on an array.
Advanced tree structures that automatically maintain a balanced height, ensuring that operations like search, insert, and delete remain efficient (logarithmic time). They are incredibly flexible for complex order-based problems.
Structures where modifying the data structure creates a new version while keeping the old version accessible. This is useful for querying past states of the data.
- Problem 0: kth smallest value in an interval (online algorithm only, *the problem description is in Chinese)
- Problem 1
- Problem 2: find the mex (smallest non-negative integer that does not appear in a set) of an interval (online algorithm, *the problem description is in Chinese)
- Problem 3
A technique that divides an array into blocks of size
sqrt(N) to perform range queries and updates. It's often simpler to implement than more complex structures like segment trees and can be surprisingly versatile.
- Problem 1 (also can be done by using segment tree)
- Problem 2 (Mo's algorithm)
Fundamental concepts in number theory. Sieves, like the Sieve of Eratosthenes or Euler's Sieve, are highly efficient algorithms for finding all prime numbers up to a specified integer.
The inverse of a number a modulo m is a number x such that (a*x) % m = 1. It's possible to precompute inverses for all numbers up to n in linear time.
A branch of mathematics concerned with strategy. The Nim Game is a classic impartial game whose solution often involves the Sprague-Grundy theorem and XOR operations.
- Problem 0 (*the problem description is in Chinese)
- Problem 1 (*the problem description is in Chinese)
- Problem 2 (K-Nim, a little difficult) (*the problem description is in Chinese)
- Problem 3 (Anti-Nim) (*the problem description is in Chinese)
- Problem 4 (altered Nim Game) (*the problem description is in Chinese)