Competitive Programming in Python: 128 Algorithms to Develop your Coding Skills

Cover
Half-title
Title page
Copyright information
Contents
Preface
1 Introduction
	1.1 Programming Competitions
	1.2 Python in a Few Words
	1.3 Input-Output
	1.4 Complexity
	1.5 Abstract Types and Essential Data Structures
	1.6 Techniques
	1.7 Advice
	1.8 A Problem: `Frosting on the Cake\'
2 Character Strings
	2.1 Anagrams
	2.2 T9—Text on 9 Keys
	2.3 Spell Checking with a Lexicographic Tree
	2.4 Searching for Patterns
	2.5 Maximal Boundaries—Knuth–Morris–Pratt
	2.6 Pattern Matching—Rabin–Karp
	2.7 Longest Palindrome of a String—Manacher
3 Sequences
	3.1 Shortest Path in a Grid
	3.2 The Levenshtein Edit Distance
	3.3 Longest Common Subsequence
	3.4 Longest Increasing Subsequence
	3.5 Winning Strategy in a Two-Player Game
4 Arrays
	4.1 Merge of Sorted Lists
	4.2 Sum Over a Range
	4.3 Duplicates in a Range
	4.4 Maximum Subarray Sum
	4.5 Query for the Minimum of a Range—Segment Tree
	4.6 Query the Sum over a Range—Fenwick Tree
	4.7 Windows with k Distinct Elements
5 Intervals
	5.1 Interval Trees
	5.2 Union of Intervals
	5.3 The Interval Point Cover Problem
6 Graphs
	6.1 Encoding in Python
	6.2 Implicit Graphs
	6.3 Depth-First Search—DFS
	6.4 Breadth-First Search—BFS
	6.5 Connected Components
	6.6 Biconnected Components
	6.7 Topological Sort
	6.8 Strongly Connected Components
	6.9 2-Satisfiability
7 Cycles in Graphs
	7.1 Eulerian Tour
	7.2 The Chinese Postman Problem
	7.3 Cycles with Minimal Ratio of Weight to Length—Karp
	7.4 Cycles with Minimal Cost-to-Time Ratio
	7.5 Travelling Salesman
	7.6 Full Example: Menu Tour
8 Shortest Paths
	8.1 Composition Property
	8.2 Graphs with Weights 0 or 1
	8.3 Graphs with Non-negative Weights—Dijkstra
	8.4 Graphs with Arbitrary Weights—Bellman–Ford
	8.5 All Source–Destination paths—Floyd–Warshall
	8.6 Grid
	8.7 Variants
9 Matchings and Flows
	9.1 Maximum Bipartite Matching
	9.2 Maximal-Weight Perfect Matching—Kuhn–Munkres
	9.3 Planar Matching without Crossings
	9.4 Stable Marriages—Gale–Shapley
	9.5 Maximum Flow by Ford–Fulkerson
	9.6 Maximum Flow by Edmonds–Karp
	9.7 Maximum Flow by Dinic
	9.8 Minimum s-t Cut
	9.9 s-t Minimum Cut for Planar Graphs
	9.10 A Transport Problem
	9.11 Reductions between Matchings and Flows
	9.12 Width of a Partial Order—Dilworth
10 Trees
	10.1 Huffman Coding
	10.2 Lowest Common Ancestor
	10.3 Longest Path in a Tree
	10.4 Minimum Weight Spanning Tree—Kruskal
11 Sets
	11.1 The Knapsack Problem
	11.2 Making Change
	11.3 Subset Sum
	11.4 The k-sum Problem
12 Points and Polygons
	12.1 Convex Hull
	12.2 Measures of a Polygon
	12.3 Closest Pair of Points
	12.4 Simple Rectilinear Polygon
13 Rectangles
	13.1 Forming Rectangles
	13.2 Largest Square in a Grid
	13.3 Largest Rectangle in a Histogram
	13.4 Largest Rectangle in a Grid
	13.5 Union of Rectangles
	13.6 Union of Disjoint Rectangles
14 Numbers and Matrices
	14.1 GCD
	14.2 Bézout Coefficients
	14.3 Binomial Coefficients
	14.4 Fast Exponentiation
	14.5 Prime Numbers
	14.6 Evaluate an Arithmetical Expression
	14.7 System of Linear Equations
	14.8 Multiplication of a Matrix Sequence
15 Exhaustive Search
	15.1 All Paths for a Laser
	15.2 The Exact Cover Problem
	15.3 Problems
	15.4 Sudoku
	15.5 Enumeration of Permutations
	15.6 Le Compte est Bon
16 Conclusion
	16.1 Combine Algorithms to Solve a Problem
	16.2 For Further Reading
	16.3 Rendez-vous on tryalgo.org
Debugging tool
References
Index