Distance 3.60555 is wrong, should be 3.16228

There are also union-by-rank and path-compression heuristics. Should they be mentioned? Also the implementation could be shorter.

johdanto.tex, kirj.tex, kkkk.pdf, kkkk.tex and luku**.tex are all still named in Finnish.

Hint: Git recognizes filename changes and preserves their history.

The implementation for Z-algorithm is rather interesting since I believe the so called textbook implementation involves a lot of branches and potential one-off errors. Here's a rather short implementation that could be included in the book, similar to Manacher's algorithm. The key observation is that the while-loop will fail on the first iteration whenever we are strictly inside a longer match.

Any ideas on how to make it even simpler?

int l = 0, r = 0;
for(int i = 1; i < s.size(); i++) {
     // if i inside current rightmost match (l..r), 
     //   set z[i] to match "shadow" position (i-l) but capped at r-i+1
    if(i <= r) z[i] = min(r - i + 1, z[i - l]);

    // increase z[i] until mismatch or end
    while(z[i] + i < s.size() && s[z[i]] == s[i + z[i]]) z[i]++; 

    // update current rightmost match
    if(i + z[i] - 1 > r) {
         l = i;
         r = i + z[i] - 1;
     }
}

Implementation and some test cases on ideone.com in case you want to fork and try improving this one.

This is the eternal question. C++ uses 0-indexing, but 1-indexing is used in algorithm theory.

What would be good examples on square root algorithms?

Fix typo - "consider the state [10,2,5]" should be changed to "consider the state [10,12,5]"
Reference - https://github.com/pllk/cphb/blob/master/chapter25.tex#L287

"C++ template" is not a good term here

g++ -std=c++11 -O2 -Wall code.cpp -o code

Why would I name the program as "code"?

Many people have asked links to practice problems, thus something should be done. Maybe an external list and not in the book?

Perhaps they should be mentioned somewhere?

http://codeforces.com/blog/entry/11080

Calling memset is more efficient and quicker to write, than a loop, to set all values to 0/INF.

What do you think about changing the loops in graph algorithms to memset?

The time complexity table is misleading. O(n log n) is always ok when n = 10^6. Also O(n^2) is ok for n=5000, O(n^3) is ok for n=500.

Maybe add "about" before -10^38...10^38

Maybe there should be some warning for the use of getline. If you use cin before getline you should eat the whitespaces with cin>>ws; before the getline command.

"If the graph is directed, the adjacency matrix representation can be extended so that the matrix contains the weight of the edge if the edge exists": i suppose there must be "weighted" unstead of "directed".

It's often difficult to remember what one-character names mean

Macro for make_pair is useless in c++11 and it is therefore a bad example. For example make_tuple could be more fitting for c++11.

In this line

u = (u*u)%m;

u is int so it could overflow.

signed -> unsigned (in two places) in the first paragraph.

The second implementation could be done without the while loop, but is it a good idea?

Syntax highlighting in code examples would be nice

z[s] = 1; e[x] = 0; q.push(x); while (!q.empty()) { int s = q.front(); q.pop(); // process node s for (auto u : v[s]) { if (z[u]) continue; z[u] = 1; e[u] = e[s]+1; q.push(u); } }

The BFS code on page 118 uses wrong variable -
z[s] = 1; should be changed to z[x] = 1;

In this line

in an unsigned representation, the next number after $2^{n-1}$ is $0$.

$2^{n-1}$ should be $2^n-1$.

Similar to what is stated few lines above

An unsigned variable of $n$ bits can contain any integer between $0$ and $2^n-1$.

"The time complexity of the algorithm is O(n^3), because it consists of three nested loops and each loop contains O(n) steps." I think that the reasoning "it consists of three nested loops and each loop contains O(n) steps" should lead to a O(n^4) algorithm.

This problem is a bad example, because there is an easier O(n log n) algorithm.

Maybe it's not a good idea to use negative distances in the Dijkstra implementation. One could just use a proper priority queue.

Hi @pllk, I really appreciate your huge efforts for writing this book and making it free and available. Thank you so much!

I have a question when I am reading 27.1 Batch Processing. The problem statement (not the latest version) is

Given a grid of size k by k initially consists of white squares and our task is to perform n operations, each of which is one of the following:

• paint square (y,x) black

• find the nearest black square to square (y,x) where the distance between
  squares (y1,x1) and (y2,x2) is |y1 - y2| + |x1 - x2|

There is a pre-processing step in each batch, to calculate for each square of the grid the smallest distance to a black square. This can be done in O(k^2) time using breadth-first search.

My question is: how is calculating for each square of the grid the smallest distance to a black square done in one BFS? (I can't figure out which square to start the BFS.)

Thanks in advance!

Btw, which is the better place, codeforces or this repo, to post questions when reading the book?

Why does the binary indexed tree update query work?

It could be a good idea to merge sections 1.6 and 1.7.

On the first page of Chapter 10, the range of int is stated as being from 2^{n-1} to 2^{n-1}-1. The same range is mentioned twice, and both of them are missing '-' from the lower bound.

The name "sparse table" should be mentioned. Also the description is not so good at the moment.

"both in" -> "in both"

Parberry, Ian: An efficient algorithm for the Knight's tour problem. Discrete appl math. 73 (1997), 251--260

"and unlike in the IOI, the students work together; there is even only one computer available for each team" doesn't sound right for me. Also the number of finals slots varies from year to year.

"A special property of square roots is that sqrt(n) = n/sqrt(n), so the square root sqrt(n) lies, in some sense, in the middle of the input."

This is difficult to understand.

This is not the usual implementation found in textbooks, maybe there should be more discussion why the implementation works.

It seems that this section is difficult to understand.

There could be an example where a macro yields a bug

I'm translating your book in Italian and I have a doubt. At the end of chapter 5, you state that "it is possible to check in $O(2^{n/2})$ time if the sum $x$ can be created from $S_A$ and $S_B$". Maybe I'm wrong, but I think that this could be possibile only if both $S_A and $S_B are sorted, as it seems in the example. If I'm wrong, could you explain more about how to achieve that complexity? Otherwise, could you add the assumption about sorting?

This code snippet uses a seemingly Finnish word, hattivatti.

In your dijkstra algorithm you suggest using negative distances, as a workaround for priority_queue sorting by the maximum element by default.

I think, a better solution would be to use std::greater as a template argument.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;

Shouldn't this line be using term large instead of small?

The phenomenon in scenario 3 is known as the birthday paradox: if there are n people in a room, the probability that some two people have the same birthday is large even if n is quite small.

Not a big deal, but I figured I would document this. For smaller devices (phones, smaller tablets) an eBook is preferable to a PDF.

The code doesn't work if n=1 and m=1

Perhaps to Chapter 18?

In at least some modern compilers, it's not needed to use make_tuple.

The analysis of nim and examples could be improved

Why does the last subset iteration code work?

Maybe you should just say that the time and space complexities of counting sort are O(n+c) instead of writing about "a small constant".