Competitive Programming


Errata

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 Wed, 2 Jun 2021, ~4.45pm 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 more easier..." "...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 a certain letters..." "...uses certain letters..."
41 1 1 1 Ex 1.3.2.1 Dragon of Loowater; Greedy (Non Classical) 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..28/29/30/31])..."; off-by-one error Change it to "/month ([0..27/28/29/30])..."
86 1 1 2 Ex 2.3.3.2 "...support the these..." "...support these..."
108 1 1 2 Last line "...we can can slightly..." "...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.2* 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
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 subsets..." "...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 i = 0; j < V; ++j) for (int j = 0; j < V; ++j)
245 1 1 4 Top printf(" %d", v); 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..."
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 mathematicians" "...was a French mathematician"
293 3 2 5 Example 1+2+3 12 % 7 = 2 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 subtracts..." "...player id can subtract..."
314 1 2 5 Middle "...problems that is discussed..." "...problems that are discussed..."
315 2 2 5 Middle "Compute the number of paths of length L" "Compute the number of walks (repeated vertices are allowed) of length L"
315 1 2 5 Footnote 31 "...elements of the matrix is..." "...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 A..."; ".., then |A| = 1M/7 = ..."; and "...|A| = 1M/35 = ..." "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 must be..." "...the pattern can be..."
338 1 2 6 Bottom "We insertion of each..." "We insert each..."
345 2 2 6 Middle "Suffix 0 = 'GACAGATA$'" "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 depends on..." "...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 edges..." "...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 now the convex hull must now..." "But the convex hull must now be..."
405 1 2 8 Ex 8.2.1.2* "...an arithmetic equations..." "...an arithmetic equation..."
424 2 2 8 Ex 8.2.1.2* "...at Figure Figure 8.16-3" and "...totalling 4+12 = 12..." "...at Figure 8.16-3" and "...totalling 4+8 = 12..."
429 1 2 8 Top "... pass it to our Edmonds-Karp implementation..." "... pass it to our Dinic's implementation..."
431 1 2 8 Top "Teams are are numbered..." "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 each person..." "...and each person..."
452 1 2 8 Ex 8.6.6.2 "...the input graph of the the MVC..." "...the input graph of the MVC..."
452 1 2 8 Ex 8.6.6.3* "Does the Greedy algorithm works..." "Does the Greedy algorithm work..."
453 3 2 8 Fig 8.31, Left MIS = {1, 2} MIS = {2, 4}
459 2 2 8 Fig 8.36 "... These Planar Graphs..." 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.3.1 LaTeX referencing error It should be Exercise 8.4.4.1
481 2 2 9 Last paragraph "..., 14 rare problems, and 1 to-be-written." "..., 15 rare problems."
485 1 2 9 Last line "we want cover..." "we want to cover..."
497 2 2 9 Bottom "... a.mat[i][k] + b.mat[k][j];" "... a.mat[i][k] * b.mat[k][j];"
513 1 2 9 Middle "...of the the same size as A[]..." "...of the same size as A[]..."
526 1 2 9 Middle "...issue can be addressed by substracting..." "...issue can be addressed by subtracting..."
548 2 2 9 Top "...in Chapter 3+4 and the earlier subsections of this Section are 'uninformed'... "...in Chapter 3+4+8 are 'uninformed'...
549 2 2 9 Top "...visit the states in ascending order of... "...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] > B[j]" "...A[i] > A[j]"
563 1 2 9 Footnote 66 "..., works backward, and..." "..., work backwards, and..."
564 1 2 9 Middle "...only interates from..." "...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

Buy Now!


Partner Links