codebook.tex

% Compiled and edited by Brian Bi
\documentclass[9pt]{extarticle}
\setlength{\parindent}{0.0in}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{hyperref}
\usepackage[landscape,a4paper,twoside=false,top=15mm,bottom=10mm,left=10mm,right=10mm]{geometry}
\usepackage{fancyhdr}
\pagestyle{fancy}
\setlength{\headsep}{0mm}
\setlength{\voffset}{8mm}
\fancyhead[EOL]{Moradonellani (Politecnico di Milano)}
\fancyhead[EOR]{\thepage}
\cfoot{}
\usepackage{listings}
\usepackage{titlesec}
\usepackage{color}
\lstset{
	tabsize=2,
    basicstyle=\ttfamily\scriptsize,
    %upquote=true,
    aboveskip={1.5\baselineskip},
    columns=fixed,
    showstringspaces=false,
    extendedchars=true,
    breaklines=true,
    prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
    frame=single,
    rulecolor=\color[rgb]{0.75,0.75,0.75},
    showtabs=false,
    showspaces=false,
    showstringspaces=false,
    keywordstyle=\color[rgb]{0,0,1},
    commentstyle=\color[rgb]{0.133,0.545,0.133},
    stringstyle=\color[rgb]{0.627,0.126,0.941},
}
\titlespacing*{\section} {0pt}{0.5ex plus 1ex minus .2ex}{0.3ex plus .2ex}
\titlespacing*{\subsection} {0pt}{0.25ex plus 1ex minus .2ex}{0.3ex plus .2ex}

\begin{document}
% Disable balancing of columns on last page, which is ugly
\begin{multicols*}{3}
% Want compact table of contents, but normal spacing between paragraphs later on
\setlength{\parskip}{0.0in}
\tableofcontents
\setlength{\parskip}{0.1in}
% New codebook
\section{Flow and matching}

\subsection{Hungarian algorithm} % https://raw.githubusercontent.com/ADJA/algos/master/Graphs/HungarianMatching.cpp
\lstinputlisting[language=c++]{hungarian.cpp}

\subsection{Max bipartite matching} % Stanford
\lstinputlisting[language=c++]{bipartite.cpp}

\subsection{Min-cost max-flow (successive shortest paths)}
% Frank Chu and Igor Naverniouk (modified by Brian Bi)
\lstinputlisting[language=c++]{mcmf4.cpp}

\subsection{Max flow (Edmonds-Karp)}
\lstinputlisting[language=c++]{edmonds-karp.cpp}

