Graph Algorithms (S4)

Dijkstra and weighted shortest paths Minimum spanning trees Topological sort and DAGs Strongly connected components DSU applications and offline processing

Trees

Tree DP and rerooting LCA and binary lifting

Dynamic Programming

1D DP and state design The knapsack family Grid and interval DP DP on DAGs and shortest-path-as-DP DP over sequences and subsequences DP optimization (CHT, D&C, monotone)DP with geometry/counting states

Number Theory and Combinatorics

Modular exponentiation, inverses, sieves Binomial coefficients and counting mod p

Geometry II

Convex hull and orientation Sweep line and geometric counting

Data Structures II

BIT and segment trees

Dynamic Programming

DP over sequences and subsequences

common

Work in progress

This module is still being written — the content here is a placeholder. This guide is open source, and contributions are welcome.

Contribute on GitHub — help write this module by opening a pull request.

DP on DAGs and shortest-path-as-DP

DP on DAGs and shortest-path-as-DP — anchored on 2020 S4 *Swapping Seats* and 2024 S4 *Minecarts*

DP optimization (CHT, D&C, monotone)

DP optimization (CHT, D&C, monotone) — anchored on 2019 S5 *Triangle: The Data Structure*

On this page

DP over sequences and subsequences