Skip to content

YouKn0wWho Academy — The Ultimate Topic List (Full Topic Map)

Source / attribution: The Ultimate Topic List by YouKn0wWho (Shahjalal Shohag). Structure extracted from the author's official open-source export ShahjalalShohag/the-ultimate-topic-list (MIT License, data exported from the same database as the live site; static mirror: the-ultimate-topic-list.vercel.app). Templates come from ShahjalalShohag/code-library.

This file contains roadmap structure and official links only — topic names, IDs, difficulty/importance ratings, prerequisites, resource links, template links, and problem links. No explanations, editorials, or problem statements are reproduced. Use the topic page links for the actual content.

Generated: 2026-06-05 · Data export: 2025-09-28 · Live site currently reports 576 topics; this export contains 570 (delta: Number Theory +2, Combinatorics +1, Math +1, Miscellaneous +2 on the live site). Re-sync from the live site for the newest additions.

How to read this map

  • Hierarchy: Category → Subcategory → Topic. The order is the author's recommended learning order — earlier items are the implied prerequisites of later ones. Explicit Prerequisites are listed only where the author defined them.
  • Topic page: every topic links to https://youkn0wwho.academy/topic-list/<topic_id> (resources, starred picks, and the problem list live there).
  • Difficulty: Very Easy · Easy · Medium · Hard · Very Hard (author's rating).
  • Importance: ★★★ must-know · ★★☆ good-to-know · ★☆☆ rare/optional.
  • Phase: the author's learning-path phase number (lower = earlier), where defined.
  • ★ on a resource/problem: starred (recommended) by the author.
  • Problem difficulty tag [VE/E/M/H/VH]: author's per-problem rating where it parses to the 0–4 scale, [—] otherwise.

Contents

  1. Basics — 19 subcategories, 56 topics
  2. Data Structures (DS) — 18 subcategories, 82 topics
  3. Graph Theory — 21 subcategories, 103 topics
  4. Number Theory — 9 subcategories, 57 topics
  5. Combinatorics — 7 subcategories, 24 topics
  6. Math — 10 subcategories, 79 topics
  7. Strings — 7 subcategories, 31 topics
  8. Dynamic Programming (DP) — 10 subcategories, 35 topics
  9. Game Theory — 4 subcategories, 7 topics
  10. Geometry — 10 subcategories, 55 topics
  11. Miscellaneous — 11 subcategories, 41 topics

1. Basics

Category ID: basics · Subcategories: 19 · Topics: 56

1.1 Intro to Programming

Subcategory ID: intro_to_programming · Topics: 1

1.1.1 What is Programming?

1.2 Learn a Language

Subcategory ID: learning_a_language · Topics: 10

1.2.1 Intro to C++ and Setting up the Environment

1.2.2 Data Types, Variables and Input Output

1.2.3 Operators

1.2.4 Conditional Statements

1.2.5 Loops

1.2.6 Functions

1.2.7 Arrays

1.2.8 Strings

1.2.9 Pointers and References

1.2.10 Structures

1.3 Intro to Competitive Programming

Subcategory ID: intro_to_cp · Topics: 1

1.3.1 What is Competitive Programming?

1.4 Bitwise Thinking

Subcategory ID: bitwise_thinking · Topics: 1

1.4.1 Bitwise Operations and Bitmasks

1.5 Complexity Analysis

Subcategory ID: complexity_analysis · Topics: 2

1.5.1 Big O Notation and Time and Space Complexity Analysis

1.5.2 Fast Input Output

1.6 Recursion

Subcategory ID: recursion · Topics: 1

1.6.1 Recursion

1.7 Very Basic Math

Subcategory ID: very_basic_math · Topics: 3

1.7.1 Divisors

1.7.2 GCD and LCM

1.7.3 Harmonic Number

1.8 Range Queries Without Updates

Subcategory ID: range_queries_without_updates · Topics: 2

1.8.1 Prefix Sum

1.8.2 Prefix XOR

1.9 Standard Template Library (STL)

Subcategory ID: stl · Topics: 11

1.9.1 Intro to STL, Containers and Iterators

1.9.2 Pairs and Tuples

1.9.3 Vector

1.9.4 Stack

1.9.5 Queue

1.9.6 Priority Queue

1.9.7 Deque

1.9.8 Set, Unordered Set and Multiset

1.9.9 Map and Unordered Map

1.9.10 Bitset

1.9.11 List / Linked List

1.10 Leveraging Monotonicity

Subcategory ID: leveraging_monotonicity · Topics: 2

1.10.2 Two Pointers

1.11 Basic Sorting Algorithms

Subcategory ID: basic_sorting_algorithms · Topics: 8

1.11.1 Bubble Sort

1.11.2 Selection Sort

1.11.3 Insertion Sort

1.11.4 Counting Sort

1.11.5 Merge Sort

1.11.6 Quick Sort

1.11.7 Radix Sort

1.11.8 C++ STL Sort and Custom Comparator

1.12 Divide and Conquer

Subcategory ID: divide_and_conquer · Topics: 1

1.12.1 Divide and Conquer

1.13 Greedy and Constructive

Subcategory ID: greedy_and_constructive · Topics: 2

1.13.1 Basic Greedy Algorithms

1.13.2 Basic Constructive Algorithms

1.14 2D Prefix Sum

Subcategory ID: 2d_prefix_sum · Topics: 1

1.14.1 2D Prefix Sum

1.15 More Techniques

Subcategory ID: more_techniques · Topics: 2

1.15.1 Difference Array

1.15.2 Sliding Window Technique

1.16 Bit Manipulation

Subcategory ID: bit_manipulation · Topics: 2

1.16.1 Bit Manipulation

1.16.2 The XOR Trick

1.17 Basic Modular Arithmetic

Subcategory ID: modular_arithmetic · Topics: 2

1.17.1 Binary Exponentiation and Basic Modular Arithmetic

1.17.2 Fermat's Little Theorem and Modular Inverse

1.18 Basic Counting

Subcategory ID: basic_counting · Topics: 3

1.18.1 Permutations, Combinations and Basic Counting Problems

1.18.2 Stars and Bars

1.18.3 Pigeonhole Principle

1.19 Very Basic Graphs

Subcategory ID: very_basic_graphs · Topics: 1

1.19.1 Introduction to Graphs | Definitions and Representations

2. Data Structures (DS)

Category ID: data_structures · Subcategories: 18 · Topics: 82

2.1 Segment Tree

Subcategory ID: segment_tree · Topics: 13

2.1.1 Segment Tree (Point Update Range Query)

2.1.2 Segment Tree with Lazy Propagation

2.1.3 Persistent Segment Tree

2.1.4 Persistent Segment Tree with Lazy Propagation

2.1.5 2D Segment Tree

2.1.6 Dynamic Segment Tree

2.1.7 2D Dynamic Segment Tree

2.1.8 Merge Sort Tree

2.1.9 Iterative Segment Tree

2.1.10 Segment Tree Merging

2.1.11 Segment Tree Beats

2.1.12 XOR Segment Tree

2.1.13 Historic Information on Segment Trees

2.2 Binary Indexed Tree (BIT)

Subcategory ID: binary_indexed_tree · Topics: 5

2.2.1 BIT / Fenwick Tree

2.2.2 Lower bound on BIT

2.2.3 BIT with Range Update and Range Query

2.2.4 2D BIT

2.2.5 2D BIT with Range Update and Range Query

2.3 Sparse Table

Subcategory ID: sparse_table · Topics: 3

2.3.1 Sparse Table

2.3.2 Sparse Table 2D

2.3.3 Disjoint Sparse Table

2.4 Trie

Subcategory ID: trie · Topics: 2

2.4.1 Trie on Strings and Bits

2.4.2 Persistent Trie

2.5 Disjoint Set Union (DSU)

Subcategory ID: dsu · Topics: 8

2.5.1 DSU / Union Find

2.5.2 DSU with Rollbacks

2.5.3 Reachability Tree / DSU Tree / Kruskal Reconstruction Tree (KRT)

2.5.4 Partially Persistent DSU

2.5.5 Persistent DSU

2.5.6 Augmented DSU / Weighted DSU

2.5.7 DSU on Tree and Small to Large Merging

2.5.8 [Trick] Maintaining Log N DSU / Range Parallel DSU

2.6 Square Root Decomposition

Subcategory ID: sqrt_decomposition · Topics: 12

2.6.1 Basic SQRT Decomposition

2.6.2 Splitting Objects into Light and Heavy / Case Processing

2.6.3 Batch Processing / SQRT Decomposition on Queries

2.6.4 SQRT Decomposition Split and Build Technique

2.6.5 SQRT Fragmented Tree / Block Tree / SQRT Decomposition on Trees

2.6.6 Mo's Algorithm

2.6.7 Rollback Mo and Mo's with DSU

2.6.8 Mo's on Tree

2.6.9 Sweepline Mo

2.6.10 Mo's with Update / 3D Mo (Offline)

2.6.11 Mo's with Update / 3D Mo (Online)

2.6.12 4D Mo

  • ID: 4d_mo · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/4d_mo
  • Templates (1):
  • 4D MO.cpp
  • Problems (2):
  • [M] ★ Strange Queries
  • [M] ★ Two Subtrees

2.7 Heavy Light Decomposition (HLD)

Subcategory ID: hld · Topics: 1

2.7.1 Heavy Light Decomposition (HLD) ft Subtrees and Path Query

2.8 Centroid Decomposition

Subcategory ID: centroid_decomposition · Topics: 2

2.8.1 Centroid Decomposition

2.8.2 Persistent Centroid Decomposition

2.9 Long Path Decomposition

Subcategory ID: undefined · Topics: 1

2.9.1 Long Path Decomposition

  • ID: long_path_decomposition · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/long_path_decomposition
  • Templates (1):
  • Long Path Decomposition.cpp
  • Problems (1):
  • [M] ★ Spiders Evil Plan

2.10 BST

Subcategory ID: binary_search_tree · Topics: 1

2.10.1 Binary Search Tree (BST)

2.11 Balanced Binary Search Tree (BBST)

Subcategory ID: bbst · Topics: 5

2.11.1 Treap

2.11.2 Implicit Treap

2.11.3 Persistent Treap

2.11.4 Rope

2.11.5 Splay Tree

Subcategory ID: lct · Topics: 4

2.12.2 Euler Tour Tree (ETT)

2.12.3 Top Tree / AAA Tree

2.13 Policy Based Data Structures

Subcategory ID: policy_based_data_structures · Topics: 2

2.13.1 Ordered Set

2.13.2 GP Hash Table

2.14 More Tree Data Structures

Subcategory ID: more_tree_data_structures · Topics: 6

2.14.1 Wavelet Tree

2.14.2 Cartesian Tree

2.14.3 K-Dimensional Tree (KD Tree)

2.14.4 SQRT Tree

2.14.5 Permutation Tree

2.14.6 PQ Tree

2.15 Dynamic Connectivity

Subcategory ID: dynamic_connectivity · Topics: 2

2.15.1 Dynamic Connectivity Problem (Offline)

2.15.2 Dynamic Connectivity Problem (Online) / HDLT Algorithm

2.16 Monotonic Data Structures

Subcategory ID: monotonic_data_structures · Topics: 4

2.16.1 Monotonic Stack: All Nearest Smaller Values and All Subarray Maximum/Minimum

2.16.2 Monotonic Queue

2.16.3 Monotonic Queue 2D

2.16.4 Monotonic Deque

2.17 Miscellaneous

Subcategory ID: miscellaneous · Topics: 4

2.17.1 Interval Set

2.17.2 Persistent Array

2.17.3 Persistent Queue

2.17.4 Persistent Meldable Heap / Leftist Heap

2.18 Techniques

Subcategory ID: techniques · Topics: 7

2.18.1 Venice Technique

2.18.2 Offline Queries

2.18.3 Static to Dynamic Trick / Log Decomposition

2.18.4 Divide and Conquer on Queries

2.18.5 CDQ Divide and Conquer

2.18.6 Queue Undo Trick

2.18.7 Priority Queue Undo Trick

3. Graph Theory

Category ID: graph_theory · Subcategories: 21 · Topics: 103

3.1 Graph Traversal

Subcategory ID: graph_traversal · Topics: 7

3.1.1 Depth First Search (DFS)

3.1.2 Breadth First Search (BFS)

3.1.3 DFS Tree

3.1.4 Topological Sorting

3.1.5 Tree Diameter

3.1.6 Euler Tour Technique

3.1.7 Inverse Graph

3.2 Lowest Common Ancestor (LCA)

Subcategory ID: lca · Topics: 2

3.2.1 Binary Lifting and LCA

3.2.2 LCA in O(1)

3.3 Graph Connectivity

Subcategory ID: graph_connectivity · Topics: 9

3.3.1 Strongly Connected Components (SCC)

3.3.2 Incremental SCC

3.3.3 Articulation Bridges and Bridge Tree

3.3.4 Online Articulation Bridges

3.3.5 Articulation Points and Block Cut Tree

3.3.6 Three Edge Connectivity

3.3.7 Four Edge Connectivity

3.3.8 Dynamic K-Connectivity

3.3.9 Ear Decomposition

3.4 Orientation

Subcategory ID: orientation · Topics: 2

3.4.1 Strong Orientation

3.4.2 ST-numbering / Bipolar Orientation

3.5 Minimum Spanning Tree (MST)

Subcategory ID: minimum_spanning_tree · Topics: 9

3.5.1 Minimum Spanning Tree (Prim's and Kruskal's)

3.5.2 Steiner Tree Problem

3.5.3 Boruvka's Algorithm

3.5.4 Minimum Diameter Spanning Tree

3.5.5 Manhattan MST

3.5.6 Euclidean MST

3.5.7 Directed MST

3.5.8 Dynamic MST

3.5.9 Kirchoffs Theorem ft Number of MSTs

3.6 Shortest Paths

Subcategory ID: shortest_paths · Topics: 11

3.6.1 Dijkstra's Algorithm

3.6.2 [Trick] Dijkstra on Segment Tree

3.6.3 Floyd Warshall

3.6.4 Bellman Ford

3.6.5 Shortest Path Faster Algorithm (SPFA)

3.6.6 Johnson's Alogrithm

3.6.7 0/1 BFS

3.6.8 Dial's algorithm

3.6.9 Eppsteins Algorithm

3.6.10 Suurballe's Algorithm

3.6.11 A* Algorithm

3.7 Cycles

Subcategory ID: cycles · Topics: 5

3.7.1 Cycle Detection

3.7.2 [Problem] Minimum Weight Cycle For Each Vertex

3.7.3 [Problem] Minimum Weight Cycle For Each Edge

3.7.4 Minimum Mean Weight Cycle

3.7.5 Number of 3 and 4 length Cycles

3.8 More Tree Stuff

Subcategory ID: more_tree_stuff · Topics: 7

3.8.1 Virtual Tree / Auxiliary Tree

3.8.2 Rerooting Technique

3.8.3 Union of Two Paths on a Tree

  • ID: path_union · Difficulty: Medium · Importance: ★★☆
  • Topic page: https://youkn0wwho.academy/topic-list/path_union
  • Templates (1):
  • Path Union.cpp
  • Problems (2):
  • [M] ★ Max Mex
  • [M] ★ MEX Tree

3.8.4 Intersection of Two Paths on a Tree

  • ID: path_intersection · Difficulty: Medium · Importance: ★★☆
  • Topic page: https://youkn0wwho.academy/topic-list/path_intersection
  • Templates (1):
  • Path Intersection.cpp
  • Problems (1):
  • [M] ★ Path Intersection

3.8.5 [Problem] Number of Paths of Each Length in a Tree

3.8.6 Dynamic Online Tree Diameter

3.8.7 [Problem] Tree Orientation to Maximize Pairs of Reachable Nodes

  • ID: tree_orientation_to_maximize_pairs_of_reachable_nodes · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/tree_orientation_to_maximize_pairs_of_reachable_nodes
  • Templates (1):
  • Tree Orientation.cpp
  • Resources (1):
  • ★ A comment by Bruteforceman
  • Problems (1):
  • [M] ★ Polarization

3.9 Satisfiability

Subcategory ID: satisfiability · Topics: 3

3.9.1 2 SAT

3.9.2 3 SAT

3.9.3 System Of Difference Constraints

3.10 Eulerian Path

Subcategory ID: eulerian_path · Topics: 1

3.10.1 Eulerian Path and Cycle

3.11 Hamiltonian Path

Subcategory ID: hamiltonian_path · Topics: 2

3.11.1 Hamiltonian Path and Cycle

3.11.2 Hamiltonian Path Heuristic Algorithm

3.12 Cliques and Independent Sets

Subcategory ID: cliques_and_independent_sets · Topics: 2

3.12.1 Maximum Clique

3.12.2 Maximum Independent Set (MIS)

3.13 Graph Coloring

Subcategory ID: graph_coloring · Topics: 5

3.13.1 Chromatic Number

3.13.2 Welsh-Powell Algorithm

3.13.3 Chromatic Polynomial ft Number of DAGs

3.13.4 Edge Coloring of Simple Graph

3.13.5 Edge Coloring of Bipartite Graph

3.14 Graph Counting

Subcategory ID: graph_counting · Topics: 5

3.14.1 Counting Labeled Graphs

3.14.2 Prufer Code

3.14.3 [Problem] Number of Arborescences with n Nodes

3.14.4 Tuttes Theorem ft Arborescences in a Graph

3.14.5 BEST Theorem

3.15 Dynamic Acyclic Graphs (DAG)

Subcategory ID: dynamic_acyclic_graphs · Topics: 2

3.15.1 DAG Reachability

3.15.2 Incremental DAG Reachability

3.16 Dominators

Subcategory ID: dominators · Topics: 1

3.16.1 Dominator Tree

3.17 Special Graphs

Subcategory ID: special_graphs · Topics: 3

3.17.1 Cactus Graph

3.17.2 Tournament Graph

3.17.3 Chordal Graph

3.18 Flow and Min Cut

Subcategory ID: flow_and_min_cut · Topics: 13

3.18.1 Maximum Flow / Minimum Cut

3.18.2 Min Cost Max Flow (MCMF)

3.18.3 Min Cost Max Flow with Negative Cycles

3.18.4 Maximum Closure Problem

3.18.5 L-R Flow

3.18.6 Gomory-Hu Tree

3.18.7 Gomory-Hu Tree of a Planar Graph

3.18.8 Stoer Wagner Algorithm

3.18.9 Chinese Postman Problem

3.18.10 Uniqueness of Min Cut

3.18.11 Maximum Density Subgraph

3.18.12 Min Cut in a Planar Graph

3.18.13 Max Cut in a Planar Graph

  • ID: max_cut_in_a_planar_graph · Difficulty: Very Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/max_cut_in_a_planar_graph
  • Problems (1):
  • [H] Planar Max Cut

3.19 Matching

Subcategory ID: matching · Topics: 8

3.19.1 Bipartite Matching (HopCroft Karp Algorithm and Kuhn's Algorithm)

3.19.2 Hungarian Algorithm / Bipartite Weighted Matching

3.19.3 Blossom Algorithm Unweighted / General Matching / Randomized General Matching

3.19.4 Blossom Algorithm Weighted / General Weighted Matching

3.19.5 Stable Marriage Problem

3.19.6 Konig's Theorem and Maximum Independent Set in Bipartite Graphs

3.19.7 Halls Theorem

3.19.8 Matching using Determinants

3.20 Partially Ordered Set (POSET)

Subcategory ID: poset · Topics: 1

3.20.1 POSET ft Dilworth's and Mirsky's Theorem

3.21 Miscellaneous

Subcategory ID: miscellaneous · Topics: 5

3.21.1 Functional Graphs

3.21.2 Degree Sequences

3.21.3 Tree Isomorphism

3.21.4 Binarizing a Tree

3.21.5 Planarity Check

4. Number Theory

Category ID: number_theory · Subcategories: 9 · Topics: 57

4.1 Primes and Divisors

Subcategory ID: primes_and_divisors · Topics: 12

4.1.1 Sieve, Prime Factorization and Divisors

4.1.2 Linear Sieve

4.1.3 Segmented Sieve

4.1.4 Sieve upto 1e9

4.1.5 Miller-Rabin Primality Test

4.1.6 Pollard Rho

4.1.7 Prime Counting Function

4.1.8 [Problem] Counting Numbers Having Exactly K Divisors

4.1.9 [Problem] Smallest Number Having Exactly K Divisors

  • ID: smallest_number_having_exactly_k_divisors · Difficulty: Medium · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/smallest_number_having_exactly_k_divisors
  • Templates (1):
  • Smallest Number Having Exactly K Divisors.cpp
  • Problems (1):
  • [M] ★ Politeness

4.1.10 Sum of The Number of Divisors in cbrt(n)

  • ID: sum_of_the_number_of_divisors_in_cbrt_n · Difficulty: Very Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/sum_of_the_number_of_divisors_in_cbrt_n
  • Templates (1):
  • Sum of The Number of Divisors in cbrt(n).cpp

4.1.11 Wilson's Theorem

4.1.12 Implicit Prime Factorization

4.2 Multiplicative Functions

Subcategory ID: multiplicative_functions · Topics: 7

4.2.1 Number of Divisors / Sum of Divisors / Sigma Function

4.2.2 Euler's Totient Function / Phi Function

4.2.3 Power Tower / Generalized Euler theorem

4.2.4 Mobius Function and Mobius Inversion

4.2.5 Dirichlet convolution

4.2.6 Min_25 Sieve

4.2.7 Powerful Number Sieve / PN Sieve

4.3 Euclidean Algorithm

Subcategory ID: euclidean_algorithm · Topics: 4

4.3.1 Euclidean Algorithm

4.3.2 Extended Euclid

4.3.3 Bezout's Identity

4.3.4 Chicken McNugget Theorem

4.4 Modular Arithmetic

Subcategory ID: modular_arithmetic · Topics: 10

4.4.1 Linear Congruence Equation

4.4.2 Chinese Remainder Theorem (CRT)

4.4.3 Primitive Root

4.4.4 Multiplicative Order and Carmichael's Lambda Function

4.4.5 Discrete Log / Baby Step Giant Step

4.4.6 Discrete Root

4.4.7 Discrete Root in O(P^(1/4))

4.4.8 Discrete Square Root, Tonelli Shanks Algorithm, Cipolla's Algorithm

4.4.9 Number of Distinct Kth Powers Modulo N

4.4.10 Number of Solutions to X^2 = 1 mod M

4.5 Linear Diophantine Equations

Subcategory ID: linear_diophantine_equations · Topics: 5

4.5.1 Linear Diophantine Equation with Two Variables

4.5.2 Linear Diophantine Equation with N Variables

4.5.3 Trivariable Linear Diophantine Equation with Nonnegative Solutions

4.5.4 Multivariable Linear Diophantine Equation with Nonnegative Solutions

4.5.5 Linear Diophantine With N Unknowns and Two Equations

4.6 Solutions to Equations

Subcategory ID: solutions_to_equations · Topics: 6

4.6.1 Number of Solutions to a Basic Linear Algebraic Equation

4.6.2 Number of Solutions to a Basic Linear Algebraic Equation using Meet in the Middle

4.6.3 Number of Nonnegative Integer Solutions to ax + by ≤ c

4.6.4 Number of Integer Solutions to 1/x + 1/y = 1/k

4.6.5 Two / Three / Four Squares Theorem

4.6.6 Pell's Equation

4.7 Floor Sum

Subcategory ID: floor_sum · Topics: 3

4.7.1 Sum of Floors

4.7.2 Floor Sum and Mod Sum of Arithmetic Progression

4.7.3 Generalized Floor Sum of Arithmetic Progression

4.8 Fibonacci Numbers

Subcategory ID: fibonacci_numbers · Topics: 4

4.8.1 Fibonacci Numbers

4.8.2 [Problem] LCM of Fibonacci Numbers

4.8.3 Pisano Period

4.8.4 Phi Field

4.9 Miscellaneous

Subcategory ID: miscellaneous · Topics: 6

4.9.1 Pythagorean Triplets

4.9.2 Min of Mod of Arithmetic Progression

4.9.3 Factorial Number System

4.9.4 Stern-Brocot Tree and Rational Approximation

4.9.5 [Problem] Number of a * x mod p in a Range

  • ID: number_of_ax_mod_p_in_a_range · Difficulty: Hard · Importance: ★★☆
  • Topic page: https://youkn0wwho.academy/topic-list/number_of_ax_mod_p_in_a_range
  • Templates (1):
  • Number of ax%p in a Range.cpp

4.9.6 [Problem] Smallest Nonnegative Integer x s.t. l ≤ a * x mod p ≤ r

5. Combinatorics

Category ID: combinatorics · Subcategories: 7 · Topics: 24

5.1 Techniques

Subcategory ID: techniques · Topics: 1

5.1.1 Contribution Technique

5.2 Catalan

Subcategory ID: catalan · Topics: 2

5.2.1 Catalan Numbers

5.2.2 Catalan Convolution

5.3 Inclusion Exclusion

Subcategory ID: inclusion_exclusion · Topics: 3

5.3.1 Principle of Inclusion and Exclusion (PIE)

5.3.2 Derangements

5.3.3 Inclusion Exclusion on Multiples

5.4 Factorials and Binomial Coefficients (nCr)

Subcategory ID: binomial_coefficient · Topics: 8

5.4.1 Lucas Theorem

5.4.2 nCr Modulo Any Mod

5.4.3 Large Factorials and Binomial Coefficients

5.4.4 Legendre's Formula

5.4.5 Prefix Sum Queries of Binomial Coefficients

5.4.6 Prefix Sum of Binomial Coefficients for a Fixed Large N

5.4.7 Sum of nCr Over a Fixed Congruence Class

  • ID: sum_of_ncr_over_a_fixed_congruence_class · Difficulty: Medium · Importance: ★★☆
  • Topic page: https://youkn0wwho.academy/topic-list/sum_of_ncr_over_a_fixed_congruence_class
  • Templates (1):
  • Sum of nCi over a Fixed Congruence Class.cpp
  • Problems (2):
  • [M] ★ You
  • [H] ★ Simple nCr

5.4.8 [Problem] Sum of nCr(a[i], K) for each K from 1 to N

5.5 Stirling Numbers

Subcategory ID: stirling_numbers · Topics: 5

5.5.1 Stirling Numbers (Basic)

5.5.2 Stirling Number of the First Kind for Fixed N

5.5.3 Stirling Number of the First Kind for Fixed K

5.5.4 Stirling Number of the Second Kind for Fixed N

5.5.5 Stirling Number of the Second Kind for Fixed K

5.6 Partitions

Subcategory ID: partitions · Topics: 2

5.6.1 Partitions of an Integer, Partition Function and Pentagonal Number Theorem

5.6.2 Partitions of a Set / Bell Number

5.7 Miscellaneous

Subcategory ID: miscellaneous · Topics: 3

5.7.1 Burnside's Lemma / Polya Enumeration Theorem

5.7.2 Bertrand's Ballot Theorem

5.7.3 Young Tableaus and the Hook Length Formula

6. Math

Category ID: math · Subcategories: 10 · Topics: 79

6.1 Convolution

Subcategory ID: convolution · Topics: 7

6.1.1 Fast Fourier Transform (FFT)

6.1.2 Number Theoretic Transform (NTT)

6.1.3 2D FFT / NTT

6.1.4 Online FFT / NTT

6.1.5 Fast Walsh Hadamard Transform (FWHT) and its Variations

6.1.6 GCD Convolution

6.1.7 LCM Convolution

6.2 Polynomial

Subcategory ID: polynomial · Topics: 22

6.2.1 Generating Functions

6.2.2 Polynomial Inverse

6.2.3 Polynomial Exp

6.2.4 Polynomial Log

6.2.5 Polynomial Pow

6.2.6 Polynomial Sqrt

6.2.7 Polynomial Composition

6.2.8 Multipoint Evaluation

6.2.9 Chirp Z Transform

6.2.10 Polynomial Interpolation

6.2.11 Polynomial Shift

6.2.12 Shift of Sampling Points of Polynomial

6.2.13 Polyomial Division and Remainder

6.2.14 Polynomial Roots Under a Modulo

6.2.15 Resultant of Two Polynomials and Half-GCD Algorithm

6.2.16 Lagrange Interpolation

6.2.17 [Problem] Sum of r^i * poly(i)

6.2.18 Polynomial with Binomial Coefficients

6.2.19 Subset Sum Problem using Generating Functions

6.2.20 Polynomial Factorization of (x^n - 1) and Cyclotomic Polynomials

6.2.21 Schwartz–Zippel Lemma

6.2.22 Lagrange Inversion Theorem

6.3 Matrices

Subcategory ID: matrices · Topics: 6

6.3.1 Matrix Exponentiation

6.3.2 Permanent of a Matrix

6.3.3 Freivald's Algorithm

6.3.4 Vandermonde Matrix

6.3.5 Hafnian of a Matrix / Number of Perfect Matchings in a Graph

6.3.6 Frobenius Form of a Matrix and Fast Matrix Power

6.4 Linear Recurrence

Subcategory ID: linear_recurrence · Topics: 8

6.4.1 Linear Recurrence Relations

6.4.2 Linear Recurrence using Cayley-Hamilton Theorem in O(N^2 log K)

6.4.3 Linear Recurrence using Generating Functions in O(N log N log K)

6.4.4 Linear Recurrence with Polynomial Coefficients

6.4.5 Linear Recurrence on Matrices

  • ID: linear_recurrence_on_matrices · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/linear_recurrence_on_matrices
  • Resources (1):
  • ★ PANIC - Editorial | YouKn0wWho
  • Problems (1):
  • [H] ★ Panic! at the Disco

6.4.6 Generating Function of a Linear Recurrence

6.4.7 Berlekamp Massey

6.4.8 Reeds-Sloane Algorithm

6.5 Linear Algebra

Subcategory ID: linear_algebra · Topics: 18

6.5.1 Gaussian Elimination

6.5.2 Gaussian Elimination Modulo 2

6.5.3 Determinant of a Matrix

6.5.4 Determinant under Composite Modulo

6.5.5 Characteristic Polynomial and Hesserberg Matrix

6.5.6 [Problem] Determinant of Product Matrix

6.5.7 Determinant of Sparse Matrix and Black Box Linear Algebra

6.5.8 [Problem] Determinant of Permutant and Circulant Matrix

6.5.9 GCD Determinant / Smith's Determinant

6.5.10 Cauchy–Binet formula

6.5.11 Inverse of a Matrix

6.5.12 Inverse of a Matrix modulo 2

6.5.13 Thomas Algorithm

6.5.14 Vector Space and XOR Basis

6.5.15 [Technique] XOR Basis ft Reduced Row Echelon Form

6.5.16 [Technique] XOR Basis ft Lexicographically Largest Basis

6.5.17 XOR Basis with Deletions (Online)

6.5.18 q Binomial

6.6 Formulas

Subcategory ID: formulas · Topics: 4

6.6.1 Gauss's Eureka Theorem

6.6.2 Titu's Lemma

6.6.3 Lifting-the-exponent(LTE) Lemma

6.6.4 Faulhaber's Formula and Bernoulli Numbers

6.7 Calculus

Subcategory ID: calculus · Topics: 2

6.7.1 Differentiation and Integration

6.7.2 Line Integral

6.8 Probabilities and Expected Values

Subcategory ID: probabilities_and_expected_values · Topics: 6

6.8.1 Probabilities and Expected Values

6.8.2 Expected Value Powers Technique

6.8.3 The Slime Trick

6.8.4 Expected Occurrence Time as Substring

6.8.5 Gambler's Ruin

6.8.6 Martingale

6.9 Mathematical Optimization

Subcategory ID: mathematical_optimization · Topics: 3

6.9.1 Lagrange Multiplier

6.9.2 Linear Programming / Simplex Algorithm

6.9.3 Duality in Linear Programming (LP <> Flow)

6.10 Miscellaneous

Subcategory ID: miscellaneous · Topics: 3

6.10.1 Continued Fractions

6.10.2 Polynomial Real Roots

6.10.3 Finite Field Arithmetic Binary

7. Strings

Category ID: strings · Subcategories: 7 · Topics: 31

7.1 String Matching

Subcategory ID: string_matching · Topics: 4

7.1.1 Knuth Morris Pratt (KMP) and Prefix Automaton

7.1.2 Z algorithm

7.1.3 String Matching using Bitsets

7.1.4 String Matching with FFT ft Wildcard Matching

7.2 Hashing

Subcategory ID: hashing · Topics: 4

7.2.1 String Hashing

7.2.2 2D String Hashing

7.2.3 XOR Hashing

7.2.4 Multiset Hashing

7.3 Aho Corasick

Subcategory ID: aho_corasick · Topics: 2

7.3.1 Aho Corasick

7.3.2 Dynamic Aho Corasick

7.4 Suffix Structures

Subcategory ID: suffix_structures · Topics: 6

7.4.1 Suffix Array

7.4.2 Isomorphic Suffix Array

  • ID: isomorphic_suffix_array · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/isomorphic_suffix_array
  • Templates (1):
  • Suffix Array Isomorphic.cpp
  • Problems (1):
  • [M] ★ Similar Strings

7.4.3 Dynamic Suffix Array

7.4.4 Suffix Automaton

7.4.5 [Problem] Distinct Substring Queries in Range

7.4.6 Suffix Tree

7.5 Palindromes

Subcategory ID: palindromes · Topics: 5

7.5.1 Palindromic Tree

7.5.2 Persistent Palindromic Tree

7.5.3 Manachers Algorithm

7.5.4 [Problem] Minimum Palindrome Factorization

7.5.5 [Problem] Number of Palindromes in Range

7.6 Longest Common Subsequence (LCS)

Subcategory ID: lcs · Topics: 5

7.6.1 Longest Common Subsequence (LCS)

7.6.2 All Substring Longest Common Subsequence

7.6.3 Bit LCS

7.6.4 Cyclic LCS

7.6.5 LCS on RLE compressed string

  • ID: lcs_on_rle_compressed_string · Difficulty: Very Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/lcs_on_rle_compressed_string
  • Resources (1):
  • Matching for Run-Length Encoded Strings

7.7 Miscellaneous

Subcategory ID: miscellaneous · Topics: 5

7.7.1 Balanced Brackets

7.7.2 Expression Parsing

7.7.3 Lyndon Factorization / Duval Algorithm

7.7.4 Finding Repetitions / Main-Lorentz Algorithm

7.7.5 De Bruijn Sequence

8. Dynamic Programming (DP)

Category ID: dynamic_programming · Subcategories: 10 · Topics: 35

8.1 Intro to DP

Subcategory ID: intro_to_dp · Topics: 2

8.1.1 Knapsack and Basic Dynamic Programming

8.1.2 Knapsack and Subset Sum Optimizations

8.2 Digit DP

Subcategory ID: digit_dp · Topics: 1

8.2.1 Digit DP

8.3 DP Optimizations

Subcategory ID: dp_optimizations · Topics: 5

8.3.1 Divide and Conquer Optimization

8.3.2 Knuth Optimization

8.3.4 1D1D DP Optimization

8.3.5 DP Optimization using Data Structures [Some Practice Problems]

8.4 Convex Hull Trick (CHT)

Subcategory ID: convex_hull_trick · Topics: 2

8.4.1 Convex Hull Trick (CHT) and Dynamic CHT

8.4.2 Persistent CHT

8.5 Li Chao Tree

Subcategory ID: li_chao_tree · Topics: 3

8.5.1 Li Chao Tree

8.5.2 Persistent Li Chao Tree

8.5.3 Extended Li Chao tree

Subcategory ID: bit_related_dp · Topics: 6

8.6.1 Bitmask DP

8.6.2 Sum Over Subsets DP (SOS DP)

8.6.3 [Problem] Subset Union of Bitsets

  • ID: subset_union_of_bitsets · Difficulty: Medium · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/subset_union_of_bitsets
  • Templates (1):
  • Subset Union of Bitsets.cpp
  • Problems (1):
  • [E] ★ Radio Radius

8.6.4 Subset Convolution

8.6.5 [Trick] Dynamic Submask Count

8.6.6 [Problem] XOR Equation

8.7 More Tricks

Subcategory ID: more_tricks · Topics: 4

8.7.1 Open and Close Interval Trick

8.7.2 Slope Trick

8.7.3 x2 +1 Trick

8.7.4 Combining Subtrees Technique

8.8 Classic DP

Subcategory ID: classic_dp · Topics: 3

8.8.1 Longest Increasing Subsequence (LIS)

8.8.2 Interval DP / Range DP / Matrix Chain Multiplication (MCM)

8.8.3 Edit Distance

8.9 Dp on Different Structures

Subcategory ID: dp_on_different_structures · Topics: 4

8.9.1 DP on Trees and DAGs

8.9.2 DP over Divisors

8.9.3 Substring DP

8.9.4 DP on Convex Hulls

8.10 Miscellaneous

Subcategory ID: miscellaneous · Topics: 5

8.10.1 Connected Component DP

8.10.2 Broken Profile DP / Plug DP

8.10.3 Hirschberg's Algorithm

8.10.4 [Problem] Number of Subsequences Having Product at least K

8.10.5 [Problem] Range LIS Query

9. Game Theory

Category ID: game_theory · Subcategories: 4 · Topics: 7

9.1 Grundy Number / Nim

Subcategory ID: grundy_number · Topics: 2

9.1.1 Grundy Number and Basic Game Theory

9.1.2 Nimber

9.2 Hackenbush

Subcategory ID: hackenbush · Topics: 2

9.2.1 Green Hackenbush on Trees and Graphs

9.2.2 Blue Red HackenBush

9.3 Graph Games

Subcategory ID: graph_games · Topics: 2

9.3.1 Games on Arbitrary Graphs

9.3.2 [Problem] Matching Game On A Graph

9.4 Miscellaneous

Subcategory ID: miscellaneous · Topics: 1

9.4.1 Alpha Beta Pruning

10. Geometry

Category ID: geometry · Subcategories: 10 · Topics: 55

10.1 Euclidean Geometry

Subcategory ID: euclidean_geometry · Topics: 1

10.1.1 Euclidean Geometry

10.2 Geometry 2D

Subcategory ID: geo_2d · Topics: 24

10.2.1 Points, Vectors, Transformations, Dot Products, Cross Products, Precision Issues and Polar Sort(2D)

10.2.2 Lines, Segments, Rays, Distance and Relation Between Two Structures, Projections and Reflections(2D)

10.2.3 Circles, Circle Relations, Intersections, Inscribed Circles and Circumcircles(2D)

10.2.4 Tangents(2D)

10.2.5 Circles of Apollonius(2D)

10.2.6 Circle Union(2D)

10.2.7 Polygons(2D)

10.2.8 Centroid of a Polygon(2D)

10.2.9 Geometric Median(2D)

10.2.10 Convex Hull(2D)

10.2.11 Point in Convex Polygon in log(N)(2D)

10.2.12 Winding Number and Point in Simple Polygon(2D)

10.2.13 Extreme Vertex(2D)

  • ID: extreme_vertex_2d · Difficulty: Medium · Importance: ★★☆
  • Topic page: https://youkn0wwho.academy/topic-list/extreme_vertex_2d
  • Templates (1):
  • Geometry 2D.cpp#L715-L740
  • Resources (1):
  • ★ 5. Extreme points

10.2.14 Rotating Calipers ft Diameter and Width of a Convex Polygon and Minimum Enclosing Rectangle(2D)

10.2.15 Minimum Enclosing Circle(2D)

10.2.16 Polygon Line and Convex Line Intersection, and Polygon Cutting(2D)

10.2.17 Tangents from Point to Convex and Convex to Convex(2D)

10.2.18 Distance from Point to Convex, Convex to Line and Convex to Convex(2D)

10.2.19 Maximum Distance from Convex to Convex(2D)

10.2.20 Polygon Union(2D)

  • ID: polygon_union_2d · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/polygon_union_2d
  • Templates (1):
  • Geometry 2D.cpp#L999-L1044
  • Problems (1):
  • [E] ★ Darts

10.2.21 Polygon Triangulation(2D)

10.2.22 Maximum Circle Cover(2D)

10.2.23 Maximum Inscribed Circle in a Convex(2D)

10.2.24 Triangle Circle and Polygon Circle Intersection(2D)

10.3 Geometry 3D

Subcategory ID: geo_3d · Topics: 9

10.3.1 Points, Vectors, Dot Products, Cross Products and Mixed Products(3D)

10.3.2 Planes(3D)

10.3.3 Plane Based Coordinate System(3D)

10.3.4 Lines, Segments, and Distances, Angles and Intersections Between Lines and Planes(3D)

10.3.5 Triangles and Distance from Triangle to Triangle(3D)

10.3.6 Spherical Geometry and Winding Number(3D)

10.3.7 Minimum Enclosing Sphere(3D)

10.3.8 Polyhedron, Pyramid, Cone and Cylinder(3D)

10.3.9 Convex Hull(3D)

10.4 Delaunay

Subcategory ID: delaunay · Topics: 1

10.4.1 Delaunay Triangulation and Voronoi Diagram

10.5 Half Plane

Subcategory ID: half_plane · Topics: 2

10.5.1 Half Plane Intersection

10.5.2 Dynamic Half Plane Intersection

  • ID: dynamic_half_plane_intersection · Difficulty: Very Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/dynamic_half_plane_intersection
  • Templates (1):
  • Half Plane Intersection Dynamic.cpp
  • Problems (1):
  • [E] ★ Defend the Recipe

10.6 Convex Polygon

Subcategory ID: convex_polygon · Topics: 3

10.6.1 Minkowski Sum

10.6.2 Dynamic Convex Hull

10.6.3 Onion Decomposition

10.7 Lattice Points

Subcategory ID: lattice_points · Topics: 2

10.7.1 Picks Theorem

10.7.2 Lattice Points inside a Non-Lattice Polygon

10.8 Sweep Line

Subcategory ID: sweep_line · Topics: 5

10.8.1 Sweep Line Algorithm and Radial Sweep

10.8.2 Closest Pair of Points

10.8.3 Rectangle Union

10.8.4 All Pair Segment Intersection.

10.8.5 Vertical decomposition

10.9 Planar Geometry

Subcategory ID: planar_geometry · Topics: 2

10.9.1 Faces in Planar Graph

10.9.2 Point Location

10.10 Miscellaneous

Subcategory ID: miscellaneous · Topics: 6

10.10.1 Hill Climbing and Simulated Annealing

10.10.2 [Trick] Linear Combination of Vectors

10.10.3 Reflections on a Rectangle

10.10.4 [Problem] Maximum Area of a Triangle from Given Lengths

  • ID: maximum_area_of_a_triangle_from_given_lengths · Difficulty: Hard · Importance: ★☆☆
  • Topic page: https://youkn0wwho.academy/topic-list/maximum_area_of_a_triangle_from_given_lengths
  • Templates (1):
  • Maximum Area of Triangle, Given are Lengths.cpp
  • Problems (1):
  • [M] ★ Triangle

10.10.5 [Problem] Maximum Area of a Polygon using Given Lengths in CCW Order

10.10.6 [Problem] Circle/Polygon Inclusion Tree

11. Miscellaneous

Category ID: miscellaneous · Subcategories: 11 · Topics: 41

11.1 Greedy Algorithms

Subcategory ID: greedy_algorithms · Topics: 4

11.1.1 Activity Selection Problem

11.1.2 Fractional Knapsack Problem

11.1.3 Huffman Coding

11.1.4 Exchange Arguments

11.2 Search Techniques

Subcategory ID: search_techniques · Topics: 4

11.3 Interactive Problems

Subcategory ID: interactive_problems · Topics: 2

11.3.1 Interactive Problems

11.3.2 Interactive Problems on Centroids

11.4 Permutations

Subcategory ID: permutations · Topics: 3

11.4.1 Permutations and Permutation Cycles

11.4.2 [Problem] K-th Root of a Permutation

11.4.3 Schreier–Sims Algorithm

11.5 Matroids

Subcategory ID: matroids · Topics: 1

11.5.1 Matroid Intersection

11.6 Chess

Subcategory ID: chess · Topics: 3

11.6.1 [Problem] Knight Moves in Infinity Grid

11.6.2 [Problem] Knight's Tour Problem

11.6.3 [Problem] Bishop Placement

11.7 Techniques

Subcategory ID: techniques · Topics: 9

11.7.1 Coordinate Compression

11.7.2 Direction Array

11.7.3 Meet in the Middle

11.7.4 Invariants and Monovariants

11.7.5 Manhattan <> Chebyshev

11.7.6 LCM OR Technique

11.7.7 [Trick] Logarithmic Subarray Aggregator (LSA Trick)

  • ID: logarithmic_bruteforce · Difficulty: Medium · Importance: ★★★
  • Topic page: https://youkn0wwho.academy/topic-list/logarithmic_bruteforce

  • Author's blog: Imagine a problem where you have to find sum of all subarray GCDs.
    Normally you will have to use sparse table and binary search to solve this by leveraging the fact that there will be O(log(MAX)) different GCDs ending at each index.
    But you can do this in a better way with minimal code! You can store a vector or map v[r] which stores all GCDs of subarrays ending at r.
    Note that there will be O(log(MAX)) different GCDs ending at r. So, you can store their info directly in the vector.
    Then, you can iterate over all elements in v[r] to get the vector v[r+1].
    So, you are basically doing a bruteforce in log(N) time. Pretty simple and elegant!
    You can do the same for subarray AND, OR etc.
    Check the template code below for a better understanding.

  • Templates (1):

  • Logarithmic Subarray Aggregator.cpp
  • Problems (10):
  • [E] ★ Bitwise ORs of Subarrays
  • [E] ★ The Brand New Function
  • [M] ★ CGCDSSQ
  • [M] ★ Maximum of GCDs
  • [M] ★ Have Some Water
  • [M] Eri and Expanded Sets
  • [M] ★ Alter the GCD
  • [M] ★ GCD Counting
  • [H] ★ GCD cost on the tree
  • [H] ★ Different GCD Subarray Query

11.7.8 Bitwise Disjoint Partitioning

11.7.9 [Trick] Efficient Non-Increasing Sequence Recovery of Length n with a[i] <= n/i

11.8 Min Plus Convolution

Subcategory ID: min_plus_convolution · Topics: 2

11.8.1 Min Plus Convolution (Convex and Convex)

11.8.2 SMAWK Algorithm and Min Plus Convolution (Convex and Arbitrary)

11.9 Randomized

Subcategory ID: randomized · Topics: 2

11.9.1 Randomized Algorithms

11.9.2 Birthday Paradox

11.10 Bigint

Subcategory ID: bigint · Topics: 2

11.10.1 Big Integers

11.10.2 Trygub Numbers

11.11 Miscellaneous

Subcategory ID: miscellaneous · Topics: 9

11.11.1 Inversions

11.11.2 Josephus Problem

11.11.3 Gray Code

11.11.4 Backtracking

11.11.5 [Problem] MEX of all Subarrays

11.11.6 Lindstrom Gessel Viennot(LGV) Lemma

11.11.7 Dynamic Bitsets

11.11.8 Pragmas

11.11.9 Boyer–Moore Voting Algorithm and Misra–Gries Algorithm

Useful Links (from the topic-list page)

Totals: 11 categories · 126 subcategories · 570 topics · 1542 resource links · 451 template links · 4437 topic→problem links (3888 unique problems).