Competitive Programming
While we strive to minimize the number of errors in the book, it is near impossible to have 0 error in a 681 pages Book 1+2 despite multiple re-reads by 20+ beta-readers.
Here is the list of known (minor) issues that are found after Sunday, 19 July 2020 initial release, ordered by severity, then by page numbers (tap the page number column if you view this page on a small screen for the full details).
Abbreviations used: S(everity: 3-extremely serious error/2-major error/1-minor grammatical or typographical error), B(ook 1 or 2), C(hapter 0/Preface, 1-9), P(age number), Pos(ition in the page), Ex(ercise), Fig(ure).
This list is last updated on Fri, 13 Jan 2023, ~3.51pm SGT.
Steven expects that this list should not grow that fast and will eventually 'stop' being updated anymore :).
However, if you spot any issue that is not already compiled below, please drop an email to Steven (stevenhalim at gmail dot com) with similar format as shown below.
| P | S | B | C | Pos | The "Error" | The Fix |
|---|---|---|---|---|---|---|
| 0-ix | 1 | 1 | 0-P | middle | "...of is teaching job..." | "...of his teaching job..." |
| 0-xxi | 1 | 1 | 0-P | middle | "...its basic form is much |
"...its basic form is much easier..." |
| 0-xix | 1 | 1 | 0-P | middle | The achievement info will always be out of date over time | See this instead |
| 15 | 1 | 1 | 1 | footnote 26 | Java is dropped after IOI 2020, Singapore (Online) | Focus on C++ and Python for CP in the 2020s |
| 17 | 1 | 1 | 1 | Ex 1.3.4.1, Q5 | There is a shorter Python answer | Add "Using C++, " |
| 20 | 2 | 1 | 1 | Ex 1.3.5.2, Q4+Q5 | 4 occurrences of \\n triggers 4 LaTeX new line commands | Ignore those 4 new lines |
| 27 | 2 | 1 | 1 | Take 1 | "...a > 1, b > 1, c > 1..." | "...a ≥ 1, b ≥ 1, c ≥ 1..." (as shown in the code) |
| 34 | 1 | 1 | 1 | Roman Numerals | "...uses |
"...uses certain letters..." |
| 41 | 1 | 1 | 1 | Ex 1.3.2.1 | Dragon of Loowater; Greedy ( |
Dragon of Loowater; Greedy (Classical) — this is classic in the 2020s |
| 42 | 2 | 1 | 1 | Task 4 | The tokens (integers) are sorted as strings | Add ", key=int" so that the tokens are sorted as integers |
| 42 | 2 | 1 | 1 | Task 6 | L[] = {10, 7, 5, 20, 8} is unsorted, but L is guaranteed to be sorted | sort it, i.e., L[] = {5, 7, 8, 10, 20} and remove the sort routine |
| 43 | 2 | 1 | 1 | Task 8 | printf("%d ", __builtin_ctz(ls)); | printf("%d ", __builtin_ctz(ls)+1); // 1-based output |
| 45 | 1 | 1 | 1 | Ex 1.3.5.2, task 2 | "...use __builtin_ctzl(v)..."; (1 'l' = unsigned long) | "...use __builtin_ctzll(v)..."; (2 'l's = unsigned long long, safer) |
| 69 | 3 | 1 | 2 | Top+Bottom | Python list is not really a Linked List | Just use Python deque as queue to get O(1) popleft() |
| 82 | 2 | 1 | 2 | Bottom | "/month ([0.. |
Change it to "/month ([0..27/28/29/30])..." |
| 86 | 1 | 1 | 2 | Ex 2.3.3.2 | "...support |
"...support these..." |
| 87 | 1 | 1 | 2 | O(n^2) algorithm | "...is to this: find ..." | "...is to do this: find ..." |
| 105 | 1 | 1 | 2 | Top | "...the operation ((S) & (-S)) produces..." | "...the operation ((S) & -(S)) produces..." |
| 108 | 1 | 1 | 2 | Last line | "...we can |
"...we can slightly..." |
| 112 | 1 | 1 | 2 | Middle+Bottom | int v in range_update method in RUPQ and RURQ classes | Change them to ll v to minimize overflow cases |
| 124 | 1 | 1 | 2 | Middle | Exercise 2.2.1. |
LaTeX referencing error, it should be Exercise 2.2.1.3* |
| 162 | 1 | 1 | 3 | Also p163 | Wrong usage of LaTeX itemize; '.' between playground and wordspin | Enumerate the list: a), b), ..., f); also use ',' between playground and wordspin |
| 168 | 1 | 1 | 3 | Bottom sample code | int dp(int g, b) { | int dp(int g, int b) { |
| 175 | 2 | 1 | 3 | Table 3.3 | cell A[1][3] on Table 3.3.B and C is not |
cell A[1][3] on Table 3.3.B and C should be -2 |
| 182 | 1 | 1 | 3 | Bottom | O(n!) Complete Search Algorithm | O(n!*n) Complete Search Algorithm |
| 184 | 1 | 1 | 3 | Ex 3.5.2.3* | "...the |
"...the minimum number of subsequences..." |
| 184 | 1 | 1 | 3 | Ex 3.5.2.3* | The second Exercise 3.5.2.3* is a LaTeX referencing error | It should be Exercise 3.5.2.4* |
| 213 | 2 | 1 | 4 | Kattis - hoppers | "...CC-1 if there is at least one bipartite component..." | "...CC-1 if there is at least one non-bipartite component..." |
| 223 | 2 | 1 | 4 | Middle | "...all edges have constant weight13 C" | "...all edges have non-negative constant weight13 C" |
| 233 | 1 | 1 | 4 | Ex 4.4.3.5* | "...in O(V^2) instead such complete..." | "...in O(V^2) instead on such complete..." |
| 244 | 1 | 1 | 4 | Bottom | for (int |
for (int j = 0; j < V; ++j) |
| 245 | 1 | 1 | 4 | Top | printf(" %d", |
printf(" %d", j); |
| 260 | 2 | 1 | 4 | Ex 4.6.3.2* | "...randomize the vertex order in Adjacency List..." | "...randomize the vertex order in each row of the Adjacency List..." |
| 262 | 1 | 1 | 4 | Third line from the top | "...which we expand in ABCDA with AFGA." | "...which we expand in ABCDA with AGFA." |
| 263 | 1 | 1 | 4 | Middle | "...involving it the last two decades..." | "...involving it in the last two decades..." |
| 263 | 2 | 1 | 4 | Middle | "does not have K5 or K3,3 as its subgraph" is not precise | "does not contain a subgraph that is a subdivision of K5 or of K3,3" |
| 267 | 2 | 1 | 4 | Ex 4.2.8.1 | The answer mentions 3 occurrences of "(directed)" | They should be "(undirected)" |
| 275 | 1 | 1 | 5 | Point 7 | "Note that r > 1" | "Note that r ≠ 1" |
| 285 | 1 | 1 | 5 | Marin Mersenne | "...was a French mathematician |
"...was a French mathematician" |
| 293 | 3 | 2 | 5 | Example 1+2+3 | 12 % 7 = |
12 % 7 = 5; also remove extra '(' in those 3 examples |
| 304 | 1 | 2 | 5 | The whole page | The section numbering: c, c, c, c is incorrect | It should be c, d, e, f |
| 312 | 1 | 2 | 5 | Middle | "...player id can subtract |
"...player id can subtract..." |
| 314 | 1 | 2 | 5 | Middle | "...problems that |
"...problems that are discussed..." |
| 315 | 2 | 2 | 5 | Middle | "Compute the number of |
"Compute the number of walks (repeated vertices are allowed) of length L" |
| 315 | 1 | 2 | 5 | Footnote 31 | "...elements of the matrix |
"...elements of the matrix are..." |
| 320 | 1 | 2 | 5 | Top | Incomplete constraint for Kattis - linearrecurrence | Add 1 ≤ N ≤ 40 as one of the constraints |
| 320 | 3 | 2 | 5 | Ex 5.8.4.2* | O(k^2 log n) is wrong | Change to O(k^3 log n) and lower k to k ≤ 100 |
| 322 | 2 | 2 | 5 | Ex 5.4.4.3 | "...%1e9+7 = ..." is missing parentheses | It should be "...%(1e9+7) = ..." |
| 322 | 2 | 2 | 5 | Ex 5.4.4.6 | "Let |
"Let B..."; ".., then |B| = 1M/7 = ..."; and "...|A ⋂ B| = 1M/35 = ..." |
| 323 | 3 | 2 | 5 | Ex 5.5.2 | The final answer is not 0.2 | It should be 7*6*5*4*3/(15*14*13*12*11) = 1/143 |
| 331 | 1 | 2 | 6 | Middle | "...what was the previous used..." | "...what was the previously used..." |
| 336 | 1 | 2 | 6 | Middle | "...the pattern can |
"...the pattern can be..." |
| 338 | 1 | 2 | 6 | Bottom | "We insertion of each..." | "We insert each..." |
| 345 | 2 | 2 | 6 | Middle | "Suffix 0 = 'GA |
"Suffix 0 = 'GATAGACA$'" |
| 356 | 2 | 2 | 6 | Top | "the S0,1,...,R in the formulas have to be changed to T0,1,...,R | "the S0,1,...,R in the formulas have to be changed to T0,1,...,R |
| 356 | 1 | 2 | 6 | Bottom | "...we have take out..." | "...we have taken out..." |
| 365 | 1 | 2 | 7 | Middle | "...geometry-specific problems depend |
"...geometry-specific problems depend on..." |
| 374 | 1 | 2 | 7 | Top | The functions dot and norm_sq are already used 1 page earlier | They should have been declared in page 373 for angle function |
| 387 | 2 | 2 | 7 | Middle | "...where (P[i], P[i+1]) are consecutive |
"...where (P[i], P[i+1]) are consecutive vertices..." |
| 392 | 1 | 2 | 7 | Also page 391 | The implementation to find P0 actually finds the bottommost (and leftmost if tie) point | Fortunately it is still correct |
| 393 | 1 | 2 | 7 | Middle | "But |
"But the convex hull must now be..." |
| 405 | 1 | 2 | 8 | Ex 8.2.1.2* | "...an arithmetic equation |
"...an arithmetic equation..." |
| 424 | 2 | 2 | 8 | Ex 8.2.1.2* | "...at Figure |
"...at Figure 8.16-3" and "...totalling 4+8 = 12..." |
| 429 | 1 | 2 | 8 | Top | "... pass it to our |
"... pass it to our Dinic's implementation..." |
| 414 | 1 | 2 | 8 | Code | "... a Boolean array 'used' ... calling rec(0, 0, 0) ... unordered_set 'used'" | "... a Boolean array 'visited' ... calling dp(0, 0, 0) ... unordered_set 'S'" |
| 416 | 1 | 2 | 8 | 8.3.6 | "... 200 * 2000 * 2000 = 8 * 10^6 initialization operations." | "... 200 * 2000 * 2000 = 8 * 10^8 initialization operations." |
| 428 | 1 | 2 | 8 | 8.4.5 | "Max Cardinality Bipartite Maching (MCBM)" | "Max Cardinality Bipartite Matching (MCBM)" |
| 431 | 1 | 2 | 8 | Top | "Teams are |
"Teams are numbered..." |
| 431 | 1 | 2 | 8 | Ex 8.4.5.3* | "An potential..." | "A potential..." |
| 433 | 2 | 2 | 8 | Figure 8.22 | Missing dash at the bottom right corner | There should be a dash connecting '.' and '*' at the bottom right |
| 436 | 1 | 2 | 8 | Bottom | "...and later and Section..." | "...and later in Section..." |
| 436 | 1 | 2 | 8 | Footnote 16 | "...and each |
"...and each person..." |
| 438 | 2 | 2 | 8 | Middle | "...can be implemented in O(V^2). ... estimated to be O(V^2 + kE)." | "...can be implemented in O(V+E). ... estimated to be O(V+E + kE) = O(kE)." |
| 452 | 1 | 2 | 8 | Ex 8.6.6.2 | "...the input graph of the |
"...the input graph of the MVC..." |
| 452 | 1 | 2 | 8 | Ex 8.6.6.3* | "Does the Greedy algorithm work |
"Does the Greedy algorithm work..." |
| 453 | 3 | 2 | 8 | Fig 8.31, Left | MIS = |
MIS = {2, 4} |
| 459 | 2 | 2 | 8 | Fig 8.36 | "... These |
The middle K5 is not planar |
| 466 | 1 | 2 | 8 | Middle | "... illustration of Binary Search the Answer tecnique..." | "... illustration Binary Search the Answer technique" |
| 478 | 1 | 2 | 8 | Ex 8.4. |
LaTeX referencing error | It should be Exercise 8.4.4.1 |
| 481 | 2 | 2 | 9 | Last paragraph | "..., 1 |
"..., 15 rare problems." |
| 485 | 1 | 2 | 9 | Figure 9.1 | The second box has 2^4 = 4 | It should be 2^2 = 4 |
| 485 | 1 | 2 | 9 | Last line | "we want cover..." | "we want to cover..." |
| 497 | 2 | 2 | 9 | Bottom | "... a.mat[i][k] |
"... a.mat[i][k] * b.mat[k][j];" |
| 513 | 1 | 2 | 9 | Middle | "...of the |
"...of the same size as A[]..." |
| 526 | 1 | 2 | 9 | Middle | "...issue can be addressed by sub |
"...issue can be addressed by subtracting..." |
| 548 | 2 | 2 | 9 | Top | "...in Chapter 3+4 |
"...in Chapter 3+4+8 are 'uninformed'... |
| 549 | 2 | 2 | 9 | Top | "...visit the states in |
"...visit the states in non-decreasing order of... |
| 549 | 2 | 2 | 9 | Top | "...also known as admissible heuristic), this A* search algorithm is optimal... | Add a stronger constraint: consistent heuristic |
| 562 | 1 | 2 | 9 | Footnote 65 | "...A[i] > |
"...A[i] > |
| 563 | 1 | 2 | 9 | Footnote 66 | "..., work |
"..., work backwards, and..." |
| 564 | 1 | 2 | 9 | Middle | "...only i |
"...only iterates from..." |
| 571 | 1 | 2 | 9 | Middle | Missing "10 units of flow..." in the 3rd bullet point | Add "10 units of flow..." in the 3rd bullet point |
