Competitive Programming 4 - Book 1

CP4: Book 1
Contents
1 Introduction
	1.1 Competitive Programming
	1.2 The Competitions
		1.2.1 International Olympiad in Informatics (IOI)
		1.2.2 International Collegiate Programming Contests (ICPC)
		1.2.3 Other Programming Contests
	1.3 Tips to be Competitive
		1.3.1 Tip 1: Type Code Faster!
		1.3.2 Tip 2: Quickly Identify Problem Types
		1.3.3 Tip 3: Do Algorithm Analysis
		1.3.4 Tip 4: Master Programming Languages
		1.3.5 Tip 5: Master the Art of Testing Code
		1.3.6 Tip 6: Practice and More Practice
		1.3.7 Tip 7: Team Work (for ICPC)
	1.4 Getting Started: The Easy Problems
		1.4.1 Anatomy of a Programming Contest Problem
		1.4.2 Typical Input/Output Routines
		1.4.3 Time to Start the Journey
		1.4.4 Getting Our First Accepted (AC) Verdict
	1.5 Basic String Processing Skills
	1.6 The Ad Hoc Problems
	1.7 Solutions to Non-Starred Exercises
	1.8 Chapter Notes
2 Data Structures and Libraries
	2.1 Overview and Motivation
	2.2 Linear DS with Built-in Libraries
		2.2.1 Array
		2.2.2 Special Sorting Problems
		2.2.3 Bitmask
		2.2.4 Big Integer (Python & Java)
		2.2.5 Linked Data Structures
		2.2.6 Special Stack-based Problems
	2.3 Non-Linear DS with Built-in Libraries
		2.3.1 Binary Heap (Priority Queue)
		2.3.2 Hash Table
		2.3.3 Balanced Binary Search Tree (bBST)
		2.3.4 Order Statistics Tree
	2.4 DS with Our Own Libraries
		2.4.1 Graph
		2.4.2 Union-Find Disjoint Sets
		2.4.3 Fenwick (Binary Indexed) Tree
		2.4.4 Segment Tree
	2.5 Solution to Non-Starred Exercises
	2.6 Chapter Notes
3 Problem Solving Paradigms
	3.1 Overview and Motivation
	3.2 Complete Search
		3.2.1 Iterative Complete Search
		3.2.2 Recursive Complete Search
		3.2.3 Complete Search Tips
		3.2.4 Complete Search in Programming Contests
	3.3 Divide and Conquer
		3.3.1 Interesting Usages of Binary Search
		3.3.2 Ternary Search
		3.3.3 Divide and Conquer in Programming Contests
	3.4 Greedy
		3.4.1 Examples
		3.4.2 Greedy Algorithm in Programming Contests
	3.5 Dynamic Programming
		3.5.1 DP Illustration
		3.5.2 Classical Examples
		3.5.3 Non-Classical Examples
		3.5.4 Dynamic Programming in Programming Contests
	3.6 Solution to Non-Starred Exercises
	3.7 Chapter Notes
4 Graph
	4.1 Overview and Motivation
	4.2 Graph Traversal
		4.2.1 Overview and Motivation
		4.2.2 Depth First Search (DFS)
		4.2.3 Breadth First Search (BFS)
		4.2.4 Finding Connected Components (Undirected Graph)
		4.2.5 Flood Fill (Implicit 2D Grid Graph)
		4.2.6 Topological Sort (Directed Acyclic Graph)
		4.2.7 Bipartite Graph Check (Undirected Graph)
		4.2.8 Cycle Check (Directed Graph)
		4.2.9 Finding Articulation Points and Bridges (Undirected Graph)
		4.2.10 Finding Strongly Connected Components (Directed Graph)
		4.2.11 Graph Traversal in Programming Contests
	4.3 Minimum Spanning Tree (MST)
		4.3.1 Overview and Motivation
		4.3.2 Kruskal’s Algorithm
		4.3.3 Prim’s Algorithm
		4.3.4 Other Applications
		4.3.5 MST in Programming Contests
	4.4 Single-Source Shortest Paths (SSSP)
		4.4.1 Overview and Motivation
		4.4.2 On Unweighted Graph: BFS
		4.4.3 On Weighted Graph: Dijkstra’s
		4.4.4 On Small Graph (with Negative Cycle): Bellman-Ford
		4.4.5 SSSP in Programming Contests
	4.5 All-Pairs Shortest Paths (APSP)
		4.5.1 Overview and Motivation
		4.5.2 Floyd-Warshall Algorithm
		4.5.3 Other Applications
		4.5.4 APSP in Programming Contests
	4.6 Special Graphs
		4.6.1 Directed Acyclic Graph
		4.6.2 Tree
		4.6.3 Bipartite Graph
		4.6.4 Eulerian Graph
		4.6.5 Special Graphs in Programming Contests
	4.7 Solution to Non-Starred Exercises
	4.8 Chapter Notes
Index