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: P(age number), S(everity: 3-extremely serious error; we are ashamed.../2-major error/1-minor grammatical or typographical error that should not matter much), B(ook 1 or 2), C(hapter 0/Preface, 1-9), Pos(ition in the page), Ex(ercise), Fig(ure).
This list is last updated on Mon, 01 Jul 2024, ~6.25pm 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.
The Fix that has been applied in Steven's ongoing CP5 draft (may or may not be released) are highlighted with this lightgreen color.
| 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 | 2 | 1 | 0-P | top | const |
const long long LLINF = 4e18; |
| 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 |
| 6 | 1 | 1 | 1 | middle | "...coding skill ... and ... typing speed ... that determine |
"...coding skill ... and ... typing speed ... that determine the winner." |
| 8 | 1 | 1 | 1 | bottom | "...was not known before 19 |
"...was not known before 1950s, nor..." |
| 11 | 1 | 1 | 1 | Familiarity with these bounds: | 10! = 3 628 800 ≈ |
10! = 3 628 800 ≈ 4 * 10^6... — it is better to round this up |
| 15 | 1 | 1 | 1 | footnote 26 | Java is dropped after IOI 2020, Singapore (Online) — i.e., only used in IOI in 2015-2020 | Focus on C++ and Python for CP in the 2020s |
| 16 | 1 | 1 | 1 | bottom | "...compare your answers with the mod |
"...compare your answers with the model solutions..." |
| 17 | 1 | 1 | 1 | Ex 1.3.4.1, Q5 | There is a shorter Python answer | Add "Use C++." at the end |
| 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 |
| 22 | 1 | 1 | 1 | Third paragraph from the top | " |
"These online judges use a rating system..." |
| 24 | 1 | 1 | 1 | Footnote 33 | "Note that |
"Note that modern online judges, e.g., Kattis, ignore..." |
| 26 | 1 | 1 | 1 | Selection Only | "...selection statements (if-else |
"...selection statements (if-else or switch-case statements)." |
| 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..." |
| 35 | 1 | 1 | 1 | Input Parsing (Iterative) | "...to be formatted as simpl |
"...to be formatted as simple as possible." |
| 41 | 1 | 1 | 1 | Ex 1.3.2.1 | Dragon of Loowater; Greedy ( |
Dragon of Loowater; Greedy (Classical) — this is now 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) |
| 59 | 1 | 1 | 2 | Top | "---by |
"---by prepending zeroes if necessary." |
| 61 | 1 | 1 | 2 | Top | a. Inversion |
a. Inversion Count — I think this is the proper problem name |
| 64 | 1 | 1 | 2 | Top | "To enumerate all |
"To enumerate all non-empty subsets of a given bitmask,..." |
| 68 | 1 | 1 | 2 | Bottom | Exercise 2.2.4. |
Exercise 2.2.4.3* |
| 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..." — notice the bracket |
| 108 | 1 | 1 | 2 | Last line | "...we can |
"...we can slightly..." |
| 110 | 2 | 1 | 2 | Second line from bottom | "rsq(1, 6) = rupq.point_query(6)* |
"rsq(1, 6) = rupq.point_query(6)*6 - (-3) = 0*6 + 3 = 3" |
| 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 |
| 121 | 1 | 1 | 2 | Exercise 2.4.4.1 | "Using a similar Segment Tree as in the Exercise |
"Using a similar Segment Tree as in the Exercise 2.4.4.2* below, ..." |
| 124 | 1 | 1 | 2 | Middle | Exercise 2.2.1. |
LaTeX referencing error, it should be Exercise 2.2.1.3* |
| 139 | 1 | 1 | 3 | Tip 2 | "... row[1] = {0, 4, 5, 6, 7},..." | "... row[1] ∈ {0, 4, 5, 6, 7},..." |
| 149 | 1 | 1 | 3 | Last paragraph | "..., and i = 10 |
"..., and i = 10." (twice) — the interest rate is already in "i%" |
| 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) { |
| 173 | 1 | 1 | 3 | a1. Max 1D Range Sum | A[i] + A[i+1] + |
A[i] + A[i+1] + ... + A[j] |
| 175 | 2 | 1 | 3 | Table 3.3 | cell A[1][3] on Table 3.3.B and C is not 2 | 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 increasing subsequences..." |
| 184 | 1 | 1 | 3 | Ex 3.5.2.3* | The second Exercise 3.5.2. |
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 |
