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); |
© 2000-2024 Steven Halim
