Competitive Programming 4 - Book 2

CP4: Book 2
Contents
5 Mathematics
	5.1 Overview and Motivation
	5.2 Ad Hoc Mathematical Problems
	5.3 Number Theory
		5.3.1 Prime Numbers
		5.3.2 Probabilistic Prime Testing (Java Only)
		5.3.3 Finding Prime Factors with Optimized Trial Divisions
		5.3.4 Functions Involving Prime Factors
		5.3.5 Modified Sieve
		5.3.6 Greatest Common Divisor & Least Common Multiple
		5.3.7 Factorial
		5.3.8 Working with Prime Factors
		5.3.9 Modular Arithmetic
		5.3.10 Extended Euclidean Algorithm
		5.3.11 Number Theory in Programming Contests
	5.4 Combinatorics
		5.4.1 Fibonacci Numbers
		5.4.2 Binomial Coefficients
		5.4.3 Catalan Numbers
		5.4.4 Combinatorics in Programming Contests
	5.5 Probability Theory
	5.6 Cycle-Finding
		5.6.1 Problem Description
		5.6.2 Solutions using Efficient Data Structures
		5.6.3 Floyd’s Cycle-Finding Algorithm
	5.7 Game Theory (Basic)
	5.8 Matrix Power
		5.8.1 Some Definitions and Sample Usages
		5.8.2 Efficient Modular Power (Exponentiation)
		5.8.3 Efficient Matrix Modular Power (Exponentiation)
		5.8.4 DP Speed-up with Matrix Power
	5.9 Solution to Non-Starred Exercises
	5.10 Chapter Notes
6 String Processing
	6.1 Overview and Motivation
	6.2 Ad Hoc String (Harder)
	6.3 String Processing with DP
		6.3.1 String Alignment (Edit Distance)
		6.3.2 Longest Common Subsequence
		6.3.3 Non Classical String Processing with DP
	6.4 String Matching
		6.4.1 Library Solutions
		6.4.2 Knuth-Morris-Pratt (KMP) Algorithm
		6.4.3 String Matching in a 2D Grid
	6.5 Suffix Trie/Tree/Array
		6.5.1 Suffix Trie and Applications
		6.5.2 Suffix Tree
		6.5.3 Applications of Suffix Tree
		6.5.4 Suffix Array
		6.5.5 Applications of Suffix Array
	6.6 String Matching with Hashing
		6.6.1 Hashing a String
		6.6.2 Rolling Hash
		6.6.3 Rabin-Karp String Matching Algorithm
		6.6.4 Collisions Probability
	6.7 Anagram and Palindrome
		6.7.1 Anagram
		6.7.2 Palindrome
	6.8 Solution to Non-Starred Exercises
	6.9 Chapter Notes
7 (Computational) Geometry
	7.1 Overview and Motivation
	7.2 Basic Geometry Objects with Libraries
		7.2.1 0D Objects: Points
		7.2.2 1D Objects: Lines
		7.2.3 2D Objects: Circles
		7.2.4 2D Objects: Triangles
		7.2.5 2D Objects: Quadrilaterals
	7.3 Algorithms on Polygon with Libraries
		7.3.1 Polygon Representation
		7.3.2 Perimeter of a Polygon
		7.3.3 Area of a Polygon
		7.3.4 Checking if a Polygon is Convex
		7.3.5 Checking if a Point is Inside a Polygon
		7.3.6 Cutting Polygon with a Straight Line
		7.3.7 Finding the Convex Hull of a Set of Points
	7.4 3D Geometry
	7.5 Solution to Non-Starred Exercises
	7.6 Chapter Notes
