Instead of performing both bfs (initialize dist) and dfs (find augmenting path) from source, we can bfs from sink but still dfs from source. Doing so avoids exploring useless nodes that do not take us closer to sink while finding augmenting paths and a crude benchmark shows 10-20% runtime reduction on random graphs. This also makes dist more consistent with the labeling function in Push-relabel algorithm.

Considering the following section in /ch6/string_matching.cpp, we call modInverse for every check (we check O(n) possible sub-strings of length m). The comment for hash_fast states it is O(1) but since the extended euclidean algorithm is O(log m), then our total time for string matching is O(n log m).

We can fix this by pre-computing the inverse of each P[i] using the following implementation in O(log m + n) since we only use modInverse once.

class RollingHash {
   public:
    vi P, H;   // P[i] = p^i mod m, H[i] is the hash of prefix length i
    vi P_inv;  // P_inv[i] = p^(-i) mod m
    const int n;
    string T;
    const ll p, M;

    RollingHash(string _s, int _p = 131, int _M = (int)1e9 + 7)
        : n(_s.size()), T(_s), p(_p), M(_M) {
        PrepareP();
        computeRollingHash();
    }
    void PrepareP() {  // precompute P and P_inv
        P.assign(n, 0);
        P[0] = 1;
        for (int i = 1; i < n; i++) P[i] = (P[i - 1] * p) % M;

        P_inv.assign(n, 0);
        P_inv[n - 1] = modInverse(P[n - 1], M);
        for (int i = n - 2; i >= 0; i--) P_inv[i] = (P_inv[i + 1] * p) % M;
    }

    void computeRollingHash() {  // precompute H
        H.assign(n, 0);
        for (int i = 0; i < n; i++) {
            if (i != 0) H[i] = H[i - 1];
            H[i] = (H[i] + ((ll)T[i] * P[i]) % M) % M;
        }
    }

    int getHash(int l, int r) {  // get hash of substring [l, r]
        if (l == 0) return H[r];
        int ans = ((H[r] - H[l - 1]) % M + M) % M;
        ans = ((ll)ans * P_inv[l]) % M;
        return ans;
    }
};

// Returns a vector of indices of all occurrences of pattern in text
vi rabinKarp(string P, string T) {
    RollingHash P_rolling(P);
    RollingHash T_rolling(T);
    vi matches;

    int n = T.size(), m = P.size();
    int p_hash = P_rolling.getHash(0, m - 1);
    for (int i = 0; i <= n - m; i++) {
        if (p_hash == T_rolling.getHash(i, i + m - 1)) {  // match
            matches.push_back(i);
        }
    }
    return matches;
};

Note that using the original code gets TLE for kattis stringmatching while the modified can AC.

from discord:

(what if j is something like a&b. Admittedly unlikely)
better to write (j) there, or even better just use a function (compilers these days good at inlining)

In this main code,

i changed into

point[] P = new point[7];
P[0] = new point(3.6, 4.5);
P[1] = new point(0, 2);
P[2] = new point(1.75, 6.75);
P[3] = new point(2.4, 3);
P[4] = new point(5.6, 5.8);
P[5] = new point(0.5, 1.5);
P[6] = new point(4.75, 2.1);

And the result after Arrays.sort(P) is

(0.00, 2.00)
(0.50, 1.50)
(1.75, 6.75)
(2.40, 3.00)
(3.60, 4.50)
(5.60, 5.80)
(4.75, 2.10)

Shouldn't the (4.75, 2.10) appear before (5.60, 5.80)?

In line 17 we assign P2 a size of L2_n, implying we have the range [0,L2_n) available. Then we iterate i through [0,L2_n] and assign P2[i]. This leads to a problem when i = L2_n. This is a really hard to catch bug, as C++ usually allocate more size than necessary, but this very mistake has got me a runtime error in problem https://www.codechef.com/problems/TALCA?tab=statement

Hi,

