Competitive Programming

Number of Pages:
329+4 (Book 1) and 352+4 (Book 2)

Selling price (Printed)
Book 1: 19.99 USD (+Shipping Cost), Buy A5 Paperback
Book 2: 22.99 USD (+Shipping Cost), Buy A5 Paperback

Chapter 1: Introduction

1. Even gentler intro: C++ 17, Python 3 (NEW), Java 11, and OCaml (NEW - not used in any programming contest yet but available at Kattis; the inclusion of OCaml is due to generous sponsorship towards CP4 writing project from Tezos Southeast Asia
2. NEW: Add writeup about the two main contests supported by this book: IOI and ICPC — including tips to do well from our decades of experience
3. NEW: Introduction of Kattis online judge, on top of (UVa) online judge
4. NEW: Addition of 1783 (more than double) UVa and especially Kattis programming exercises compared to CP3, i.e., 1675 problems in CP3 compared with 3458 problems in CP4
5. NEW: To help our readers, we have selected 1 entry level (the most basic UVa or Kattis problem for that category), plus additional top 3 UVa and top 3 Kattis starred programming exercise problems (total = 7) per category, with the 'less interesting (but still good)' exercises only displayed at Methods to Solve page
6. We move basic string and simpler Ad Hoc string processing problems from Book 2 (Chapter 6) to Chapter 1 so that readers can be presented with (harder to parse/format) String I/O-related problems earlier
7. We share the most up-to-date competitive programming techniques at the time of release (year 2020, but admittedly will get less up-to-date over time)

Chapter 2: Data Structures and Libraries

1. Much closer integration with VisuAlgo; addition of Python and OCaml data structures-related libraries
2. REORGANIZATION: We move Inversion Index, Sorting in Linear Time, Bracket Matching, Postfix Conversion/Calculator, all from Book 2 (Chapter 9) to this chapter
3. REORGANIZATION: We move Big Integer from Book 2 (Chapter 5) to this chapter as linear data structure with library (for Python and Java)
4. Expanded discussion about Binary Heap, Hash Table (DAT and other proper hashing libraries), and balanced Binary Search Tree (bBST, and its versatility as powerful PQ/Tree Sort)
5. REORGANIZATION: We move Order Statistics Tree from Book 2 (Chapter 9) to this chapter as extension of bBST (and other techniques—see Fenwick Tree below)
6. NEW: using unordered_map/unordered_set more prominently
7. NEW: we expand discussion about graphs that have non-integer labels and various special graph data structures
8. REORGANIZATION + NEW: we present Fenwick Tree first before Segment Tree. For Fenwick Tree, we add order statistics, Range Update Point Query, Range Update Range Query, For Segment Tree, we add Range Update (Lazy Propagation)

Chapter 3: Problem Solving Paradigms

1. NEW: Pre-calculate answers and Try all possible answers categories added in Complete Search section; REORGANIZATION: We move Maths-related Iterative Brute Force from Book 2 (Chapter 5) to this chapter
2. REORGANIZATION: We move ternary search from Book 2 (Chapter 9) to after discussion of Binary Search the Answer (BSTA) in D&C section
3. REORGANIZATION: Greedy (bipartite) matching listed as classic greedy algorithm; NEW: We add new category: Greedy problems that involves the usage of Priority Queue for dynamic ordering
4. Enhanced presentation of 'DP' LIS using the faster O(n log k) solution and DP-TSP implementation up to n=18

Chapter 4: Graph

1. Much closer integration with VisuAlgo; addition of Python and OCaml implementation of these graph algorithms
2. REORGANIZATION: We set Kosaraju's as new default SCC finding algorithm
3. NEW: We significantly expand the Shortest Paths section to cover its many known 'classic' variants. We discuss two Dijkstra's implementations in more details
4. NEW: Basic Graph (Bipartite) Matching problem is now integrated in this chapter with details later in Chapter 8; We change Fleury's algorithm to Hierholzer's algorithm for finding Eulerian path

Chapter 5: Mathematics

1. REORGANIZATION: Ad Hoc mathematics section reorganized and expanded, e.g., discussion of Fractions-related problems
2. NEW: Number theory section significantly expanded, especially the Modular Arithmetic, Modular Multiplicative Inverse, Fermat's little theorem, Extended Euclid, Linear Diophantine Equation
3. NEW: Combinatorics expanded with modular arithmetic component
4. Floyd's cycle-finding algorithm explanation is now with VisuAlgo screenshots
5. REORGANIZATION: Matrix Power is now integrated in this chapter (from Chapter 9) and discussed in context of modular arithmetic too

Chapter 6: String Processing

1. Python is now used for various basic string processing stuffs
2. NEW: Discussion of Digit DP technique
3. Further strengthening of Trie/Suffix Trie/Tree/Array explanation
4. NEW: We add String Hashing as alternative way to solve some string-related problems
5. REORGANIZATION: We integrate discussion of two common string-related problems: anagram/palindrome with their associated techniques

Chapter 7: (Computational) Geometry

1. Further enhancement of existing library routines. Main change: The usage of Andrew's Monotone Chain convex hull algorithm on top of the improved but still longer/slower Graham's scan algorithm
2. Major rewrite of the explanations of various algorithms on polygon

Chapter 8: More Advanced Topics

1. REORGANIZATION: We move Network Flow from Book 1 (Chapter 4) to here as it is still outside the IOI syllabus and the full form of Graph Matching (from Chapter 4/9) to here before some form of matching is used in the discussion of NP-complete/hard problems
2. Expanded discussion of Network Flow topic. NEW: Dinic's algorithm (with its implementation) is now the preferred max flow algorithm instead of Edmonds Karp's algorithm
3. Graph Matching: All augmenting path based matching algorithm has randomized greedy pre-processing step upfront by default; addition of more detailed overview of weighted MCBM, unweighted MCM, and weighted MCM
4. REORGANIZATION + NEW: We discuss NP-complete decision and/or NP-hard optimization problems in competitive programming and reorganizes problems that were previously just labeled as brute force or DP problems to this category
5. NEW: Many new exercises/insights about combining problem types in the Problem Decomposition section

Chapter 9: Rare Topics

1. Even more collection of rare algorithms, data structures, and/or programming problems that have not been listed in the first eight chapters
2. NEW topics that are not in CP3: Square Root Decomposition, Heavy-Light Decomposition, Tree Isomorphism, De Bruijn Sequence, Fast Fourier Transform, Chinese Remainder Theorem, Lucas' Theorem, Combinatorial Game Theory, Egg Dropping Puzzle, Dynamic Programming Optimization, Push-Relabel algorithm, Kuhn-Munkres algorithm, Edmonds' Matching algorithm, Constructive Problem, Interactive Problems, Linear Programming, and Gradient Descent

Index

1. More collection of data structure/algorithm/competitive programming keywords for easier search
2. Listing of 3458 UVa + Kattis problems that we have solved