Zero_OP 's VOI 2024 training topics

Data structure

. Segment Tree : Lazy Propagation, Walk on Tree, with Vectors, Merge sort Tree, Persistent, Sparse, Beats, …
. Fenwick Tree : Walk on Tree, 2D, coord compression 2D, …
. Sparse Table : 1D, 2D, LCA, …
. DSU : standard, Rollback version, Dynamic Connectivity, Bipartite online, …
. SQRT decomposition : blocks, standard, spilt and rebuild, queries, Mo, baby step giant step, …
. Deque trick : min, max, gcd

Graph Theory

. DFS/BFS : easy
. Bellman-Ford / Dijkstra / Floyd-Warshall : 3 shortest path algorithm
. DFS - Tree : bridges / joints, Strongly Connected Components, 2SAT, …
. Bridge Tree : implementation
. Block Cut Tree : implementation
. Minimum Spanning Tree : Kruskal, Prim, …
. Euler Cycle/Path : implementation
. Hamiltonian Cycle/Path : properties
. Maximum Flow / Minimum Cut : implementation / properties, …
. Minimum Cost Maximum Flow : implementation
. Maximum Bipartite Matching : implementation
. Segment Tree and Graph : implementation

Tree Algorithm

. Lowest Common Ancestor :

$O(log)$ per queries +

$O(nlog)$ precompute /

$O(1)$ per queries +

$O(2n\times log)$ precompute
. Binary Lifting : implementation
. Euler tour on Tree : properties + implementation, fenwick path update sum
. Small to Large : implementation
. Sack on Tree : implementation
. Heavy-ligh Decomposition : implementation
. Centroid Decomposition : implementation
. DSU tree / IOI18 Werewolf Trick : implementation

String Processing

. Hashing : multi Modulo, 2 styles
. Z algorithm : implementation
. KMP algorithm : implementation, automaton, …
. Trie : dynamic implementation, string and binary number, add, delete, kth, lower bound, max xor, xor all elements, all operations in range

$[L,R]$, …
. Manacher : implementation
. Suffix Array : implementation

Math (Combinatorics / Number Theory)

. Sieve of Eratosthenes : implementation, many variants, …
. Basic Combinatorics :

$n!$,

$C_n^k$,

$A_n^k$, …
. Modulo inverse :

$\frac{1}{x}(modM)$
. Fermat's little theorem :

$a^{\phi (n)}\equiv 1(modM)$, …
. Inclusion-Exclusion : basic
. Stars and bars : 2 variants non-negative and positive
. Lucas theorem : basic
. Multiplicative functions : Euler totient function, Mobius, …
. Chinese Remainder Theorem : implementation and properties
. Diophantine equation : implementation

Geometry

. Basic 2D : basic knowledges
. Rotate : basic
. Convex hull : implementation and properties
. Sweepline : minimum euclidean distance points, manhattan MST, …
. Minkowski sum : implementation and properties, …
. Planar Graph : properties and theorem

Game Theory

. Basic adhoc games : finding properties and optimal
. Nim games : basic properties
. Grundy number : finding

$G(x)$

Dynamic Programming

. Basic Variants : LIS, LCS, knapsack, grid, bitmask
. Digit : states and transitions
. Matrix multiplication transition : hint by small states
. Sum over subset : iteractive implementation
. DAG : longest path
. Knuth optimization : properties
. Divide and Conquer optimization : properties
. Tree : merging subtree

Other tricks

. Lichao Tree : implementation
. Convex Hull Trick : implementation
. Meet in the middle : split into 2 sets
. Bitset : /64 complexity
. Montone-Queue optimization : remove RMQ
. Divide and Conquer : divide to

$[l,mid]$ and

$(mid,r]$ and compute the intersection
. Ternary Search : search on a parabol
. Parallel Binary search : do

$O(log)$ times of searching and using Data structure to calculate
. Matrix multiplication : solving

$f(n)$ with matrix
. Basis XOR : insert vectors and some properties
. XOR hasing : randomize hash
. Probability : randmize chance to appear solution
. Extension Field :

$Z_p=\{a+b\sqrt{5}|a\in Z,a\in Z\}$
. Alien trick / WQS Binary search : Optimize 1 dimension
. CDQ Divide and Conquer : offline divide and conquer