Guide to Competitive Programming: Learning and Improving Algorithms Through Contests

✍ Scribed by Antti Laaksonen

• Publisher: Springer
• Year: 2018
• Tongue: English
• Leaves: 286
• Category: Library

✦ Synopsis

This invaluable textbook presents a comprehensive introduction to modern competitive programming. The text highlights how competitive programming has proven to be an excellent way to learn algorithms, by encouraging the design of algorithms that actually work, stimulating the improvement of programming and debugging skills, and reinforcing the type of thinking required to solve problems in a competitive setting. The book contains many "folklore" algorithm design tricks that are known by experienced competitive programmers, yet which have previously only been formally discussed in online forums and blog posts.



Topics and features: reviews the features of the C++ programming language, and describes how to create efficient algorithms that can quickly process large data sets; discusses sorting algorithms and binary search, and examines a selection of data structures of the C++ standard library; introduces the algorithm design technique of dynamic programming, and investigates elementary graph algorithms; covers such advanced algorithm design topics as bit-parallelism and amortized analysis, and presents a focus on efficiently processing array range queries; surveys specialized algorithms for trees, and discusses the mathematical topics that are relevant in competitive programming; examines advanced graph techniques, geometric algorithms, and string techniques; describes a selection of more advanced topics, including square root algorithms and dynamic programming optimization.





This easy-to-follow guide is an ideal reference for all students wishing to learn algorithms, and practice for programming contests. Knowledge of the basics of programming is assumed, but previous background in algorithm design or programming contests is not necessary. Due to the broad range of topics covered at various levels of difficulty, this book is suitable for both beginners and more experienced readers.

✦ Table of Contents