I couldn't find where to submit errors found in the book. I recently bought CP4 Book 1 and in the example for Max 2D Range Sum I believe there is an error in the cumulative array sum on page 175, table 3.3, figure b.

Original Array

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

Cumulative Sum Array (In Book)

 0 -2 -9 -9 
 9  9 -4  2
 ...

I believe A[1][3] should be -2 and not 2.

Thanks!
JT

In ch5/primes.cpp -- primeFactors(ll N):

while (PF*PF <= N) {
  while (N%PF == 0) { N /= PF; factors.push_back(PF); }
  PF = primes[++PF_idx];
}

This code might crash due to index-out-of-bound in PF = primes[++PF_idx]. Consider the case when PF_idx = primes.size()-1 (the last prime in primes), then when it goes to the problematic line, PF_idx becomes primes.size() which does not exist in PF.

This bug also happened in other functions as well, i.e., numPF(), numDiffPF(), sumPF(), numDiv(), sumDiv(), EulerPhi().

In CP4 Page 517, code for an in-place FFT is written. However, it contains (multiple) errors. Here is a working version of the same function.

typedef complex<long double> cd;
const double PI = acos(-1.0);

int reverseBit(int x, int m) {  // m is the binary length A.size()-1
    int ret = 0;
    for (int k = 0; k < m; k++) {
        if (x & (1 << k)) ret |= (1 << (m - 1 - k));
    }
    return ret;
}

void FFT(vector<cd> &A) {  // evaulates A at the nth roots of unity for n = 2^k >= A.size()
    int m = 0;
    while ((1 << m) < (int)A.size()) m++;
    A.resize(1 << m, 0);                       // size of A should be a power of 2, resizes A
    for (int k = 0; k < (int)A.size(); k++) {  // sort to bit-reversal permutation
        if (k < reverseBit(k, m)) swap(A[k], A[reverseBit(k, m)]);
    }

    for (int n = 2; n <= (int)A.size(); n <<= 1) {
        for (int k = 0; 2 * k < n; k++) {
            // we are going to get the kth and k+n/2th element of each length n block
            cd x = cd(cos(2 * PI * k / n), sin(2 * PI * k / n));  // nth root of unity
            for (int j = 0; j < (int)A.size(); j += n) {  // apply to every sub-array of length n
                cd A0k = A[k + j];                        // previously computed
                cd A1k = A[k + j + n / 2];                // previously computed
                A[k + j] = A0k + x * A1k;
                A[k + j + n / 2] = A0k - x * A1k;
            }
        }
    }
}

In ch9/SparseTable.cpp

P2.assign(L2_n, 0);
L2.assign(1<<L2_n, 0);
for (int i = 0; i <= L2_n; ++i) {
  P2[i] = (1<<i);
  L2[(1<<i)] = i;
}

P1 is a vector and is assigned with L2_n elements of 0 (from index 0 to L2_n-1), but in the iteration, it accesses P2[i = L2_n] which does not exist.

Example of Problem

AVL* A = new AVL();

int n = 9;
int arr[] = {7, 4, 8, 2, 5, 9, 1, 3, 6};
for (int i = 0; i < n; i++) {
    A->insert(arr[i]);
}
A->remove(9);
BSTVertex* L = A->root->left; // make root public to check this
printf("%d\n", L->key);
printf("%d\n", L->height);
printf("%d\n", L->right == NULL);

After insertion of the 9 elements, the tree looks like this:

After deletion of the 9, the tree looks like this:

The tree is imbalanced at the 4 node, as it has height 2 but the right child is NULL.

What causes the issue

In the above example, the tree after deleting 9, and before rebalancing looks like this:

The root is now imbalanced and needs to be rebalanced.
This is the relevant rebalancing code:

