Gold

Divisibility

Rare

Using the information that one integer evenly divides another.

Modular Arithmetic

Not Frequent

Working with remainders from division.

Combinatorics

Not Frequent

How to count.
Updated: 3 weeks ago

Introduction to DP

Very Frequent

Speeding up naive recursive solutions with memoization.

Knapsack DP

Not Frequent

Problems that can be modeled as filling a limited-size container with items.

Paths on Grids

Not Frequent

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.

Bitmask DP

Not Frequent

DP problems that require iterating over subsets.

Range DP

Rare

Solving a DP problem on every contiguous subarray of the original array.

Digit DP

Rare

Finding the number of integers in a range that have a property.
Updated: 2 weeks ago

Shortest Paths with Unweighted Edges

Not Frequent

Introduces how BFS can be used to find shortest paths in unweighted graphs.

Disjoint Set Union

Somewhat Frequent

The Disjoint Set Union (DSU) data structure, which allows you to add edges to a graph and test whether two vertices of the graph are connected.

Topological Sort

Rare

Ordering the vertices of a directed acyclic graph such that each vertex is visited before its children.

Shortest Paths with Non-Negative Edge Weights

Not Frequent

Bellman-Ford, Floyd-Warshall, and Dijkstra.

Minimum Spanning Trees

Not Frequent

Finding a subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight.

Stacks

Rare

A data structure that only allows insertion and deletion at one end.

Sliding Window

Not Frequent

Maintaining data over consecutive subarrays.

Point Update Range Sum

Somewhat Frequent

Segment Tree, Binary Indexed Tree, and Order Statistic Tree (in C++).

Euler Tour Technique

Not Frequent

Flattening a tree into an array to easily query and update subtrees.

DP on Trees - Introduction

Not Frequent

Using subtrees as subproblems.

DP on Trees - Solving For All Roots

Rare

Tree DP problems involving rerooting.

String Hashing

Rare

Quickly testing equality of substrings with a small probability of failure.

(Optional) Hashmaps

Rare

Maintaining collections of distinct elements with hashing.

Meet In The Middle

Rare

Problems involving dividing the search space into two.

Additional Practice for USACO Gold

Final tips for Gold and additional practice problems.