Preparation to IOI Part 5 - Comprehensive Course

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

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Preparation to IOI Part 5

Preparation to IOI Part 5

Master advanced ideas for high-level problems. This course includes string algorithms, advanced graph algorithms, deeper dynamic programming techniques, Fenwick tree, meet-in-the-middle, centroid decomposition, virtual trees, parallel binary search, and other advanced topics.

10 modules

·

21 lessons

Part 1

Module 1: String Algorithms

Hashing, Z Function, Prefix function, Manacher’s algorithm

String Hashing Algorithms
String Hashing Algorithms
Z-function
Z-function
Prefix function. Knuth-Morris-Pratt algorithm
Prefix function. Knuth-Morris-Pratt algorithm

Manacher's Algorithm

Manacher's Algorithm

Part 2

Module 2: Graph Algorithms

Graph Algorithms

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

Part 3

Module 3: Various DP ideas

Subtree DP, DP on DAG, Connected component DP etc

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

Part 4

Module 4: Combinatorics

Combinatorics

Inclusion-Exclusion (Advanced)
Inclusion-Exclusion (Advanced)

Part 5

Module 5: Meet-in-the-middle

Meet-in-the-middle

Meet in the Middle
Meet in the Middle

Part 6

Module 6: Fenwick Tree

Fenwick Tree

Fenwick Tree
Fenwick Tree

Part 7

Module 7: Centroid Decomposition

Centroid Decomposition

Centroid Decomposition
Centroid Decomposition

Part 8

Module 8: Virtual Trees

Virtual Trees

Virtual Tree / Auxiliary Tree
Virtual Tree / Auxiliary Tree

Part 9

Module 9: Parallel Binary Search

Parallel Binary Search

Parallel binary search
Parallel binary search

Part 10

Module 10: [BONUS]

Bonus topics

Bitset Optimization
Bitset Optimization
Hashing techniques
Hashing techniques