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[top=3pt, bottom=1cm, left=0.3cm, right=0.3cm]{geometry}
\usepackage{graphicx}
% \usepackage{listings}
\usepackage{subcaption}
\usepackage[scaled]{beramono}
\usepackage{titling}
\usepackage{datetime}
\usepackage{enumitem}
\usepackage{multicol}

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

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

% Header/Footer
% \geometry{includeheadfoot}
%\fancyhf{}
\pagestyle{fancy}
\lhead{Reykjavík University}
\rhead{\thepage}
\cfoot{}
\setlength{\headheight}{15.2pt}
\setlength{\droptitle}{-20pt}
\posttitle{\par\end{center}}
\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}}}

\newenvironment{myitemize}
{ \begin{itemize}[leftmargin=.5cm]
    \setlength{\itemsep}{0pt}
    \setlength{\parskip}{0pt}
    \setlength{\parsep}{0pt}     }
{ \end{itemize}                  }

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

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

\begin{document}

\maketitle
\thispagestyle{fancy}
\vspace{-3em}
% \addtocontents{toc}{\protect\enlargethispage{\baselineskip}}
\tableofcontents

\clearpage

\section{Code Templates}
    \subsection{Basic Configuration}
        \subsubsection{.bashrc}
        \bashcode{bashrc.sh}
        ProTip\texttrademark: setxkbmap dvorak on qwerty: \texttt{o.yqtxmal ekrpat}

        \subsubsection{.vimrc}
        \bashcode{vimrc.sh}

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

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


