Our objective in writing this book is similar with the ICPC vision: To further improve humanity by training current students to be more competitive in programming contests. The possible long term effect is future Computer Science researchers who are well versed in problem solving skills. Target audience: The reader must have some background knowledge in basic data structures,
algorithms, and programming languages. Typically, a 2nd year Computer
Science students in a University (who have passed a kind of "programming
methodology" and "basic data structures and algorithms" modules) or
selected high school students who are preparing for National or
International Olympiad in Informatics (and thus have done self-study on year-1 University CS curriculum) should have the necessary
background. In the second edition of the book, we use both C++ and Java
codes to illustrate the concepts.
"I cannot imagine a better complement for the UVa Online Judge site" -- Miguel A. Revilla, UVa Online Judge site creator, ACM-ICPC Problem Archivist
"Competitive Programming is a unique resource that I recommend to any
student interested in raising their algorithmic programming skills to
the next level. It is packed with insightful tips and techniques that
are hard to find elsewhere, and remarkably thorough in its use of
examples and references to sample problems." -- Brian C. Dean, Associate Director, USA Computing Olympiad New URL: http://www.lulu.com/spotlight/stevenhalimatgmaildotcom
Visualization of various algorithms in CP2: http://www.comp.nus.edu.sg/~stevenha/visualization Breaking news (24 May 2012): A large (A4) edition of CP2 has just been released @ lulu,
Steven has also decided that CP3 (406 :O A5 pages at the moment) will have a self-imposed deadline of 24 May 2013 (exactly one year from now).
About the Book:
|
Item |
First Edition
|
Second Edition (A5)
|
Second & Large Edition (A4)
|
Number of Pages
|
152 (76 double-sided A4 sheets + 4 pages cover)
|
262 (131 double-sided A5 sheets + 4 pages cover)
|
| Total Chapters
| 7 | 8 | |
Sample Pages
|
Click this link (23 from 152 pages) |
Click this link (27 from 262 pages) |
| Errata & plan for the next edition
| Errata of 1st edition and plan for the 2nd edition | Errata of 2nd edition and plan for the 3rd edition | |
Selling Price (Printed)
|
18.05 USD (now 16.25 USD + shipping cost)
Buy the 1st
edition
|
22.24 USD (+ shipping cost)
Buy the 2nd edition
Note: lulu only accepts PayPal, MasterCard, Visa,
Discover, American Express.
You need to have one of these to buy online from lulu.
|
24.55 USD (+ shipping cost)
Buy the 2nd and large edition
There is NO difference between this A4 (large)
and A5 (small) versions. This large edition is
released to serve the needs of some readers
who have difficulties with small font size.
CP3 will be in A5 size again but with larger
font size and larger figures.
|
| Selling Price (eBook) |
just 14.87 USD
|
N/A
|
N/A |
Printed Version Release Date
|
Monday, 9 August 2010, before IOI 2010
|
Monday, 1 August 2011, after IOI 2011
|
Thursday, 24 May 2012, the day Steven turned 30
|
eBook Version Release Date
|
Saturday, 16 July 2011
|
Confirmed: 31 December 2012 :)
|
31 December 2012 too
|
100 copies mark
|
Tuesday, 30 November 2010 (~ 113 days after release) | Thursday, 11 August 2011 (11 days after release) :D
|
|
Sales Status
|
|
Very good :)
Start off with 23 copies sold during IOI 2011 :)
Exactly 200 copies sold @ lulu on 16/10/2011,
(about 2.5 months since release date :D)
Another 364 copies sold @ lulu up to 03/05/2012,
~125 copies sold locally @ NUS, Singapore so far.
~100 copies is printed by TOKI for OSN 2011.
26 copies sold in ICPC Phuket + KL 2011.
19 copies sold/given in ICPC WF Warsaw 2012.
so, 857 copies have been circulating so far :O,
and counting...
CP2 sales has reached > 550 copies mark, thanks :D
Now looking forward to the day it reaches 1000 copies
At 2 books/day, 1K should be reachable in 2/3 months
|
|
Table of Contents:
| Chapter |
Title |
First Edition
|
Second Edition
|
Plan for the Third Edition
(will not appear until 24 May 2013
a self imposed deadline for this project)
|
| 1 |
Introduction
|
- Introducing the world of Competitive Programming
- Tips to be a competitive programmer, shared by us who were
IOI & ICPC contestants in the past and now are coaches
- Collection of (easy-medium) Ad Hoc problems to start your journey
|
- Collection of hundreds more Ad Hoc problems with hints to kick start your training programme.
- More contest-related exercises :)
- More persuasive writing that the world of competitive programming is fun
- More balanced viewpoint: C++ vs Java, ICPC vs IOI.
- Lots of footnotes in the second edition that gives more insights on the stuffs being discussed in the body text.
|
- A gentler intro: Anatomy of programming contest problem; Parsing Input/Formatting Output for beginners; Common errors; Common shortcut tricks.
|
| 2 |
Data Structures and Libraries |
- Are you aware that many DS have built-in libraries?
Do you use them often?
- Are you aware that there are many other useful DS out there without built-in libraries as of 2010?
|
- New: 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
- New: Short discussion on implicit graph
- New: Fenwick Tree (Binary Indexed Tree), uses bit manipulation
- More conceptual exercises
|
- NEW: Deque
- NEW: Many written exercises about basic data structures from Steven's other course in SoC, NUS.
|
| 3 |
Problem Solving Paradigms |
- Do you hammer every contest problem with brute force?
- Are you sure that you are familiar with these terms:
- Complete Search that is not that brute... Master the art of search space reduction...
- Divide and Conquer (D&C)... Master the art of using binary search principle...
- Greedy... Increase your aptitude towards problems solvable with greedy technique...
- Dynamic Programming (DP)... Master one of the most useful technique in the world of Competitive Programming...
|
- More speed up tips to improve your solution (thanks to nhahtdh),
(especially the brute force solution)
- More Divide and Conquer examples,
clearer explanation of "binary search the answer" technique
- More Greedy example: interval covering problem.
- Clearer explanation of DP technique: the steps required to come up with a DP solution, especially the bottom-up version
- Reconstructing the optimal DP solution
- O(n log k) solution for LIS problem
- 0-1 Knapsack/Subset Sum
- DP TSP (bitmask technique again)
|
- NEW: iterative solution for subset and permutation problems
|
| 4 |
Graph |
- Graph Traversals, Min Spanning Trees, Shortest Paths, Max Flow
- Special Graphs (our highlight, this section usually does not exist in other algorithm books)
|
- Reorganization of graph sections (more reader friendly now)
- Prim's algorithm, Minimax/Maximin problem
- Clearer explanation of the 'TopCoder' style Dijkstra's implementation
- More application of Floyd Warshall's algorithm: Arbitrage
- Clearer explanation of Edmonds Karp's max flow algorithm
- Training to identify the flow graph of a problem solvable with max flow
- DP as a traversal of (implicit) DAG
- One more special graph: Eulerian Graph
- Augmenting Path Bipartite Matching algorithm
- A chapter with lots of short profiles of algorithm inventors (new feature of this book)
|
|
5
|
Mathematics |
- Number Theory, Big Integer, and many more topics in mathematics that are frequently appear in programming contests
|
- Much more mathematics problems
- Combinatorics section expanded: Binomial Coefficients, Catalan Numbers, principle of counting
- More emphasis on the 3 important methods for dealing with large computations: BigInteger, prime power, or modulo arithmetic.
- More discussion on Floyd's cycle finding algorithm
- Game Theory (new section)
- Powers of a (Square) Matrix (new section), can be applied to DP too
|
|
| 6 |
String Processing |
- Ad Hoc string problems,
- String problems solvable with DP,
-
Large string problems that must be solved with efficient DS: Suffix Tree/Array
|
- Basic string processing skills (new section)
- Much more string problems + categorization
- String matching: KMP, matching on 2D grid
- Enhanced explanation of Suffix Trie, Tree, and Array
|
|
7
|
(Computational) Geometry |
- Library of "Geometry Basics", Convex Hull, Intersection Problems, D&C in Geometry Problems
|
- Expanded libraries, especially on points, lines and polygons
- New: inPolygon, cutPolygon routines
- Clearer explanation of Graham's scan convex hull algorithm
|
|
| 8 |
More Advanced Techniques
|
|
- Problem Decomposition: 2 components, 3 components...
- More advanced search techniques: A*, Depth Limited Search, Iterative Deepening Search, Iterative Deepening A*
- More advanced DP: bitmask technique, compilation of common DP states, better state representation, etc
|
- Reorder the sections so that the more advanced search and DP techniques are listed before problem decomposition (as it may involve those advanced search/DP techniques)
- NEW: Meet in the middle
| | 9 | Rare Algorithms
| | | - Collection of (many) rare algorithms that have not been listed in the first eight chapters
|
Appendix A
|
Hints/Brief Solutions
|
|
- Lots of conceptual exercises scattered throughout the book
|
- N/A again; the solutions for non-starred written exercises are listed at the back of each section now for easier access.
| |
|
|
- Steven's Methods to Solve is now integrated in the second edition
- 1198 UVa problems are listed, 600 more than the 1st edition. Getting more than 1000 problems AC is no longer a wild dream.
|
- Discussion of at least 2000 UVa problems by the time CP3 is released
|
Note: All data structure and algorithm discussions come with practical implementations and lots of programming exercises. :)
|
