Competitive Programming

Number of Pages:
262+4 (cover)

Selling price (Printed)
This project has been retired

Chapter 1: Introduction

1. Collection of hundreds more Ad Hoc problems with hints to kick start your training programme
2. More contest-related exercises :)
3. More persuasive writing that the world of competitive programming is fun
4. More balanced viewpoint: C++ vs Java, ICPC vs IOI
5. Lots of footnotes in the second edition that gives more insights on the stuffs being discussed in the body text

Chapter 2: Data Structures and Libraries

1. NEW in 2011: Discussion of lightweight set of Boolean (bitmask technique). This technique is important for competitive programmers and will be used several times in various sections of this book
2. NEW in 2011: Short discussion on implicit graph
3. NEW in 2011: Fenwick Tree (Binary Indexed Tree), uses bit manipulation
4. More conceptual exercises

Chapter 3: Problem Solving Paradigms

1. More speed up tips to improve your solution, (especially the brute force solution)
2. More Divide and Conquer examples, clearer explanation of 'Binary Search the Answer' technique
3. More Greedy example: interval covering problem
4. Clearer explanation of DP technique: the steps required to come up with a DP solution, especially the bottom-up version
5. Reconstructing the optimal DP solution
6. O(n log k) solution for LIS problem
7. 0-1 Knapsack/Subset Sum
8. DP TSP (bitmask technique again)

Chapter 4: Graph

1. Reorganization of graph sections (more reader friendly now)
2. Prim's algorithm, Minimax/Maximin problem
3. Clearer explanation of the 'TopCoder' style Dijkstra's implementation
4. More application of Floyd-Warshall algorithm: Arbitrage
5. Clearer explanation of Edmonds-Karp max flow algorithm
6. Training to identify the flow graph of a problem solvable with max flow
7. DP as a traversal of (implicit) DAG
8. One more special graph: Eulerian Graph
9. Augmenting Path Bipartite Matching algorithm
10. A chapter with lots of short profiles of algorithm inventors (new feature of this book)

Chapter 5: Mathematics

1. Much more mathematics problems
2. Combinatorics section expanded: Binomial Coefficients, Catalan Numbers, principle of counting
3. More emphasis on the 3 important methods for dealing with large computations: BigInteger, prime power, or modulo arithmetic
4. More discussion on Floyd's cycle finding algorithm
5. NEW in 2011: Game Theory
6. NEW in 2011: Powers of a (Square) Matrix, can be applied to DP too

Chapter 6: String Processing

1. Basic string processing skills (new section)
2. Much more string problems + categorization
3. String matching: KMP, matching on 2D grid
4. Enhanced explanation of Suffix Trie, Tree, and Array

Chapter 7: (Computational) Geometry

1. Expanded libraries, especially on points, lines and polygons
2. NEW in 2011: inPolygon, cutPolygon routines
3. Clearer explanation of Graham's scan convex hull algorithm

Chapter 8: More Advanced Topics

1. Problem Decomposition: 2 components, 3 components...
2. More advanced search techniques: A*, Depth Limited Search, Iterative Deepening Search, Iterative Deepening A*
3. More advanced DP: bitmask technique, compilation of common DP states, better state representation, etc

Index

1. Steven's Methods to Solve is now integrated in the second edition
2. 1198 UVa problems are listed, 600 more than the 1st edition. Getting more than 1000 problems AC is no longer a wild dream