The topics below are not exhaustive for this division.
Contest problems may contain topics not covered in the guide, or topics listed under different divisions!
Introductory Number Theory
Every (?) Gold and Platinum contest has at least one DP problem.
Introduction to DP
Speeding up naive recursive solutions with memoization.
Problems that can be modeled as filling a limited-size container with a subset of items.
Paths on Grids
Counting the number of "special" paths on a grid, and how some string problems can be solved using grids.
Longest Increasing Subsequence
Has Not Appeared
Finding and using the longest increasing subsequence of an array.
Updated: 3 weeks ago
DP problems that require iterating over subsets.
Solving the problem on every contiguous subarray of the original array.
Breadth First Search (BFS)
Traversing a graph in a way such that vertices closer to the starting vertex are processed first.
Disjoint Set Union
The Disjoint Set Union (DSU) data structure allows you to add edges to an initially empty graph and test whether two vertices of the graph are connected.
An ordering of vertices in a directed acyclic graph that ensures that a node is visited before every node it has a directed edge to.
Shortest Paths with Non-Negative Edge Weights
Introduces Bellman-Ford, Floyd-Warshall, Dijkstra.
Minimum Spanning Trees
A subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight, where no cycles are allowed.
A data structures that only allows insertion and deletion at one end.
Maintaining data over consecutive subarrays.
Updated: Last week
Point Update Range Sum
Introduces Segment Tree, Binary Indexed Tree, and C++ Order Statistic Tree.
Updated: 2 weeks ago
Rarely required at this level, but still good to know.