External Problem Index¶
This page lists curated external problems imported into the topic-map system.
- Total curated external problems:
688 - Data files: external-problem-catalog.json, external-problem-catalog.csv
- Fastest route: Problem Finder when you want one filtered view across repo notes and external practice
- Best use: open a topic map first, then pick from the external problems table that matches your current subtopic and difficulty.
Foundations¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Foundations -> Binary Search |
Core |
032 - Binary Search | AtCoder |
Easy |
- | - | Membership; Sorted-Array |
Foundations -> Binary Search |
Core |
C - Buy an Integer | AtCoder |
Medium |
- | - | Digit-Length; Math |
Foundations -> Binary Search |
Classics |
Array Division | CSES |
Medium |
- | Proof-Heavy; Greedy-Heavy | Binary-Search-On-Answer; Partitioning; Greedy-Check; Partition |
Foundations -> Binary Search |
Classics |
Factory Machines | CSES |
Medium |
- | Proof-Heavy; Math-Heavy | Binary-Search-On-Answer; Monotonicity; Counting; Monotone-Predicate; Minimize-Answer |
Foundations -> Binary Search |
Classics |
Magic Powder - 2 | Codeforces |
Medium |
- | Proof-Heavy; Greedy-Heavy | Binary-Search-On-Answer; Resource-Feasibility |
Foundations -> Binary Search |
Classics |
Maximum Median | Codeforces |
Medium |
- | Proof-Heavy; Math-Heavy | Binary-Search-On-Answer; Median |
Foundations -> Bit Tricks |
Warm-Up |
Gray Code | CSES |
Easy |
Bit Manipulation | Implementation | Gray-Code; Constructive |
Foundations -> Bit Tricks |
Core |
Raising Bacteria | Codeforces |
Easy |
Bit Manipulation | Implementation | Popcount; Greedy View |
Foundations -> C++ Language |
Warm-Up |
Missing Number | CSES |
Easy |
- | Implementation-Heavy | Arrays; Math; Accumulation; Scan |
Foundations -> C++ Language |
Warm-Up |
Repetitions | CSES |
Easy |
- | Implementation-Heavy | Scanning; Runs; Run-Length; Scan |
Foundations -> C++ Language |
Warm-Up |
Weird Algorithm | CSES |
Easy |
- | Implementation-Heavy | Simulation; Loops; I/O; Branching |
Foundations -> C++ Language |
Core |
Coin Piles | CSES |
Easy |
- | - | Parity; Cases; Math |
Foundations -> C++ Language |
Core |
Permutations | CSES |
Easy |
- | Implementation-Heavy | Construction; Parity; Output-Formatting |
Foundations -> C++ Language |
Theory / Course |
Increasing Array | CSES |
Easy |
- | Proof-Heavy; Implementation-Heavy | Arrays; Invariants |
Foundations -> Complexity And Invariants |
Core |
Collecting Numbers | CSES |
Easy |
- | Proof-Heavy; Implementation-Heavy | Permutations; Position-Mapping; Positions |
Foundations -> Complexity And Invariants |
Core |
Missing Coin Sum | CSES |
Medium |
- | - | Sorting |
Foundations -> Complexity And Invariants |
Core |
Stick Lengths | CSES |
Medium |
- | - | Median; Absolute-Deviation; Sorting |
Foundations -> Complexity And Invariants |
Core |
Collecting Numbers II | CSES |
Hard |
- | - | Updates; Swap-Delta |
Foundations -> Complexity And Invariants |
Variants |
Distinct Values Subarrays | CSES |
Medium |
- | Proof-Heavy; Implementation-Heavy | Two-Pointers; Distinctness; Subarrays |
Foundations -> Complexity And Invariants |
Variants |
Playlist | CSES |
Medium |
- | Proof-Heavy; Data-Structure-Heavy | Sliding-Window; Distinctness; Amortized-Analysis |
Foundations -> Complexity And Invariants |
Classics |
Towers | CSES |
Medium |
- | Proof-Heavy; Data-Structure-Heavy | Patience-Sorting; Lower Bound |
Foundations -> Complexity And Invariants |
Theory / Course |
Increasing Array | CSES |
Easy |
- | Proof-Heavy; Greedy-Heavy | Prefix-Maintenance; Prefix-Max |
Foundations -> Difference Arrays |
Core |
D - Water Heater | AtCoder |
Medium |
Imos | - | Difference Array; Sweep Line; Events |
Foundations -> Difference Arrays |
Core |
Range Update Queries | CSES |
Medium |
Difference Array | Implementation-Heavy | Range-Add; Point-Query |
Foundations -> Difference Arrays |
Core |
D - Snuke Prime | AtCoder |
Hard |
Imos | - | Difference Array; Sweep Line; Interval-Cost |
Foundations -> Difference Arrays |
Classics |
Greg and Array | Codeforces |
Medium |
- | Modeling-Heavy; Implementation-Heavy | Difference Array; Offline; Range-Operations |
Foundations -> Difference Arrays |
Classics |
Little Girl and Maximum Sum | Codeforces |
Medium |
- | Greedy-Heavy; Math-Heavy | Difference Array; Sorting; Frequency |
Foundations -> Prefix Sums |
Warm-Up |
Static Range Sum Queries | CSES |
Easy |
- | Implementation-Heavy | Range-Sum; Prefix-Sum; Range-Query; Precompute |
Foundations -> Prefix Sums |
Core |
Range Xor Queries | CSES |
Easy |
- | - | Prefix-XOR; Range-Query; Bitwise |
Foundations -> Prefix Sums |
Core |
Subarray Sums I | CSES |
Medium |
- | Implementation-Heavy | Two-Pointers; Subarrays |
Foundations -> Prefix Sums |
Core |
Subarray Sums II | CSES |
Medium |
- | Implementation-Heavy; Math-Heavy | Hash-Map; Subarrays |
Foundations -> Prefix Sums |
Classics |
Subarray Divisibility | CSES |
Medium |
- | Math-Heavy | Mod Arithmetic; Counting |
Foundations -> Prefix Sums |
Cross-Topic |
Forest Queries | CSES |
Medium |
- | Modeling-Heavy; Query-Heavy | 2D Prefix Sums; Rectangles; Rectangle-Query; Grid |
Foundations -> Recursion And Backtracking |
Warm-Up |
Apple Division | CSES |
Easy |
- | Implementation | Subset Search; Brute Force |
Foundations -> Recursion And Backtracking |
Core |
Creating Strings | CSES |
Easy |
- | Implementation | Permutations; Duplicates |
Foundations -> Recursion And Backtracking |
Classics |
Chessboard and Queens | CSES |
Medium |
- | Implementation; Pruning | Pruning; Board Search |
Foundations -> STL Basics |
Warm-Up |
Distinct Numbers | CSES |
Easy |
- | Data-Structure-Heavy; Implementation-Heavy | Set; Deduplication; Frequency; Sort; Unique |
Foundations -> STL Basics |
Core |
Restaurant Customers | CSES |
Easy |
- | Modeling-Heavy; Implementation-Heavy | Events; Sweep Line; Sorting |
Foundations -> STL Basics |
Core |
Towers | CSES |
Medium |
- | - | Multiset; Lower Bound; Patience |
Foundations -> STL Basics |
Classics |
Concert Tickets | CSES |
Medium |
- | Data-Structure-Heavy; Greedy-Heavy | Multiset; Lower Bound |
Foundations -> STL Basics |
Classics |
Room Allocation | CSES |
Medium |
- | Data-Structure-Heavy; Greedy-Heavy | Priority-Queue; Intervals; Assignment |
Foundations -> STL Basics |
Classics |
Traffic Lights | CSES |
Medium |
- | Data-Structure-Heavy | Ordered-Set; Intervals; Updates; Neighbors |
Foundations -> STL Basics |
Advanced |
Sliding Window Cost | CSES |
Hard |
- | Data-Structure-Heavy | Median; Sliding-Window; Absolute-Deviation |
Foundations -> STL Basics |
Advanced |
Sliding Window Median | CSES |
Hard |
- | Data-Structure-Heavy; Query-Heavy | Multiset; Median; Sliding-Window |
Foundations -> Sorting |
Core |
Apartments | CSES |
Easy |
- | Greedy-Heavy; Implementation-Heavy | Two-Pointers; Matching; Sort |
Foundations -> Sorting |
Core |
Movie Festival | CSES |
Easy |
- | Greedy-Heavy | Intervals; Sort |
Foundations -> Sorting |
Core |
Reading Books | CSES |
Easy |
- | Greedy-Heavy | Scheduling |
Foundations -> Sorting |
Core |
Tasks and Deadlines | CSES |
Medium |
- | - | Sort; Ordering |
Foundations -> Sorting |
Classics |
Ferris Wheel | CSES |
Easy |
- | Greedy-Heavy | Two-Pointers; Pairing; Sort |
Foundations -> Sorting |
Classics |
Stick Lengths | CSES |
Medium |
- | Math-Heavy; Greedy-Heavy | Median; Absolute-Deviation |
Foundations -> Sorting |
Advanced |
Nested Ranges Check | CSES |
Medium |
- | Proof-Heavy; Greedy-Heavy | Intervals; Containment |
Foundations -> Two Pointers |
Core |
Playlist | CSES |
Medium |
Sliding Window | Implementation-Heavy; Proof-Heavy | Distinctness; Subarrays; Distinct |
Foundations -> Two Pointers |
Core |
Subarray Sums I | CSES |
Medium |
Sliding Window | Implementation-Heavy | Subarrays; Positive-Sums; Positive-Array |
Foundations -> Two Pointers |
Core |
Sum of Two Values | CSES |
Medium |
- | Implementation-Heavy | Pair-Sum; Hash-Map |
Foundations -> Two Pointers |
Variants |
Sliding Window Distinct Values | CSES |
Medium |
- | Implementation-Heavy | Sliding-Window; Frequency-Counting; Distinct-Count |
Foundations -> Two Pointers |
Classics |
Ferris Wheel | CSES |
Easy |
- | Greedy-Heavy | Pairing |
Foundations -> Two Pointers |
Classics |
Distinct Values Subarrays | CSES |
Medium |
Sliding Window | Proof-Heavy; Implementation-Heavy | Distinctness; Distinct-Count |
Data Structures¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Data Structures -> B-Trees |
Core |
B-Tree Dictionary Benchmark | Open Data Structures |
Medium |
B-Tree, Textbook Breadth | Data-Structure-Heavy; Implementation-Heavy | Split-Full-Child; Multiway-Search |
Data Structures -> Balanced BSTs For Contests |
Compare |
ORDERSET - Order Statistic Set | SPOJ |
Medium |
Balanced Bst Compare, Order Statistics | Data-Structure-Heavy; Classic | Rank-Query; Kth-Smallest; Compare-Route |
Data Structures -> Balanced BSTs For Contests |
Compare |
Salary Queries | CSES |
Medium |
Balanced Bst Compare, Treap Compare | Data-Structure-Heavy; Query-Heavy | Duplicate-Safe-Wrapper; Range-Count; Compare-Route |
Data Structures -> Balanced BSTs For Contests |
Implementation Challenge |
Luogu P3369 - 普通平衡树 | Luogu |
Hard |
Avl, Red-Black, Scapegoat, Size-Balanced-Tree, Balanced Bst | Data-Structure-Heavy; Implementation-Heavy | Rotations; Order-Statistics; Predecessor-Successor |
Data Structures -> Binary Trie / XOR Queries |
Core |
Vasiliy's Multiset | Codeforces |
Medium |
Binary Trie, XOR Queries | Data-Structure-Heavy; Bitwise | Dynamic-Multiset; Maximum-XOR |
Data Structures -> Binary Trie / XOR Queries |
Stretch |
SUBXOR | SPOJ |
Hard |
Binary Trie, Counting Variant, Classic | Bitwise; Classic | Prefix-XOR; Counting |
Data Structures -> Binary Trie / XOR Queries |
Bridge |
Maximum Xor Subarray | CSES |
Hard |
Bitwise Operations, Prefix XOR, Binary Trie | Bitwise; Array Transformation | Maximum-XOR |
Data Structures -> DSU |
Warm-Up |
Disjoint Set Union I | AOJ |
Easy |
- | Implementation-Heavy | Intro; Online-Judge |
Data Structures -> DSU |
Core |
Building Roads | CSES |
Easy |
- | Data-Structure-Heavy; Implementation-Heavy | Components; Connectivity |
Data Structures -> DSU |
Core |
Road Construction | CSES |
Easy |
- | Data-Structure-Heavy | Dynamic-Connectivity; Largest-Component; Component-Size |
Data Structures -> DSU |
Classics |
Road Reparation | CSES |
Medium |
- | Greedy-Heavy; Data-Structure-Heavy | Minimum-Spanning-Tree; Kruskal; MST |
Data Structures -> DSU |
Classics |
Union Find | Library Checker |
Medium |
- | Data-Structure-Heavy | Connectivity |
Data Structures -> DSU On Tree / Small-To-Large |
Core |
Distinct Colors | CSES |
Hard |
Subtree Queries | Small-To-Large Merging; Subtree Frequency Maps; Offline Aggregation | Distinct Values; Subtree Aggregation; Small-To-Large |
Data Structures -> DSU On Tree / Small-To-Large |
Stretch |
Lomsat gelral | Codeforces |
Hard |
Subtree Queries | Small-To-Large Merging; Frequency Aggregation; Heavy Child Compare Point | Color Frequency; Subtree Aggregation; Small-To-Large |
Data Structures -> DSU Rollback / Offline Dynamic Connectivity |
Core |
Dynamic Connectivity | CSES |
Hard |
Advanced Techniques, Dynamic Connectivity | Offline; Data-Structure-Heavy; Timeline Modeling | Rollback-DSU; Segment-Tree-Over-Time; Component-Count |
Data Structures -> DSU Rollback / Offline Dynamic Connectivity |
Stretch |
Dynamic Graph Vertex Add Component Sum | Library Checker |
Hard |
Dynamic Connectivity | Offline; Verification; Data-Structure-Heavy | Rollback-DSU; Segment-Tree-Over-Time; Component Metadata |
Data Structures -> Fenwick Tree |
Core |
Dynamic Range Sum Queries | CSES |
Medium |
- | Data-Structure-Heavy; Query-Heavy | Point-Update; Range-Sum |
Data Structures -> Fenwick Tree |
Core |
Range Update Queries | CSES |
Medium |
- | Data-Structure-Heavy | Difference Array; Range-Update; Range-Add |
Data Structures -> Fenwick Tree |
Classics |
Point Add Range Sum | Library Checker |
Medium |
- | Query-Heavy; Data-Structure-Heavy | Range-Sum |
Data Structures -> Fenwick Tree |
Classics |
Salary Queries | CSES |
Medium |
- | Query-Heavy; Data-Structure-Heavy | Coordinate-Compression; Range-Count; Compression; Rank-Query |
Data Structures -> Fenwick Tree |
Advanced |
Forest Queries II | CSES |
Hard |
- | Data-Structure-Heavy; Cross-Topic | 2D-Fenwick; Rectangle-Query; Grid-Updates; Grid; Point-Update |
Data Structures -> Fenwick Tree |
Advanced |
Range Add Range Sum | Library Checker |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Range-Update |
Data Structures -> Heaps And Ordered Sets |
Core |
Restaurant Customers | CSES |
Easy |
- | Modeling-Heavy | Events; Sweep Line; Maximum-Overlap |
Data Structures -> Heaps And Ordered Sets |
Core |
Room Allocation | CSES |
Medium |
- | Greedy-Heavy; Data-Structure-Heavy | Priority-Queue; Interval-Scheduling; Assignment |
Data Structures -> Heaps And Ordered Sets |
Core |
Movie Festival II | CSES |
Hard |
- | - | Multiset; K-Members |
Data Structures -> Heaps And Ordered Sets |
Classics |
Concert Tickets | CSES |
Medium |
- | Data-Structure-Heavy; Greedy-Heavy | Multiset; Predecessor-Query; Lower Bound |
Data Structures -> Heaps And Ordered Sets |
Classics |
Traffic Lights | CSES |
Medium |
- | Data-Structure-Heavy | Ordered-Set; Intervals; Max-Gap; Neighbors |
Data Structures -> Heaps And Ordered Sets |
Advanced |
Sliding Window Cost | CSES |
Hard |
- | Data-Structure-Heavy | Median; Absolute-Deviation |
Data Structures -> Heaps And Ordered Sets |
Advanced |
Sliding Window Median | CSES |
Hard |
- | Data-Structure-Heavy | Median; Sliding-Window |
Data Structures -> Interval Trees |
Core |
Reservation System | AOJ |
Easy |
Interval Tree, Interval Overlap | Data-Structure-Heavy; Query-Heavy | Half-Open-Intervals; Overlap-Query; Augmented-Bst |
Data Structures -> Lazy Segment Tree |
Core |
HORRIBLE | SPOJ |
Medium |
Range Queries, Lazy Propagation | Data-Structure-Heavy; Query-Heavy | Range-Add; Range-Sum; Classic |
Data Structures -> Lazy Segment Tree |
Stretch |
Polynomial Queries | CSES |
Hard |
Range Queries | Data-Structure-Heavy; Math-Heavy | Lazy-Propagation; Range-Update; Arithmetic-Progression |
Data Structures -> Lazy Segment Tree |
Stretch |
Range Updates and Sums | CSES |
Hard |
Range Queries | Data-Structure-Heavy | Lazy-Propagation; Range-Add; Range-Assign |
Data Structures -> Lazy Segment Tree |
Advanced |
Range Affine Range Sum | AtCoder |
Hard |
- | Data-Structure-Heavy; Verification | Lazy-Propagation; Affine-Update; Acl-Style |
Data Structures -> Mo's Algorithm |
Core |
Powerful Array | Codeforces |
Hard |
Frequency Maintenance | Query-Heavy; Data-Structure-Heavy | Range-Frequency; Offline |
Data Structures -> Mo's Algorithm |
Practice |
Static Range Count Distinct | Library Checker |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Distinct-Count; Offline |
Data Structures -> Mo's Algorithm |
Classics |
D-query | SPOJ |
Hard |
Classic | Query-Heavy; Data-Structure-Heavy | Distinct-Count; Offline Range Queries |
Data Structures -> Mo's Algorithm |
Bridge |
Distinct Values Queries | CSES |
Hard |
Compare Point | Query-Heavy; Compare-Point | Distinct-Count; Offline |
Data Structures -> Monotonic Stack / Queue |
Core |
Nearest Smaller Values | CSES |
Medium |
Monotonic Stack | Implementation; Amortized | Previous-Smaller; Boundary |
Data Structures -> Monotonic Stack / Queue |
Core |
Sliding Window Minimum | CSES |
Medium |
Monotonic Deque | Implementation; Streaming | Window-Minimum; Stream |
Data Structures -> Monotonic Stack / Queue |
Classics |
Advertisement | CSES |
Medium |
Monotonic Stack | Implementation; Geometry-On-Array | Histogram; Nearest-Smaller; Rectangle Area |
Data Structures -> ODT / Chtholly |
Core |
896C - Willem, Chtholly and Seniorious | Codeforces |
Hard |
Interval-Partition | Data-Structure-Heavy; Implementation; Randomized-Input | Range Assign; Ordered Set; Expected Complexity; Kth Query |
Data Structures -> ODT / Chtholly |
Bridge |
915E - Physical Education Lessons | Codeforces |
Hard |
Interval-Partition | Data-Structure-Heavy; Query-Heavy | Range Assign; Piecewise Constant; Interval Counting |
Data Structures -> Offline Tricks |
Core |
Static Range Count Distinct | Library Checker |
Hard |
- | - | Mo's Algorithm; Distinct-Count |
Data Structures -> Offline Tricks |
Core |
Point Add Rectangle Sum | Library Checker |
Very Hard |
- | - | Sweep Line; Fenwick |
Data Structures -> Offline Tricks |
Classics |
Distinct Values Queries | CSES |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Mo's Algorithm; Range-Distinct; Frequency |
Data Structures -> Offline Tricks |
Classics |
Powerful Array | Codeforces |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Mo's Algorithm; Range-Frequency |
Data Structures -> Offline Tricks |
Advanced |
Rectangle Sum | Library Checker |
Medium |
- | Query-Heavy; Modeling-Heavy | Sweep Line; 2D-Queries; Fenwick |
Data Structures -> Offline Tricks |
Advanced |
Distinct Values Queries II | CSES |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Updates; Distinctness; Query-Processing |
Data Structures -> Offline Tricks |
Cross-Topic |
Salary Queries | CSES |
Medium |
- | Query-Heavy; Data-Structure-Heavy | Coordinate-Compression; Range-Count; Updates; Fenwick |
Data Structures -> PBDS / Order Statistics Tree |
Core |
ORDERSET - Order Statistic Set | SPOJ |
Medium |
Order Statistics | Data-Structure-Heavy; Classic | Kth-Smallest; Rank-Query |
Data Structures -> PBDS / Order Statistics Tree |
Practice |
Josephus Problem II | CSES |
Hard |
Circular Elimination | Simulation-Heavy; Data-Structure-Heavy | Find-By-Order; Josephus |
Data Structures -> PBDS / Order Statistics Tree |
Bridge |
Salary Queries | CSES |
Medium |
Order Statistics | Query-Heavy; Data-Structure-Heavy | Duplicate-Safe-Wrapper; Range-Count |
Data Structures -> Pairing Heap / Leftist Heap |
Core |
P3377 [Template] Mergeable Heap 1 | Luogu |
Medium |
Meldable-Heap, Leftist-Heap | Data-Structure-Heavy; Implementation | Delete Min; DSU; Simulation |
Data Structures -> Pairing Heap / Leftist Heap |
Challenge |
P1456 Monkey King | Luogu |
Hard |
Meldable-Heap | Data-Structure-Heavy; Implementation | Leftist Heap; Heap Merge |
Data Structures -> Persistent Data Structures |
Core |
Range Queries and Copies | CSES |
Hard |
Persistent Segment Tree | Data-Structure-Heavy; Versioned Queries | Path-Copying; Version-Roots; Range-Sum |
Data Structures -> Persistent Data Structures |
Stretch |
K-th Number | SPOJ |
Hard |
Order Statistics, Persistent Segment Tree | Data-Structure-Heavy; Value Compression | Prefix-Versions |
Data Structures -> Persistent Data Structures |
Challenge |
Persistent Union Find | Library Checker |
Hard |
Persistent Union Find | Verification; Versioned Queries | Persistence; Versioned Connectivity |
Data Structures -> Persistent Treap |
Core |
Persistent List | E-olymp |
Hard |
Implicit Treap, Persistence | Data-Structure-Heavy; Modeling-Heavy | Split-Merge; Branching-Versions; Sequence-Persistence |
Data Structures -> Segment Tree |
Core |
Dynamic Range Minimum Queries | CSES |
Medium |
- | Data-Structure-Heavy | Range-Min; Point-Update |
Data Structures -> Segment Tree |
Core |
Dynamic Range Sum Queries | CSES |
Medium |
- | Data-Structure-Heavy; Query-Heavy | Point-Update; Range-Sum |
Data Structures -> Segment Tree |
Classics |
Hotel Queries | CSES |
Medium |
- | Data-Structure-Heavy; Greedy-Heavy | First-Fit; Prefix-Max; Max-Query |
Data Structures -> Segment Tree |
Classics |
Prefix Sum Queries | CSES |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Prefix-Max; Range-Query |
Data Structures -> Segment Tree |
Advanced |
Point Set Range Composite | Library Checker |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Function-Composition |
Data Structures -> Segment Tree |
Advanced |
Polynomial Queries | CSES |
Hard |
- | Data-Structure-Heavy; Math-Heavy | Lazy-Propagation; Range-Add; Arithmetic-Progression; Range-Update |
Data Structures -> Segment Tree |
Advanced |
Range Updates and Sums | CSES |
Hard |
- | Data-Structure-Heavy | Lazy-Propagation; Range-Add; Range-Assign |
Data Structures -> Segment Tree |
Advanced |
Subarray Sum Queries | CSES |
Hard |
- | Data-Structure-Heavy; Query-Heavy | Max-Subarray; Point-Update |
Data Structures -> Segment Tree Beats |
Core |
Range Chmin Chmax Add Range Sum | Library Checker |
Hard |
Range Queries | Data-Structure-Heavy; Verification | Range-Chmin; Range-Chmax; Range-Add |
Data Structures -> Segment Tree Beats |
Bridge |
The Child and Sequence | Codeforces |
Hard |
Compare Point | Data-Structure-Heavy; Compare-Point | Beats-Like-Pruning; Range-Modulo; Range-Sum |
Data Structures -> Skip Lists |
Core |
Skiplist Dictionary Benchmark | Open Data Structures |
Medium |
Skiplist, Textbook Breadth | Data-Structure-Heavy; Implementation-Heavy | Random Heights; Expected Logarithmic |
Data Structures -> Sparse Table |
Core |
Static Range Minimum Queries | CSES |
Easy |
- | Query-Heavy; Data-Structure-Heavy | Range-Min; Static-Queries; Idempotent |
Data Structures -> Sparse Table |
Core |
Range GCD Query | Library Checker |
Medium |
- | - | GCD; Idempotent |
Data Structures -> Sparse Table |
Classics |
Static RMQ | Library Checker |
Easy |
- | Query-Heavy | Range-Min; Idempotent |
Data Structures -> Splay Tree |
Core |
Luogu P3369 - 普通平衡树 | Luogu |
Hard |
Order Statistics | Data-Structure-Heavy; Implementation-Heavy | Rank-Query; Kth-Smallest; Predecessor-Successor |
Data Structures -> Splay Tree |
Stretch |
Luogu P3391 - 文艺平衡树 | Luogu |
Hard |
Sequence Route | Data-Structure-Heavy; String-Like | Sequence; Reverse-Interval |
Data Structures -> Splay Tree |
Compare |
ORDERSET - Order Statistic Set | SPOJ |
Medium |
Compare Route | Data-Structure-Heavy; Classic | Order-Statistics |
Data Structures -> Treap / Implicit Treap |
Core |
Salary Queries | CSES |
Medium |
Key-Based Treap, Order Statistics | Data-Structure-Heavy; Query-Heavy | Range-Count; Pair-Key-Wrapper |
Data Structures -> Treap / Implicit Treap |
Practice |
Cut and Paste | CSES |
Hard |
Implicit Treap, Sequence Surgery | Data-Structure-Heavy; Modeling-Heavy | Split-Merge; Sequence-Edits |
Data Structures -> Treap / Implicit Treap |
Practice |
Substring Reversals | CSES |
Hard |
Implicit Treap, Sequence Lazy Tags | Data-Structure-Heavy; String-Like | Reverse; Lazy-Tag |
Data Structures -> Treap / Implicit Treap |
Stretch |
Dynamic Sequence Range Affine Range Sum | Library Checker |
Very Hard |
Implicit Treap, Advanced | Data-Structure-Heavy; Verification | Affine-Lazy; Range-Sum |
Data Structures -> Wavelet Tree |
Core |
MKTHNUM - K-th Number | SPOJ |
Hard |
Order Statistics | Query-Heavy; Data-Structure-Heavy | Range-Kth; Static-Queries |
Data Structures -> Wavelet Tree |
Practice |
Range K-th Smallest | Library Checker |
Hard |
- | Query-Heavy; Data-Structure-Heavy | Range-Kth |
Data Structures -> Wavelet Tree |
Classics |
K-query | SPOJ |
Hard |
Threshold Counting, Classic | Query-Heavy; Classic | Threshold-Count |
Data Structures -> X-Fast / Y-Fast Tries |
Core |
X-Fast Dictionary Benchmark | Open Data Structures |
Hard |
X-Fast Trie, Textbook Breadth | Data-Structure-Heavy; Implementation-Heavy | Bounded-Universe; Prefix-Hashing; Predecessor-Successor |
Graphs¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Graphs -> BFS And DFS |
Core |
Monsters | CSES |
Medium |
Multi-Source BFS, Grid BFS | Two-Phase BFS; Distance Grid; Path Reconstruction | Grid; Timing |
Graphs -> BFS And DFS |
BFS Shortest Path |
Labyrinth | CSES |
Easy |
Grid | BFS Tree; Parent Array; Route Recovery | Shortest Path; Path Reconstruction; Maze |
Graphs -> BFS And DFS |
Bipartite Check |
Building Teams | CSES |
Easy |
Bipartite | DFS Coloring; Conflict Detection; Component Handling | Two-Coloring; Bipartite Graph |
Graphs -> BFS And DFS |
Connected Components |
Counting Rooms | CSES |
Easy |
Grid | DFS Flood Fill; Component Sweep; Boundary Checks | Flood Fill; Components; Visited Cells |
Graphs -> BFS And DFS |
Directed Cycle |
Round Trip II | CSES |
Medium |
Directed Graphs | DFS State Colors; Stack-Based Recovery; Cycle Witness | Directed Cycle; Recursion Stack; Witness Path; Topological Intuition; Reconstruction |
Graphs -> BFS And DFS |
Undirected Cycle |
Round Trip | CSES |
Medium |
Cycles | DFS Parent Tracking; Cycle Reconstruction; Component Scan | Undirected Cycle; Back Edge; Witness Path; Cycle Detection; Undirected Graph; Reconstruction |
Graphs -> BFS And DFS |
Unweighted BFS |
Message Route | CSES |
Easy |
Paths | Layered BFS; Parent Tracking; Shortest Route Recovery | Unweighted Shortest Path; Path Reconstruction; Network; Shortest Path |
Graphs -> Bridges, Articulation, And BCC |
Core |
Necessary Cities | CSES |
Medium |
Low-Link | Low-Link DFS; Root Special Case; Critical Vertex Output | Critical Vertices; Root Case; Cut Vertices |
Graphs -> Bridges, Articulation, And BCC |
Core |
Necessary Roads | CSES |
Medium |
Low-Link | Low-Link DFS; Bridge Detection; Critical Edge Output | Critical Edges; DFS Tree; Bridge Detection |
Graphs -> Bridges, Articulation, And BCC |
Practice |
Two-Edge-Connected Components | Library Checker |
Medium |
Two-Edge-Connected Components | Bridge Removal; Component Compression; Tree Of Components | Bridge Compression; 2-Edge Connectivity |
Graphs -> Bridges, Articulation, And BCC |
Classics |
Submerging Islands | SPOJ |
Medium |
Classic | Low-Link DFS; Cut Vertex Counting; Root Handling | Cut Vertices; Articulation Points |
Graphs -> Bridges, Articulation, And BCC |
Stretch |
Forbidden Cities | CSES |
Hard |
Bcc, Block-Cut Tree | Block-Cut Tree; LCA On Reduced Structure; Query Reduction | Vertex-Biconnected Components |
Graphs -> Centroid Decomposition |
Warm-Up |
Finding a Centroid | CSES |
Medium |
Trees | Subtree Sizes; Balance Check; Candidate Descent | Subtree Sizes; Balance Check |
Graphs -> Centroid Decomposition |
Core |
Ciel the Commander | Codeforces |
Hard |
Construction | Centroid Decomposition; Recursive Labeling; Tree Partition | Centroid Tree; Recursive Labeling; Balanced Split |
Graphs -> Centroid Decomposition |
Practice |
Xenia and Tree | Codeforces |
Hard |
Queries | Centroid Ancestors; Distance Aggregation; Online Queries | Nearest Marked Node; Centroid Ancestors; Distance Aggregation |
Graphs -> Centroid Decomposition |
Stretch |
Fixed-Length Paths I | CSES |
Hard |
Path Counting | Path Counting; Depth Collection; Frequency Merge | Exact Length; Depth Histogram; Through-Centroid Counting |
Graphs -> Centroid Decomposition |
Advanced |
Fixed-Length Paths II | CSES |
Hard |
Path Counting | Path Counting; Range Counting; Prefix Merge | Length Range; Depth Prefix Counts; Through-Centroid Counting |
Graphs -> De Bruijn Sequence |
Core |
De Bruijn Sequence | CSES |
Hard |
Graph Modeling, Construction | State Graph Modeling; Eulerian Construction; String Reconstruction | De Bruijn Graph; Eulerian Cycle; Bitmask States |
Graphs -> Edmonds Blossom / General Matching |
Core |
Matching on General Graph | Library Checker |
Hard |
Blossom | Template Problem; Non-Bipartite Matching | Edmonds Blossom; Odd Cycle; Maximum Matching |
Graphs -> Edmonds Blossom / General Matching |
Practice |
P6113 [Template] General Graph Maximum Matching | Luogu |
Hard |
Blossom | Template Drill; Non-Bipartite Matching | Template; Maximum Matching |
Graphs -> Edmonds Blossom / General Matching |
Bridge |
QBFLOWER - Tặng hoa | VN SPOJ |
Medium |
Edge Cover | Modeling; Transformation | Minimum Edge Cover; Graph Transformation |
Graphs -> Euler Tour / Subtree Queries |
Core |
Subtree Queries | CSES |
Medium |
Trees, Euler Tour | Flatten Tree; Fenwick Tree; Range Sum Queries | Subtree Sum; Updates; Fenwick |
Graphs -> Euler Tour / Subtree Queries |
Stretch |
Count Descendants | AtCoder |
Medium |
Trees, Euler Tour | Flatten Tree; Offline Counting; Binary Search | Subtree Interval; Depth Buckets; Offline |
Graphs -> Euler Tour / Subtree Queries |
Stretch |
Distinct Colors | CSES |
Hard |
Trees | Flatten Tree; Offline Queries; Subtree Aggregation | Distinct Values; Subtree Aggregation; Offline |
Graphs -> Euler Tour / Subtree Queries |
Bridge |
Path Queries | CSES |
Medium |
Trees, Euler Tour | Euler Tour; Fenwick Tree; Prefix On Tree | Root Path Sum; Updates; Tree Flattening |
Graphs -> Euler Tour Tree |
Core |
Dynamic Tree Vertex Add Subtree Sum | Library Checker |
Very Hard |
Dynamic Trees | Dynamic Trees; Subtree Aggregate; Verifier | Dynamic Forest; Subtree Sum; Vertex Add |
Graphs -> Euler Tour Tree |
Stretch |
Dynamic Tree Subtree Add Subtree Sum | Library Checker |
Very Hard |
Dynamic Trees | Dynamic Trees; Lazy Range Update; Verifier | Dynamic Forest; Lazy Propagation; Subtree Sum |
Graphs -> Eulerian Path / Cycle |
Core |
Mail Delivery | CSES |
Medium |
Undirected | Hierholzer Traversal; Degree Check; Witness Output | Eulerian Cycle; Hierholzer; Degree Parity; Undirected Graphs |
Graphs -> Eulerian Path / Cycle |
Core |
Teleporters Path | CSES |
Hard |
Directed | Directed Hierholzer; Balance Check; Start-End Enforcement | Eulerian Path; Directed Graphs; In-Out Balance; Hierholzer |
Graphs -> Eulerian Path / Cycle |
Classics |
Play on Words | UVa |
Medium |
Classic | Modeling; Balance Check; Connected Support | String To Graph; Directed Eulerian Path |
Graphs -> Flow With Lower Bounds |
Core |
Reactor Cooling | Codeforces acmsguru |
Hard |
Lower Bounds | Reduction; Witness Output | Feasible Circulation; Balance Array; Witness Output |
Graphs -> Flow With Lower Bounds |
Advanced |
Minimum Cost b-Flow | Library Checker |
Hard |
Lower Bounds, Cost | Verification; Cross-Topic | Node Supply/Demand; Costed Flow |
Graphs -> Gomory-Hu Tree |
Core |
Download Speed | CSES |
Medium |
Cuts | - | Max Flow; Source-Sink Cut; Network |
Graphs -> Gomory-Hu Tree |
Core |
Maximum Flow | AOJ |
Medium |
Cuts | - | Max Flow; Min Cut; Baseline |
Graphs -> Gomory-Hu Tree |
Core |
Police Chase | CSES |
Medium |
Min Cut, Edge-Disjoint Separation, Cuts | S-T Min Cut; Edge Extraction | Flow; Roads; Edge Cut; Certificate |
Graphs -> Gomory-Hu Tree |
Core |
Gomory-Hu Tree | Library Checker |
Hard |
Cut-Trees | - | All-Pairs Min-Cut; Tree Of Cuts |
Graphs -> Gomory-Hu Tree |
Classics |
Sabotage | UVa |
Medium |
Min Cut, Global Min Cut | Undirected Min Cut; Cut Extraction | Flow; Cuts; Graph Partition |
Graphs -> Gomory-Hu Tree |
Advanced |
Pumping Stations | Codeforces |
Very Hard |
Gomory-Hu Tree, Pairwise Min Cuts | Gh Tree Reasoning; Cut-Tree Structure | Flow; Trees; Divide And Conquer |
Graphs -> Gomory-Hu Tree |
Theory / Course |
All Pairs Maximum Flow | UVa |
Hard |
Gomory-Hu Tree, All-Pairs Min Cut | Build Cut Tree; Query Path Minima | Flow; Trees |
Graphs -> Graph Modeling |
Core |
Building Roads | CSES |
Easy |
Components | - | Connected Components; Construction; Union-Find |
Graphs -> Graph Modeling |
Core |
Message Route | CSES |
Easy |
BFS | - | Unweighted Graph; Path Reconstruction; Shortest Path |
Graphs -> Graph Modeling |
Core |
Third Avenue | AtCoder |
Medium |
Grid BFS | - | Teleporters; Implicit Graph; Grid |
Graphs -> Graph Modeling |
2 SAT Modeling |
Giant Pizza | CSES |
Medium |
2-SAT, SCC | Implication Graph; SCC Condensation; Assignment Extraction | Implication Graph; Boolean Constraints |
Graphs -> Graph Modeling |
Coordinate MST |
Built? | AtCoder |
Medium |
MST, Geometry | Edge Generation By Sorting; DSU; Kruskal | Coordinate Graph; Kruskal; Sparse Edges |
Graphs -> Graph Modeling |
Grid Cycle |
Fox And Two Dots | Codeforces |
Medium |
Grid DFS | DFS With Parent Tracking; Cycle Witness; Component Scan | Cycle Detection; Same-Color Regions; Grid Graph |
Graphs -> Graph Modeling |
Grid Flood Fill |
Counting Rooms | CSES |
Easy |
Grid DFS | Iterative DFS; Visited Marking; 4-Neighbor Traversal | Flood Fill; Connected Components; Implicit Graph |
Graphs -> Graph Modeling |
Grid Shortest Path |
Labyrinth | CSES |
Easy |
Grid BFS | Single-Source BFS; Parent Pointers; Route Recovery | Shortest Path; Path Reconstruction; Maze; Grid |
Graphs -> Graph Modeling |
Multi Source BFS |
Monsters | CSES |
Medium |
Grid BFS | Two-Phase BFS; Distance Grid; Path Reconstruction | Multi-Source BFS; Escape Path; Timing Constraints; Timing; Escape |
Graphs -> Heavy-Light Decomposition |
Core |
Path Queries II | CSES |
Medium |
Path Max Query | Path Decomposition; Node Updates | Trees; Updates; Segment Tree; Path Max; Point Update |
Graphs -> Heavy-Light Decomposition |
Core |
Vertex Add Path Sum | Library Checker |
Medium |
- | - | Path Sum; Verify |
Graphs -> Heavy-Light Decomposition |
Core |
Vertex Set Path Composite | Library Checker |
Hard |
- | - | Non-Commutative; Path Queries; Verify |
Graphs -> Heavy-Light Decomposition |
Classics |
QTREE2 | SPOJ |
Medium |
Path Queries | Path Distance; K-Th Node | Trees; Distance; K-Th Node |
Graphs -> Heavy-Light Decomposition |
Classics |
QTREE3 | SPOJ |
Medium |
Dynamic Path Query | Toggle Queries; Path Prefix Search | Trees; Toggle; Nearest Black Node |
Graphs -> Heavy-Light Decomposition |
Classics |
QTREE | SPOJ |
Hard |
Heavy-Light Decomposition, Path Queries | Edge Path Queries; Segment Tree | Trees; Segment Tree |
Graphs -> Heavy-Light Decomposition |
Advanced |
QTREE4 | SPOJ |
Hard |
Dynamic Tree Queries | Color Toggles; Global Path Aggregate | Trees; Toggle; Path Aggregate |
Graphs -> Heavy-Light Decomposition |
Advanced |
Water Tree | Codeforces |
Hard |
Subtree Updates | Subtree Update / Ancestor Query; Lazy Propagation | Trees; Range Updates; Online Queries |
Graphs -> Hungarian / Assignment Problem |
Core |
Task Assignment | CSES |
Hard |
Weighted Matching | Dense Cost Matrix; Weighted Bipartite Matching | Cost Matrix; Perfect Matching |
Graphs -> Hungarian / Assignment Problem |
Practice |
Another Assignment Problem | SPOJ |
Medium |
- | Weighted Bipartite Matching; Assignment Matrix | Weighted Matching; Optimization |
Graphs -> Hungarian / Assignment Problem |
Stretch |
The Great Wall Game | ACM regional archive |
Hard |
Geometry | Geometry To Cost Matrix; Minimum Cost Perfect Matching | Manhattan Distance; Modeling |
Graphs -> LCA |
Core |
Company Queries I | CSES |
Easy |
- | - | Binary Lifting; Kth Ancestor; Jump Pointers |
Graphs -> LCA |
Binary Lifting |
Company Queries II | CSES |
Medium |
Binary Lifting | Jump Pointers; Depth Equalization; Ancestor Climbing | Lowest Common Ancestor; Boss Queries; Ancestor Table; Boss Hierarchy |
Graphs -> LCA |
LCA Application |
閉路 | AtCoder |
Medium |
Distances | Distance Via LCA; Path Length Formula; Query Preprocessing | Cycle Length; Tree Path; Query Answer |
Graphs -> LCA |
LCA Basics |
LCA: Lowest Common Ancestor | AOJ |
Medium |
- | Binary Lifting; Euler Tour; Ancestor Checks | Rooted Tree; Binary Lifting; Ancestor Queries |
Graphs -> LCA |
LCA Basics |
Lowest Common Ancestor | Library Checker |
Medium |
- | Binary Lifting; HLD-Style Interface; Query Batching | Implementation Check; Rooted Tree; Verify; Binary Lifting |
Graphs -> LCA |
LCA Distance Formula |
Distance Queries | CSES |
Medium |
Distances | Depth Plus LCA; Distance Formula; Binary Lifting | Tree Distance; Path Length; Distance; Rooted Tree |
Graphs -> Link-Cut Tree |
Core |
Dynamic Tree Vertex Add Path Sum | Library Checker |
Very Hard |
Dynamic Trees | Dynamic Trees; Path Aggregate; Verifier | Dynamic Forest; Path Sum; Vertex Add |
Graphs -> Link-Cut Tree |
Stretch |
Dynamic Tree Vertex Set Path Composite | Library Checker |
Very Hard |
Dynamic Trees | Dynamic Trees; Non-Commutative Query; Verifier | Dynamic Forest; Path Composite; Non-Commutative |
Graphs -> Matching |
Warm-Up |
Gopher II | UVa |
Easy |
Bipartite Matching, Geometry-To-Graph | Distance-Threshold Graph; Max Matching | Geometry; Reachability |
Graphs -> Matching |
Warm-Up |
The dog task | UVa |
Easy |
Bipartite Matching | Small Bipartite Graph; Matching | Animals; Assignment |
Graphs -> Matching |
Core |
Bipartite Matching | AOJ |
Easy |
- | - | Bipartite Graph; Augmenting Paths; Kuhn |
Graphs -> Matching |
Core |
Guardian of Decency | UVa |
Medium |
Bipartite Matching, Independent Set | Compatibility Graph; Matching To Cover | Compatibility Graph |
Graphs -> Matching |
Core |
School Dance | CSES |
Medium |
Bipartite Matching | Augmenting Paths; Bipartite Matching | Bipartite Graphs; Pairing; Construction |
Graphs -> Matching |
Core |
Stable Marriage | Canonical / Gale-Shapley |
Medium |
- | Two-Sided Preferences; Deferred Acceptance | Stable Matching; Preferences; Blocking Pair |
Graphs -> Matching |
Core |
General Matching | Library Checker |
Hard |
- | - | Blossom; Non-Bipartite; Verify |
Graphs -> Matching |
Core |
Task Assignment | CSES |
Hard |
- | - | Assignment; Weighted Matching; Bipartite Graph |
Graphs -> Matching |
Classics |
A Plug for UNIX | UVa |
Medium |
Bipartite Matching, Adapter Graph | Reachability Closure; Max Matching | Conversion Graph |
Graphs -> Matching |
Classics |
Antenna Placement | UVa |
Medium |
Minimum Vertex Cover | Grid Bipartization; Vertex Cover Extraction | Grid Graphs; Domination |
Graphs -> Matching |
Classics |
Machine Schedule | UVa |
Medium |
Bipartite Matching, Job Assignment | Job-Machine Bipartite Graph; Minimum Cover Intuition | Scheduling |
Graphs -> Matching |
Advanced |
Sorting Slides | UVa |
Hard |
Unique Assignment | Forced-Edge Reasoning; Matching Plus Uniqueness | Geometry; Deduction |
Graphs -> Maximum Flow |
Core |
Download Speed | CSES |
Medium |
- | Dinic; S-T Max Flow | Directed Graphs; S-T Cut; Max Flow; Capacity; Network Throughput |
Graphs -> Maximum Flow |
Core |
Maximum Flow | AOJ |
Medium |
- | - | Max Flow; Push-Relabel; Dinic; Network |
Graphs -> Maximum Flow |
Core |
Police Chase | CSES |
Medium |
- | - | Min Cut; Max Flow; Edge Cut |
Graphs -> Maximum Flow |
Classics |
Fast Maximum Flow | SPOJ |
Medium |
Min Cut | Dinic; Residual Graph | Undirected Graphs; Capacity |
Graphs -> Maximum Flow |
Advanced |
Angry Programmer | UVa |
Hard |
Min Cut, Node Splitting | Node/Edge Splitting; Min Cut Modeling | Vertex Cuts; Security Model |
Graphs -> Maximum Flow |
Advanced |
Distinct Routes | CSES |
Hard |
Path Decomposition | Unit-Capacity Flow; Path Extraction | Route Packing; Max Flow; Edge-Disjoint Paths; Route Recovery |
Graphs -> Maximum Flow |
Cross-Topic |
The Problem with the Problem Setter | UVa |
Medium |
Bipartite Flow | Bipartite Flow; Source-Sink Layering | Matching; Assignment |
Graphs -> Maximum Flow |
Cross-Topic |
Power Transmission | UVa |
Hard |
Node Splitting | Vertex Splitting; Capacity Constraints | Vertex Capacities |
Graphs -> Min-Cost Flow |
Core |
Crime Wave - The Sequel | UVa |
Medium |
Min-Cost Max-Flow, Assignment | Assignment Model; Min-Cost Matching | Bipartite Matching |
Graphs -> Min-Cost Flow |
Core |
Minimum Cost Flow | AOJ |
Medium |
- | - | Min-Cost Max-Flow; Potentials; Shortest Augmenting Path |
Graphs -> Min-Cost Flow |
Core |
Distinct Routes II | CSES |
Hard |
- | - | K Routes; Path Reconstruction |
Graphs -> Min-Cost Flow |
Core |
Parcel Delivery | CSES |
Hard |
- | - | Capacitated Edges; Transport |
Graphs -> Min-Cost Flow |
Core |
Task Assignment | CSES |
Hard |
- | - | Assignment; Bipartite Matching; Cost Matrix |
Graphs -> Min-Cost Flow |
Classics |
Another Assignment Problem | SPOJ |
Medium |
Assignment | Costed Bipartite Matching; Successive Shortest Augmenting Path | Matching |
Graphs -> Min-Cost Flow |
Advanced |
Data Flow | UVa |
Hard |
Capacity Planning | Binary Search Over Time; Min-Cost Flow Feasibility | Latency; Throughput |
Graphs -> Min-Cost Flow |
Advanced |
Dijkstra, Dijkstra. | UVa |
Hard |
Min-Cost Max-Flow, Disjoint Paths | Successive Shortest Augmenting Path | Shortest Path |
Graphs -> Min-Cost Flow |
Advanced |
Yet Another Assignment Problem | SPOJ |
Hard |
Scheduling | Time-Expanded Scheduling; Cost Minimization | Assignment |
Graphs -> Min-Cost Flow |
Cross-Topic |
Warehouse | UVa |
Hard |
Grid Modeling | Graph Construction From Grid; Minimum Cost Assignment | Grid; Movement Cost |
Graphs -> Minimum Spanning Tree |
Core |
Minimum Spanning Tree | Kattis |
Easy |
- | - | Kruskal; Classic |
Graphs -> Minimum Spanning Tree |
Coordinate MST |
Built? | AtCoder |
Medium |
Geometry | Sorting By Coordinate; Candidate Edge Pruning; Kruskal | Coordinate Graph; Sparse Edges |
Graphs -> Minimum Spanning Tree |
Kruskal |
Minimum Spanning Tree | AOJ |
Medium |
DSU | Edge Sorting; Union-Find; Weight Accumulation | MST Sum; Weighted Graph; Kruskal; Weighted Undirected |
Graphs -> Minimum Spanning Tree |
Kruskal |
Road Reparation | CSES |
Medium |
DSU | Edge Sorting; DSU Merges; Component Counting | Minimum Spanning Tree; Connectivity |
Graphs -> Minimum Spanning Tree |
MST Variants |
Minimum spanning tree for each edge | Codeforces |
Hard |
- | Kruskal Base Tree; Max-Edge Queries On Path; Replacement Reasoning | Replacement Edge; MST Variants; Binary Lifting |
Graphs -> Minimum Spanning Tree |
MST Verification |
Minimum Spanning Tree | Library Checker |
Medium |
- | Kruskal Template; Edge Index Handling; DSU | Sparse Graph; DSU; Verify |
Graphs -> Randomized / Global Min-Cut |
Warm-Up |
Police Chase | CSES |
Medium |
Min Cut, Edge Cut, Flow | S-T Min Cut; Edge Extraction | Roads; Certificate |
Graphs -> Randomized / Global Min-Cut |
Core |
Minimum Cut | POJ |
Hard |
Undirected Cuts | Stoer-Wagner; Dense Cut Phases | Stoer-Wagner; Cut Contraction |
Graphs -> Randomized / Global Min-Cut |
Classics |
Sabotage | UVa |
Medium |
Min Cut, Flow | S-T Min Cut; Cut Extraction | Graph Partition |
Graphs -> Shortest Paths |
All Pairs DP |
Shortest Routes II | CSES |
Medium |
APSP | Floyd-Warshall; Dense-Graph DP; Distance Matrix | All-Pairs Shortest Path; Floyd-Warshall; All-Pairs; Undirected Weighted |
Graphs -> Shortest Paths |
All Pairs Shortest Paths |
バスと避けられない運命 | AtCoder |
Hard |
APSP | All-Pairs DP; Radius Minimization; Dense Graph Reasoning | Floyd-Warshall; Graph Center; Minimax Distance |
Graphs -> Shortest Paths |
Classic Dijkstra |
Dijkstra? | Codeforces |
Medium |
Dijkstra | Priority Queue Dijkstra; Parent Pointers; Simple Path Output | Weighted Graph; Shortest Route; Path Reconstruction |
Graphs -> Shortest Paths |
Dijkstra |
Shortest Routes I | CSES |
Easy |
Dijkstra | Priority Queue Relaxation; Distance Array; Outdated-State Skipping | Single-Source Shortest Path; Weighted Digraph; Priority Queue; Single-Source; Directed Weighted |
Graphs -> Shortest Paths |
Dijkstra Plus Counting |
Investigation | CSES |
Medium |
Dijkstra | Augmented Relaxations; Path Counting; Tie Handling | Count Shortest Paths; Min/Max Edges; Mod Arithmetic; Counts; Min/Max Hops |
Graphs -> Shortest Paths |
Layered Dijkstra |
Flight Discount | CSES |
Medium |
Dijkstra | Two-State Dijkstra; Forward And Reverse Distances; Coupon Use | One-Time Discount; Layered Graph; Stateful Shortest Path; State Expansion |
Graphs -> Shortest Paths |
Negative Cycle Handling |
High Score | CSES |
Hard |
Bellman-Ford | Bellman-Ford; Cycle Reachability; Score Inversion | Negative Cycles; Maximum Path; Cycle Detection; Longest Path Transform |
Graphs -> Shortest Paths |
Negative Cycle Witness |
Cycle Finding | CSES |
Hard |
Bellman-Ford | Bellman-Ford Witness Extraction; Parent Recovery; Cycle Backtracking | Negative Cycle; Witness Cycle; Directed Graph; Cycle Reconstruction |
Graphs -> Shortest Paths |
Path Restoration |
Shortest Path | Library Checker |
Medium |
Path Reconstruction | Distance Predecessor Arrays; Path Rebuilding; Single-Source SSSP | Weighted Digraph; Route Output; Dijkstra |
Graphs -> Stable Marriage |
Core |
Stable Marriage | Canonical / Gale-Shapley |
Medium |
Stable Matching, Gale-Shapley | Two-Sided Preferences; Canonical Benchmark | Blocking Pair; Deferred Acceptance |
Graphs -> Stable Marriage |
Practice |
Stable Marriage Problem | Library Checker |
Medium |
Stable Matching, Gale-Shapley | Verifier-Style Problem; Stable Matching | Verify; Preferences |
Graphs -> Topological Sort And SCC |
Condensation DAG |
Coin Collector | CSES |
Hard |
DAG DP | SCC Compression; Post-Order DP; Component Aggregation | SCC Condensation; DP On DAG; Weighted Nodes; Max Path Weight |
Graphs -> Topological Sort And SCC |
DAG DP |
Game Routes | CSES |
Medium |
DAG DP | Topo-Based DP; Path Counts; Mod Arithmetic | Path Counting; Topological Order; Mod Arithmetic |
Graphs -> Topological Sort And SCC |
DAG Longest Path |
Longest Flight Route | CSES |
Medium |
DAG DP | Topo-Based DP; Parent Reconstruction; Reachability Filtering | Longest Path; Topological Order; Path Reconstruction |
Graphs -> Topological Sort And SCC |
Lexicographic Topo |
Course Schedule II | CSES |
Medium |
Lexicographic | Priority-Queue Kahn; Smallest Available Node; Deterministic Order | Lexicographic Order; Topological Sort; Directed Acyclic Graph; Lexicographic Topo; DAG; Ordering |
Graphs -> Topological Sort And SCC |
SCC Basics |
Strongly Connected Components | AOJ |
Medium |
- | Kosaraju; Tarjan; Component Ids | Mutual Reachability; Tarjan; Kosaraju; Component Queries |
Graphs -> Topological Sort And SCC |
SCC Labeling |
Planets and Kingdoms | CSES |
Medium |
Condensation | Kosaraju Or Tarjan; Component Numbering; Condensation DAG | SCC Labels; Kingdoms; Directed Graph; Strongly Connected Components; Labels |
Graphs -> Topological Sort And SCC |
Strong Connectivity |
Flight Routes Check | CSES |
Medium |
Reachability | SCC Decomposition; Condensation Reasoning; Counterexample Extraction | Strong Connectivity; Constructive Counterexample |
Graphs -> Topological Sort And SCC |
Topological Sort |
Course Schedule | CSES |
Easy |
DAG | Kahn Queue; In-Degree Tracking; Valid Order Output | Topological Sort; Prerequisites; Ordering; Kahn |
Graphs -> Topological Sort And SCC |
Topological Sort |
Topological Sort | AOJ |
Medium |
DFS | DFS Finish Order; Stack Reversal; DAG Validation | DAG; Ordering; Directed Graph; Kahn |
Graphs -> Tree DP |
Core |
Choosing Capital for Treeland | Codeforces |
Medium |
Rerooting, Tree DP On Directed Edges | One Reroot Pass; Edge-Cost Delta | Directed Tree |
Graphs -> Tree DP |
Core |
Tree Distances I | CSES |
Medium |
Rerooting | Two DFS Passes; Diameter Endpoints | Distance |
Graphs -> Tree DP |
Core |
Tree Distances II | CSES |
Hard |
Rerooting | Subtree Sums; Rerooting Formulas | Distance Sums; Sum Of Distances |
Graphs -> Tree DP |
Classics |
Independent Set | AtCoder DP Contest |
Medium |
Coloring DP | Bottom-Up DFS; Two-State DP | Mod Arithmetic |
Graphs -> Tree DP |
Classics |
Tree Matching | CSES |
Medium |
Matching On Trees | Postorder DFS; Local State Merge | Matching; Matching DP; States |
Graphs -> Tree DP |
Advanced |
Subtree | AtCoder DP Contest |
Hard |
Rerooting | Prefix/Suffix Rerooting; Subtree Products | Mod Arithmetic; Mod DP; Rooted Tree; Independent Set |
Graphs -> Tree DP |
Advanced |
Zero Tree | Codeforces |
Hard |
Difference Accumulation | Postorder Balancing; Sign-Aware Subtree Merge | Greedy |
Graphs -> Tree Isomorphism |
Core |
Tree Isomorphism I | CSES |
Hard |
Canonical Encoding | Bottom-Up Canonicalization; Postorder; Structural Comparison | Rooted Tree; Canonical Form; Unordered Children |
Graphs -> Tree Isomorphism |
Stretch |
Tree Isomorphism II | CSES |
Hard |
Tree Centers | Center Rooting; Bottom-Up Canonicalization; Structural Comparison | Unrooted Tree; Centers; Canonical Form |
Graphs -> Trees |
Core |
Diameter of a Tree | AOJ |
Easy |
- | - | Tree Diameter; DFS; Weighted Tree |
Graphs -> Trees |
Centroid |
Finding a Centroid | CSES |
Medium |
Subtree Sizes, Centroid | Size DFS; Balance Check; Candidate Descent | Balance; DFS |
Graphs -> Trees |
DSU On Tree |
Distinct Colors | CSES |
Hard |
DSU On Tree, Subtrees | Small-To-Large Merging; Subtree Frequency Maps; Offline Aggregation | Distinct Values; Subtree Aggregation; Small-To-Large |
Graphs -> Trees |
Euler Tour Bit |
Subtree Queries | CSES |
Medium |
Euler Tour, Fenwick | Flatten Tree; Fenwick Tree; Range Sum Queries | Subtree Sum; Updates |
Graphs -> Trees |
Rerooting DP |
Tree Distances I | CSES |
Medium |
Rerooting, Distances | Two-Pass DP; Downward And Upward Values; Distance Maxima | Eccentricity; Distance Propagation; Tree DP |
Graphs -> Trees |
Rerooting Sums |
Tree Distances II | CSES |
Medium |
Rerooting, Sums | Subtree DP; Reroot Transition; Sum Aggregation | Sum Of Distances; Tree DP |
Graphs -> Trees |
Root Path Queries |
Path Queries | CSES |
Medium |
Euler Tour, Fenwick | Euler Tour; Fenwick Tree; Prefix-On-Tree | Root Path Sum; Updates; Tree Flattening |
Graphs -> Trees |
Subtree Sizes |
Subordinates | CSES |
Easy |
DFS, Subtree Sizes | Postorder DFS; Size Accumulation; Rooted Traversal | Subtree Size; Rooted Tree; Counting |
Graphs -> Trees |
Tree Diameter |
Tree Diameter | CSES |
Easy |
DFS, Diameter | Double Sweep; DFS/BFS Diameter; Farthest Node | Two BFS; Longest Path |
Graphs -> Trees |
Tree DP |
Tree Matching | CSES |
Medium |
Tree DP, Greedy | Bottom-Up DP; Leaf Processing; Pairing Choices | Matching; Independent Edges; Independent Edge Set |
Graphs -> Two-SAT |
Warm-Up |
Two SAT | Library Checker |
Medium |
2-SAT | Implication Graph; SCC Check; Witness Recovery | Implication Graph; SCC; Assignment Extraction |
Graphs -> Two-SAT |
Core |
Giant Pizza | CSES |
Medium |
2-SAT, Assignment | Clause Rewrite; Implication Graph; Assignment Extraction | Implication Graph; Clause Modeling; SCC; Witness |
Graphs -> Two-SAT |
Classics |
Wedding | UVa |
Medium |
2-SAT, Classic | Boolean Modeling; Complement Pairs; SCC Assignment | Seating Constraints; Implication Graph |
Graphs -> Two-SAT |
Stretch |
The Door Problem | Codeforces |
Hard |
2-SAT, Modeling | Constraint Reframing; Implication Graph; Witness Recovery | Boolean Constraints; Parity-Like Modeling; Assignment |
Graphs -> Virtual Tree / Auxiliary Tree |
Core |
Kingdom and its Cities | Codeforces |
Very Hard |
- | Marked-Subset Compression; LCA; Query-Local DP | Marked Nodes; LCA; Tree DP; Minimum Separator |
Graphs -> Virtual Tree / Auxiliary Tree |
Stretch |
Leaf Color | AtCoder |
Very Hard |
- | Marked-Subset Compression; Per-Color Processing; Tree DP | Marked Nodes; Color Grouping; Compressed Tree |
DP¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
DP -> Bit-Parallelism / Bitset Optimization |
Core |
School Excursion | CSES |
Hard |
Bitset DP | Dynamic Programming; Implementation; Graph Modeling | Bitset; Reachability; Component Sizes; Subset Sum |
DP -> Bit-Parallelism / Bitset Optimization |
Stretch |
Money Sums | CSES |
Easy |
Subset Sum | Dynamic Programming; Implementation | Bitset; Reachable Sums; Boolean DP |
DP -> Bitmask DP |
Core |
Travelling Salesman Problem | AtCoder Beginner Contest 406 |
Hard |
- | - | TSP |
DP -> Bitmask DP |
Covering With Subsets |
Moovie Mooving | USACO Gold |
Medium |
Coverage-DP | Tabulation | Interval-Coverage |
DP -> Bitmask DP |
Gift Reassignment |
Redistributing Gifts | USACO Gold |
Hard |
Assignment-DP | Tabulation | Permutations |
DP -> Bitmask DP |
Hamiltonian Path Counting |
Hamiltonian Flights | CSES |
Hard |
Graph-Subset-DP | Tabulation | Graph; State Compression; Hamiltonian Path |
DP -> Bitmask DP |
Merge Subsets |
Grouping | AtCoder DP Contest |
Hard |
Subset-Partition | Tabulation | Partition |
DP -> Bitmask DP |
Minimum Cover |
Smallest Sufficient Team | LeetCode |
Hard |
Cover-DP | Tabulation | Set-Cover |
DP -> Bitmask DP |
Perfect Matching Count |
Matching | AtCoder DP Contest |
Medium |
Assignment-DP | Tabulation | Matching; Assignment; State Compression; Perfect Matching |
DP -> Bitmask DP |
Safety Constrained Subset |
Guard Mark | USACO Gold |
Medium |
Subset-Selection | Tabulation | Stacking |
DP -> Bitmask DP |
Small N Graph Editing |
Friendship Editing | USACO Gold |
Hard |
Graph-Subset-DP | Tabulation | Graphs |
DP -> Bitmask DP |
State Compressed Traversal |
Shortest Path Visiting All Nodes | LeetCode |
Hard |
Graph-Search | BFS; State-Compression | BFS |
DP -> Bitmask DP |
Subset Packing |
Elevator Rides | CSES |
Hard |
Subset-Packaging | Tabulation | Packing; Subset DP |
DP -> Broken Profile / Plug DP |
Core |
Counting Tilings | CSES |
Hard |
Grid DP | Counting; Frontier DP | Domino Tiling; Frontier Mask; Column Sweep |
DP -> Broken Profile / Plug DP |
Challenge |
Compound Escape | USACO Platinum |
Very Hard |
Plug-DP | Counting; Frontier DP | Frontier State; Counting; Challenge |
DP -> Convex Hull Trick / Li Chao Tree |
Core |
Line Add Get Min | Library Checker |
Medium |
Line Container | Implementation; Verification | Point Queries |
DP -> Convex Hull Trick / Li Chao Tree |
Core |
Monster Game I | CSES |
Hard |
Convex Hull Trick | Optimization; Monotone Structure | Affine DP; Monotone Hull; Line Container |
DP -> Convex Hull Trick / Li Chao Tree |
Core |
Monster Game II | CSES |
Hard |
Li Chao Tree | Optimization; Data-Structure-Heavy | Affine DP; Line Container |
DP -> Convex Hull Trick / Li Chao Tree |
Challenge |
Segment Add Get Min | Library Checker |
Hard |
Li Chao Tree, Segment Li Chao | Implementation; Verification | Segment-Limited Lines; Advanced |
DP -> Digit DP |
Core |
Almost Everywhere Zero | AtCoder Beginner Contest 154 |
Medium |
- | - | Tight DP; Count Digits |
DP -> Digit DP |
Core |
Digit Sum | AtCoder DP Contest |
Medium |
- | - | Tight DP; Mod Sum |
DP -> Digit DP |
Core |
Digit Products | AtCoder Beginner Contest 208 |
Hard |
- | - | Tight DP; Digit Product |
DP -> Digit DP |
Core |
Digit Sum Divisible | AtCoder Beginner Contest 336 |
Hard |
- | - | Tight DP; Sum+Remainder |
DP -> Digit DP |
Adjacent Digit Constraints |
Counting Numbers | CSES |
Medium |
Tight-DP | Memoization; Tabulation | Tight; Adjacency Constraint |
DP -> Digit DP |
Binary Digit DP |
Find Integers | LeetCode |
Medium |
Binary-DP | Memoization | Binary; Fibonacci-Like |
DP -> Digit DP |
Bounded Digit Set |
Numbers At Most N Given Digit Set | LeetCode |
Medium |
Counting | Memoization | Combinatorics |
DP -> Digit DP |
Complement Counting |
Numbers With Repeated Digits | LeetCode |
Hard |
Unique-Digits | Memoization | Combinatorics |
DP -> Digit DP |
Digit DP With Divisibility Masks |
Beautiful Numbers | Codeforces |
Very Hard |
Prime-Mask-DP | Memoization | Number Theory |
DP -> Digit DP |
Digit DP With Sums |
Segment Sum | Codeforces |
Very Hard |
Range-Aggregation | Memoization | Sum |
DP -> Digit DP |
No Repeated Digits |
Count Special Integers | LeetCode |
Hard |
Unique-Digits | Memoization | Bitmask |
DP -> Digit DP |
Range Digit Count |
Digit Sum | SPOJ |
Medium |
Range-Counting | Memoization | Sum |
DP -> Digit DP |
Restricted Digit Patterns |
Magic Numbers | Codeforces |
Medium-Hard |
Mod-Constraint | Memoization | Mod |
DP -> Digit DP |
Special Number Counting |
Travelling Salesman and Special Numbers | Codeforces |
Medium-Hard |
Counting | Memoization | - |
DP -> Digit DP |
Valid Digit Transforms |
Rotated Digits | LeetCode |
Medium |
Counting | Memoization | Rotation |
DP -> Divide and Conquer DP |
Core |
Ciel and Gondolas | Codeforces |
Very Hard |
Partition DP | Partition DP; Cost Preprocessing; Decision Monotonicity | Monotone Opt; 2D Prefix Sums; Contiguous Groups |
DP -> Divide and Conquer DP |
Stretch |
Yet Another Minimization Problem | Codeforces |
Very Hard |
Partition DP | Partition DP; Cost Maintenance; Decision Monotonicity | Monotone Opt; Mo-Style Cost Maintenance; Distinct Pair Cost |
DP -> FWHT / XOR Convolution / Subset Convolution |
Core |
Bitwise XOR Convolution | Library Checker |
Hard |
XOR Convolution, Boolean Cube | Dynamic Programming; Algebra; Implementation | Walsh-Hadamard; Full Cube |
DP -> FWHT / XOR Convolution / Subset Convolution |
Stretch |
Subset Convolution | Library Checker |
Hard |
Subset Convolution, Boolean Cube | Dynamic Programming; Algebra; Implementation | Popcount Layers; Zeta Transform; Full Cube |
DP -> Foundations |
Warm-Up |
Grid 1 | AtCoder DP Contest |
Easy-Medium |
Grid DP | Tabulation | Path Counting |
DP -> Foundations |
Warm-Up |
LCS | AtCoder DP Contest |
Medium |
String DP | Tabulation | 2D DP |
DP -> Foundations |
Base Recurrence |
Climbing Stairs | LeetCode |
Easy |
Linear DP | Memoization; Tabulation | Recurrence; 1D |
DP -> Foundations |
Choice States |
Vacation | AtCoder DP Contest |
Easy |
State DP | Tabulation | Choices; Day-By-Day; 2D DP; Daily Choice |
DP -> Foundations |
Choose Or Skip |
House Robber | LeetCode |
Medium |
Linear DP | Tabulation; Rolling-Array | Skip-Take; Optimization |
DP -> Foundations |
Counting Ways |
Dice Combinations | CSES |
Easy |
Counting DP | Tabulation | Counting; Mod |
DP -> Foundations |
Grid Paths |
Unique Paths | LeetCode |
Medium |
Grid DP | Tabulation | Grid; Combinatorics |
DP -> Foundations |
Pairwise String DP |
Longest Common Subsequence | CSES |
Medium |
String DP | Tabulation | 2D |
DP -> Foundations |
Prefix String Transforms |
Edit Distance | CSES |
Hard |
String DP | Tabulation | Transformations |
DP -> Foundations |
Segment Partitioning |
Teamwork | USACO Gold |
Easy |
Segmented DP | Tabulation | Partitioning; Bounded-Lookback |
DP -> Foundations |
Small Transition Window |
Frog 2 | AtCoder DP Contest |
Easy |
Linear DP | Tabulation | Min-Cost; Windowed-Transition; 1D DP; Bounded Jump |
DP -> Foundations |
State Transition Basics |
Frog 1 | AtCoder DP Contest |
Easy |
Linear DP | Tabulation; Memoization | Min-Cost; Recurrence; 1D DP |
DP -> Interval DP |
Core |
Deque | AtCoder DP Contest |
Medium |
- | - | Game DP |
DP -> Interval DP |
Core |
Zuma | Codeforces |
Hard |
- | - | Palindrome Removal |
DP -> Interval DP |
Color Mixing |
Mixtures | SPOJ |
Hard |
Merge-DP | Tabulation | Color-Merge |
DP -> Interval DP |
Extra Carried State |
Remove Boxes | LeetCode |
Hard |
Compressed-State-DP | Memoization | Memoization |
DP -> Interval DP |
Interval Repainting |
Modern Art 3 | USACO Gold |
Hard |
String-Like-Intervals | Tabulation | Painting |
DP -> Interval DP |
Last Burst Split |
Burst Balloons | LeetCode |
Hard |
Split-DP | Tabulation | Maximize |
DP -> Interval DP |
Merge Intervals |
Slimes | AtCoder DP Contest |
Hard |
Range-DP | Tabulation | Merge-Cost |
DP -> Interval DP |
Optimal Cut Ordering |
Minimum Cost to Cut a Stick | LeetCode |
Medium |
Cut-DP | Tabulation | Cuts |
DP -> Interval DP |
Palindrome Like Merging |
Strange Printer | LeetCode |
Hard |
String DP | Tabulation | Strings |
DP -> Interval DP |
Polygon Splitting |
Minimum Score Triangulation of Polygon | LeetCode |
Medium |
Polygon-DP | Tabulation | Geometry |
DP -> Interval DP |
Sorted Interval Expansion |
The Cow Run | USACO Gold |
Hard |
Ordered-Intervals | Tabulation | Path |
DP -> Interval DP |
Take From Ends Game |
Removal Game | CSES |
Medium |
Game-DP | Tabulation | Game-Theory; Minimax |
DP -> Knapsack Family |
Core |
Book Shop II | CSES |
Medium-Hard |
- | - | Bounded Knapsack; Multi-Copy |
DP -> Knapsack Family |
0 1 Capacity DP |
Book Shop | CSES |
Easy |
0-1-Knapsack | Tabulation; Rolling-Array | Capacity; Value Maximization; Budget |
DP -> Knapsack Family |
0 1 Knapsack |
Knapsack 1 | AtCoder DP Contest |
Medium |
0-1-Knapsack | Tabulation | Capacity; Value Maximization |
DP -> Knapsack Family |
Equal Partition Counting |
Two Sets II | CSES |
Easy |
Subset Sum | Tabulation | Partition; Combinatorics |
DP -> Knapsack Family |
Knapsack With A Toggle |
Fruit Feast | USACO Gold |
Easy |
State-Augmented-Knapsack | Tabulation | Unbounded; One-Time-State |
DP -> Knapsack Family |
Minimum Coin Count |
Minimizing Coins | CSES |
Easy |
Unbounded-Knapsack | Tabulation | Min-Coins; Unbounded; Min-Count |
DP -> Knapsack Family |
Minimum Coins With Repetition |
Coin Change | LeetCode |
Medium |
Unbounded-Knapsack | Tabulation | Min-Coins; Unbounded |
DP -> Knapsack Family |
Ordered Unbounded Counting |
Coin Combinations I | CSES |
Easy |
Unbounded-Knapsack | Tabulation | Counting; Order-Matters |
DP -> Knapsack Family |
Ratio Knapsack |
Talent Show | USACO Gold |
Hard |
Ratio-Optimization | Tabulation; Binary-Search-Check | Binary-Search-On-Answer |
DP -> Knapsack Family |
Reachable Sums |
Money Sums | CSES |
Easy |
Subset Sum | Tabulation | Reachable-Sums; Bitset-Friendly |
DP -> Knapsack Family |
Signed Subset Sum |
Target Sum | LeetCode |
Medium |
Counting-Knapsack | Tabulation | Sign-Assignments; Counting |
DP -> Knapsack Family |
Subset Partition |
Partition Equal Subset Sum | LeetCode |
Medium |
Subset Sum | Tabulation | Partition; Boolean |
DP -> Knapsack Family |
Two Dimensional Capacity |
Ones and Zeroes | LeetCode |
Medium |
2D-Knapsack | Tabulation | Dual-Capacity; 0-1 |
DP -> Knapsack Family |
Unordered Counting |
Coin Combinations II | CSES |
Easy |
Subset-Knapsack | Tabulation | Counting; Order-Does-Not-Matter |
DP -> Knapsack Family |
Value Indexed Knapsack |
Knapsack 2 | AtCoder DP Contest |
Hard |
Value-Based-DP | Tabulation | Capacity; Value-State; Value-Based Knapsack; Large W |
DP -> Knuth Optimization |
Core |
Knuth Division | CSES |
Hard |
Interval DP | Interval DP; Cost Preprocessing; Opt Window Monotonicity | Prefix Sums; Merge Cost |
DP -> Knuth Optimization |
Stretch |
Slimes | AtCoder DP Contest |
Hard |
Interval DP | Interval DP; Cost Preprocessing; Optimization Compare Point | Merge Cost; Prefix Sums; Optimization Compare Point |
DP -> Lagrangian Relaxation / Aliens Trick |
Core |
Red and Blue Lamps | AtCoder |
Hard |
Aliens Trick | Penalty Search; Linear DP; Binary Search On Answer Space | Exact K; Penalty Search; Non-Adjacent Picks |
DP -> Lagrangian Relaxation / Aliens Trick |
Stretch |
Shojin | AtCoder |
Hard |
Aliens Trick | Penalty Search; Follow-Up | Exact K; Penalty Search; Follow-Up |
DP -> Lagrangian Relaxation / Aliens Trick |
Challenge |
Patisserie ABC 3 | AtCoder |
Hard |
Aliens Trick | Penalty Search; Advanced Modeling | Exact K; Penalty Search; Advanced |
DP -> Lagrangian Relaxation / Aliens Trick |
Challenge |
Welcome to Tokyo! | AtCoder |
Hard |
Aliens Trick | Penalty Search; Theory-Heavy | Exact K; Penalty Search; Challenge |
DP -> SOS DP |
Core |
Compatible Numbers | Codeforces |
Very Hard |
Bitmask | Full-Cube Sweep; Complement Modeling; Offline Propagation | Bitmasks; Subset Zeta; Witness Propagation; Bitwise Complement |
DP -> SOS DP |
Stretch |
SOS Bit Problem | CSES |
Hard |
Bitmask | Full-Cube Sweep; Count Aggregation; Complement Counting | Subset Zeta; Superset Zeta; Bitwise Or; Bitwise And |
DP -> Sliding Window And Window DP |
Core |
Dice Combinations | CSES |
Easy |
- | - | 1D DP; Window Size 6 |
DP -> Sliding Window And Window DP |
Core |
Array Description | CSES |
Medium |
- | - | Bounded Transition DP; Prefix Sums |
DP -> Sliding Window And Window DP |
Core |
Candies | AtCoder DP Contest |
Medium-Hard |
- | - | Prefix-Sum DP; Bounded Range |
DP -> Sliding Window And Window DP |
At Most K Distinct |
Fruit Into Baskets | LeetCode |
Medium |
Frequency-Window | Two-Pointers | Distinct-Count; Two-Pointers |
DP -> Sliding Window And Window DP |
Distinct Count Window |
Sliding Window Distinct Values | CSES |
Easy |
Frequency-Window | Two-Pointers; Hash-Map | Frequency-Map; Distinct |
DP -> Sliding Window And Window DP |
Fixed Length Frequency Match |
Permutation in String | LeetCode |
Easy |
Frequency-Window | Two-Pointers | Anagram; Frequency-Array |
DP -> Sliding Window And Window DP |
Median Cost |
Sliding Window Cost | CSES |
Medium |
Order-Statistics | Balanced-Multiset | Median; Cost |
DP -> Sliding Window And Window DP |
Median Maintenance |
Sliding Window Median | CSES |
Medium |
Order-Statistics | Balanced-Multiset | Median; Multiset |
DP -> Sliding Window And Window DP |
Minimum Covering Window |
Minimum Window Substring | LeetCode |
Hard |
Frequency-Window | Two-Pointers; Hash-Map | Substring; Frequency-Map |
DP -> Sliding Window And Window DP |
Monotonic Minimum |
Sliding Window Minimum | CSES |
Easy |
Window-Maintenance | Deque | Deque; Minimum |
DP -> Sliding Window And Window DP |
Product Constraint |
Subarray Product Less Than K | LeetCode |
Medium |
Product-Window | Two-Pointers | Multiplicative; Two-Pointers |
DP -> Sliding Window And Window DP |
Single Character Dominance |
Longest Repeating Character Replacement | LeetCode |
Medium |
Frequency-Window | Two-Pointers | Frequency; Replacement |
DP -> Sliding Window And Window DP |
Unique Character Window |
Longest Substring Without Repeating Characters | LeetCode |
Medium |
Two-Pointers | Two-Pointers | Hash-Map; Substring |
DP -> Sliding Window And Window DP |
Unique Sum Window |
Maximum Erasure Value | LeetCode |
Medium |
Frequency-Window | Two-Pointers | Unique-Window; Prefix-Sums |
DP -> Sliding Window And Window DP |
Window Inversion Count |
Sliding Window Inversions | CSES |
Hard |
Inversion-Counting | Fenwick-Tree | Inversions; Fenwick |
DP -> Sliding Window And Window DP |
Windowed Histogram |
Sliding Window Advertisement | CSES |
Medium |
Monotonic-Window | Deque; Prefix-Scan | Deque; Max-Area |
DP -> Slope Trick |
Warm-Up |
Absolute Minima | AtCoder |
Hard |
- | Online Queries; Median Structure | Absolute Value Updates; Median Maintenance; Convex Function |
DP -> Slope Trick |
Core |
Snuketoon | AtCoder |
Hard |
- | Convex DP; Data-Structure-Heavy | One-Sided Penalties; Shift Min; Convex DP |
DP -> Slope Trick |
Stretch |
Travelling Salesman Problem | AtCoder |
Hard |
- | Convex DP; Follow-Up | Absolute Distance; Shift Min; Follow-Up |
DP -> Slope Trick |
Challenge |
Many Increasing Problems | AtCoder |
Hard |
- | Convex DP; Theory-Heavy | Monotone Sequence DP; Convex DP; Advanced |
DP -> Tree DP |
Core |
Tree Matching | CSES |
Medium |
- | - | Matching |
DP -> Tree DP |
Core |
Subtree | AtCoder DP Contest |
Medium-Hard |
- | - | Rerooting |
DP -> Tree DP |
All Roots Distance DP |
Sum of Distances in Tree | LeetCode |
Hard |
Rerooting | DFS; Rerooting | - |
DP -> Tree DP |
Best Path Through A Node |
Binary Tree Maximum Path Sum | LeetCode |
Hard |
Path-Aggregation | DFS; Postorder | Path |
DP -> Tree DP |
Maximum Distance Per Node |
Tree Distances I | CSES |
Medium |
Rerooting | DFS; Rerooting | Distance |
DP -> Tree DP |
Root Choice Optimization |
Directory Traversal | USACO Gold |
Medium |
Rerooting | DFS; Rerooting | - |
DP -> Tree DP |
Sum Of Distances |
Tree Distances II | CSES |
Medium |
Rerooting | DFS; Rerooting | - |
DP -> Tree DP |
Tree Coloring |
Barn Painting | USACO Gold |
Easy |
Coloring-DP | DFS; Postorder | Coloring |
DP -> Tree DP |
Tree Independent Set |
Independent Set | AtCoder DP Contest |
Medium |
Subtree-DP | DFS; Postorder | Independent-Set; 2-State |
DP -> Tree DP |
Tree Skip Take |
House Robber III | LeetCode |
Medium |
Tree-Structure | DFS; Postorder | Binary-Tree; Skip-Take |
Greedy¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Greedy -> Huffman / Data Compression |
Core |
Huffman Coding Benchmark | Algorithms 4/e |
Medium |
Data-Compression, Prefix-Codes | Heap Greedy; Tree Construction | Optimal Merge; Min-Heap; Weighted Path Length |
Greedy -> Prefix Constraints |
Core |
Lemonade Line | USACO 2018 US Open Silver |
Easy-Medium |
- | - | Sort+Greedy; Threshold |
Greedy -> Prefix Constraints |
Binary Construction |
Two Binary Strings | Codeforces |
Easy |
Construction | Greedy-Construction | Binary-Strings; Prefix-Conditions |
Greedy -> Prefix Constraints |
Extremal Constraints |
Prefix Min and Suffix Max | Codeforces |
Easy |
Prefix-Extrema | Greedy-Check | Prefix-Min; Suffix-Max |
Greedy -> Prefix Constraints |
Prefix Extrema |
Prefix Max | Codeforces |
Easy |
Prefix-Extrema | Greedy-Check | Prefix-Max; Arrays |
Greedy -> Prefix Constraints |
Prefix Feasibility |
Prefix Sum Addicts | Codeforces |
Easy |
Prefix-Feasibility | Greedy-Check | Prefix-Sum; Construction |
Greedy -> Prefix Constraints |
Prefix Monotonicity |
Keep it Beautiful | Codeforces |
Easy |
Stateful-Greedy | Greedy-Check | Binary-Array |
Greedy -> Prefix Constraints |
Prefix Trimming |
Remove Prefix | Codeforces |
Easy |
Prefix-Invariant | Greedy-Check | Construction |
Greedy -> Prefix Constraints |
Structured Prefix Cleanup |
Binary Removals | Codeforces |
Easy |
Prefix-Structure | Greedy-Check | Binary-String |
Math¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Math -> BSGS / Discrete Log |
Core |
Discrete Logarithm Mod | Library Checker |
Hard |
Discrete Logarithm | Math; Meet-In-The-Middle; Implementation | Discrete Log; Meet In The Middle; GCD Reduction |
Math -> BSGS / Discrete Log |
Stretch |
LibreOJ #6542 | LibreOJ |
Hard |
Discrete Logarithm | Math; Implementation | Template; Discrete Log |
Math -> Berlekamp-Massey / Kitamasa |
Core |
K-th Term of Linearly Recurrent Sequence | Library Checker |
Hard |
Linear Recurrence | Math; Algebra; Implementation | Characteristic Polynomial; K-Th Term |
Math -> Berlekamp-Massey / Kitamasa |
Stretch |
Find Linear Recurrence | Library Checker |
Hard |
Berlekamp-Massey, Linear Recurrence | Math; Algebra; Implementation | Minimal Recurrence; Sequence Recovery |
Math -> Chinese Remainder And Linear Congruences |
Core |
General Chinese Remainder | Kattis |
Medium |
Congruence Systems | Math; Implementation | Chinese Remainder Theorem; Extended Euclid; Non-Coprime Moduli |
Math -> Chinese Remainder And Linear Congruences |
Stretch |
System of Linear Congruence | Library Checker |
Medium |
Congruence Systems | Math; Implementation | Chinese Remainder Theorem; Linear Congruence; Extended Euclid |
Math -> Dirichlet Convolution / Prefix Sums Of Number-Theoretic Functions |
Core |
Sum of Divisors | CSES |
Medium |
Summatory Arithmetic Functions | Math; Implementation | Dirichlet Convolution; Sigma Function; Quotient Grouping; Harmonic Lemma |
Math -> Dirichlet Convolution / Prefix Sums Of Number-Theoretic Functions |
Stretch |
Totient sums | CSES |
Hard |
Summatory Arithmetic Functions | Math; Implementation | Totient; Prefix Sums; Quotient Grouping; Follow-Up |
Math -> FFT And NTT |
Core |
Convolution | AtCoder |
Easy |
Convolution, NTT, Polynomial Multiplication | Implementation; Math | Number Theoretic Transform; Acl |
Math -> FFT And NTT |
Core |
Convolution | Library Checker |
Easy-Medium |
Polynomial Multiplication, NTT | - | Convolution; 998244353 |
Math -> FFT And NTT |
Core |
Convolution Mod | Library Checker |
Medium |
Polynomial Multiplication, NTT | - | Mod Convolution; NTT-Friendly; Formal Power Series |
Math -> FFT And NTT |
Core |
Fast Fourier Transform | AtCoder |
Medium |
Convolution | Math; Implementation | Signal Processing |
Math -> FFT And NTT |
Stretch |
Divisor Set | Codeforces |
Hard |
Number Theory | Math; Divide-And-Conquer | Divisors |
Math -> FFT And NTT |
Stretch |
Function Sum | Codeforces |
Hard |
Combinatorics | Combinatorics; Math | Generating Functions |
Math -> FFT And NTT |
Stretch |
Substring Search | Codeforces |
Hard |
Strings | Strings; Convolution | Substring Matching; Bitmasks |
Math -> FFT And NTT |
Stretch |
Yet Another String Matching Problem | Codeforces |
Hard |
String-Matching | Strings; Convolution | Pattern Matching |
Math -> GCD And LCM |
Core |
Calculate GCD | AtCoder |
Easy |
Euclid | Implementation | GCD; Euclid |
Math -> GCD And LCM |
Core |
Greatest Common Divisor of N Integers | AtCoder |
Easy |
Euclid | Implementation | GCD; Reduce |
Math -> GCD And LCM |
Core |
Least Common Multiple of N Integers | AtCoder |
Easy |
Overflow-Safety | Implementation | LCM; GCD; Overflow |
Math -> GCD And LCM |
Core |
GCD and LCM | Kattis |
Easy-Medium |
- | - | GCD Formula; LCM Formula; Integer Arithmetic |
Math -> GCD And LCM |
Core |
GCD Pairs | Kattis |
Medium |
GCD Counting, Mobius | - | Pair Counting; Divisors; Coprime |
Math -> GCD And LCM |
Core |
GCD on Blackboard | AtCoder |
Medium |
Prefix/Suffix GCD | - | Remove-One; GCD Array; Prefix Suffix |
Math -> GCD And LCM |
Core |
Orac and LCM | Codeforces |
Medium |
Number Theory | Math; Implementation | GCD; LCM; Prime Exponents |
Math -> GCD And LCM |
Core |
GCD Harmony | Kattis |
Hard |
GCD Constraints, Optimization | - | GCD Reasoning; Integer Transform; Number Theory |
Math -> GCD And LCM |
Practice |
Common Divisors | CSES |
Medium |
Frequency-Ideas, Divisibility | Number Theory | GCD; Divisor Frequency; Maximum GCD; Frequency Over Divisors; Array GCD |
Math -> GCD And LCM |
Practice |
LCM on Whiteboard | AtCoder |
Medium |
Prime-Factorization | Number Theory; Implementation | LCM; Prime Exponents; Set Cover |
Math -> GCD And LCM |
Practice |
Large LCM | AtCoder |
Medium |
Overflow-Safety | Implementation; Math | LCM; Overflow; Large Integers |
Math -> Game Theory / Sprague-Grundy |
Core |
S-Nim | Kattis |
Medium |
Sprague-Grundy | Math; Implementation | Subtraction-Game; Nim-Sum |
Math -> Game Theory / Sprague-Grundy |
Stretch |
Nim Game II | CSES |
Medium |
Sprague-Grundy, Multi-Heap Games | Math; Observation | Nim-Sum; Pattern; Subtraction-Game |
Math -> Game Theory / Sprague-Grundy |
Challenge |
Dividing Game | AtCoder |
Hard |
Number Theory | Math; Observation | Sprague-Grundy; Prime-Factor-Count; Independent-Heaps |
Math -> Game Theory / Sprague-Grundy |
Bridge |
Stick Game | CSES |
Medium |
Single-Heap Games, Sprague-Grundy | Math; Dynamic Programming | Winning-Losing-DP; Subtraction-Game; Mex |
Math -> Gaussian Elimination And Linear Algebra |
Core |
System of Linear Equations | CSES |
Hard |
Linear Systems | Math; Implementation | Linear Algebra; Mod Prime; Free Variables |
Math -> Gaussian Elimination And Linear Algebra |
Stretch |
System of Linear Equations | Library Checker |
Hard |
Linear Systems | Math; Implementation | Affine Solution Space; Mod Prime |
Math -> Linear Recurrence And Matrix Exponentiation |
Core |
Fibonacci Numbers | CSES |
Medium |
Matrix/Recurrence | Math; Implementation | Matrix Exponentiation; Fibonacci; Fast Doubling Compare |
Math -> Linear Recurrence And Matrix Exponentiation |
Core |
Throwing Dice | CSES |
Medium |
DP/Recurrences | Dynamic Programming; Math | Matrix Exponentiation; Companion Matrix; Mod Arithmetic |
Math -> Linear Recurrence And Matrix Exponentiation |
Stretch |
Graph Paths I | CSES |
Hard |
Graphs/Walk Counting | Graphs; Math | Matrix Exponentiation; Adjacency Matrix; Walk Counting |
Math -> Lucas Theorem And Large Binomial Mod Prime |
Core |
Binomial Coefficient (Prime Mod) | Library Checker |
Medium |
Binomial Coefficients | Math; Implementation | Binomial Coefficient; Prime Modulus |
Math -> Lucas Theorem And Large Binomial Mod Prime |
Stretch |
Odd Binomial Coefficients | Kattis |
Hard |
Binomial Coefficients, Pascal Structure | Math; Observation | Parity; Bitwise Pattern |
Math -> Min_25 / Du Jiao |
Core |
Sum of Totient Function | Library Checker |
Hard |
Prefix Sums | Math; Implementation | Du Jiao Sieve; Euler Totient; Quotient Set; Dirichlet Convolution |
Math -> Min_25 / Du Jiao |
Stretch |
Totient sums | CSES |
Hard |
Prefix Sums | Math; Implementation | Totient; Quotient Set; Follow-Up |
Math -> Mobius And Multiplicative Counting |
Core |
Counting Coprime Pairs | CSES |
Medium |
Coprime Pair Counting | Math; Implementation | Mobius Function; Divisor Frequency; Coprime Pairs; Linear Sieve |
Math -> Modular Arithmetic |
Core |
Exponentiation | CSES |
Easy |
Fast-Exponentiation, Mod Arithmetic | Implementation; Math | Binary Exponentiation; Pow |
Math -> Modular Arithmetic |
Core |
Distributing Apples | CSES |
Easy-Medium |
Stars And Bars, Mod Arithmetic | - | Combinations; Distributions |
Math -> Modular Arithmetic |
Core |
Binomial Coefficients | CSES |
Medium |
Combinatorics/Counting-Basics, Mod Inverses, Combinatorics | Math; Precomputation | Ncr; Factorials; Modular Inverse; Inverse Factorials |
Math -> Modular Arithmetic |
Core |
Creating Strings II | CSES |
Medium |
Factorials, Mod Inverses | - | Multiset Permutations; Combinatorics; Mod Arithmetic |
Math -> Modular Arithmetic |
Core |
Exponentiation II | CSES |
Medium |
Fast-Exponentiation, Mod-Inverse, Totient Tricks | Implementation; Number Theory | Tower Exponentiation; Fermats-Little-Theorem; Mod Arithmetic; Phi |
Math -> Modular Arithmetic |
Stretch |
Counting Grids | CSES |
Hard |
Combinatorics/Bracelet-Counting | Combinatorics; Algebra | Burnside; Pólya Counting; Mod Arithmetic |
Math -> Modular Arithmetic |
Stretch |
Counting Necklaces | CSES |
Hard |
Combinatorics/Burnside | Combinatorics; Number Theory | Burnside; Group Actions; Mod Arithmetic |
Math -> Modular Arithmetic |
Stretch |
Graph Paths I | CSES |
Hard |
Matrix-Exponentiation | Graphs; Math | Graph Walks; Mod Arithmetic |
Math -> Modular Square Root / Discrete Root |
Core |
Sqrt Mod | Library Checker |
Hard |
Quadratic Residues | Math; Implementation | Modular Square Root; Tonelli-Shanks; Quadratic Residue; Prime Modulus |
Math -> Modular Square Root / Discrete Root |
Stretch |
K-th Root Mod | Library Checker |
Hard |
Discrete Root | Math; Implementation | Primitive Root; Bsgs; Linear Congruence In Exponents |
Math -> Number Theory Basics |
Core |
Calculate GCD | AtCoder |
Easy |
GCD/LCM | Implementation; Math | GCD; Euclid |
Math -> Number Theory Basics |
Core |
Divisor Enumeration | AtCoder |
Easy |
Divisors | Implementation; Math | Enumeration |
Math -> Number Theory Basics |
Core |
Factorization | AtCoder |
Easy |
Primes, Factorization | Implementation; Math | Prime Factorization; Trial Division |
Math -> Number Theory Basics |
Core |
Greatest Common Divisor of N Integers | AtCoder |
Easy |
GCD/LCM | Implementation; Math | GCD; Fold/Reduce |
Math -> Number Theory Basics |
Core |
Least Common Multiple of N Integers | AtCoder |
Easy |
GCD/LCM | Implementation; Math | LCM; GCD; Overflow Avoidance |
Math -> Number Theory Basics |
Core |
Primality Test | AtCoder |
Easy |
Primes | Implementation; Math | Primality; Trial Division |
Math -> Number Theory Basics |
Core |
Prime Multiples | CSES |
Medium |
Inclusion-Exclusion, Primes | - | Subset Enumeration; LCM; Counting Multiples |
Math -> Number Theory Basics |
Core |
Counting Coprime Pairs | CSES |
Medium-Hard |
Mobius Inversion, GCD | - | Coprime Pairs; Number Theory; Inclusion-Exclusion |
Math -> Number Theory Basics |
Practice |
Counting Divisors | CSES |
Easy |
Divisors, Factorization, Prime Factorization, Divisor Counting | Math; Implementation | Divisor-Count; Sieve; Tau(n) |
Math -> Number Theory Basics |
Practice |
Next Prime | CSES |
Easy-Medium |
Primes, Sieving, Primality Testing | Implementation; Number Theory | Prime Search; Miller-Rabin-Style Thinking; Next Prime; Miller-Rabin; Trial Division |
Math -> Number Theory Basics |
Practice |
Common Divisors | CSES |
Medium |
GCD/LCM, Frequency-Ideas | Number Theory; Sieving | GCD; Max-Frequency Divisor |
Math -> Number Theory Basics |
Practice |
Sum of Divisors | CSES |
Medium |
Divisors, Prefix-Sums, Divisor Sums, Arithmetical Functions | Math; Optimization | Sigma Function; Divisor Summatory Function; Sigma(n); Floor Division; Mod Arithmetic |
Math -> Number Theory Basics |
Stretch |
Divisor Analysis | CSES |
Medium |
Divisors, Modular-Arithmetic, Prime Factorization, Multiplicative Functions | Math; Precomputation | Number Of Divisors; Sum Of Divisors; Product Of Divisors |
Math -> Pollard-Rho |
Core |
Factorize | Library Checker |
Hard |
Integer Factorization | Math; Implementation | Miller-Rabin; Prime Factorization; 64-Bit |
Math -> Polynomial / Formal Power Series |
Core |
Inv of Formal Power Series | Library Checker |
Hard |
Formal Power Series, NTT | Implementation; Algebra | Inverse; Newton Iteration |
Math -> Polynomial / Formal Power Series |
Stretch |
Log of Formal Power Series | Library Checker |
Hard |
Formal Power Series, NTT | Implementation; Algebra | Logarithm; Derivative; Inverse |
Math -> Polynomial / Formal Power Series |
Challenge |
Exp of Formal Power Series | Library Checker |
Hard |
Formal Power Series, NTT | Implementation; Advanced Algebra | Exponential; Newton Iteration; Advanced |
Math -> Polynomial / Formal Power Series |
Challenge |
Pow of Formal Power Series | Library Checker |
Hard |
Formal Power Series, NTT | Implementation; Advanced Algebra | Power; Log-Exp; Advanced |
Math -> Primitive Root |
Core |
Primitive Root | Library Checker |
Hard |
- | Math; Implementation | Generator; Prime Modulus; Factorization |
Math -> Primitive Root |
Stretch |
K-th Root Mod | Library Checker |
Hard |
Discrete Root | Math; Implementation | Discrete Log; Linear Congruence In Exponents |
Math -> Probability |
Core |
Dice Probability | CSES |
Medium |
Distributions | Math; Dynamic Programming | Probability-DP; Pmf; Dice |
Math -> Probability |
Stretch |
Moving Robots | CSES |
Hard |
Random Walks | Math; State Transitions | Transition-Probability; Independence; Expectation |
Math -> Probability |
Challenge |
Inversion Probability | CSES |
Hard |
Expected Value | Math; Counting | Linearity-Of-Expectation; Pairs; Expectation |
Math -> Probability |
Bridge |
Candy Lottery | CSES |
Medium |
Expected Value | Math; Observation | Distribution-Of-Maximum; Independence |
Math -> XOR Basis / Linear Basis |
Core |
XMAX - XOR Maximization | SPOJ |
Medium |
Bitwise Algebra | Math; Implementation | Linear-Basis; Maximum-Subset-XOR |
Math -> XOR Basis / Linear Basis |
Stretch |
Shortest Path Problem? | Codeforces |
Hard |
Graphs/Cycle XOR, Bitwise Algebra | Graphs; Math | Cycle-Space; Path-XOR |
Math -> XOR Basis / Linear Basis |
Challenge |
ZC's School | Codeforces |
Hard |
Prefix XOR, Bitwise Algebra | Math; Observation | Dimension |
Combinatorics¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Combinatorics -> Bounded Compositions |
Core |
Coins | AtCoder |
Easy |
Coin-Change | Brute Force; Counting | Bounded Composition; Coin Sums |
Combinatorics -> Bounded Compositions |
Core |
Distributing Apples | CSES |
Easy-Medium |
Stars-And-Bars, Bounded Counting | Math; Combinatorics | Nonnegative Parts; Combinations |
Combinatorics -> Bounded Compositions |
Core |
M - Candies | AtCoder |
Medium |
Prefix DP | - | Upper Bounds; Children And Candies; DP |
Combinatorics -> Bounded Compositions |
Core |
D - Between Two Arrays | AtCoder |
Hard |
Prefix DP | - | Nondecreasing Arrays; Range Bounds; Mod 998244353 |
Combinatorics -> Bounded Compositions |
Practice |
How Many Ways? | AtCoder |
Medium |
Triple-Counting | Counting; Brute Force | Triples; Sum Constraint |
Combinatorics -> Bounded Compositions |
Practice |
Tak and Cards | AtCoder |
Medium |
Subset Sum | DP; Counting | Sum Constraints; Card Selection |
Combinatorics -> Burnside / Pólya / Group Actions |
Core |
Counting Necklaces | CSES |
Hard |
Group Actions, Orbit Counting | Combinatorics; Math | Necklaces; Rotations; Mod Arithmetic |
Combinatorics -> Burnside / Pólya / Group Actions |
Stretch |
Counting Grids | CSES |
Hard |
Rotation Symmetry | Combinatorics; Math | Grids; Quarter Turns; Mod Arithmetic |
Combinatorics -> Counting Basics |
Core |
Bit Strings | CSES |
Easy |
Basic Counting, Mod Arithmetic | - | Powers Of Two |
Combinatorics -> Counting Basics |
Core |
Choose Cards 1 | AtCoder |
Easy |
Pair-Counting | Implementation; Counting | Pairs |
Combinatorics -> Counting Basics |
Core |
Choose Cards 3 | AtCoder |
Easy |
Pair-Counting | Implementation; Counting | Two-Sum; Frequency Counting |
Combinatorics -> Counting Basics |
Core |
Combination Easy | AtCoder |
Easy |
Binomial-Coefficients | Math | Ncr |
Combinatorics -> Counting Basics |
Core |
Two Knights | CSES |
Easy |
- | - | Board Counting; Pair Counting; Formula |
Combinatorics -> Counting Basics |
Core |
Binomial Coefficients | CSES |
Medium |
Modular-Arithmetic | Math; Precomputation | Ncr; Factorials; Modular Inverse |
Combinatorics -> Counting Basics |
Core |
Choose Cards 2 | AtCoder |
Medium |
Subset-Counting | Search; Counting | Meet-In-The-Middle |
Combinatorics -> Counting Basics |
Core |
Creating Strings II | CSES |
Medium |
Multiset Permutations | Math; Precomputation | Factorials |
Combinatorics -> Counting Basics |
Core |
Two Sets II | CSES |
Medium |
DP | - | Partitions; Subset Sum; Mod Arithmetic |
Combinatorics -> Counting Basics |
Practice |
Christmas Party | CSES |
Medium |
Derangements | Combinatorics; DP | Derangements; Inclusion-Exclusion |
Combinatorics -> Counting Basics |
Practice |
Distributing Apples | CSES |
Medium |
Stars-And-Bars | Math; Combinatorics | Compositions; Combinations; Mod Arithmetic |
Combinatorics -> Counting Basics |
Stretch |
Counting Necklaces | CSES |
Hard |
Group-Actions | Combinatorics | Burnside; Pólya |
Combinatorics -> Counting Basics |
Stretch |
Counting Permutations | CSES |
Hard |
Permutation-Counting, Inclusion-Style Counting | DP; Combinatorics | Permutations; Adjacency Constraints; Adjacency Restriction; Beautiful Permutations |
Combinatorics -> Inclusion-Exclusion |
Core |
Christmas Party | CSES |
Medium |
Derangements | - | Fixed Points; Permutations; Mod Arithmetic |
Combinatorics -> Inclusion-Exclusion |
Core |
Prime Multiples | CSES |
Medium |
Number Theory, Subset Counting | Math; Enumeration | Multiples; Primes; Prime Set; LCM |
Combinatorics -> Inclusion-Exclusion |
Core |
Counting Coprime Pairs | CSES |
Medium-Hard |
Mobius, Mobius Inversion | Number Theory; Sieving | Coprime Pairs; GCD 1; Pair Counting; Number Theory |
Combinatorics -> Inclusion-Exclusion |
Practice |
Coprime | Codeforces |
Medium |
GCD | Number Theory; Greedy | Coprime; Number Theory |
Combinatorics -> Inclusion-Exclusion |
Stretch |
Coprime Subsequences | Codeforces |
Hard |
Mobius | Combinatorics; Number Theory | Subsequences; Number Theory |
Combinatorics -> Inclusion-Exclusion |
Cross-Topic |
Counting Necklaces | CSES |
Hard |
Burnside, Symmetry Counting | - | Orbit Counting; Pólya; Rotations |
Combinatorics -> Lexicographic Enumeration |
Core |
Count Order | AtCoder |
Easy |
Permutation Ranking | Math; Permutation | Permutations; Lexicographic Rank |
Combinatorics -> Lexicographic Enumeration |
Core |
Creating Strings | CSES |
Easy |
Multiset Permutations, Lexicographic Order | Backtracking; Enumeration | Duplicate Permutations; Generation; Sorting |
Combinatorics -> Lexicographic Enumeration |
Core |
C - One More aab aba baa | AtCoder |
Medium |
Multiset Permutations | - | K-Th Permutation; Duplicate Letters; Sorting |
Combinatorics -> Lexicographic Enumeration |
Core |
Permutation Order | CSES |
Medium |
Permutation Ranking, Lexicographic Order | Implementation; Math | K-Th Permutation; Factoradic; Inverse Permutation Order |
Combinatorics -> Lexicographic Enumeration |
Practice |
Creating Strings II | CSES |
Medium |
Multiset Permutations, Ranking And Counting, Lexicographic Combinatorics | Math; Precomputation | Counting Strings; Factorials; Mod Arithmetic |
Combinatorics -> Lexicographic Enumeration |
Stretch |
Lexicographically Smallest Permutation | AtCoder |
Hard |
Permutation-Cycles | Construction; Greedy | Lexicographic Order; Permutations; Cycle Decomposition |
Combinatorics -> Lexicographic Enumeration |
Stretch |
Reverse and Count | AtCoder |
Hard |
Permutation Ranking | Construction; Combinatorics | Lexicographic Order |
Strings¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Strings -> Aho-Corasick |
Core |
Finding Patterns | CSES |
Medium |
- | Offline Matching | Multi-Pattern Matching; Automata |
Strings -> Aho-Corasick |
Core |
String Multimatching | Kattis |
Medium |
Multi-Pattern-Matching | - | Text Scanning; Output-All |
Strings -> Aho-Corasick |
Core |
Word Combinations | CSES |
Medium |
DP | - | Dictionary; Segmentation; Prefix-Automaton |
Strings -> Aho-Corasick |
Core |
aho_corasick | Library Checker |
Medium |
Multi-Pattern-Matching | - | Failure Links; Dictionary |
Strings -> Aho-Corasick |
Core |
Counting Patterns | CSES |
Hard |
- | Aggregation; Offline Matching | Multi-Pattern Matching; Counting |
Strings -> Aho-Corasick |
Core |
Pattern Positions | CSES |
Hard |
Trie | Offline Matching | Multi-Pattern Matching; First Occurrence; Many-Patterns; Text-Search |
Strings -> Aho-Corasick |
Challenge |
Genetic engineering | Codeforces |
Hard |
- | DP On Automaton; Pattern Exclusion | DP; Automata |
Strings -> Eertree / Palindromic Tree |
Core |
Palindromes and Super Abilities | Timus |
Medium |
Distinct Palindromes | Online Append; Data Structure; Per-Prefix Counting | Palindromic Tree; Append-Only String; Per-Prefix Output |
Strings -> Eertree / Palindromic Tree |
Practice |
eertree | Library Checker |
Medium |
- | Verification; Construction | Palindromic Tree; Construction |
Strings -> Eertree / Palindromic Tree |
Stretch |
Palindromic characteristics | Codeforces |
Hard |
DP | DP; Palindrome Structure | Palindrome; Distinct Structure |
Strings -> Hashing |
Core |
String Hashing | Kattis |
Easy |
Rolling Hash, Substring Comparison | - | LCS; Equality |
Strings -> Hashing |
Core |
Good Substrings | Codeforces |
Medium |
Distinct Substrings | Enumeration; Deduplication | Trie; Substrings; Hash Or Trie |
Strings -> Hashing |
Core |
Watto and Mechanism | Codeforces |
Medium |
Dictionary Matching | - | One-Change; String-Lookup; Collision-Safe |
Strings -> Hashing |
Core |
rolling_hash | Library Checker |
Medium |
Rolling Hash | - | Substring Comparison |
Strings -> Hashing |
Core |
Palindrome Queries | CSES |
Hard |
Rolling Hash, Dynamic Queries | Data-Structure-Heavy; Offline/Online Hybrid | Palindrome; Range Queries; Substring-Equality; Updates |
Strings -> Hashing |
Challenge |
"a" String Problem | Codeforces |
Hard |
- | Query Processing; Invariant Maintenance | Suffix Structures |
Strings -> Hashing |
Challenge |
String Set Queries | Codeforces |
Hard |
- | Online; Dynamic Data Structures | Online Queries; String Sets |
Strings -> KMP |
Core |
Finding Borders | CSES |
Easy |
Borders | Proof; Implementation | Prefix-Suffix; Periods; Prefix-Function |
Strings -> KMP |
Core |
String Functions | CSES |
Easy |
Z-Function | Implementation | Prefix-Function; Z-Array; Pi-Array |
Strings -> KMP |
Core |
String Matching | CSES |
Easy |
Pattern-Matching | Implementation | Prefix-Function; Single-Pattern; Occurrences |
Strings -> KMP |
Core |
Finding Periods | CSES |
Medium |
Periodicity | Implementation; Pattern Analysis | Prefix-Function; Periods; String-Structure |
Strings -> KMP |
Core |
Required Substring | CSES |
Medium |
Automaton-DP | - | DP; Forbidden-States; Substring-Automaton |
Strings -> Palindromes / Manacher |
Core |
Enumerate Palindromes | Library Checker |
Medium |
Manacher, Palindrome Radii | Implementation; Verification | Odd-Even Centers; Radius Arrays |
Strings -> Palindromes / Manacher |
Core |
Longest Palindrome | CSES |
Medium |
Manacher | Implementation; Static Scan | Longest Palindromic Substring; Odd-Even Centers; Exact Scan |
Strings -> Palindromes / Manacher |
Challenge |
All Palindromes | CSES |
Hard |
Manacher, Palindrome Radii | Implementation; Output Transformation | Per-Position Output; Static String |
Strings -> Regular Expressions / Finite Automata |
Core |
Regex Membership Benchmark | Algorithms 4/e |
Medium |
Regular-Expressions, Finite-Automata | Automaton Construction; Simulation | Thompson Nfa; Epsilon Closure; Regex Membership |
Strings -> Suffix Array And LCP |
Core |
Distinct Substrings | CSES |
Medium |
Suffix-Array | Counting; Suffix Processing | Distinct Substrings; Counting; Suffix-Structure |
Strings -> Suffix Array And LCP |
Core |
Repeating Substring | CSES |
Medium |
Suffix-Array | Maximization; Substring Search | Repetition; Longest-Repeat; Binary-Search; Suffix-Structure |
Strings -> Suffix Array And LCP |
Core |
lcp_array | Library Checker |
Medium |
Suffix-Array | - | Kasai; Adjacent-Suffixes |
Strings -> Suffix Array And LCP |
Core |
longest_common_substring | Library Checker |
Medium |
Suffix-Array | - | Two-Strings; Common-Substring |
Strings -> Suffix Array And LCP |
Core |
suffix_array | Library Checker |
Medium |
Suffix-Array, String-Indexing | - | Lexicographic-Order; Core |
Strings -> Suffix Array And LCP |
Challenge |
Inverse Suffix Array | CSES |
Hard |
- | Construction; Consistency Checking | Suffix Array; Construction; Inverse Problems |
Strings -> Suffix Array And LCP |
Challenge |
String Transform | CSES |
Hard |
- | Construction; Inverse Transform | Suffix Array; Burrows-Wheeler Transform; Reconstruction |
Strings -> Suffix Array And LCP |
Challenge |
Substring Order I | CSES |
Hard |
Suffix-Array, Lexicographic-Order | K-Th Selection; Suffix Processing | Order Statistics; Kth-Substring; Ranking |
Strings -> Suffix Array And LCP |
Challenge |
Substring Order II | CSES |
Hard |
- | K-Th Selection; Suffix Processing | Suffix Array; Order Statistics |
Strings -> Suffix Automaton |
Core |
Distinct Substrings | CSES |
Medium |
Counting | - | Substrings; States; Endpos |
Strings -> Suffix Automaton |
Core |
Good Substrings | Codeforces |
Medium |
- | Enumeration; Deduplication | Distinct Substrings; Trie |
Strings -> Suffix Automaton |
Core |
Repeating Substring | CSES |
Medium |
Longest-Repeat | - | Repeat; Substring; Suffix-Structure |
Strings -> Suffix Automaton |
Core |
suffix_automaton | Library Checker |
Medium |
String-Indexing | - | States; Transitions |
Strings -> Suffix Automaton |
Core |
Substring Order I | CSES |
Hard |
Kth-Substring | - | Ranking; Distinct-Substrings; Advanced |
Strings -> Suffix Automaton |
Challenge |
A Trivial String Problem | Codeforces |
Hard |
- | Query Processing; Hybrid Techniques | Hashing |
Strings -> Suffix Automaton |
Challenge |
Cyclical Quest | Codeforces |
Hard |
- | String Compression; Counting | Cyclic Strings; Counting |
Strings -> Suffix Automaton |
Challenge |
Martian Strings | Codeforces |
Hard |
- | Multi-Pattern Checking | Substring Queries; Pattern Matching |
Strings -> Suffix Tree |
Core |
Pattern Positions | CSES |
Hard |
Substring-Index | Many Queries; Suffix Processing | Earliest Occurrence; Pattern Matching |
Strings -> Suffix Tree |
Stretch |
Distinct Substrings | CSES |
Medium |
- | Counting; Suffix Processing | Distinct Substrings; Compressed Edges |
Strings -> Trie |
Core |
Watto and Mechanism | Codeforces |
Medium |
Hashing | Implementation; Branching Search | Approximate Matching; One-Edit; Dictionary; Lookup |
Strings -> Trie |
Core |
Word Combinations | CSES |
Medium |
DP | Dynamic Programming; Data-Structure-Heavy | Dictionary Matching; Dictionary; Prefixes; Counting |
Strings -> Trie |
Core |
trie | Library Checker |
Medium |
Data-Structure | - | Insert; Lookup |
Strings -> Trie |
Challenge |
A Lot of Games | Codeforces |
Hard |
Game-Theory | Game-State Analysis | Games; Winning-States; Game-DP; Prefix-Tree |
Strings -> Z-Function |
Core |
String Functions | CSES |
Easy |
Prefix-Function | Implementation | String Processing; Z-Array; Pi-Array; Fundamentals |
Strings -> Z-Function |
Core |
String Matching | CSES |
Easy |
Pattern-Matching | Implementation | Linear-Time String Algorithms; Single-Pattern; Occurrences; Linear-Time |
Strings -> Z-Function |
Core |
Finding Periods | CSES |
Medium |
Periodicity | Proof; Implementation | Borders; Periods; Prefix-Structure; String-Analysis |
Strings -> Z-Function |
Core |
Password | Codeforces |
Medium |
Borders | - | Prefix-Suffix; Longest-Border; Classic |
Strings -> Z-Function |
Core |
Prefixes and Suffixes | Codeforces |
Medium |
Border-Enumeration | - | Prefixes; Suffixes; Counts |
Geometry¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Geometry -> Convex Hull |
Core |
Convex Hull | CSES |
Medium |
Sorting | Sorting; Stack/Scan | Orientation; Monotone-Chain; Boundary |
Geometry -> Convex Hull |
Core |
Convex Hull Extension | Codeforces Gym |
Hard |
Extension | - | Hull-Expansion; Distance; Construction |
Geometry -> Convex Hull |
Core |
Polygons | Codeforces |
Hard |
Containment | - | Strictly-Convex; Inside-Test; Polygon |
Geometry -> Convex Hull |
Core |
U2 | Codeforces |
Hard |
- | - | Parabolas; Upper-Hull; Counting |
Geometry -> Convex Hull |
Challenge |
Maximum Manhattan Distances | CSES |
Hard |
- | Extreme-Point Reasoning | Manhattan Distance; Transformations |
Geometry -> Convex Hull |
Challenge |
Minimum Euclidean Distance | CSES |
Hard |
- | Divide-And-Conquer; Sweep-Line | Closest Pair; Sweep Line; Plane Geometry |
Geometry -> Counting Geometry |
Core |
Polygon Lattice Points | CSES |
Medium |
- | Counting | Lattice Points; Pick's Theorem |
Geometry -> Counting Geometry |
Core |
Right Triangles | Codeforces |
Medium |
- | Combinatorics | Grid Geometry; Right Triangles |
Geometry -> Counting Geometry |
Core |
Satyam and Counting | Codeforces |
Hard |
Triangles | - | Points; Right-Triangles; Combinatorics |
Geometry -> Counting Geometry |
Core |
Triangles 3000 | Codeforces |
Very Hard |
Lines | - | Intersections; Triangle-Counting; Arrangements |
Geometry -> Counting Geometry |
Challenge |
Area of Rectangles | CSES |
Hard |
Union-Area | Coordinate Compression | Area Union; Sweep Line; Measure; Events; Rectangle-Union |
Geometry -> Counting Geometry |
Challenge |
Intersection Points | CSES |
Hard |
Sweep-Line | Event Counting | Intersection Counting; Orthogonal-Segments; Events; Counts |
Geometry -> Half-Plane Intersection |
Core |
Big Brother | Kattis |
Medium |
Polygon-Kernel | Geometry; Implementation | Directed Lines; Continuous Geometry; Deque |
Geometry -> Minkowski Sum |
Stretch |
Mogohu-Rea Idol | Codeforces |
Very Hard |
Point-In-Convex | Geometry; Modeling; Implementation | Convex Polygon; Repeated Sum; Point Query; Center Of Mass |
Geometry -> Nearest Pair of Points |
Core |
Closest Pair | AOJ |
Medium |
Sweep-Line | Geometry; Implementation | Closest Pair; Active Strip; Euclidean Distance; Ordered Set |
Geometry -> Nearest Pair of Points |
Challenge |
Minimum Euclidean Distance | CSES |
Hard |
- | Implementation; Sweep-Line | Closest Pair; Sweep Line; Squared Distance; Plane Geometry |
Geometry -> Polygon Area And Point Location |
Core |
Point Location Test | CSES |
Easy |
Point-Location, Orientation | Implementation | Cross-Product; Relative-Position |
Geometry -> Polygon Area And Point Location |
Core |
Polygon Area | CSES |
Easy |
Polygon-Area, Shoelace | Formula Derivation | Shoelace Formula; Signed-Area; Cross-Product; Simple-Polygon |
Geometry -> Polygon Area And Point Location |
Core |
Point in Polygon | CSES |
Medium |
Point-Location | Parity Counting | Ray Casting; Orientation; Inside-Outside |
Geometry -> Polygon Area And Point Location |
Core |
Polygon Lattice Points | CSES |
Medium |
Polygon-Area, Lattice-Points | Counting | Pick's Theorem; Pick-Theorem; Boundary; Interior |
Geometry -> Right Triangles |
Core |
Triangle | Codeforces |
Easy |
Classification | - | Distance-Checks; Integer-Grid; Right-Angle |
Geometry -> Right Triangles |
Core |
Pythagorean Triples | Codeforces |
Medium |
Number Theory | - | Integer-Sides; Construction; Pythagorean |
Geometry -> Right Triangles |
Core |
Right Triangles | Codeforces |
Medium |
Grid-Counting | Counting | Combinatorics; Orthogonal; Stars-Grid |
Geometry -> Right Triangles |
Core |
Triangle | Codeforces |
Medium |
Construction | - | Integer-Coordinates; Existence; Coordinate-Geometry |
Geometry -> Right Triangles |
Challenge |
Lovely Perfect Right Triangles | Codeforces Gym |
Hard |
- | Enumeration; Number Theoretic Filtering | Number Theory; Counting |
Geometry -> Segment Intersection |
Core |
Line Segment Intersection | CSES |
Medium |
Orientation | Case Analysis | Robust Geometry; Ccw; Overlap; Touching |
Geometry -> Segment Intersection |
Core |
Line Segments Trace I | CSES |
Medium |
Sweep-Line | - | Envelope; Max-Point; Scan |
Geometry -> Segment Intersection |
Core |
Line Segments Trace II | CSES |
Hard |
Sweep-Line | - | Envelope; Comparisons; Scan |
Geometry -> Segment Intersection |
Challenge |
Area of Rectangles | CSES |
Hard |
- | Sweep-Line; Coordinate Compression | Sweep Line; Interval Coverage; Rectangles |
Geometry -> Segment Intersection |
Challenge |
Intersection Points | CSES |
Hard |
Sweep-Line, Intersection-Counting | Sweep-Line | Orthogonal Segments; Horizontal-Vertical; Events; Count |
Geometry -> Sweep Line |
Core |
Line Segments Trace I | CSES |
Medium |
Envelope | - | Scan; Max-Query; Segments |
Geometry -> Sweep Line |
Core |
Line Segments Trace II | CSES |
Hard |
Envelope | - | Scan; Events; Segments |
Geometry -> Sweep Line |
Challenge |
Area of Rectangles | CSES |
Hard |
Area-Union | Coordinate Compression | Rectangle Union; Events; Coordinate-Compression; Rectangles |
Geometry -> Sweep Line |
Challenge |
Intersection Points | CSES |
Hard |
Intersection-Counting | Event Sorting | Orthogonal Segments; Intersections; Events; Active-Set |
Geometry -> Sweep Line |
Challenge |
Lines and Queries I | CSES |
Hard |
- | Online; Data-Structure-Heavy | Line Containers; Optimization |
Geometry -> Sweep Line |
Challenge |
Minimum Euclidean Distance | CSES |
Hard |
- | Divide-And-Conquer; Sweep-Line | Closest Pair |
Geometry -> Vector And Orientation |
Core |
Point Location Test | CSES |
Easy |
- | Implementation | Cross Product; Half-Plane; Left-Right; Point-In-Sector |
Geometry -> Vector And Orientation |
Core |
Polygon Area | CSES |
Easy |
Shoelace | Formula Derivation | Shoelace Formula; Area; Signed-Area; Cross-Product; Polygon |
Geometry -> Vector And Orientation |
Core |
Triangle | Codeforces |
Easy |
Triangle-Classification | - | Right-Angle; Integer-Coordinates; Bruteforce |
Geometry -> Vector And Orientation |
Core |
Line Segment Intersection | CSES |
Medium |
Segment-Geometry | Case Analysis | Segment Intersection; Cross Product; Ccw; Intersection |
Geometry -> Vector And Orientation |
Core |
Triangle | Codeforces |
Medium |
Construction | - | Integer-Points; Right-Triangle; Existence |
Advanced¶
| Topic | Bucket | Problem | Source | Difficulty | Context | Style | Tags |
|---|---|---|---|---|---|---|---|
Advanced -> Algorithm Engineering |
Core |
Robot Path | CSES |
Medium |
- | Implementation | Hashing; Simulation; Sets |
Advanced -> Algorithm Engineering |
Core |
Dynamic Values And Maximum Sum | Codeforces |
Very Hard |
- | - | Tree Process; State Transitions |
Advanced -> Algorithm Engineering |
Core |
Juan's Colorful Tree | Codeforces |
Very Hard |
- | - | Tree Queries; Set Intersections; Hybrid Techniques |
Advanced -> Algorithm Engineering |
Core |
Minimum Difference | Codeforces |
Very Hard |
- | - | Data Structures; Query Optimization; Implementation Detail |
Advanced -> Algorithm Engineering |
Core |
Query Jungle | Codeforces |
Very Hard |
- | - | Tree Queries; Toggle Updates; Global State Maintenance |
Advanced -> Algorithm Engineering |
Challenge |
Area of Rectangles | CSES |
Hard |
- | Engineering; Event Processing | Coordinate Compression; Sweep Line; Interval Coverage |
Advanced -> Algorithm Engineering |
Challenge |
Lines and Queries I | CSES |
Hard |
- | Online; Optimized Query Processing | Convex Hull Trick; Data Structures |
Advanced -> Algorithm Engineering |
Challenge |
Minimum Euclidean Distance | CSES |
Hard |
- | Performance Tuning; Geometric Data Structures | Implementation; Sweep Line; Closest Pair |
Advanced -> Approximation And Relaxation |
Core |
Problem Set 1 | Dartmouth EO249 |
Theory |
Approximation Algorithms | - | TSP; Cycle Cover; Euler Tour |
Advanced -> Approximation And Relaxation |
Core |
Problem Set 2 | Dartmouth EO249 |
Theory |
Approximation Algorithms | - | Set Cover; Submodular; Greedy Approximation |
Advanced -> Approximation And Relaxation |
Core |
Problem Set 4 | Dartmouth EO249 |
Theory |
Approximation Algorithms | - | Facility Location; Integrality Gap; LP Relaxation |
Advanced -> Approximation And Relaxation |
Core |
Problem Set 5 | Dartmouth EO249 |
Theory |
Approximation Algorithms | - | Knapsack PTAS; Iterated Rounding; Laminar Families |
Advanced -> Approximation And Relaxation |
Core |
Problem Set 6 | Dartmouth CS 49/149 |
Theory |
Approximation Algorithms | - | Duality; Randomized Rounding; LP |
Advanced -> Complexity And Hardness |
Core |
Problem Set 0 | Harvard CS221 |
Theory |
- | - | Search Vs Decision; Reductions; Complexity Classes |
Advanced -> Complexity And Hardness |
Core |
Problem Set 1 | Harvard CS221 |
Theory |
- | - | P-Completeness; Circuit Complexity; Factoring |
Advanced -> Complexity And Hardness |
Core |
Problem Set 3 | Harvard CS221 |
Theory |
- | - | PSPACE; Branching Programs; Circuit Lower Bounds |
Advanced -> Complexity And Hardness |
Core |
Problem Set 4 | Harvard CS221 |
Theory |
- | - | Promise Problems; #P; Approximation Hardness |
Advanced -> Complexity And Hardness |
Core |
Problem Set 6 | Harvard CS221 |
Theory |
- | - | PCP; Property Testing; Hardness Of Approximation |
Advanced -> Constructive |
Core |
Same Parity Summands | Codeforces |
Easy |
- | Construction | Math |
Advanced -> Constructive |
Core |
Snow Walking Robot | Codeforces |
Easy |
- | Path Construction | Paths; Grid |
Advanced -> Constructive |
Core |
A-B Palindrome | Codeforces |
Medium |
- | Construction | Palindrome |
Advanced -> Constructive |
Core |
Build the Permutation | Codeforces |
Medium |
- | Greedy Construction | Permutations |
Advanced -> Constructive |
Core |
Corrupted Array | Codeforces |
Medium |
- | Reconstruction | Arrays |
Advanced -> Constructive |
Core |
Beautiful Tree | Codeforces |
Hard |
- | - | Tree Construction; Number Theory; Perfect Square |
Advanced -> Constructive |
Core |
Multiples and Power Differences | Codeforces |
Hard |
- | - | Matrix Construction; Number Theory; Invariants |
Advanced -> Constructive |
Core |
Nezzar and Nice Beatmap | Codeforces |
Hard |
- | - | Ordering; Geometry; Greedy Construction |
Advanced -> Constructive |
Core |
Strange Housing | Codeforces |
Hard |
- | - | Graph Construction; DFS |
Advanced -> Constructive |
Core |
Cycle Closing | Codeforces |
Very Hard |
- | - | Graph Operations; Shortest Paths; Tree Structure |
Advanced -> Contest Engineering |
Core |
Hidden Integer | CSES |
Easy-Medium |
Interactive | - | Binary Search; Query Budget; Flushing |
Advanced -> Contest Engineering |
Core |
Colored Chairs | CSES |
Medium |
Interactive | - | Parity; Binary Search; Query Budget |
Advanced -> Contest Engineering |
Core |
Hidden Permutation | CSES |
Medium |
Interactive | - | Comparison Oracle; Reconstruction; Query Strategy |
Advanced -> Contest Engineering |
Core |
K-th Highest Score | CSES |
Medium |
Interactive | - | Merge Logic; Query Strategy; Two Sorted Sources |
Advanced -> Contest Engineering |
Core |
Permuted Binary Strings | CSES |
Medium |
Interactive | - | Bit Probing; Reconstruction; Query Design |
Advanced -> Contest Engineering |
Core |
Inversion Sorting | CSES |
Hard |
Interactive | - | Sorting By Feedback; Adaptive Strategy; Interaction Protocol |
Advanced -> Gradient Descent |
Core |
Linear Regression Gradient Descent Benchmark | Stanford CS229 |
Theory |
Smooth Optimization | Theory Benchmark; Deterministic Update Rule | Linear Regression; Squared Loss; Learning Rate |
Advanced -> Gradient Descent |
Stretch |
Gradient descent | MIT Open Learning Library |
Theory |
Further Theory | Course Notes; Theory Breadth | Convexity; Step Size; Convergence; Optimization |
Advanced -> Machine Learning Algorithms |
Core |
Perceptron Classification Benchmark | Stanford CS229 |
Theory |
Machine Learning, Perceptron | Theory Benchmark; Online Update Rule | Binary Classification; Linear Separability; Mistake-Driven Update |
Advanced -> Machine Learning Algorithms |
Stretch |
Perceptron, convergence, and generalization | MIT OCW 6.867 |
Theory |
Machine Learning, Margins | Lecture Notes; Theory Breadth | Perceptron; Convergence; Generalization |
Advanced -> Matroid Intersection |
Core |
Pick Your Own Nim | Codeforces Gym |
Very Hard |
Optimization | Modeling; Augmenting Path; Theory-Heavy | Partition Matroid; Linear Matroid; XOR Basis |
Advanced -> Meet-In-The-Middle |
Core |
Meet in the Middle | CSES |
Medium-Hard |
Mitm | Exact Search; Sort-And-Merge | Subset-Sum; Counting |
Advanced -> Meet-In-The-Middle |
Core |
Programming Contest | AtCoder |
Medium-Hard |
Mitm | Exact Search; Optimization | Best-Feasible-Sum; Binary Search |
Advanced -> Meet-In-The-Middle |
Classics |
SUBSUMS | SPOJ |
Medium-Hard |
Mitm | Exact Search; Counting | Subset-Sum; Range Counting |
Advanced -> Online Algorithms |
Core |
Ski Rental Benchmark | JHU Intro Algorithms |
Theory |
Competitive Analysis | Competitive Analysis; Theory Benchmark | Ski Rental; Competitive Ratio; Threshold Policy; Adversarial Future |
Advanced -> Online Algorithms |
Stretch |
Online Algorithms Notes: Ski Rental and Paging | Stanford CS369 |
Theory |
Paging, Randomized Compare | Lecture Notes; Theory Breadth | Competitive Ratio; Randomized Adversary; List Update |
Advanced -> Optimization And Duality |
Core |
Giant Pizza | CSES |
Medium |
- | Logical Modeling | 2-SAT; Constraint Satisfaction |
Advanced -> Optimization And Duality |
Core |
Police Chase | CSES |
Medium |
- | - | Minimum Cut; Certificate; Flow Dual |
Advanced -> Optimization And Duality |
Core |
School Dance | CSES |
Medium |
- | Augmenting Paths | Matching; Bipartite Graphs; Flow; Bipartite Graph |
Advanced -> Optimization And Duality |
Core |
Distinct Routes | CSES |
Hard |
- | - | Edge-Disjoint Paths; Flow Decomposition; Packing |
Advanced -> Optimization And Duality |
Challenge |
Download Speed | CSES |
Hard |
- | Flow Modeling | Max Flow; Min Cut; Network Optimization; Duality Intuition |
Advanced -> Optimization And Duality |
Challenge |
Task Assignment | CSES |
Hard |
- | Exact Optimization | Assignment; Min-Cost Optimization; Min-Cost Flow; Bipartite Optimization |
Advanced -> Parallel Algorithms |
Core |
Parallel Prefix Sum Benchmark | CMU / Blelloch |
Theory |
Scan | Theory Benchmark; Simulator | Prefix Sum; Blelloch Scan; Work Span; Pram |
Advanced -> Parallel Algorithms |
Stretch |
Parallel algorithms notes: Brent and work-efficient scan | MIT 6.854 |
Theory |
Further Theory | Lecture Notes; Theory Breadth | Brent's Theorem; Work Efficient; Pram; Parallel Prefix |
Advanced -> Quantum Algorithms |
Core |
Deutsch-Jozsa Oracle Benchmark | MIT OCW 6.845 |
Theory |
Promise Problems | Theory Benchmark; Simulator | Deutsch-Jozsa; Phase Oracle; Hadamard; Constant Vs Balanced |
Advanced -> Quantum Algorithms |
Stretch |
Quantum computation notes | Waterloo |
Theory |
Further Theory | Lecture Notes; Theory Breadth | Grover; Shor; Quantum States; Amplitudes |
Advanced -> Randomized Algorithms |
Core |
Problem Set 1 | UT Austin CS388R |
Theory |
- | - | Min-Cut; Sampling; Expected Complexity |
Advanced -> Randomized Algorithms |
Challenge |
Problem with Random Tests | Codeforces |
Hard |
- | Probabilistic Reasoning | Probability; Adversarial Tests |
Advanced -> Randomized Algorithms |
Challenge |
Wizards and Huge Prize | Codeforces |
Hard |
- | Probabilistic Model | Probability; Randomization; Expected Value |
Advanced -> Randomized Algorithms |
Challenge |
Gosha is hunting | Codeforces |
Very Hard |
- | Stochastic Analysis | Probability; Randomization; Expected Value |
Advanced -> Randomized Algorithms |
Challenge |
Isaac's Queries | Codeforces |
Very Hard |
- | Interactive Reasoning | Probability; Interactive |
Advanced -> Randomized Algorithms |
Cross-Topic |
Journey | Codeforces |
Medium |
Tree Expectation, Expected Value | DFS Expectation | Tree DFS; Probability |
Advanced -> Randomized Algorithms |
Cross-Topic |
Control of Randomness | Codeforces |
Hard |
Probability On Trees, Tree DP | Tree DP; Case Analysis | Probability; Expected Process |
Advanced -> Randomized Algorithms |
Cross-Topic |
I Love Balls | Codeforces |
Hard |
Probability DP, Expected Value | State Expectation | Game Process |
Advanced -> Randomized Algorithms |
Cross-Topic |
Expected Value Again | Codeforces |
Very Hard |
Combinatorial Expectation, Expected Value | Counting; Expectation Analysis | Combinatorics |
Advanced -> Simplex |
Core |
Cheese, If You Please | Kattis |
Medium-Hard |
Optimization, Linear Programming | Modeling; Floating Point | Continuous Optimization; Resource Allocation; Blending |
Advanced -> Simplex |
Challenge |
Road Times | ICPC World Finals |
Very Hard |
Optimization, Linear Programming | Modeling; Theory-Heavy | LP Modeling; Shortest Paths; Challenge |
Maintenance¶
Regenerate the catalog and topic maps with:
python3 scripts/generate_problem_catalog.py