# 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: Last month

Knapsack DP

Not Frequent

Problems that can be modeled as filling a limited-size container with a subset of 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.

Updated: Last week

Bitmask DP

Rare

DP problems that require iterating over subsets.

Range DP

Rare

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

## 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: Last week

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: 3 weeks 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.

Shortest Paths with Non-Negative Edge Weights

Somewhat Frequent

Introduces Bellman-Ford, Floyd-Warshall, Dijkstra.

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.

## Data Structures

## Trees

## 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: 3 weeks ago

(Optional) More on Unordered Sets & Maps

Rare

Maintaining collections of distinct elements with hashing.

Updated: Last month

(Optional) A Faster Hash Table in C++

Rare

Introduces gp_hash_table.