8 More Advanced Topics
	8.1 Overview and Motivation
	8.2 More Advanced Search Techniques
		8.2.1 Backtracking with Bitmask
		8.2.2 State-Space Search with BFS or Dijkstra’s
		8.2.3 Meet in the Middle
	8.3 More Advanced DP Techniques
		8.3.1 DP with Bitmask
		8.3.2 Compilation of Common (DP) Parameters
		8.3.3 Handling Negative Parameter Values with O↵set
		8.3.4 MLE/TLE? Use Better State Representation
		8.3.5 MLE/TLE? Drop One Parameter, Recover It from Others
		8.3.6 Multiple Test Cases? No Memo Table Re-initializations
		8.3.7 MLE? Use bBST or Hash Table as Memo Table
		8.3.8 TLE? Use Binary Search Transition Speedup
		8.3.9 Other DP Techniques
	8.4 Network Flow
		8.4.1 Overview and Motivation
		8.4.2 Ford-Fulkerson Method
		8.4.3 Edmonds-Karp Algorithm
		8.4.4 Dinic’s Algorithm
		8.4.5 Flow Graph Modeling - Classic
		8.4.6 Flow Graph Modeling - Non Classic
		8.4.7 Network Flow in Programming Contests
	8.5 Graph Matching
		8.5.1 Overview and Motivation
		8.5.2 Graph Matching Variants
		8.5.3 Unweighted MCBM
		8.5.4 Weighted MCBM and Unweighted/Weighted MCM
	8.6 NP-hard/complete Problems
		8.6.1 Preliminaries
		8.6.2 Pseudo-Polynomial: Knapsack, Subset-Sum, Coin-Change
		8.6.3 Traveling-Salesman-Problem (TSP)
		8.6.4 Hamiltonian-Path/Tour
		8.6.5 Longest-Path
		8.6.6 Max-Independent-Set and Min-Vertex-Cover
		8.6.7 Min-Set-Cover
		8.6.8 Min-Path-Cover
		8.6.9 Satisfiability (SAT)
		8.6.10 Steiner-Tree
		8.6.11 Graph-Coloring
		8.6.12 Min-Clique-Cover
		8.6.13 Other NP-hard/complete Problems
		8.6.14 Summary
	8.7 Problem Decomposition
		8.7.1 Two Components: Binary Search the Answer and Other
		8.7.2 Two Components: Involving Efficient Data Structure
		8.7.3 Two Components: Involving Geometry
		8.7.4 Two Components: Involving Graph
		8.7.5 Two Components: Involving Mathematics
		8.7.6 Two Components: Graph Preprocessing and DP
		8.7.7 Two Components: Involving 1D Static RSQ/RMQ
		8.7.8 Three (or More) Components
	8.8 Solution to Non-Starred Exercises
	8.9 Chapter Notes
9 Rare Topics
	9.1 Overview and Motivation
	9.2 Sliding Window
	9.3 Sparse Table Data Structure
	9.4 Square Root Decomposition
	9.5 Heavy-Light Decomposition
	9.6 Tower of Hanoi
	9.7 Matrix Chain Multiplication
	9.8 Lowest Common Ancestor
	9.9 Tree Isomorphism
	9.10 De Bruijn Sequence
	9.11 Fast Fourier Transform
	9.12 Pollard’s rho Algorithm
	9.13 Chinese Remainder Theorem
	9.14 Lucas’ Theorem
	9.15 Rare Formulas or Theorems
	9.16 Combinatorial Game Theory
	9.17 Gaussian Elimination Algorithm
	9.18 Art Gallery Problem
	9.19 Closest Pair Problem
	9.20 A* and IDA*: Informed Search
	9.21 Pancake Sorting
	9.22 Egg Dropping Puzzle
	9.23 Dynamic Programming Optimization
	9.24 Push-Relabel Algorithm
	9.25 Min Cost (Max) Flow
	9.26 Hopcroft-Karp Algorithm
	9.27 Kuhn-Munkres Algorithm
	9.28 Edmonds’ Matching Algorithm
	9.29 Chinese Postman Problem
	9.30 Constructive Problem
	9.31 Interactive Problem
	9.32 Linear Programming
	9.33 Gradient Descent
	9.34 Chapter Notes
Index