comprog.tex

\documentclass[9pt,a4paper,twocolumn,landscape,oneside]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{booktabs}
\usepackage{caption}
\usepackage{color}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
%\usepackage{geometry}
\usepackage[top=0pt, bottom=1cm, left=0.3cm, right=0.3cm]{geometry}
\usepackage{graphicx}
% \usepackage{listings}
\usepackage{subcaption}
\usepackage[scaled]{beramono}
\usepackage{titling}
\usepackage{datetime}

\newcommand{\subtitle}[1]{%
  \posttitle{%
    \par\end{center}
    \begin{center}\large#1\end{center}
    \vskip0.5em}%
}

% Minted
\usepackage{minted}
\newcommand{\code}[1]{\inputminted{cpp}{_code/#1}}

% Header/Footer
% \geometry{includeheadfoot}
%\fancyhf{}
\pagestyle{fancy}
\lhead{Reykjavík University}
\rhead{\thepage}
\cfoot{}
\setlength{\headheight}{15.2pt}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

% Math and bit operators
\DeclareMathOperator{\lcm}{lcm}
\newcommand*\BitAnd{\mathrel{\&}}
\newcommand*\BitOr{\mathrel{|}}
\newcommand*\ShiftLeft{\ll}
\newcommand*\ShiftRight{\gg}
\newcommand*\BitNeg{\ensuremath{\mathord{\sim}}}

% Title/Author
\title{viRUs}
\subtitle{Team Reference Document}
\date{\ddmmyyyydate{\today{}}}

% Output Verbosity
\newif\ifverbose
\verbosetrue
% \verbosefalse

\begin{document}

\maketitle
\thispagestyle{fancy}
\tableofcontents

\newpage

\section{Code Templates}
    \subsection{Basic Configuration}
        Vim and (Caps Lock = Escape) configuration.
        \begin{minted}{bash}
o.yqtxmal ekrpat  # setxkbmap dvorak for dvorak on qwerty
setxkbmap -option caps:escape
set -o vi
xset r rate 150 100
cat > ~/.vimrc
set nocp et sw=4 ts=4 sts=4 si cindent hi=1000 nu ru noeb showcmd showmode
syn on | colorscheme slate
        \end{minted}

    \subsection{C++ Header}
        A C++ header.
        \code{header.cpp}

    \subsection{Java Template}
        A Java template.
        \code{template.java}


\section{Data Structures}

    \subsection{Union-Find}
        An implementation of the Union-Find disjoint sets data structure.
        \code{data-structures/union_find.cpp}

    \subsection{Segment Tree}
        An implementation of a Segment Tree.
        \code{data-structures/segment_tree.cpp}

    \subsection{Fenwick Tree}
        A Fenwick Tree is a data structure that represents an array of $n$
        numbers. It supports adjusting the $i$-th element in $O(\log n)$ time,
        and computing the sum of numbers in the range $i..j$ in $O(\log n)$
        time. It only needs $O(n)$ space.
        \code{data-structures/fenwick_tree.cpp}

    \subsection{Matrix}
        A Matrix class.
        \code{data-structures/matrix.cpp}

    \subsection{AVL Tree}
        A fast, easily augmentable, balanced binary search tree.
        \code{data-structures/avl_tree.cpp}

        Also a very simple wrapper over the AVL tree that implements a map
        interface.
        \code{data-structures/avl_map.cpp}

    \subsection{Heap}
        An implementation of a binary heap.
        \code{data-structures/heap.cpp}

    \subsection{Skiplist}
        An implementation of a skiplist.
        \code{data-structures/skiplist.cpp}

    \subsection{Dancing Links}
        An implementation of Donald Knuth's Dancing Links data structure. A
        linked list supporting deletion and restoration of elements.
        \code{data-structures/dancing_links.cpp}

    \subsection{Misof Tree}
        A simple tree data structure for inserting, erasing, and querying the
        $n$th largest element.
        \code{data-structures/misof_tree.cpp}

    \subsection{$k$-d Tree}
        A $k$-dimensional tree supporting fast construction, adding points, and
        nearest neighbor queries.
        \code{data-structures/kd_tree.cpp}

\section{Graphs}
    \subsection{Breadth-First Search}
        An implementation of a breadth-first search that counts the number of
        edges on the shortest path from the starting vertex to the ending
        vertex in the specified unweighted graph (which is represented with an
        adjacency list). Note that it assumes that the two vertices are
        connected. It runs in $O(|V|+|E|)$ time.
        \code{graph/bfs.cpp}

        Another implementation that doesn't assume the two vertices are
        connected. If there is no path from the starting vertex to the ending
        vertex, a $-1$ is returned.
        \code{graph/bfs_visited.cpp}

    \subsection{Single-Source Shortest Paths}
        \subsubsection{Dijkstra's algorithm}
            An implementation of Dijkstra's algorithm. It runs in
            $\Theta(|E|\log{|V|})$ time.
            \code{graph/dijkstra.cpp}

        \subsubsection{Bellman-Ford algorithm}
            The Bellman-Ford algorithm solves the single-source shortest paths
            problem in $O(|V||E|)$ time. It is slower than Dijkstra's
            algorithm, but it works on graphs with negative edges and has the
            ability to detect negative cycles, neither of which Dijkstra's
            algorithm can do.
            \code{graph/bellman_ford.cpp}

    \subsection{All-Pairs Shortest Paths}
        \subsubsection{Floyd-Warshall algorithm}
            The Floyd-Warshall algorithm solves the all-pairs shortest paths
            problem in $O(|V|^3)$ time.
            \code{graph/floyd_warshall.cpp}

    \subsection{Strongly Connected Components}
        \subsubsection{Kosaraju's algorithm}
            Kosarajus's algorithm finds strongly connected components of a
            directed graph in $O(|V|+|E|)$ time.
            \code{graph/scc.cpp}

    \subsection{Minimum Spanning Tree}
        \subsubsection{Kruskal's algorithm}
            \code{graph/kruskals_mst.cpp}

    \subsection{Topological Sort}
        \subsubsection{Modified Depth-First Search}
            \code{graph/tsort.cpp}

    \subsection{Euler Path}
        Finds an euler path (or circuit) in a directed graph, or reports that
        none exist.
        \code{graph/euler_path.cpp}

    \subsection{Bipartite Matching}

        \subsubsection{Alternating Paths algorithm}
            The alternating paths algorithm solves bipartite matching in $O(mn^2)$
            time, where $m$, $n$ are the number of vertices on the left and right
            side of the bipartite graph, respectively.
            \code{graph/bipartite_matching.cpp}

        \subsubsection{Hopcroft-Karp algorithm}
            An implementation of Hopcroft-Karp algorithm for bipartite
            matching. Running time is $O(|E|\sqrt{|V|})$.
            \code{graph/hopcroft_karp.cpp}

    \subsection{Maximum Flow}
        \subsubsection{Dinic's algorithm}
            An implementation of Dinic's algorithm that runs in
            $O(|V|^2|E|)$. It computes the maximum flow of a flow network.
            \code{graph/dinic.cpp}

        \subsubsection{Edmonds Karp's algorithm}
            An implementation of Edmonds Karp's algorithm that runs in
            $O(|V||E|^2)$. It computes the maximum flow of a flow network.
            \code{graph/edmonds_karps.cpp}

    \subsection{Minimum Cost Maximum Flow}
        An implementation of Edmonds Karp's algorithm, modified to find
        shortest path to augment each time (instead of just any path). It
        computes the maximum flow of a flow network, and when there are
        multiple maximum flows, finds the maximum flow with minimum cost. Running time is $O(|V|^2|E|\log|V|)$.
        \code{graph/edmonds_karps_mcmf.cpp}

    \subsection{All Pairs Maximum Flow}
        \subsubsection{Gomory-Hu Tree}
        An implementation of the Gomory-Hu Tree. The spanning tree is constructed using Gusfield's algorithm
        in $O(|V| ^ 2)$ plus $|V|-1$ times the time it takes to calculate the maximum flow.
        If Dinic's algorithm is used to calculate the max flow, the running time is $O(|V|^3|E|)$.
        \code{graph/gomory_hu_tree.cpp}

    \subsection{Heavy-Light Decomposition}
        \code{graph/hld.cpp}

\section{Strings}
    \subsection{Trie}
        A Trie class.
        \code{strings/trie.cpp}

    \subsection{Suffix Array}
        An $O(n \log^2 n)$ construction of a Suffix Tree.
        \code{strings/suffix_array.cpp}

    \subsection{Aho-Corasick Algorithm}
        An implementation of the Aho-Corasick algorithm. Constructs a state
        machine from a set of keywords which can be used to search a string for
        any of the keywords.
        \code{strings/aho_corasick.cpp}

    \subsection{The $Z$ algorithm}
        Given a string $S$, $Z_i(S)$ is the longest substring of $S$ starting
        at $i$ that is also a prefix of $S$. The $Z$ algorithm computes these
        $Z$ values in $O(n)$ time, where $n = |S|$. $Z$ values can, for
        example, be used to find all occurrences of a pattern $P$ in a string
        $T$ in linear time. This is accomplished by computing $Z$ values of $S
        = T P$, and looking for all $i$ such that $Z_i \geq |T|$.
        \code{strings/z_algorithm.cpp}

\section{Mathematics}
    \ifverbose
    \subsection{Fraction}
        A fraction (rational number) class. Note that numbers are stored in
        lowest common terms.
        \code{mathematics/fraction.cpp}
    \fi

    \subsection{Big Integer}
        A big integer class.
        \code{mathematics/intx.cpp}

        \subsubsection{Fast Multiplication}
            Fast multiplication for the big integer using Fast Fourier Transform.
            \code{mathematics/fastmul.cpp}

    \subsection{Binomial Coefficients}
        The binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ is the
        number of ways to choose $k$ items out of a total of $n$ items.
        \code{mathematics/nck.cpp}

    \subsection{Euclidean algorithm}
        The Euclidean algorithm computes the greatest common divisor of two
        integers $a$, $b$.
        \code{mathematics/gcd.cpp}

        The extended Euclidean algorithm computes the greatest common divisor
        $d$ of two integers $a$, $b$ and also finds two integers $x$, $y$ such
        that $a\times x + b\times y = d$.
        \code{mathematics/egcd.cpp}

    \subsection{Trial Division Primality Testing}
        An optimized trial division to check whether an integer is prime.
        \code{mathematics/is_prime.cpp}

    \subsection{Miller-Rabin Primality Test}
        The Miller-Rabin probabilistic primality test.
        \code{mathematics/miller_rabin.cpp}

    \subsection{Sieve of Eratosthenes}
        An optimized implementation of Eratosthenes' Sieve.
        \code{mathematics/prime_sieve.cpp}

    \subsection{Modular Multiplicative Inverse}
        A function to find a modular multiplicative inverse.
        \code{mathematics/mod_inv.cpp}

    \subsection{Modular Exponentiation}
        A function to perform fast modular exponentiation.
        \code{mathematics/mod_pow.cpp}

    \subsection{Chinese Remainder Theorem}
        An implementation of the Chinese Remainder Theorem.
        \code{mathematics/crt.cpp}

    \subsection{Linear Congruence Solver}
        A function that returns all solutions to $ax \equiv b \pmod{n}$, modulo $n$.
        \code{mathematics/linear_congruence.cpp}

    \subsection{Numeric Integration}
        Numeric integration using Simpson's rule.
        \code{mathematics/numeric_integration.cpp}

    \subsection{Fast Fourier Transform}
        The Cooley-Tukey algorithm for quickly computing the discrete Fourier
        transform. Note that this implementation only handles powers of two,
        make sure to pad with zeros.
        \code{mathematics/fft.cpp}

    \subsection{Formulas}
        \begin{itemize}
            \item Number of ways to choose $k$ objects from a total of $n$
                objects where order matters and each item can only be chosen
                once: $P^n_k = \frac{n!}{(n-k)!}$
            \item Number of ways to choose $k$ objects from a total of $n$
                objects where order matters and each item can be chosen
                multiple times: $n^k$
            \item Number of permutations of $n$ objects, where there are $n_1$
                objects of type $1$, $n_2$ objects of type $2$, \ldots, $n_k$
                objects of type $k$: $\binom{n}{n_1,n_2,\ldots,n_k} =
                \frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}$
            \item Number of ways to choose $k$ objects from a total of $n$
                objects where order does not matter and each item can only be
                chosen once: \\ $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}k
                = \binom{n}{n-k} = \prod_{i=1}^k \frac{n-(k-i)}{i} =
                \frac{n!}{k!(n-k)!}, \binom n0 = 1, \binom 0k = 0$
            \item Number of ways to choose $k$ objects from a total of $n$
                objects where order does not matter and each item can be chosen
                multiple times: $f^n_k = \binom{n+k-1}{k} =
                \frac{(n+k-1)!}{k!(n-1)!}$
            \item Number of integer solutions to $x_1 + x_2 + \cdots + x_n = k$
                where $x_i \geq 0$: $f^n_k$
            \item Number of subsets of a set with $n$ elements: $2^n$
            \item $|A \cup B| = |A| + |B| - |A \cap B|$
            \item $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap
                C| - |B \cap C| + |A \cap B \cap C|$
            \item Number of ways to walk from the lower-left corner to the
                upper-right corner of an $n\times m$ grid by walking only up
                and to the right: $\binom{n+m}{m}$
            \item Number of strings with $n$ sets of brackets such that the
                brackets are balanced: \\ $C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k}
                = \frac{1}{n+1}\binom{2n}n$
            \item Number of triangulations of a convex polygon with $n$ points,
                number of rooted binary trees with $n+1$ vertices, number of
                paths across an $n\times n$ lattice which do not rise above the
                main diagonal: $C_n$
            \item Number of permutations of $n$ objects with exactly $k$
                ascending sequences or {\it runs}: \\ $\left\langle {n \atop k}
                \right\rangle = \left\langle {n \atop n - k - 1} \right\rangle
                = k\left\langle {n - 1 \atop k} \right\rangle + (n - k +
                1)\left\langle {n-1 \atop k-1} \right\rangle =
                \sum_{i=0}^{k}(-1)^i \binom{n+1}{i} (k+1-i)^n, \left\langle {n
                \atop 0} \right\rangle = \left\langle {n \atop n -1}
                \right\rangle = 1$
            \item Number of permutations of $n$ objects with exactly $k$
                cycles: $\left[n \atop k\right] = \left[n-1 \atop k-1\right] +
                (n-1)\left[n-1 \atop k\right]$
            \item Number of ways to partition $n$ objects into $k$ sets:
                $\left\{n \atop k\right\} = k\left\{n-1 \atop k\right\} +
                \left\{n-1 \atop k-1\right\}, \left\{n\atop 0\right\} =
                \left\{n\atop n\right\} = 1$
            \item Number of permutations of length $n$ that have no fixed
                points (derangements): $D_0 = 1, D_1 = 0, D_n = (n - 1)(D_{n-1}
                + D_{n-2})$
            \item Number of permutations of length $n$ that have exactly $k$
                fixed points: $\binom{n}{k} D_{n-k}$
            \item \textbf{Jacobi symbol:} $\left(\frac{a}{b}\right) = a^{(b-1)/2} \pmod{b}$
            \item \textbf{Heron's formula:} A triangle with side lengths
                $a,b,c$ has area $\sqrt{s(s-a)(s-b)(s-c)}$ where $s =
                \frac{a+b+c}{2}$.
            \item \textbf{Pick's theorem:} A polygon on an integer grid
                containing $i$ lattice points and having $b$ lattice points on
                the boundary has area $i + \frac{b}{2} - 1$.
            \item \textbf{Divisor sigma:} The sum of divisors of $n$ to the
                $x$th power is $\sigma_x(n) = \prod_{i=0}^{r} \frac{p_i^{(a_i +
                1)x} - 1}{p_i^x - 1}$ where $n = \prod_{i=0}^r p_i^{a_i}$ is
                the prime factorization.
            \item \textbf{Divisor count:} A special case of the above is
                $\sigma_0(n) = \prod_{i=0}^r (a_i + 1)$.
            \item \textbf{Euler's totient:} The number of integers less than
                $n$ that are comprime to $n$ are $n\prod_{p|n}\left(1 - \frac{1}{p}\right)$
                where each $p$ is a distinct prime factor of $n$.
            \item \textbf{König's theorem:} In any bipartite graph, the number
                of edges in a maximum matching is equal to the number of
                vertices in a minimum vertex cover.
            \item The number of vertices of a graph is equal to its minimum
                vertex cover number plus the size of a maximum independent set.
        \end{itemize}


\section{Geometry}
    \subsection{Primitives}
        Geometry primitives.
        \code{geometry/primitives.cpp}

    \subsection{Polygon}
        Polygon primitives.
        \code{geometry/polygon.cpp}

    \subsection{Convex Hull}
        An algorithm that finds the Convex Hull of a set of points.
        \code{geometry/convex_hull.cpp}

    \subsection{Line Segment Intersection}
        Computes the intersection between two line segments.
        \code{geometry/line_segment_intersect.cpp}

    \subsection{Great-Circle Distance}
        Computes the distance between two points (given as latitude/longitude
        coordinates) on a sphere of radius $r$.
        \code{geometry/gc_distance.cpp}

    \subsection{Closest Pair of Points}
        A sweep line algorithm for computing the distance between the closest
        pair of points.
        \code{geometry/closest_pair.cpp}

    \subsection{Formulas}
        Let $a = (a_x, a_y)$ and $b = (b_x, b_y)$ be two-dimensional vectors.
        \begin{itemize}
            \item $a\cdot b = |a||b|\cos{\theta}$, where $\theta$ is the angle
                between $a$ and $b$.
            \item $a\times b = |a||b|\sin{\theta}$, where $\theta$ is the
                signed angle between $a$ and $b$.
            \item $a\times b$ is equal to the area of the parallelogram with
                two of its sides formed by $a$ and $b$. Half of that is the
                area of the triangle formed by $a$ and $b$.
        \end{itemize}


\section{Other Algorithms}
    \subsection{Binary Search}
        An implementation of binary search that finds a real valued root of the
        continous function $f$ on the interval $[a,b]$, with a maximum error of
        $\varepsilon$.
        \code{other/binary_search_continuous.cpp}

        Another implementation that takes a binary predicate $f$, and finds an
        integer value $x$ on the integer interval $[a,b]$ such that $f(x) \land
        \lnot f(x - 1)$.
        \code{other/binary_search_discrete.cpp}

    \subsection{Ternary Search}
        Given a function $f$ that is first monotonically increasing and then
        monotonically decreasing, ternary search finds the $x$ such that $f(x)$ is
        maximized.
        \code{other/ternary_search_continuous.cpp}

    \subsection{2SAT}
        A fast 2SAT solver.
        \code{other/two_sat.cpp}

    \subsection{Stable Marriage}
        The Gale-Shapley algorithm for solving the stable marriage problem.
        \code{other/stable_marriage.cpp}

    \subsection{Algorithm X}
        An implementation of Knuth's Algorithm X, using dancing links. Solves the Exact Cover problem.
        \code{other/algorithm_x.cpp}

    \subsection{$n$th Permutation}
        A very fast algorithm for computing the $n$th permutation of the list
        $\{0,1,\ldots,k-1\}$.
        \code{other/nth_permutation.cpp}

    \subsection{Cycle-Finding}
        An implementation of Floyd's Cycle-Finding algorithm.
        \code{other/floyds_algorithm.cpp}

    \subsection{Dates}
        Functions to simplify date calculations.
        \code{other/dates.cpp}


\section{Useful Information}
    \subsection{Tips \&{} Tricks}
        \begin{itemize}
            \item How fast does our algorithm have to be? Can we use
                brute-force?
            \item Does order matter?
            \item Is it better to look at the problem in another way? Maybe
                backwards?
            \item Are there subproblems that are recomputed? Can we cache them?
            \item Do we need to remember everything we compute, or just the
                last few iterations of computation?
            \item Does it help to sort the data?
            \item Can we speed up lookup by using a map (tree or hash) or an
                array?
            \item Can we binary search the answer?
            \item Can we add vertices/edges to the graph to make the problem
                easier? Can we turn the graph into some other kind of a graph
                (perhaps a DAG, or a flow network)?
            \item Make sure integers are not overflowing.
            \item Is it better to compute the answer modulo $n$? Perhaps we can
                compute the answer modulo $m_1,m_2,\ldots,m_k$, where
                $m_1,m_2,\ldots,m_k$ are pairwise coprime integers, and find
                the real answer using CRT?
            \item Are there any edge cases? When $n=0, n=-1, n=1, n=2^{31}-1$
                or $n=-2^{31}$? When the list is empty, or contains a single
                element? When the graph is empty, or contains a single vertex?
                When the graph contains self-loops?  When the polygon is
                concave or non-simple?
            \item Can we use exponentiation by squaring?
        \end{itemize}

    \subsection{Fast Input Reading}
        If input or output is huge, sometimes it is beneficial to optimize the
        input reading/output writing. This can be achieved by reading all input
        in at once (using fread), and then parsing it manually. Output can also
        be stored in an output buffer and then dumped once in the end (using
        fwrite). A simpler, but still effective, way to achieve speed is to use
        the following input reading method.
        \code{tricks/fast_input.cpp}

    \subsection{128-bit Integer}
        GCC has a 128-bit integer data type named \texttt{\_\_int128}. Useful
        if doing multiplication of 64-bit integers, or something needing a
        little more than 64-bits to represent.

    \subsection{Worst Time Complexity}
    \begin{center}
        \begin{tabular}{c|c|c}
            $n$ & Worst AC Algorithm & Comment \\
            \hline
            $\leq 10$ & $O(n!), O(n^6)$ & e.g. Enumerating a permutation \\
            $\leq 15$ & $O(2^n\times n^2)$ & e.g. DP TSP \\
            $\leq 20$ & $O(2^n), O(n^5)$ & e.g. DP + bitmask technique \\
            $\leq 50$ & $O(n^4)$ & e.g. DP with 3 dimensions + $O(n)$ loop, choosing  $_nC_k=4$ \\
            $\leq 10^2$ & $O(n^3)$ & e.g. Floyd Warshall's \\
            $\leq 10^3$ & $O(n^2)$ & e.g. Bubble/Selection/Insertion sort \\
            $\leq 10^5$ & $O(n\log_2{n})$ & e.g. Merge sort, building a Segment tree \\
            $\leq 10^6$ & $O(n), O(\log_2{n}), O(1)$ & Usually, contest problems have $n\leq10^6$ (e.g. to read input) \\
        \end{tabular}
    \end{center}

    \subsection{Bit Hacks}
        \begin{itemize}
            \item \texttt{n \&{} -n} returns the first set bit in $n$.
            \item \texttt{n \&{} (n - 1)} is $0$ only if $n$ is a power of two.
            \item \texttt{snoob(x)} returns the next integer that has the
                same amount of bits set as \texttt{x}. Useful for iterating
                through subsets of some specified size.
                \code{tricks/snoob.cpp}
        \end{itemize}

\end{document}