int balance = h(T->left) - h(T->right);
if (balance == 2) { // left heavy
    int balance2 = h(T->left->left) - h(T->left->right);
    if (balance2 == 1) {
        T = rotateRight(T);
    }
    else { // -1
        T->left = rotateLeft(T->left);
        T = rotateRight(T);
     }

In the example, balance2 is 0, so we enter the else case, which causes left rotation of left child followed by right rotation.
The tree after the left rotation of the left child:

The tree after the right rotation of the root (final result):

Suggested fix

Change the if condition in the rebalancing to

if (balance2 >= 0) {

to trigger the right rotation for the 0 case.
This yields the following, correctly balanced tree:

The same needs to be done for the symmetric case.

tie(a, b) = tuple(b, a%b);
tie(x, xx) = tuple(xx, x-q*xx);
tie(y, yy) = tuple(yy, y-q*yy);

The downside is that it's slightly longer and requres C++17 for https://en.cppreference.com/w/cpp/language/class_template_argument_deduction. For C++11 and C++14, make_tuple can be used instead.

In cpbook-code/ch2/ourown/fenwicktree_ds.py line 16, the second j should be an i, not a j.

Sometimes the method won't return the correct value.

How to reproduce:

FenwickTree ft(10);
for (int i = 1; i <= 10; i++){
    ft.update(i,1);
}
for (int i = 1; i <= 10; i++){
    cout << ft.select(i) << "\n";
}

Expected output:

1
2
3
4
5
6
7
8
9
10

Obtained result:

1
2
3
4
5
6
7
8
16
16

Code execution: https://ideone.com/k5IMXN

Tks for your effort! Wonderful code!
Just a little improvement for python io.

class SamInput(object):
    def __init__(self):
        self.inp = []
        for i in sys.stdin:
            i = i.replace("\n", "")
            j = list(i.split())
            self.inp.append(j)

canbe writed as:

def __init__(self):
        self.inp=[line.split() for line in list(sys.stdin)] 

😅

Hello. Looks like this code does not work properly.

Actual result:
table[n][m] outputs 1

Expected result:
table[n][m] should output 3

Great tool and website!
Under which license is your code released? Apache 2.0?

Currently some files use LF for line endings while some files use CR+LF for line endings. It would be good to convert all of them to LF.

Tks your wonderful effort, great book!
But sorry some problem about the function int LIS(int i)
LIS is a special DP problem, need to check every element of the array. So a better approach is bottom-up that use tabulation.
But cpbook-code/ch3/dp/LIS.cpp build the DP using DAG to find the single-source longest path. This method only works for the case that the last element of the array is the max, and initial ans=1. But not for the case like {5 4 2 3 1}.
Because LIS is special that need to ensure every element would be recursively
checked!
Additional caution, if initial using ans=0 then, only the first element of the array is the min, the base case i==0 would be recursively visited for every check that should be recursively visited. So using ans=0 need to ensure the first element is the min of the arrary.

in this file it does not seem that we are using globals so in this code m is missing as a parameter (n is also missing but in main its defined as just len of the string)
def longest_common_substring(sa, lcp):
idx = 0
max_lcp = -1
for i in range(1, n):
if (sa[i] < m) != (sa[i-1] < m) and lcp[i] > lcs:
max_lcp = lcp[i]
idx = i
return (max_lcp, idx)

In polygon.cpp I think the shoelace formula is missing the a_n * b1 - b_n * a_1 term, and in the alternative area function is missing the triangle with vertices O, P[0], P[P.size() -1]. Am I correct in thinking this?

https://github.com/stevenhalim/cpbook-code/blob/26fb7376417799f8b84b504d46ea7c8c0cf71c29/ch2/lineards/bit_manipulation.py#L9C1-L9C1

This repository has a few C++ code that uses variable with name that begins with an underscore followed by an uppercase letter. However, this is technically undefined behavior in C++.

According to https://en.cppreference.com/w/cpp/language/identifiers,

the identifiers that begin with an underscore followed by an uppercase letter are reserved;

"Reserved" here means that the standard library headers #define or declare such identifiers for their internal needs, the compiler may predefine non-standard identifiers of that kind, and that name mangling algorithm may assume that some of these identifiers are not in use. If the programmer uses such identifiers, the behavior is undefined.

This condition doesn't check for node u's parent to see if it's a root node.

I think it should be something like this:
if (dfs_parent[u] != -1 && dfs_low[v] >= dfs_num[u])

I think that this line should just use conquer(lsubtree,rsubtree), as currently it doesn't use the lazy value if applicable, and only checks for the minimum rather than what the conquer function specifies

Hi,
I've been looking at the KMP example on pg 335 in Chapter 6 of CP4 book 2.
I noticed that in the examples you seem to preprocess a table that is pattern size + 1,
so that the kmpSearch can reset correctly once a match is found ( j = b[j])
However the kmpPreprocess function seems to only iterate for i < m.
Assuming m is the size of the pattern string we won't fully fill out the table,
should the preprocessing iterate for i <= m ? Or is m here the size of the pattern+1?
Or maybe I am misunderstanding something. Any clarification is appreciated!

Thanks,
Anup

I tried to run this code and received a StopIteration error.

# IO_in1.txt
import sys
inputs = iter(sys.stdin.readlines())
TC = int(next(inputs))
for _ in range(TC):
    print(sum(map(int, next(inputs).split())))

Can you tell me how to prevent this traceback?

---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-221-4615b4523133> in <module>
      1 import sys
      2 inputs = iter(sys.stdin.readlines())
----> 3 TC = int(next(inputs))
      4 for _ in range(TC):
      5     print(sum(map(int, next(inputs).split())))

StopIteration: 

As of 13 July 2020, getting much better for java/py/ml
Let's reduce this as much as possible before 18 July 2020.

Missing Java
ch3/greedy/ballotboxes_UVa12390.java (direct conversion from cpp and using BufferedReader/PrintWriter still TLE...)
ch6/Trie.java
ch8/UVa10243.java (direct conversion from cpp and using BufferedReader/PrintWriter still TLE...)
ch9/mcmf.java (Felix has done this, check with him)

Missing Python
ch2/lineards/array_algorithms.py (still incomplete)
ch7/triangles.py (incomplete, too long)
ch7/polygon.py (incomplete, too long)

Missing OCaml
ch2/lineards/array_algorithms.ml (OCaml array operations)
ch3/greedy/grass_UVa10382.ml
ch5/factovisors_UVa10139.ml
ch4/traversal/toposort.ml
ch4/traversal/cyclecheck.ml
ch4/traversal/articulation.ml
ch4/hierholzer.ml
ch5/modInverse.ml
ch5/combinatorics.ml
ch6/Trie.ml
ch9/GaussianElimination.ml
ch9/mcmf.ml
ch9/LCA.ml

Also missing but in reality a low priority task
ch2/nonlineards/AVL.py (will be very tedious)
ch2/nonlineards/AVL.ml (will be very tedious)
ch3/greedy/ballotboxes_UVa12390.ml (probably TLE too)
ch5/UVa01230.ml (no OCaml in UVa)
ch7/UVa11817.ml (no OCaml in UVa)
ch8/UVa11195.java (probably TLE)
ch8/UVa11195.py (probably TLE)
ch8/UVa11212.java (probably TLE)
ch8/UVa11212.py (probably TLE)
ch8/UVa01099.java (probably TLE)
ch8/UVa01099.py (probably TLE)
ch8/UVa11065.py (probably TLE)
ch8/UVa10243.ml (no OCaml in UVa)
ch8/UVa11646.ml (no OCaml in UVa)
ch8/UVa01079.py (probably TLE)
ch9/UVa11616.ml (no OCaml in UVa)
ch9/UVa10181.py (probably TLE)
ch9/UVa10181.ml (no OCaml in UVa)

Hello.
Looks like there is a bug in the select function

Steps to reproduce:

ft = FTree([1,2,3,4,5])
ft.select(15) # this throws IndexError: list index out of range in line 36

Expected behavior:
According to CP4 book, the select function "finds the smallest index/key i so that the cumulative frequency in the range [1..i]>=k". So the function should return 6 because the smallest index (of FTree.ft array) where the cumulative frequency is at least 15 is 6