Gold
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!
Modules Progress
Problems Progress
Introductory Number Theory
Dynamic Programming
Every (?) Gold and Platinum contest has at least one DP problem.
Introduction to DP
Very Frequent
Speeding up naive recursive solutions with memoization.
Updated: 2 hours ago
Knapsack DP
Not Frequent
Problems that can be modeled as filling a limited-size container with a subset of items.
Updated: 2 hours ago
Paths on Grids
Not Frequent
Counting the number of "special" paths on a grid, and how some string problems can be solved using grids.
Updated: 2 hours ago
Longest Increasing Subsequence
Has Not Appeared
Finding and using the longest increasing subsequence of an array.
Updated: 2 hours ago
Bitmask DP
Rare
DP problems that require iterating over subsets.
Updated: 2 hours ago
Range DP
Rare
Solving the problem on every contiguous subarray of the original array.
Updated: 2 hours ago
Graphs
Breadth First Search (BFS)
Not Frequent
Traversing a graph in a way such that vertices closer to the starting vertex are processed first.
Updated: 2 hours ago
Disjoint Set Union
Somewhat Frequent
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.
Updated: 2 hours ago
Topological Sort
Rare
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.
Updated: 2 hours ago
Shortest Paths with Non-Negative Edge Weights
Somewhat Frequent
Introduces Bellman-Ford, Floyd-Warshall, Dijkstra.
Updated: 2 hours ago
Minimum Spanning Trees
Not Frequent
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.
Updated: 2 hours ago
Data Structures
Stacks
Rare
A data structures that only allows insertion and deletion at one end.
Updated: 2 hours ago
Sliding Window
Not Frequent
Maintaining data over consecutive subarrays.
Updated: 2 hours ago
Point Update Range Sum
Somewhat Frequent
Introduces Segment Tree, Binary Indexed Tree, and C++ Order Statistic Tree.
Updated: 2 hours ago
Trees
Euler Tour Technique
Not Frequent
Flattening a tree into an array to easily query and update subtrees.
Updated: 23 minutes ago
DP on Trees - Introduction
Not Frequent
Using subtrees as subproblems.
Updated: 2 weeks ago
DP on Trees - Solving For All Roots
Rare
Tree DP that uses the subtree from excluding each node's subtree.
Updated: 2 hours ago
Hashing
Rarely required at this level, but still good to know.
String Hashing
Rare
Quickly test equality of substrings with a small probability of failure.
Updated: 2 hours ago
(Optional) Unordered Sets & Maps
Rare
Maintaining collections of distinct elements with hashing.
Updated: 3 weeks ago
(Optional) A Faster Hash Table in C++
Rare
Introduces gp_hash_table.
Updated: 2 weeks ago