\subsection{Max flow (Dini\'c)} % Stanford
\lstinputlisting[language=c++]{dinic.cpp}

\subsection{Min-cost matching} % Stanford
\lstinputlisting[language=c++]{bipartite-mincost.cpp}

\subsection{Global min cut (Stoer--Wagner)} % Stanford
\lstinputlisting[language=c++]{mincut.cpp}

\subsection{K\"onig's Theorem (Text)} % Jacob Plachta and Brian Bi
In any bipartite graph, the number of edges in a maximum matching equals the
number of vertices in a minimum vertex cover. To exhibit the vertex cover:
\begin{enumerate}
\item Find a maximum matching
\item Change each edge \textbf{used} in the matching into a directed edge from
\textbf{right to left}
\item Change each edge \textbf{not used} in the matching into a directed edge
from \textbf{left to right}
\item Compute the set $T$ of all vertices reachable from unmatched vertices on
the left (including themselves)
\item The vertex cover consists of all vertices on the right that are
\textbf{in} $T$, and all vertices on the left that are \textbf{not in} $T$
\end{enumerate}

\subsection{General Unweighted Maximum Matching (Edmonds' algorithm)}
% Ilya Grebnov (modified by Brian Bi)
\lstinputlisting[language=c++]{general-matching.cpp}

\subsection{Minimum Edge Cover (Text)} % Brian Bi
If a minimum edge cover contains $C$ edges, and a maximum matching contains $M$
edges, then $C + M = |V|$. To obtain the edge cover, start with a maximum
matching, and then, for every vertex not matched, just select some edge
incident upon it and add it to the edge set. 

\subsection{Stable Marriage Problem (Gale--Shapley algorithm)} % Brian Bi
\lstinputlisting[language=c++]{stablemp.cpp}

\section{Geometry}

\subsection{Miscellaneous Geometry} % Stanford
\lstinputlisting[language=c++]{geom-2d.cpp}

\subsection{3D Geometry}
% Stanford (translated, modified, and expanded by Wesley May and Brian Bi)
\lstinputlisting[language=c++]{geom-3d.cpp}

\subsection{Minimum Enclosing Disk (Welzl's Algorithm)} % Brian Bi
\lstinputlisting[language=c++]{welzl.cpp}

\subsection{Convex hull} % Brian Bi
\lstinputlisting[language=c++]{monotone.cpp}

% TODO: Add faster one
\subsection{Slow Delaunay triangulation} % Stanford
\lstinputlisting[language=c++]{delaunay.cpp}

\subsection{Fast Delaunay triangulation}
\lstinputlisting[language=c++]{fast-delaunay.cpp}

\subsection{Delaunay triangulation to Voronoi diagram (Text)}
The Voronoi diagram is the dual graph of the Delaunay triangulation.
To obtain Voronoi diagram compute the circumcenters of the Delaunay triangles:
these are the Voronoi vertices. Voronoi edges are obtained connecting
the circumcenters of triangles that share an edge (the Voronoi edge will be
perpendicular to such edge). If a triangle edge is not shared with another triangle,
then the respective Voronoi edge goes to infinity. \\
\textit{Degenerate cases}: \\
\textbf{All points are collinear}: Delaunay triangulation does not exist and Voronoi diagram
is not connected. \\
\textbf{Four or more points lie on the same circle}: Delaunay triangulation is not unique and
the circumcenters are identical (Voronoi edges overlap).

\subsection{Pick's Theorem (Text)} % Wesley May
For a polygon with all vertices on lattice points, $A = i + b/2 - 1$, where $A$
is the area, $i$ is the number of lattice points strictly within the polygon,
and $b$ is the number of lattice points on the boundary of the polygon. (Note,
there is no generalization to higher dimensions)

\section{Math Algorithms}

\subsection{Gaussian elimination for square matrices of full rank; finds
inverses and determinants} % Stanford
\lstinputlisting[language=c++]{gaussian.cpp}

\subsection{Sieve of Eratosthenes} % Jimmy Mårdell (Yarin)
\lstinputlisting[language=c++]{yarin.cpp}

\subsection{Modular arithmetic and linear Diophantine solver} % Stanford
\lstinputlisting[language=c++]{modular.cpp}

\subsection{Reduced row echelon form (RREF), matrix rank} % Stanford
\lstinputlisting[language=c++]{rref.cpp}

\subsection{Solving linear systems (Text)} % Brian Bi
To solve a general system of linear equations, put it into matrix form and
compute the reduced row echelon form. For example,
\begin{align*}2x + y &= 5 \\ 3x + 2y &= 6\end{align*}
corresponds to the matrix
\[ \left[ \begin{array}{cc|c} 2 & 1 & 5 \\ 3 & 2 & 6 \end{array} \right] \]
with RREF
\[ \left[ \begin{array}{cc|c} 1 & 0 & 4 \\ 0 & 1 & -3 \end{array} \right] \]
After row reduction, if any row has a 1 in the rightmost column and 0
everywhere else, then the system is inconsistent and has no solution.
Otherwise, to find a solution, set the variable corresponding to the leftmost 1
in each column equal to the corresponding value in the rightmost column, and
set all other variables to 0. Ignore rows consisting entirely of 0. The
solution is unique iff the rank of the matrix equals the number of variables.

\subsection{Fast Fourier transform (FFT)} % Stanford
\lstinputlisting[language=c++]{fft.cpp}

\subsection{Simplex algorithm} % Stanford
\lstinputlisting[language=c++]{simplex.cpp}

\subsection{Number Theoretic Transform (NTT)}
\lstinputlisting[language=c++]{ntt.cpp}

\subsection{Fast factorization (Pollard rho) and primality testing
(Rabin--Miller)} % Qiyu Zhu
\lstinputlisting[language=c++]{pollard-rho.cpp}

\subsection{Euler's Totient} % Andre Hahn Pereira
\lstinputlisting[language=c++]{totient.cpp}

\subsection{Floyd's cycle-finding algorithm}
\lstinputlisting[language=c++]{cycle-finding.cpp}

\subsection{Combinatorics and Probability (Text)}
\begin{itemize}
\item Binomial Coefficient $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} = \frac{n!}{k!(n - k)!}$
\item Number of permutations with $n_k$ indistinguishable elements of type $k$ $ = \frac{n!}{\prod_{k}n_k!}$
\item Derangement: permutation of the elements of a set such that none of the elements appear in their original position. \\
Number of derangements of $n$ elements \\
$der(n) = \begin{cases}
1 & \text{$n = 0$} \\
0 & \text{$n = 1$} \\
(n - 1) * (der(n - 1) + der(n - 2)) & \text{$n > 1$} \\
\end{cases}$
\item Catalan number $Cat(n) = \begin{cases}
1 & \text{$n = 0$} \\
\frac{1}{n + 1}\binom{2n}{n} & \text{$n > 0$}
\end{cases}$ \\
$Cat(n) = \binom{2n}{n} - \binom{2n}{n - 1}$ \\
$Cat(n)$ satisfies $Cat(n + 1) = \sum_{i = 0}^{n} Cat(i)Cat(n - i)$.
\item Expected number of trials until success with probability of success $p$ in every trial is $\frac{1}{p}$.
\item Probability of exactly $k$ successes of probability $p$ out of $n$ trials is $\binom{n}{k}p^k(1 - p)^{n-k}$.
\end{itemize}

\section{Graphs}

\subsection{Strongly connected components} % Stanford (modified by Brian Bi)
\lstinputlisting[language=c++]{scc.cpp}

\subsection{Bridges} % Andre Hahn Pereira
\lstinputlisting[language=c++]{bridges.cpp}

\subsection{Eulerian path}
% Tested against:
% codeforces: 1152E
\lstinputlisting[language=c++]{eulerian.cpp}

\subsection{Eulerian Tour}
\lstinputlisting[language=c++]{eulerian-tour.cpp}

\subsection{Lowest Common Ancestor (Pseudocode)} % Jacob Plachta
Tarjan's offline algorithm (requires $O(N)$ disjoint set operations).
\begin{lstlisting}
function TarjanOLCA(u)
    MakeSet(u);
    u.ancestor := u;
    for each v in u.children do
        TarjanOLCA(v);
        Union(u,v);
        Find(u).ancestor := u;
    u.colour := black;
    for each v such that {u,v} in P do
        if v.colour == black
            print "Tarjan's Least Common Ancestor of " + u +
                " and " + v + " is " + Find(v).ancestor + ".";
\end{lstlisting}
This function is called on the root of the tree. The set P of pairs of nodes to
query must be specified in advance. Each node is initially white, and is
colored black after it and all its children have been visited. The lowest
common ancestor of the pair {u,v} is available as Find(v).ancestor immediately
(and only immediately) after u is colored black, provided v is already black.
Otherwise, it will be available later as Find(u).ancestor, immediately after v
is colored black.

\subsection{Bron-Kerbosch (Pseudocode)}
Reports maximal cliques in an undirected graph in O($3^{\frac{N}{3}}$).
To call the algorithm set R = X = $\emptyset$, P = vertex set of the graph.
N(v) is the sets of neighbor vertices to v.
\begin{lstlisting}[mathescape=true]
algorithm BronKerbosch(R, P, X) is
  if P and X are both empty then
    report R as a maximal clique
  choose a pivot vertex u in P $\cup$ X
  for each vertex v in P \ N(u) do
    BronKerbosch(R $\cup$ {v}, P $\cap$ N(v), X $\cap$ N(v))
    P := P \ {v}
    X := X $\cup$ {v}
\end{lstlisting}

\subsection{Bellman-Ford}
\lstinputlisting[language=c++]{bellman-ford.cpp}

\subsection{Floyd-Washall (All Pair Shortest Path)}
\lstinputlisting[language=c++]{floyd-warshall.cpp}

\section{Data Structures}

\subsection{Binary Indexed Tree (BIT) / Fenwick Tree} % Brian Bi
\lstinputlisting[language=c++]{BIT.cpp}

\subsection{BIT with range query/updates}
\lstinputlisting[language=c++]{BIT-range-range.cpp}

\subsection{BIT with range updates} % Brian Bi
\lstinputlisting[language=c++]{BIT-range.cpp}

\subsection{Segment Tree with Lazy Propagation} % Brian Bi
\lstinputlisting[language=c++]{segtree.cpp}

\subsection{Size-Balanced Tree}
% Tom Yubing Dong (tomtung) (modified by Brian Bi)
\lstinputlisting[language=c++]{SBT.cpp}

\subsection{Implicit Treap}
% Tested against:
% codeforces: 863D
% codeforces: 1358E
% olinfo: vasi (AC only with fast input)
\lstinputlisting[language=c++]{treap.cpp}

\section{Number Theory Reference}
\subsection{Polynomial Coefficients (Text)} % Brian Bi
$(x_1 + x_2 + ... + x_k)^n = \sum_{c_1 + c_2 + ... + c_k = n}
\frac{n!}{c_1! c_2! ... c_k!} x_1^{c_1} x_2^{c_2} ... x_k^{c_k}$

\subsection{M\"obius Function (Text)} % Brian Bi
$\mu(n) = \begin{cases}
0 & \text{$n$ not squarefree} \\
1 & \text{$n$ squarefree w/ even no. of prime factors} \\
-1 & \text{$n$ squarefree w/ odd no. of prime factors} \\
\end{cases}$ \\
Note that $\mu(a) \mu(b) = \mu(ab)$ for $a, b$ relatively prime \\
Also $\sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if $n = 1$} \\
0 & \text{otherwise} \end{cases}$

\textbf{M\"obius Inversion}
If $g(n) = \sum_{d|n} f(d)$ for all $n \ge 1$, then
$f(n) = \sum_{d|n} \mu(d)g(n/d)$ for all $n \ge 1$.

\subsection{Burnside's Lemma (Text)} % Wesley May and Brian Bi
The number of orbits of a set $X$ under the group action $G$ equals the average
number of elements of $X$ fixed by the elements of $G$.

Here's an example. Consider a square of $2n$ times $2n$ cells. How many ways
are there to color it into $X$ colors, up to rotations and/or reflections?
Here, the group has only 8 elements (rotations by 0, 90, 180 and 270 degrees,
reflections over two diagonals, over a vertical line and over a horizontal
line). Every coloring stays itself after rotating by 0 degrees, so that
rotation has $X^{4n^2}$ fixed points. Rotation by 180 degrees and reflections
over a horizonal/vertical line split all cells in pairs that must be of the
same color for a coloring to be unaffected by such rotation/reflection, thus
there exist $X^{2n^2}$ such colorings for each of them. Rotations by 90 and 270
degrees split cells in groups of four, thus yielding $X^{n^2}$ fixed colorings.
Reflections over diagonals split cells into $2n$ groups of 1 (the diagonal
itself) and $2n^2-n$ groups of 2 (all remaining cells), thus yielding
$X^{2n^2-n+2n}=X^{2n^2+n}$ unaffected colorings.  So, the answer is
$(X^{4n^2}+3X^{2n^2}+2X^{n^2}+2X^{2n^2+n})/8$.

\subsection{Euler's Totient Function Properties (Text)}
\begin{itemize}
\item $\displaystyle \sum_{d|n} \varphi(d) = n$ \\
Apply M\"obius Inversion to obtain $\displaystyle \varphi(n) = \sum_{d|n} \mu(d)\frac{n}{d}$
\item $\varphi(p^k) = p^k - p^{k-1}$ for all primes $p$ with $k \geq 1$
\item $\varphi(ab) = \varphi(a)\varphi(b)\frac{d}{\varphi(d)}$ where $d = gcd(a, b)$ \\
When $a$ and $b$ are coprimes this reduces to \\
$\varphi(ab) = \varphi(a)\varphi(b)$
\item $a^{\varphi(m)} \equiv 1 \ (mod \ m)$ \\
When m is prime $a^{m-1} \equiv 1 \ (mod \ m)$ (Fermat's little theorem)
\item $x^n \equiv x^{\varphi(m) + (n \ mod \ \varphi(m))} \ mod \ m$
\item $a | b \implies \varphi(a) | \varphi(b)$
\item $n | \varphi(a^n - 1)$ for $a, n > 1$
\end{itemize}

\section{Strings}

\subsection{Knuth--Morris--Pratt (KMP)}
\lstinputlisting[language=c++]{KMP.cpp}

\subsection{Z-Algorithm}
\lstinputlisting[language=c++]{Z-algorithm.cpp}

\subsection{Suffix array and lcp array}
% Tested against:
% olinfo: unimi_glith
% hackerrank: morgan-and-a-string
\lstinputlisting[language=c++]{suffix-array.cpp}

\subsection{Longest palindromic substring} % Brian Bi
\lstinputlisting[language=c++]{manacher.cpp}

\subsection{Aho-Corasick}
% Tested against:
% swerc 2016: passwords
\lstinputlisting[language=c++]{aho-corasick.cpp}

\section{Miscellaneous}

\subsection{2-SAT} % Brian Bi
\lstinputlisting[language=c++]{2sat.cpp}

\subsection{Convex hull trick} % Brian Bi
\lstinputlisting[language=c++]{chtrick.cpp}

\subsection{Convex hull trick (online)}
% Tested against:
% codeforces: 932F
% csacademy: building-bridges
\lstinputlisting[language=c++]{cht-online.cpp}

\subsection{Shunting Yard (Pseudocode)} % Wesley May
\begin{lstlisting}
// Add '(' to start of expression, and ')' to end.
O = empty vector of tokens (values or operators)
S = empty stack of tokens (brackets or operators)
for each token:
  if token == value:
    O.push(token)
  else if token == '(':
    S.push(token)
  else if token == ')':
    while S.top() != '(':
      O.push(S.top())
      S.pop()
    S.pop()
  else:
    // Note: If token is a right-associative operator (^), this should be <=.
	// priority('(') < priority('+') < priority('*').
    while priority(S.top()) < priority(token):
      O.push(S.top())
      S.pop()
    S.push(token)
// Finally, evaluate O as a postfix expression.
\end{lstlisting}

\subsection{Binary search} % Brian Bi
\lstinputlisting[language=c++]{bsearch.c}

\subsection{Bignums (C++, slow)} % Brian Bi
\lstinputlisting[language=c++]{bignum.cpp}

\subsection{All nearest smaller values} % Brian Bi
\lstinputlisting[language=c++]{ansv.cpp}

\subsection{Union-Find}
\lstinputlisting[language=c++]{union-find.cpp}

\subsection{Centroid decomposition}
\lstinputlisting[language=c++]{centroid.cpp}

\subsection{NTT constants generator}
\lstinputlisting[language=c++]{ntt-gen.cpp}

\subsection{Game theory, Sprague-Grundy theorem (Text)}
We consider games that are:
\begin{itemize}
\item impartial: available moves and winning/losing depend only on the state of the game;
\item with perfect information: no information is hidden to players (they know rules and possible moves);
\item finite: after a certain number of moves one of the players will end up in a losing position (state),
i.e. a position from which no moves are available.
\end{itemize}
Such games can be described with a DAG, where nodes are states and edges are transitions (moves) between states. \\
Sinks in this graph are losing states by definition. All other states are classified in the following way:
\begin{itemize}
\item a state is \textbf{winning} if there is at least a transition to a losing state;
\item a state is \textbf{losing} otherwise, i.e. there are no transitions to another losing state.
\end{itemize}
\textbf{Nim} \\
This game follows the restrictions described above. \\
There are several piles, each with several stones. In a move a player can take any positive amount of stones
from a pile and remove it (we can also consider the modification where stones can be added to a pile:
as long as the game remains acyclic this modification doesn't change how winning and losing states
are determined). A player loses when no moves are available, which happens when all piles are empty. \\
A state is losing if the xor-sum of the number of stones in each pile is zero,
otherwise is winning (can be proved by induction). \\
All states with the same xor-sum $s$ are thus equivalent and can be replaced with one another.
In particular such states can be replaced with the state represented by a single pile of size $s$. \\
\textbf{Sprague-Grundy theorem} \\
Let's consider a game that follows the restrictions described above. \\
Then for each state $v$, we can assign an equivalent state of a game of Nim with xor-sum $x$
(or simply with a pile of size $x$). This value $x$ is called the Grundy number of the state $v$. \\
Let $v_i$ be the states reachable from the state $v$ and let $x_i$ be their respective Grundy number. \\
Then $x$ can be calculated in the following recursive way: $x = mex(\{x_1, ..., x_k\})$,
where the function $mex$ (minimum excludant) is the smallest non-negative integer not found in the given set. \\
If a transition leads to a sum of indipendent games, the Grundy number of this state is computed as the
xor-sum of the Grundy number of each indipendent game. \\
Like in Nim, a state in this game if losing if its Grundy number is zero. \\
\textit{Example}: Consider a checkered strip of size $1 \times n$. In one move the current player must put one cross in
a cell, but it's forbidden to put two crosses in two adjacent cells. As usual, the player without a valid move loses.
\begin{itemize}
\item A cross is put in cell $1$ or $n$. This leads to a state of size $n - 2$,
as the cell with the cross and the one next to it can't be used.
\item A cross is put in cell $i$ with $1 < i < n$. This leads to a state with two indipendent games,
of size $i - 2$ (the left part of the strip that can still be used) and $n - i - 1$ (the right part).
\end{itemize}
The Grundy number $g(n)$ can thus be calculated in the following way:
$g(n) = mex(\{g(n - 2)\} \cup \{g(i - 2) \oplus g(n - i - 1) | 1 < i < n\})$.

\subsection{DP optimizations (Text)}
\begin{itemize}
\item $DP[i] = \displaystyle \sum_{j = 1}^{k} a_{j}DP[i - j]$ i.e. it is a linear recurrence. \\
 Matrix Exponentiation: complexity is $O(k^3logn)$.
\item $DP[i] = \displaystyle \min_{j < i} (DP[j] + cost(j)x(i))$ \\
 Convex Hull Trick: for each computed $j$ keep a line in the convex hull $y = mx + q$
 where $m = cost(j)$ and $q = DP[j]$ and get answer querying with $x = x(i)$. \\
 \textit{Further optimization if $cost(j)$ is increasing and $x(i)$ is decreasing}: \\
 Lines are always added to the left of the hull ($m = cost(j)$ is increasing)
 and query point $x(i)$ is moving to the left, so Convex Hull Trick can be
 implemented with a deque to obtain amortized constant time queries and updates.
\item $DP[i][k] = \displaystyle \min_{j < i} (DP[j][k - 1] + cost(i, j))$ \\
 \textbf{Necessary condition}: $f(i) = optj(i, k)$ must be increasing ($optj(i, k)$ is optimal $j$ that minimizes
 $DP[j][k - 1] + cost(i, j)$). \\
 Divide and Conquer:
 \begin{lstlisting}
  function solve(k, l, r, optl, optr):
    if(l > r)
      base case: return
    m := (l + r) / 2
    j := optj(m, k) // test all j between optl and optr
    solve(k, l, m - 1, optl, j)
    solve(k, m + 1, r, j, optr)
 \end{lstlisting}
 k-th layer is computed in $O(nlogn)$.
\item $DP[i][k] = \displaystyle \min_{i < j < k} (DP[i][j] + DP[j][k] + cost(i, k))$ \\
 \textbf{Necessary condition}: $optj(i, k - 1) \leq optj(i, k) \leq optj(i + 1, k)$ ($optj(i, k)$ is optimal $j$ that minimizes
 $DP[i][j] + DP[j][k] + cost(i, k)$). \\
 Fill DP in order of increasing $k - i$: search for $optj(i, k)$ only between $optj(i, k - 1)$ and $optj(i + 1, k)$.
 Complexity is reduced from $O(n^3)$ to $O(n^2)$.
\end{itemize}
Note: cost functions defined as $cost(i, j) = \displaystyle \sum_{k = i}^{j} a_{k}$ should satisfy $optj$ constraints for the last two cases.

\noindent\rule{9cm}{0.3pt}

Paolo Battellani \\
Marco Donadoni \\
Edoardo Morassutto

\end{multicols*}
\end{document}