Preface......Page 6
Contents......Page 8
1.1 What is Competitive Programming?......Page 14
1.1.1 Programming Contests......Page 15
1.2 About This Book......Page 16
1.3 CSES Problem Set......Page 18
1.4 Other Resources......Page 20
2.1 Language Features......Page 21
2.1.1 Input and Output......Page 22
2.1.2 Working with Numbers......Page 24
2.1.3 Shortening Code......Page 26
2.2.1 Generating Subsets......Page 27
2.2.2 Generating Permutations......Page 28
2.2.3 Backtracking......Page 30
2.3 Bit Manipulation......Page 31
2.3.1 Bit Operations......Page 33
2.3.2 Representing Sets......Page 35
3.1.1 Calculation Rules......Page 38
3.1.2 Common Time Complexities......Page 41
3.1.3 Estimating Efficiency......Page 42
3.2.1 Maximum Subarray Sum......Page 43
3.2.2 Two Queens Problem......Page 46
4.1 Sorting Algorithms......Page 48
4.1.1 Bubble Sort......Page 49
4.1.2 Merge Sort......Page 50
4.1.3 Sorting Lower Bound......Page 51
4.1.5 Sorting in Practice......Page 52
4.2 Solving Problems by Sorting......Page 54
4.2.1 Sweep Line Algorithms......Page 55
4.2.3 Tasks and Deadlines......Page 56
4.3 Binary Search......Page 57
4.3.1 Implementing the Search......Page 58
4.3.2 Finding Optimal Solutions......Page 59
5.1 Dynamic Arrays......Page 61
5.1.1 Vectors......Page 62
5.1.2 Iterators and Ranges......Page 63
5.1.3 Other Structures......Page 64
5.2.1 Sets and Multisets......Page 65
5.2.2 Maps......Page 67
5.2.3 Priority Queues......Page 68
5.2.4 Policy-Based Sets......Page 69
5.3.1 Set Versus Sorting......Page 70
5.3.2 Map Versus Array......Page 71
5.3.3 Priority Queue Versus Multiset......Page 72
6.1.1 When Greedy Fails......Page 73
6.1.2 Finding an Optimal Solution......Page 74
6.1.3 Counting Solutions......Page 77
6.2 Further Examples......Page 78
6.2.1 Longest Increasing Subsequence......Page 79
6.2.2 Paths in a Grid......Page 80
6.2.3 Knapsack Problems......Page 81
6.2.4 From Permutations to Subsets......Page 82
6.2.5 Counting Tilings......Page 84
7.1 Basics of Graphs......Page 86
7.1.1 Graph Terminology......Page 87
7.1.2 Graph Representation......Page 89
7.2.1 Depth-First Search......Page 92
7.2.2 Breadth-First Search......Page 94
7.2.3 Applications......Page 95
7.3 Shortest Paths......Page 96
7.3.1 Bellman--Ford Algorithm......Page 97
7.3.2 Dijkstra's Algorithm......Page 98
7.3.3 Floyd--Warshall Algorithm......Page 101
7.4.1 Topological Sorting......Page 103
7.4.2 Dynamic Programming......Page 105
7.5 Successor Graphs......Page 106
7.5.1 Finding Successors......Page 107
7.5.2 Cycle Detection......Page 108
7.6 Minimum Spanning Trees......Page 109
7.6.1 Kruskal's Algorithm......Page 110
7.6.2 Union-Find Structure......Page 112
7.6.3 Prim's Algorithm......Page 115
8.1.1 Hamming Distances......Page 116
8.1.2 Counting Subgrids......Page 117
8.1.3 Reachability in Graphs......Page 119
8.2.1 Two Pointers Method......Page 120
8.2.2 Nearest Smaller Elements......Page 122
8.2.3 Sliding Window Minimum......Page 123
8.3.1 Ternary Search......Page 124
8.3.2 Convex Functions......Page 125
8.3.3 Minimizing Sums......Page 126
9.1 Queries on Static Arrays......Page 127
9.1.1 Sum Queries......Page 128
9.1.2 Minimum Queries......Page 129
9.2.1 Binary Indexed Trees......Page 130
9.2.2 Segment Trees......Page 133
9.2.3 Additional Techniques......Page 136
10.1 Basic Techniques......Page 138
10.1.1 Tree Traversal......Page 139
10.1.2 Calculating Diameters......Page 141
10.1.3 All Longest Paths......Page 142
10.2.1 Finding Ancestors......Page 144
10.2.2 Subtrees and Paths......Page 145
10.2.3 Lowest Common Ancestors......Page 147
10.2.4 Merging Data Structures......Page 149
10.3.1 Centroid Decomposition......Page 151
10.3.2 Heavy-Light Decomposition......Page 152
11.1 Number Theory......Page 154
11.1.1 Primes and Factors......Page 155
11.1.2 Sieve of Eratosthenes......Page 157
11.1.3 Euclid's Algorithm......Page 158
11.1.5 Euler's Theorem......Page 160
11.1.6 Solving Equations......Page 162
11.2 Combinatorics......Page 163
11.2.1 Binomial Coefficients......Page 164
11.2.2 Catalan Numbers......Page 166
11.2.3 Inclusion-Exclusion......Page 168
11.2.4 Burnside's Lemma......Page 170
11.3 Matrices......Page 171
11.3.1 Matrix Operations......Page 172
11.3.2 Linear Recurrences......Page 174
11.3.3 Graphs and Matrices......Page 176
11.3.4 Gaussian Elimination......Page 177
11.4 Probability......Page 180
11.4.1 Working with Events......Page 181
11.4.2 Random Variables......Page 182
11.4.3 Markov Chains......Page 185
11.4.4 Randomized Algorithms......Page 186
11.5.1 Game States......Page 188
11.5.2 Nim Game......Page 189
11.5.3 Sprague--Grundy Theorem......Page 191
12.1 Strong Connectivity......Page 195
12.1.1 Kosaraju's Algorithm......Page 196
12.1.2 2SAT Problem......Page 198
12.2 Complete Paths......Page 199
12.2.1 Eulerian Paths......Page 200
12.2.2 Hamiltonian Paths......Page 201
12.2.3 Applications......Page 202
12.3 Maximum Flows......Page 204
12.3.1 Ford--Fulkerson Algorithm......Page 205
12.3.2 Disjoint Paths......Page 208
12.3.3 Maximum Matchings......Page 209
12.3.4 Path Covers......Page 211
12.4.1 Biconnectivity......Page 213
12.4.2 Eulerian Subgraphs......Page 215
13.1.1 Complex Numbers......Page 216
13.1.2 Points and Lines......Page 218
13.1.3 Polygon Area......Page 221
13.1.4 Distance Functions......Page 223
13.2.1 Intersection Points......Page 225
13.2.2 Closest Pair Problem......Page 226
13.2.3 Convex Hull Problem......Page 229
14.1 Basic Topics......Page 230
14.1.1 Trie Structure......Page 231
14.1.2 Dynamic Programming......Page 232
14.2.1 Polynomial Hashing......Page 233
14.2.2 Applications......Page 234
14.2.3 Collisions and Parameters......Page 235
14.3 Z-Algorithm......Page 236
14.3.1 Constructing the Z-Array......Page 237
14.3.2 Applications......Page 238
14.4 Suffix Arrays......Page 239
14.4.1 Prefix Doubling Method......Page 240
14.4.3 LCP Arrays......Page 241
15.1 Square Root Techniques......Page 243
15.1.1 Data Structures......Page 244
15.1.2 Subalgorithms......Page 245
15.1.3 Integer Partitions......Page 247
15.1.4 Mo's Algorithm......Page 248
15.2 Segment Trees Revisited......Page 249
15.2.1 Lazy Propagation......Page 250
15.2.2 Dynamic Trees......Page 253
15.2.3 Data Structures in Nodes......Page 255
15.3.1 Splitting and Merging......Page 257
15.3.2 Implementation......Page 259
15.3.3 Additional Techniques......Page 261
15.4.1 Convex Hull Trick......Page 262
15.4.2 Divide and Conquer Optimization......Page 264
15.4.3 Knuth's Optimization......Page 265
15.5 Miscellaneous......Page 266
15.5.2 Counting Subsets......Page 267
15.5.3 Parallel Binary Search......Page 269
15.5.4 Dynamic Connectivity......Page 270
Sum Formulas......Page 273
Sets......Page 275
Logic......Page 276
Functions......Page 277
Number Systems......Page 278
References......Page 280
Index......Page 282