Module 1: String Algorithms

String Hashing Algorithms
Z-function
Prefix function. Knuth-Morris-Pratt algorithm
Manacher's Algorithm

Module 2: Graph Algorithms

Kuhn's algorithm — maximum matching in a bipartite graph
Kőnig's theorem

Module 3: Various DP ideas

DP on a DAG
DP subtree
Connected Component DP
Open and Close Interval Trick
DP on Subarrays
Submask DP
Digit DP

Module 4: Combinatorics

Inclusion-Exclusion (Advanced)

Module 5: Meet-in-the-middle

Meet in the Middle

Module 6: Fenwick Tree

Fenwick Tree

Module 7: Centroid Decomposition

Centroid Decomposition

Module 8: Virtual Trees

Virtual Tree / Auxiliary Tree

Module 9: Parallel Binary Search

Parallel binary search

Module 10: [BONUS]

Bitset Optimization
Hashing techniques

Hashing techniques - Preparation to IOI Part 5

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 5/Module 10: [BONUS]/Hashing techniques

Hashing techniques

Hashing techniques