Introduction............................................. 1
1.1 What is Competitive Programming? ...................... 1
1.1.1 Programming
... [Show More] Contests.......................... 2
1.1.2 Tips for Practicing............................. 3
1.2 About This Book .................................... 3
1.3 CSES Problem Set ................................... 5
1.4 Other Resources ..................................... 7
2 Programming Techniques.................................. 9
2.1 Language Features ................................... 9
2.1.1 Input and Output .............................. 10
2.1.2 Working with Numbers......................... 12
2.1.3 Shortening Code .............................. 14
2.2 Recursive Algorithms ................................. 15
2.2.1 Generating Subsets ............................ 15
2.2.2 Generating Permutations ........................ 16
2.2.3 Backtracking ................................. 18
2.3 Bit Manipulation..................................... 20
2.3.1 Bit Operations ................................ 21
2.3.2 Representing Sets ............................. 23
3 Efficiency ............................................... 27
3.1 Time Complexity .................................... 27
3.1.1 Calculation Rules ............................. 27
3.1.2 Common Time Complexities..................... 30
3.1.3 Estimating Efficiency........................... 31
3.1.4 Formal Definitions............................. 32
3.2 Examples .......................................... 32
3.2.1 Maximum Subarray Sum........................ 32
3.2.2 Two Queens Problem .......................... 35
4 Sorting and Searching..................................... 37
4.1 Sorting Algorithms ................................... 37
4.1.1 Bubble Sort ...............
4.1.2 Merge Sort .................................. 39
4.1.3 Sorting Lower Bound .......................... 40
4.1.4 Counting Sort ................................ 41
4.1.5 Sorting in Practice ............................. 41
4.2 Solving Problems by Sorting ........................... 43
4.2.1 Sweep Line Algorithms......................... 44
4.2.2 Scheduling Events............................. 45
4.2.3 Tasks and Deadlines ........................... 45
4.3 Binary Search ....................................... 46
4.3.1 Implementing the Search ........................ 47
4.3.2 Finding Optimal Solutions....................... 48
5 Data Structures .......................................... 51
5.1 Dynamic Arrays ..................................... 51
5.1.1 Vectors ..................................... 52
5.1.2 Iterators and Ranges ........................... 53
5.1.3 Other Structures............................... 54
5.2 Set Structures ....................................... 55
5.2.1 Sets and Multisets ............................. 55
5.2.2 Maps ....................................... 57
5.2.3 Priority Queues ............................... 58
5.2.4 Policy-Based Sets ............................. 59
5.3 Experiments ........................................ 60
5.3.1 Set Versus Sorting............................. 60
5.3.2 Map Versus Array ............................. 61
5.3.3 Priority Queue Versus Multiset ................... 62
6 Dynamic Programming .................................... 63
6.1 Basic Concepts ...................................... 63
6.1.1 When Greedy Fails ............................ 63
6.1.2 Finding an Optimal Solution ..................... 64
6.1.3 Counting Solutions ............................ 67
6.2 Further Examples .................................... 68
6.2.1 Longest Increasing Subsequence .................. 69
6.2.2 Paths in a Grid ............................... 70
6.2.3 Knapsack Problems ............................ 71
6.2.4 From Permutations to Subsets .................... 72
6.2.5 Counting Tilings .............................. 74
7 Graph Algorithms ........................................ 77
7.1 Basics of Graphs..................................... 78
7.1.1 Graph Terminology ............................ 78
7.1.2 Graph Representation .......................... 80
7.2 Graph Traversal ..................................... 83
7.2.1 Depth-First Search..
Breadth-First Search ........................... 85
7.2.3 Applications ................................. 86
7.3 Shortest Paths....................................... 87
7.3.1 Bellman–Ford Algorithm........................ 88
7.3.2 Dijkstra’s Algorithm ........................... 89
7.3.3 Floyd–Warshall Algorithm ...................... 92
7.4 Directed Acyclic Graphs............................... 94
7.4.1 Topological Sorting ............................ 94
7.4.2 Dynamic Programming ......................... 96
7.5 Successor Graphs .................................... 97
7.5.1 Finding Successors ............................ 98
7.5.2 Cycle Detection ............................... 99
7.6 Minimum Spanning Trees.............................. 100
7.6.1 Kruskal’s Algorithm ........................... 101
7.6.2 Union-Find Structure ........................... 103
7.6.3 Prim’s Algorithm.............................. 106
8 Algorithm Design Topics................................... 107
8.1 Bit-Parallel Algorithms................................ 107
8.1.1 Hamming Distances............................ 107
8.1.2 Counting Subgrids............................. 108
8.1.3 Reachability in Graphs ......................... 110
8.2 Amortized Analysis .................................. 111
8.2.1 Two Pointers Method .......................... 111
8.2.2 Nearest Smaller Elements ....................... 113
8.2.3 Sliding Window Minimum ...................... 114
8.3 Finding Minimum Values.............................. 115
8.3.1 Ternary Search ............................... 115
8.3.2 Convex Functions ............................. 116
8.3.3 Minimizing Sums ............................. 117
9 Range Queries ........................................... 119
9.1 Queries on Static Arrays............................... 119
9.1.1 Sum Queries ................................. 120
9.1.2 Minimum Queries ............................. 121
9.2 Tree Structures ...................................... 122
9.2.1 Binary Indexed Trees .......................... 122
9.2.2 Segment Trees................................ 125
9.2.3 Additional Techniques.......................... 128
10 Tree Algorithms ......................................... 131
10.1 Basic Techniques .................................... 131
10.1.1 Tree Traversal ................................ 132
10.1.2 Calculating Diameters .......................... 134
10.1.3 All Longest Paths ... [Show Less]