\section{Data Structures}

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

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

        \subsubsection{Persistent Segment Tree}
        \code{data-structures/persistent_segment_tree.cpp}

    \subsection{Fenwick Tree}
        \ifverbose
        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.
        \fi
        \code{data-structures/fenwick_tree.cpp}

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

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

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

    \subsection{Cartesian Tree}
        \code{data-structures/cartesian_tree.cpp}

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

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

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

    \ifverbose
    \subsection{$k$-d Tree}
        \ifverbose
        A $k$-dimensional tree supporting fast construction, adding points, and
        nearest neighbor queries.
        \fi
        NOTE: Not completely stable, occasionally segfaults.
        \code{data-structures/kd_tree.cpp}
    \fi

    \subsection{Sqrt Decomposition}
        \ifverbose
        Design principle that supports many operations in amortized $\sqrt{n}$ per operation.
        \fi
        \code{data-structures/sqrt_decomposition.cpp}

    \subsection{Monotonic Queue}
        \ifverbose
        A queue that supports querying for the minimum element. Useful for sliding window algorithms.
        \fi
        \code{data-structures/monotonic_queue.cpp}

    \subsection{Convex Hull Trick}
        \code{data-structures/convex_hull_trick.cpp}

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

        \subsubsection{Bellman-Ford algorithm}
            \ifverbose
            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.
            \fi
            \code{graph/bellman_ford.cpp}

        \subsubsection{IDA$^\star$ algorithm}
            \code{graph/idastar.cpp}

    \ifverbose
    \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}
    \fi

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

    \subsection{Cut Points and Bridges}
        \code{graph/cut_points_and_bridges.cpp}

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

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

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

    \subsection{Bipartite Matching}

        \subsubsection{Alternating Paths algorithm}
            \ifverbose
            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.
            \fi
            \code{graph/bipartite_matching.cpp}

        \subsubsection{Hopcroft-Karp algorithm}
            \ifverbose
            An implementation of Hopcroft-Karp algorithm for bipartite
            matching.
            \fi
            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|)$.
            \ifverbose
            It computes the maximum flow of a flow network.
            \fi
            \code{graph/dinic.cpp}

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

    \subsection{Minimum Cost Maximum Flow}
        \ifverbose
        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.
        \fi
        Running time is $O(|V|^2|E|\log|V|)$. NOTE: Doesn't work on negative
        weights!
        \code{graph/edmonds_karps_mcmf.cpp}

        A second implementation that is slower but works on negative weights.
        \code{graph/mcmf_old.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|)$.
        NOTE: Not sure if it works correctly with disconnected graphs.
        \code{graph/gomory_hu_tree.cpp}

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

    \subsection{Centroid Decomposition}
        \code{graph/centroid_decomposition.cpp}

    \subsection{Least Common Ancestors, Binary Jumping}
        \code{graph/lca.cpp}

    \subsection{Tarjan's Off-line Lowest Common Ancestors Algorithm}
        \code{graph/tarjan_olca.cpp}

    \subsection{Maximum Density Subgraph}
        Given (weighted) undirected graph $G$. Binary search density. If $g$ is
        current density, construct flow network: $(S, u, m)$, $(u, T,
        m+2g-d_u)$, $(u,v,1)$, where $m$ is a large constant (larger than sum
        of edge weights). Run floating-point max-flow. If minimum cut has empty
        $S$-component, then maximum density is smaller than $g$, otherwise it's
        larger. Distance between valid densities is at least $1/(n(n-1))$. Edge
        case when density is $0$. This also works for weighted graphs by
        replacing $d_u$ be the weighted degree, and doing more iterations (if
        weights are not integers).

    \subsection{Maximum Weighted Independent Set in a Bipartite Graph}
        This is the same as the minimum weighted vertex cover. Solve this by
        constructing a flow network with edges $(S,u,w(u))$ for $u\in L$,
        $(v,T,w(v))$ for $v\in R$ and $(u,v,\infty)$ for $(u,v)\in E$. The
        minimum $S,T$-cut is the answer. Vertices adjacent to a cut edge are
        in the vertex cover.

\section{Strings}

    \subsection{The Knuth-Morris-Pratt algorithm}
        \ifverbose
        An implementation of the Knuth-Morris-Pratt algorithm. Runs in $O(n+m)$
        time, where $n$ and $m$ are the lengths of the string and the pattern.
        \fi
        \code{strings/kmp.cpp}

    \subsection{The $Z$ algorithm}
        \ifverbose
        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|$.
        \fi
        \code{strings/z_algorithm.cpp}

    \ifverbose
    \subsection{Trie}
        A Trie class.
        \code{strings/trie.cpp}
    \fi

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

    \subsection{Aho-Corasick Algorithm}
        \ifverbose
        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.
        \fi
        \code{strings/aho_corasick.cpp}

    \subsection{eerTree}
        \ifverbose
        Constructs an eerTree in $O(n)$, one character at a time.
        \fi
        \code{strings/eertree.cpp}
        % http://arxiv.org/pdf/1506.04862v1.pdf

    \subsection{Suffix Automaton}
        Minimum automata that accepts all suffixes of a string with $O(n)$
        construction. The automata itself is a DAG therefore suitable for DP,
        examples are counting unique substrings, occurrences of substrings and
        suffix.
        \code{strings/suffix_automaton.cpp}

    \subsection{Hashing}
        Modulus should be a large prime. Can also use multiple instances with
        different moduli to minimize chance of collision.
        \code{strings/hasher.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

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

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

    \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. Also
        contains an implementation of Lucas' theorem for computing the answer
        modulo a prime $p$.
        \code{mathematics/nck.cpp}

    \subsection{Euclidean algorithm}
        \ifverbose
        The Euclidean algorithm computes the greatest common divisor of two
        integers $a$, $b$.
        \fi
        \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}
        \ifverbose
        An optimized trial division to check whether an integer is prime.
        \fi
        \code{mathematics/is_prime.cpp}

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

    \subsection{Pollard's $\rho$ algorithm}
        \code{mathematics/pollard_rho.cpp}

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

    \subsection{Divisor Sieve}
        \ifverbose
        A O(n) prime sieve. Computes the smallest divisor of any number up to n.
        \fi
        \code{mathematics/divisor_sieve.cpp}

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

    \subsection{Modular Multiplicative Inverse}
        \ifverbose
        A function to find a modular multiplicative inverse. Alternatively use
        \texttt{mod\_{}pow(a,m-2,m)} when $m$ is prime.
        \fi
        \code{mathematics/mod_inv.cpp}

    \subsection{Primitive Root}
        \code{mathematics/primitive_root.cpp}

    \subsection{Chinese Remainder Theorem}
        \ifverbose
        An implementation of the Chinese Remainder Theorem.
        \fi
        \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{Tonelli-Shanks algorithm}
        Given prime $p$ and integer $1\leq n<p$, returns the square root $r$ of
        $n$ modulo $p$. There is also another solution given by $-r$ modulo
        $p$.
        \code{mathematics/tonelli_shanks.cpp}

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

    \subsection{Fast Fourier Transform}
        The Cooley-Tukey algorithm for quickly computing the discrete Fourier
        transform. The \texttt{fft} function only supports powers of twos. The
        \texttt{czt} function implements the Chirp Z-transform and supports any
        size, but is slightly slower.
        \code{mathematics/fft.cpp}
    \subsection{Number-Theoretic Transform}
        \code{mathematics/ntt.cpp}

    \subsection{Tridiagonal Matrix Algorithm}
        Solves a tridiagonal system of linear equations $a_ix_{i-1} + b_ix_i +
        c_ix_{i+1} = d_i$ where $a_1 = c_n = 0$. Beware of numerical
        instability.
        \code{mathematics/tridiagonal.cpp}

    \subsection{Mertens Function}
        Mertens function is $M(n) = \sum_{i=1}^n \mu(i)$. Let $L\approx
        (n\log{\log{n}})^{2/3}$ and the algorithm runs in $O(n^{2/3})$.
        \ifverbose
        \else
            Can also be easily changed to compute the summatory $\Phi$.
        \fi
        \code{mathematics/mertens.cpp}
    \ifverbose
    \subsection{Summatory Phi}
        The summatory phi function $\Phi(n) = \sum_{i=1}^n \phi(i)$. Let $L\approx
        (n\log{\log{n}})^{2/3}$ and the algorithm runs in $O(n^{2/3})$.
        \code{mathematics/summatory_phi.cpp}
    \fi

    \subsection{Prime $\pi$}
        Returns $\pi\left(\lfloor n/k\rfloor\right)$ for all $1\leq k \leq n$,
        where $\pi(n)$ is the number of primes $\leq n$. Can also be modified
        to accumulate any multiplicative function over the primes.
        \code{mathematics/primepi.cpp}

    \subsection{Numbers and Sequences}
        Some random prime numbers: 1031, 32771, 1048583, 33554467,
        1073741827, 34359738421, 1099511627791, 35184372088891,
        1125899906842679, 36028797018963971.

\section{Geometry}
    \subsection{Primitives}
        \ifverbose
        Geometry primitives.
        \fi
        \code{geometry/primitives.cpp}
    \subsection{Lines}
        \ifverbose
        Line related functions.
        \fi
        \code{geometry/lines.cpp}
    \subsection{Circles}
        \ifverbose
        Circle related functions.
        \fi
        \code{geometry/circles.cpp}

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

    \subsection{Convex Hull}
        \ifverbose
        An algorithm that finds the Convex Hull of a set of points.
        \fi
        NOTE: Doesn't work on some weird edge cases. (A small case that
        included three collinear lines would return the same point on both the
        upper and lower hull.)
        \code{geometry/convex_hull.cpp}

    \subsection{Line Segment Intersection}
        \ifverbose
        Computes the intersection between two line segments.
        \fi
        \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{Triangle Circumcenter}
        Returns the unique point that is the same distance from all three
        points. It is also the center of the unique circle that goes through
        all three points.
        \code{geometry/circumcenter.cpp}

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

    \subsection{3D Primitives}
        \ifverbose
        Three-dimensional geometry primitives.
        \fi
        \code{geometry/primitives3d.cpp}

    \subsection{Polygon Centroid}
        \code{geometry/polygon_centroid.cpp}

    \subsection{Rotating Calipers}
        \code{geometry/rotating_calipers.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$.
            \item \textbf{Euler's formula:} $V - E + F = 2$
            \item Side lengths $a,b,c$ can form a triangle iff.\ $a+b>c$, $b+c>a$ and $a+c>b$.
            \item Sum of internal angles of a regular convex $n$-gon is $(n-2)\pi$.
            \item \textbf{Law of sines:} $\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C}$
            \item \textbf{Law of cosines:} $b^2 = a^2 + c^2 - 2ac\cos B$
        \end{itemize}


\section{Other Algorithms}
    \subsection{2SAT}
        \ifverbose
        A fast 2SAT solver.
        \fi
        \code{other/two_sat.cpp}

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

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

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

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

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

    \subsection{Simulated Annealing}
        An example use of Simulated Annealing to find a permutation of length $n$
        that maximizes $\sum_{i=1}^{n-1}|p_i - p_{i+1}|$.
        \code{other/simulated_annealing.cpp}

    \subsection{Fast Square Testing}
        An optimized test for square integers.
        \code{tricks/is_square.cpp}

    \subsection{Fast Input Reading}
        \ifverbose
        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.
        \fi
        \code{tricks/fast_input.cpp}

    \ifverbose
    \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.
    \fi

    \subsection{Bit Hacks}
        \code{tricks/snoob.cpp}
    \begin{tabular}{@{}l|l|l@{}}
    \toprule
    Catalan	&	$C_0=1$, $C_n=\frac{1}{n+1}\binom{2n}{n} = \sum_{i=0}^{n-1}C_iC_{n-i-1} = \frac{4n-2}{n+1}C_{n-1}$  & \\
    Stirling 1st kind & $\left[{0\atop 0}\right]=1$, $\left[{n\atop 0}\right]=\left[{0\atop n}\right]=0$, $\left[{n\atop k}\right]=(n-1)\left[{n-1\atop k}\right]+\left[{n-1\atop k-1}\right]$ & \#perms of $n$ objs with exactly $k$ cycles\\
    Stirling 2nd kind & $\left\{{n\atop 1}\right\}=\left\{{n\atop n}\right\}=1$, $\left\{{n\atop k}\right\} = k \left\{{ n-1 \atop k }\right\} + \left\{{n-1\atop k-1}\right\}$ & \#ways to partition $n$ objs into $k$ nonempty sets\\
    Euler	& $\left \langle {n\atop 0} \right \rangle = \left \langle {n\atop n-1} \right \rangle = 1 $, $\left \langle {n\atop k} \right \rangle = (k+1) \left \langle {n-1\atop {k}} \right \rangle + (n-k)\left \langle {{n-1}\atop {k-1}} \right \rangle$ & \#perms of $n$ objs with exactly $k$ ascents \\
    Euler 2nd Order &  $\left \langle \!\!\left \langle {n\atop k} \right \rangle \!\! \right \rangle = (k+1) \left \langle \!\! \left \langle {{n-1}\atop {k}} \right \rangle \!\! \right \rangle +(2n-k-1)\left \langle \!\! \left \langle {{n-1}\atop {k-1}} \right \rangle  \!\! \right \rangle$ & \#perms of ${1,1,2,2,...,n,n}$ with exactly $k$ ascents \\
    Bell & $B_1 = 1$, $B_n = \sum_{k=0}^{n-1} B_k \binom{n-1}{k} = \sum_{k=0}^n\left\{{n\atop k}\right\}$ & \#partitions of $1..n$ (Stirling 2nd, no limit on k)\\
    \bottomrule
    \end{tabular}

    \vspace{10pt}
    \begin{tabular}{ll}
        \#labeled rooted trees & $n^{n-1}$ \\
        \#labeled unrooted trees & $n^{n-2}$ \\
        % Kirchoff's theorem
        $\sum_{i=1}^n i^2 = n(n+1)(2n+1)/6$ & $\sum_{i=1}^n i^3 = n^2(n+1)^2/4$ \\
        $!n = n\times!(n-1)+(-1)^n$ & $!n = (n-1)(!(n-1)+!(n-2))$ \\
        $\sum_{i=1}^n \binom{n}{i} F_i = F_{2n}$ & $\sum_{i} \binom{n-i}{i} = F_{n+1}$ \\
        $\sum_{k=0}^n \binom{k}{m} = \binom{n+1}{m+1}$ & \\

        $a\equiv b\pmod{x,y} \Rightarrow a\equiv b\pmod{\lcm(x,y)}$ & $\sum_{d|n} \phi(d) = n$ \\
        $ac\equiv bc\pmod{m} \Rightarrow a\equiv b\pmod{\frac{m}{\gcd(c,m)}}$ & $(\sum_{d|n} \sigma_0(d))^2 = \sum_{d|n} \sigma_0(d)^3$ \\
        $p$ prime $\Leftrightarrow (p-1)!\equiv -1\pmod{p}$ & $\gcd(n^a-1,n^b-1) = n^{\gcd(a,b)}-1$ \\
        $\sigma_x(n) = \prod_{i=0}^{r} \frac{p_i^{(a_i + 1)x} - 1}{p_i^x - 1}$ & $\sigma_0(n) = \prod_{i=0}^r (a_i + 1)$ \\
        $\sum_{k=0}^m (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}$ & \\
        $2^{\omega(n)} = O(\sqrt{n})$ & $\sum_{i=1}^n 2^{\omega(i)} = O(n \log n)$ \\
        $d = v_i t + \frac{1}{2}at^2$ & $v_f^2 = v_i^2 + 2ad$ \\
        $v_f = v_i + at$ & $d = \frac{v_i + v_f}{2}t$ \\
    \end{tabular}
    \subsection{The Twelvefold Way}
        Putting $n$ balls into $k$ boxes.\\
    \begin{tabular}{@{}c|c|c|c|c|l@{}}
    Balls & same & distinct & same & distinct & \\
    Boxes & same & same & distinct & distinct & Remarks\\
    \hline
    - & $\mathrm{p}_k(n)$ & $\sum_{i=0}^k \left\{{n\atop i}\right\}$ & $\binom{n+k-1}{k-1}$ & $k^n$ & $\mathrm{p}_k(n)$: \#partitions of $n$ into $\le k$ positive parts \\
    $\mathrm{size}\ge 1$ & $\mathrm{p}(n,k)$ & $\left\{{n\atop k}\right\}$ & $\binom{n-1}{k-1}$ & $k!\left\{{n\atop k}\right\}$ & $\mathrm{p}(n,k)$: \#partitions of $n$ into $k$ positive parts \\
    $\mathrm{size}\le 1$ & $[n \le k]$ & $[n \le k]$ & $\binom{k}{n}$ & $n!\binom{k}{n}$ & $[cond]$: $1$ if $cond=true$, else $0$\\
    \bottomrule
    \end{tabular}

\onecolumn
\begin{multicols*}{3}
\section{Useful Information}

    \section{Misc}
        \subsection{Debugging Tips}
            \begin{myitemize}
                \item Stack overflow? Recursive DFS on tree that is actually a long path?
                \item Floating-point numbers
                    \begin{itemize}
                        \item Getting \texttt{NaN}? Make sure \texttt{acos} etc.\ are
                            not getting values out of their range (perhaps
                            \texttt{1+eps}).
                        \item Rounding negative numbers?
                        \item Outputting in scientific notation?
                    \end{itemize}
                \item Wrong Answer?
                    \begin{itemize}
                        \item Read the problem statement again!
                        \item Are multiple test cases being handled correctly?
                              Try repeating the same test case many times.
                        \item Integer overflow?
                        \item Think very carefully about boundaries of all input parameters
                        \item Try out possible edge cases:
                            \begin{itemize}
                                \item $n=0, n=-1, n=1, n=2^{31}-1$ or $n=-2^{31}$
                                \item List is empty, or contains a single element
                                \item $n$ is even, $n$ is odd
                                \item Graph is empty, or contains a single vertex
                                \item Graph is a multigraph (loops or multiple edges)
                                \item Polygon is concave or non-simple
                            \end{itemize}
                        \item Is initial condition wrong for small cases?
                        \item Are you sure the algorithm is correct?
                        \item Explain your solution to someone.
                        \item Are you using any functions that you don't completely understand? Maybe STL functions?
                        \item Maybe you (or someone else) should rewrite the solution?
                    \end{itemize}
                \item Run-Time Error?
                    \begin{itemize}
                        \item Is it actually Memory Limit Exceeded?
                    \end{itemize}
            \end{myitemize}

        \subsection{Solution Ideas}
            \begin{myitemize}
                \item Dynamic Programming
                    \begin{itemize}
                        \item Drop a parameter, recover from others
                        \item Swap answer and a parameter
                        \item Parsing CFGs: CYK Algorithm
                        \item Optimizations
                            \begin{itemize}
                                \item Convex hull optimization
                                    \begin{itemize}
                                        \item $\mathrm{dp}[i] = \min_{j<i}\{\mathrm{dp}[j] + b[j] \times a[i]\}$
                                        \item $b[j] \geq b[j+1]$
                                        \item optionally $a[i] \leq a[i+1]$
                                        \item $O(n^2)$ to $O(n)$
                                    \end{itemize}
                                \item Divide and conquer optimization
                                    \begin{itemize}
                                        \item $\mathrm{dp}[i][j] = \min_{k<j}\{\mathrm{dp}[i-1][k] + C[k][j]\}$
                                        \item $A[i][j] \leq A[i][j+1]$
                                        \item $O(kn^2)$ to $O(kn\log{n})$
                                        \item sufficient: $C[a][c] + C[b][d] \leq C[a][d] + C[b][c]$, $a\leq b\leq c\leq d$ (QI)
                                    \end{itemize}
                                \item Knuth optimization
                                    \begin{itemize}
                                        \item $\mathrm{dp}[i][j] = \min_{i<k<j}\{\mathrm{dp}[i][k] + \mathrm{dp}[k][j] + C[i][j]\}$
                                        \item $A[i][j-1] \leq A[i][j] \leq A[i+1][j]$
                                        \item $O(n^3)$ to $O(n^2)$
                                        \item sufficient: QI and $C[b][c] \leq C[a][d]$, $a\leq b\leq c\leq d$
                                    \end{itemize}
                            \end{itemize}
                    \end{itemize}
                \item Greedy
                \item Randomized
                \item Optimizations
                    \begin{itemize}
                        \item Use bitset (/64)
                        \item Switch order of loops (cache locality)
                    \end{itemize}
                \item Process queries offline
                    \begin{itemize}
                        \item Mo's algorithm
                    \end{itemize}
                \item Square-root decomposition
                \item Precomputation
                \item Efficient simulation
                    \begin{itemize}
                        \item Mo's algorithm
                        \item Sqrt decomposition
                        \item Store $2^k$ jump pointers
                    \end{itemize}
                \item Data structure techniques
                    \begin{itemize}
                        \item Sqrt buckets
                        \item Store $2^k$ jump pointers
                        \item $2^k$ merging trick
                    \end{itemize}
                \item Counting
                    \begin{itemize}
                        \item Inclusion-exclusion principle
                        \item Generating functions
                    \end{itemize}
                \item Graphs
                    \begin{itemize}
                        \item Can we model the problem as a graph?
                        \item Can we use any properties of the graph?
                        \item Strongly connected components
                        \item Cycles (or odd cycles)
                        \item Bipartite (no odd cycles)
                            \begin{itemize}
                                \item Bipartite matching
                                \item Hall's marriage theorem
                                \item Stable Marriage
                            \end{itemize}
                        \item Cut vertex/bridge
                        \item Biconnected components
                        \item Degrees of vertices (odd/even)
                        \item Trees
                            \begin{itemize}
                                \item Heavy-light decomposition
                                \item Centroid decomposition
                                \item Least common ancestor
                            \end{itemize}
                        \item Eulerian path/circuit
                        \item Chinese postman problem
                        \item Topological sort
                        \item (Min-Cost) Max Flow
                        \item Min Cut
                            \begin{itemize}
                                \item Maximum Density Subgraph
                            \end{itemize}
                        \item Huffman Coding
                        \item Min-Cost Arborescence
                        \item Steiner Tree
                        \item Kirchoff's matrix tree theorem
                        \item Pr\"ufer sequences
                        \item Lov\'asz Toggle
                        \item Look at the DFS tree (which has no cross-edges)
                    \end{itemize}
                \item Mathematics
                    \begin{itemize}
                        \item Is the function multiplicative?
                        \item Look for a pattern
                        \item Permutations
                            \begin{itemize}
                                \item Consider the cycles of the permutation
                            \end{itemize}
                        \item Functions
                            \begin{itemize}
                                \item Sum of piecewise-linear functions is a piecewise-linear function
                                \item Sum of convex (concave) functions is convex (concave)
                            \end{itemize}
                        \item Modular arithmetic
                            \begin{itemize}
                                \item Chinese Remainder Theorem
                                \item Linear Congruence
                            \end{itemize}
                        \item Sieve
                        \item System of linear equations
                        \item Values to big to represent?
                            \begin{itemize}
                                \item Compute using the logarithm
                                \item Divide everything by some large value
                            \end{itemize}
                        \item Linear programming
                            \begin{itemize}
                                \item Is the dual problem easier to solve?
                            \end{itemize}
                    \end{itemize}
                \item Logic
                    \begin{itemize}
                        \item 2-SAT
                        \item XOR-SAT (Gauss elimination or Bipartite matching)
                    \end{itemize}
                \item Meet in the middle
                \item Only work with the smaller half ($\log(n)$)
                \item Strings
                    \begin{itemize}
                        \item Trie (maybe over something weird, like bits)
                        \item Suffix array
                        \item Suffix automaton (+DP?)
                        \item Aho-Corasick
                        \item eerTree
                        \item Work with $S+S$
                    \end{itemize}
                \item Hashing
                \item Euler tour, tree to array
                \item Segment trees
                    \begin{itemize}
                        \item Lazy propagation
                        \item Persistent
                        \item Implicit
                        \item Segment tree of X
                    \end{itemize}
                \item Geometry
                    \begin{itemize}
                        \item Minkowski sum (of convex sets)
                        \item Rotating calipers
                        \item Sweep line (horizontally or vertically?)
                        \item Sweep angle
                        \item Convex hull
                    \end{itemize}
                \item Fix a parameter (possibly the answer).
                \item Are there few distinct values?
                \item Binary search
                \item Sliding Window (+ Monotonic Queue)
                \item Computing a Convolution? Fast Fourier Transform
                \item Exact Cover (+ Algorithm X)
                \item Cycle-Finding
                \item What is the smallest set of values that identify the solution? The cycle structure of the permutation? The powers of primes in the factorization?
                \item Look at the complement problem
                    \begin{itemize}
                        \item Minimize something instead of maximizing
                    \end{itemize}
                \item Immediately enforce necessary conditions. (All values greater than 0? Initialize them all to 1)
                \item Add large constant to negative numbers to make them positive
                \item Counting/Bucket sort
            \end{myitemize}

    \section{Formulas}

        % \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}$


        \begin{itemize}[leftmargin=*]
            \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{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 $G=(L\cup R,E)$, the number
                of edges in a maximum matching is equal to the number of
                vertices in a minimum vertex cover. Let $U$ be the set of
                unmatched vertices in $L$, and $Z$ be the set of vertices that
                are either in $U$ or are connected to $U$ by an alternating
                path. Then $K=(L\setminus Z)\cup(R\cap Z)$ is the minimum
                vertex cover.
            \item A minumum Steiner tree for $n$ vertices requires at most $n-2$ additional Steiner vertices.
            \item The number of vertices of a graph is equal to its minimum
                vertex cover number plus the size of a maximum independent set.
            \item \textbf{Wilson's theorem:} $(n-1)! \equiv -1 \pmod{n}$ iff.\ $n$ is prime
            \item \textbf{Lagrange polynomial} through points $(x_0,y_0),\ldots,(x_k,y_k)$ is $L(x) = \sum_{j=0}^k y_j \prod_{\shortstack{$\scriptscriptstyle 0\leq m \leq k$ \\ $\scriptscriptstyle m\neq j$}} \frac{x-x_m}{x_j - x_m}$
            \item \textbf{Hook length formula:} If $\lambda$ is a Young diagram and $h_{\lambda}(i,j)$ is the hook-length of cell $(i,j)$, then then the number of Young tableux $d_{\lambda} = n!/\prod h_{\lambda}(i,j)$.
            \item \textbf{Möbius inversion formula:} If $f(n) = \sum_{d|n} g(d)$, then $g(n) = \sum_{d|n} \mu(d) f(n/d)$. If $f(n) = \sum_{m=1}^n g(\lfloor n/m\rfloor)$, then $g(n) = \sum_{m=1}^n \mu(m)f(\lfloor\frac{n}{m}\rfloor)$.
            \item \#primitive pythagorean triples with hypotenuse $<n$ approx $n/(2\pi)$.
            \item \textbf{Frobenius Number:} largest number which can't be
                expressed as a linear combination of numbers $a_1,\ldots,a_n$
                with non-negative coefficients. $g(a_1,a_2) = a_1a_2-a_1-a_2$,
                $N(a_1,a_2)=(a_1-1)(a_2-1)/2$. If $f(a_1,a_2,a_3) =
                g(a_1,a_2,a_3) + a_1+a_2+a_3$ then $f(d a_1,d a_2,a_3) = d f(a_1,a_2,a_3)$.
        \end{itemize}

        \subsection{Markov Chains}
            A Markov Chain can be represented as a weighted directed graph of
            states, where the weight of an edge represents the probability of
            transitioning over that edge in one timestep. Let $P^{(m)} = (p^{(m)}_{ij})$
            be the probability matrix of transitioning from state $i$ to state $j$
            in $m$ timesteps, and note that $P^{(1)}$ is the adjacency matrix of
            the graph. \textbf{Chapman-Kolmogorov:} $p^{(m+n)}_{ij} = \sum_{k}
            p^{(m)}_{ik} p^{(n)}_{kj}$. It follows that $P^{(m+n)} =
            P^{(m)}P^{(n)}$ and $P^{(m)} = P^m$. If $p^{(0)}$ is the initial
            probability distribution (a vector), then $p^{(0)}P^{(m)}$ is the
            probability distribution after $m$ timesteps.

            The return times of a state $i$ is $R_i = \{m\ |\ p^{(m)}_{ii} > 0 \}$,
            and $i$ is \textit{aperiodic} if $\gcd(R_i) = 1$. A MC is aperiodic if
            any of its vertices is aperiodic. A MC is \textit{irreducible} if the
            corresponding graph is strongly connected.

            A distribution $\pi$ is stationary if $\pi P = \pi$. If MC is
            irreducible then $\pi_i = 1/\mathbb{E}[T_i]$, where $T_i$ is the
            expected time between two visits at $i$. $\pi_j/\pi_i$ is the expected
            number of visits at $j$ in between two consecutive visits at $i$. A MC
            is \textit{ergodic} if $\lim_{m\to\infty} p^{(0)} P^{m} = \pi$. A MC is
            ergodic iff.\ it is irreducible and aperiodic.

            A MC for a random walk in an undirected weighted graph (unweighted
            graph can be made weighted by adding $1$-weights) has $p_{uv} =
            w_{uv}/\sum_{x} w_{ux}$. If the graph is connected, then $\pi_u =
            \sum_{x} w_{ux} / \sum_{v}\sum_{x} w_{vx}$. Such a random walk is
            aperiodic iff.\ the graph is not bipartite.

            An \textit{absorbing} MC is of the form $P = \left(\begin{matrix} Q & R
            \\ 0 & I_r \end{matrix}\right)$. Let $N = \sum_{m=0}^\infty Q^m = (I_t
            - Q)^{-1}$. Then, if starting in state $i$, the expected number of
            steps till absorption is the $i$-th entry in $N1$. If starting in state
            $i$, the probability of being absorbed in state $j$ is the $(i,j)$-th
            entry of $NR$.

            Many problems on MC can be formulated in terms of a system of
            recurrence relations, and then solved using Gaussian elimination.

        \subsection{Burnside's Lemma}
            Let $G$ be a finite group that acts on a set $X$. For each $g$ in $G$
            let $X^g$ denote the set of elements in $X$ that are fixed by $g$. Then
            the number of orbits \[ |X/G| = \frac{1}{|G|} \sum_{g\in G} |X^g| \]

        \subsection{Bézout's identity}
            If $(x,y)$ is any solution to $ax+by=d$ (e.g.\ found by the Extended
            Euclidean Algorithm), then all solutions are given by \[
            \left(x+k\frac{b}{\gcd(a,b)}, y-k\frac{a}{\gcd(a,b)}\right) \]

        \subsection{Misc}
            \subsubsection{Determinants and PM}
                \begin{align*}
                    det(A) &= \sum_{\sigma \in S_n}\text{sgn}(\sigma)\prod_{i = 1}^n a_{i,\sigma(i)}\\
                    perm(A) &= \sum_{\sigma \in S_n} \prod_{i = 1}^n a_{i,\sigma(i)}\\
                    pf(A) &= \frac{1}{2^nn!}\sum_{\sigma \in S_{2n}} \text{sgn}(\sigma)\prod_{i = 1}^n a_{\sigma(2i-1),\sigma(2i)}\\ &= \sum_{M \in \text{PM}(n)} \text{sgn}(M) \prod_{(i,j) \in M} a_{i,j}
                \end{align*}

            \subsubsection{BEST Theorem}
                Number of OST given by Kirchoff's Theorem (remove r/c with root)
                $\#\textsc{OST}(G,r) \cdot \prod_{v}(d_v-1)!$

            \subsubsection{Primitive Roots}
                Only exists when $n$ is $2, 4, p^k, 2p^k$, where $p$ odd prime. Assume
                $n$ prime. Number of primitive roots $\phi(\phi(n))$
                Let $g$ be primitive root. All primitive roots are of the form $g^k$
                where $k,\phi(p)$ are coprime.\\ $k$-roots:
                $g^{i \cdot \phi(n) / k}$ for $0 \leq i < k$

            \subsubsection{Sum of primes} For any multiplicative $f$:
                \[
                    S(n,p) = S(n, p-1) - f(p) \cdot (S(n/p,p-1) - S(p-1,p-1))
                \]

            \subsubsection{Floor}
                \begin{align*}
                    &\left\lfloor \left\lfloor x/y \right\rfloor / z \right\rfloor = \left\lfloor x / (yz) \right\rfloor \\
                    &x \% y = x - y \left\lfloor x / y \right\rfloor
                \end{align*}



    \clearpage
    \section*{Practice Contest Checklist}
        \begin{itemize}
            \item How many operations per second? Compare to local machine.
            \item What is the stack size?
            \item How to use printf/scanf with long long/long double?
            \item Is \texttt{\_{}\_{}int128} available?
            \item Does MLE give RTE or MLE as a verdict? What about stack overflow?
            \item What is \texttt{RAND\_{}MAX}?
            \item How does the judge handle extra spaces (or missing newlines) in the output?
            \item Look at documentation for programming languages.
            \item Try different programming languages: C++ and Java.
            \item Try the submit script.
            \item Try local programs: i?python[23], factor.
            \item Try submitting with \texttt{assert(false)} and \texttt{assert(false)}.
            \item Return-value from \texttt{main}.
            \item Look for directory with sample test cases.

            \item Remove this page from the notebook.
        \end{itemize}
\end{multicols*}
\end{document}