pllk / cphb Goto Github PK
View Code? Open in Web Editor NEWCompetitive Programmer's Handbook
Competitive Programmer's Handbook
There are also union-by-rank and path-compression heuristics. Should they be mentioned? Also the implementation could be shorter.
"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.
Not a big deal, but I figured I would document this. For smaller devices (phones, smaller tablets) an eBook is preferable to a PDF.
g++ -std=c++11 -O2 -Wall code.cpp -o code
Why would I name the program as "code"?
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.
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?
Perhaps they should be mentioned somewhere?
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
It seems that this section is difficult to understand.
Maybe it's not a good idea to use negative distances in the Dijkstra implementation. One could just use a proper priority queue.
Maybe add "about" before -10^38...10^38
The analysis of nim and examples could be improved
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".
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;
Parberry, Ian: An efficient algorithm for the Knight's tour problem. Discrete appl math. 73 (1997), 251--260
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.
signed -> unsigned (in two places) in the first paragraph.
What would be good examples on square root algorithms?
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.
This code snippet uses a seemingly Finnish word, hattivatti
.
"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.
Many people have asked links to practice problems, thus something should be done. Maybe an external list and not in the book?
The name "sparse table" should be mentioned. Also the description is not so good at the moment.
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?
"both in" -> "in both"
Syntax highlighting in code examples would be nice
There could be an example where a macro yields a bug
In at least some modern compilers, it's not needed to use make_tuple.
It could be a good idea to merge sections 1.6 and 1.7.
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.
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.
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
Perhaps to Chapter 18?
The second implementation could be done without the while loop, but is it a good idea?
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.
"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.
"C++ template" is not a good term here
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 last subset iteration code work?
Why does the binary indexed tree update query work?
This is the eternal question. C++ uses 0-indexing, but 1-indexing is used in algorithm theory.
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.
This is not the usual implementation found in textbooks, maybe there should be more discussion why the implementation works.
Distance 3.60555 is wrong, should be 3.16228
This problem is a bad example, because there is an easier O(n log n) algorithm.
The code doesn't work if n=1 and m=1
"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".
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.