pllk / cphb Goto Github PK
View Code? Open in Web Editor NEWCompetitive Programmer's Handbook
Competitive Programmer's Handbook
"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 the eternal question. C++ uses 0-indexing, but 1-indexing is used in algorithm theory.
Many people have asked links to practice problems, thus something should be done. Maybe an external list and not in the book?
"both in" -> "in both"
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;
signed -> unsigned (in two places) in the first paragraph.
This code snippet uses a seemingly Finnish word, hattivatti
.
Distance 3.60555 is wrong, should be 3.16228
g++ -std=c++11 -O2 -Wall code.cpp -o code
Why would I name the program as "code"?
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.
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
"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".
There could be an example where a macro yields a bug
"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.
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 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.
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.
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.
The code doesn't work if n=1 and m=1
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;
Why does the binary indexed tree update query work?
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?
Syntax highlighting in code examples would be nice
There are also union-by-rank and path-compression heuristics. Should they be mentioned? Also the implementation could be shorter.
Not a big deal, but I figured I would document this. For smaller devices (phones, smaller tablets) an eBook is preferable to a PDF.
Why does the last subset iteration code work?
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.
In at least some modern compilers, it's not needed to use make_tuple.
Perhaps to Chapter 18?
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
It seems that this section is difficult to understand.
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?
The analysis of nim and examples could be improved
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.
"C++ template" is not a good term here
This is not the usual implementation found in textbooks, maybe there should be more discussion why the implementation works.
Maybe it's not a good idea to use negative distances in the Dijkstra implementation. One could just use a proper priority queue.
It's often difficult to remember what one-character names mean
Perhaps they should be mentioned somewhere?
What would be good examples on square root algorithms?
This problem is a bad example, because there is an easier O(n log n) algorithm.
It could be a good idea to merge sections 1.6 and 1.7.
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".
The name "sparse table" should be mentioned. Also the description is not so good at the moment.
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.
Parberry, Ian: An efficient algorithm for the Knight's tour problem. Discrete appl math. 73 (1997), 251--260
The second implementation could be done without the while loop, but is it a good idea?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.