tn.tex

% Team Note Sample Template
% These codes should be guaranteed, fast enough, short and easy to type.

\documentclass[landscape, 10pt, a4paper, oneside, twocolumn]{extarticle}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{import}
\usepackage{mathtools}

\usepackage{teamnote}

\teamnote{Petrozavodsk State University}{QA}{(Remeslennikov, Evstafeev, Titov)}

\ShowUsage
\ShowComplexity
\HideAuthor

\begin{document}

\maketitlepage

% TODO: Add pagebreak
% Make Pagebreak if you want.
% \pagebreak 


\section{Templates}

\Algorithm
{C++ template}
{Ez win template: go to St. Petersburg, write template, solve problems, submit solutions, get OK, win NEERC 2018}
{$\mathcal{O}(1)$}
{cpp}{source/templates/solution.cpp}

\Algorithm
{Stress test}
{When you feel bad, you run this code and go walk with green badge, and get OK}
{$\mathcal{O}(\infty)$}
{cpp}{source/templates/stress.cpp}

\Algorithm
{Java template}
{Petr Mitrichev template}
{$\mathcal{O}(1)\ for\ all\ tasks$}
{java}{source/templates/solution.java}

\Algorithm
{Any troubleshoots?}
{ix ay way}
{}
{text}{source/troubleshoot.txt}




\section{Graphs}

\Algorithm
{Dinic}
{Almost linear in practice. $\mathcal{O}(m \sqrt n)$ on unit network.}
{$\mathcal{O}(n^{2}m)$}
{cpp}{source/graphs/dinic.cpp}

\Algorithm
{Mincost}
{Complexity is strange but in practice works nice.}
{$\mathcal{O}(N * M) * T(N, M)$, where $T(N, M)$ – time complexity for SPFA(or any other shortest path algorithm) for graph with $N$ vertex and $E$ edges.}
{cpp}{source/graphs/mincost.cpp}

\Algorithm
{Bridges and Cut points}
{Works with multi edges but adds extra $ \log n$.}
{$\mathcal{O}(n \log n)$}
{cpp}{source/graphs/bridges_and_cutpoints.cpp}

\Algorithm
{LCA with binary lifting}
{Need to run dfs and precalc binary liftings.}
{Precalc – $\mathcal{O}(n \log n)$, Query – $\mathcal{O}(\log n)$}
{cpp}{source/graphs/lca_binary_lifting_wiki_conspects.cpp}

\Algorithm
{Kuhn with greedy heuristic}
{Supposed to run faster than usual Kuhn.}
{$\mathcal{O}(n^{3})$}
{cpp}{source/graphs/kuhn_with_greedy_heuristic.cpp}

\Algorithm
{Weighted biparate matching}
{Kuznecov favorite algorith}
{$\mathcal{O}(n^{3})$}
{cpp}{source/graphs/weighted_biparate_matching.cpp}

\Algorithm
{Dijkstra with POTs}
{Is it really pot? seems like not}
{$\mathcal{O}(N\ M + N\ E\ logN)$}
{cpp}{source/graphs/dijkstra_pot.cpp}

\Algorithm
{MinCut}
{After running max-flow, the left side of a min-cut from $s$ to $t$ is given by all vertices reachable from $s$, only traversing edges with positive residual capacity.}
{}
{cpp}{}




\section{Data Structures}

\Algorithm
{Treap}
{Implementation supports 2 kinds of operations: sum and reverse queries on $[l, r]$.}
{Building – $\mathcal{O}(n \log n)$, Query – $\mathcal{O}(\log n)$}
{cpp}{source/data_structures/treap.cpp}

\Algorithm
{Fenwick}
{Considered to work in constant time in practice.}
{$\mathcal{O}(\log n), \mathcal{O}(\log n)$}
{cpp}{source/data_structures/fenwick.cpp}

\Algorithm
{Sparse table}
{Not to fack up.}
{$\mathcal{O}(n \log n), \mathcal{O}(1)$}
{cpp}{source/data_structures/sparse_table.cpp}

% CAN REMOVE IT
\Algorithm
{Heavy-light}
{Implementation by Jesus-Svyat}
{Building - $\mathcal{O}(n)$, Min/Max/Lca query – $\mathcal{O}(\log^2 n)$}
{cpp}{source/data_structures/heavy_light.cpp}

\Algorithm
{Centroid Decomposition}
{Store something in centroids for example pair with distance to other vertices & etc.
Properties:
    \begin{enumerate}
        \item Depth of the CD tree $ \leq \mathcal{O}(\log n)$.
        \item Every vertex $v$ of the tree $t$ is centroid of some subtree of $t$.
        \item Every vertex belongs to $\mathcal{O}(\log n)$ subtrees of $T$.
        \item For any $u, v \in T (u \neq v)$ one of the following conditions is met:
            \begin{itemize}
                \item $T(v) \subset T(u)$
                \item $T(u) \subset T(v)$
                \item $T(u) \cap T(v) = \emptyset $
            \end{itemize}
        \item Simple path between every pair vertex $u, v$ has centroid $c \in T(t)$ such that $u, v \in T(c)$. 
    \end{enumerate}
}
{$\mathcal{O}(n \log n), \mathcal{O}(1)$}
{cpp}{source/data_structures/centroid_decomposition.cpp}

\Algorithm
{Order statistic tree}
{A set (not multiset!) with support for finding the n'th element, and finding the index of an element.To get a map, change $\texttt{null\_type}$}
{Query – $\mathcal{O}(\log n)$}
{cpp}{source/data_structures/order_statistic_tree.cpp}

\Algorithm
{HashMap}
{Hash map with the same API as unordered map, but ∼3x faster. Initial capacity must be a power of 2 (if provided).}
{Query – $\mathcal{O}(1)$}
{cpp}{source/data_structures/hash_map.cpp}

\Algorithm
{Line Container}
{Container where you can add lines of the form $kx+m$, and query maximum values at points $x$. Useful for dynamic programming.}
{$\mathcal{O}(\log n)$}
{cpp}{source/data_structures/line_container.cpp}





\section{Strings}

\Algorithm
{Prefix-function}
{}
{$\mathcal{O}(n)$}
{cpp}{source/strings/prefix_function.cpp}

\Algorithm
{Z-function}
{}
{$\mathcal{O}(n)$}
{cpp}{source/strings/z_function.cpp}

\Algorithm
{Polynomial hashes}
{Almost unbreakable.}
{$\mathcal{O}(n), \mathcal{O}(1)$}
{cpp}{source/strings/hashes.cpp}

\Algorithm
{Manacher}
{$p[0][i]$ – even case, let $len = p[0][i]$,
it means that maximal even palindrome located on $[i - len, i + len - 1]$,

$p[1][i]$ – even case, let $len = p[0][i]$,
it means that maximal odd palindrome located on $[i - len, i + len]$
}
{$\mathcal{O}(n)$}
{cpp}{source/strings/manacher.cpp}

\Algorithm
{Suffix array}
{Implementation by Mihail Pyaderkin :)}
{$\mathcal{O}(n \log n)$}
{cpp}{source/strings/suffix_array.cpp}

\Algorithm
{LCP (Kasai)}
{Write suffix array and after that use this code}
{$\mathcal{O}(n)$}
{cpp}{source/strings/lcp_kasai.cpp}

\Algorithm
{Aho-Corasick}
{Build automaton on given dictionary}
{Building - $\mathcal{O}(\sum|words|)$}
{cpp}{source/strings/aho-corasick.cpp}


\Algorithm
{Palindromic tree}
{Implementation by Merkurev}
{Building - $\mathcal{O}(|s| \log \sum)$}
{cpp}{source/strings/palindromic_tree.cpp}





\section{Math}

\Algorithm
{Linear inverse modulo prime}
{Suprisingly laconic.}
{$\mathcal{O}(p)$}
{cpp}{source/math/linear_inverse.cpp}

\Algorithm
{FFT}
{You never know, you never know...}
{$\mathcal{O}(n \log n)$}
{cpp}{source/math/fft.cpp}

\Algorithm
{Gauss}
{Solves system of linear equations.}
{$\mathcal{O}(n^{3})$}
{cpp}{source/math/gauss.cpp}

\Algorithm
{Next combination}
{Gen C(N, K)}
{$\mathcal{O}(C_{n}^{k})$}
{cpp}{source/data_structures/next_combination.cpp}

\Algorithm
{Chineeze theorem find X}
{Find x from reminders.}
{$\mathcal{O}(K^{2})$}
{cpp}{source/math/chineeze_find_ans.cpp}

\Algorithm
{Calculating N! by prime P}
{Find N!}
{$\mathcal{O}(P log N)$}
{cpp}{source/math/n_fact_by_prime.cpp}

\Algorithm
{Gray's code}
{Numeric system with different between two adjansted numbers in 1 bit, ex: $000, 001, 011, 010, 110, 111, 101, 100$}
{$\mathcal{O}(1)$}
{cpp}{source/math/gray_code.cpp}

\Algorithm
{Euler function}
{$\phi(n) = $ count of number in $1..n$, with $gcd(i, n) = 1$}
{$\mathcal{O}(\sqrt{N})$}
{cpp}{source/math/euler_f.cpp}

\Algorithm
{Eratosthene's sieve}
{you can calculate with blocks, remember}
{$\mathcal{O}(N)$}
{cpp}{source/math/eratosthenes_sieve.cpp}

\Algorithm
{Extended gcd}
{Find $a x + b y = gcd(a, b)$}
{$\mathcal{O}(Good\ log\ max(A, B))$}
{cpp}{source/math/ext_gcd.cpp}

\Algorithm
{Miller Rabin primality probabilistic test}
{Probability of failing one iteration is at most 1/4. 15 iterations should be enough for 50-bit numbers.}
{15 times the complexity of $a^b \mod c$ (.)(.)}
{cpp}{source/math/miller_rabin_is_prime.cpp}

\Algorithm
{Factorization. Rho-Pollard method}
{Pollard's rho algorithm. It is a probabilistic factorisation algorithm, whose expected time complexity is good. Before you start using it, run {\tt init(bits)}, where bits is the length of the numbers you use. Returns factors of the input without duplicates.}
{$\mathcal{O}(n^{\frac{1}{4}})$}
{cpp}{source/math/rho_pollard.cpp}



\Algorithm
{Golden section search}
{Finds the argument minimizing the function $f$ in the interval $[a,b]$ assuming $f$ is unimodal on the interval, i.e. has only one local minimum. The maximum error in the result is $eps$. Works equally well for maximization with a small change in the code. See TernarySearch.h in the Various chapter for a discrete version.

double func(double x) { return 4+x+.3*x*x; }

double xmin = gss(-1000,1000,func);}
{$\mathcal{O}(\log((b-a) / \epsilon))$}
{cpp}{source/math/golden_section_search.cpp}

% TODO: add formulae for power sums
\Formula
{Power sums}
{
    \begin{gather}
        \sum_{k=1}^{n} k = \frac{n \times (n + 1)}{2} \\
        \sum_{k=1}^{n} k^{2} = \frac{n \times (n + 1) \times (2 * n + 1)}{6} \\
        \sum_{k=1}^{n} k^{3} = \frac{n^{2} \times (n + 1)^2}{4} \\
        \sum_{k=1}^{n} k^{4} = \frac{n \times (n + 1) \times (3 * n^{2} + 3 * n - 1)}{30} \\
        \sum_{k=1}^{n} k^{5} = \frac{n^{2} \times (n + 1)^{2} \times (2 * n^{2} + 2 * n - 1)}{12} \\
        \sum_{k=1}^{n} k^{6} = \frac{n \times (n + 1) \times (2 * n + 1) \times (3 * n^{4} + 6 * n^{3} + 3 * n + 1)}{42} \\
        \sum_{k=1}^{n} k^{7} = \frac{n^{2} \times (n + 1)^{2} \times (3 * n^{4} + 6 * n^{3} - n^{2} - 4 * n + 2)}{24} \\
        \sum_{k=1}^{n} k x^{k} = \frac{x - (n + 1) x^{n + 1} + n x^{n + 2}}{(x - 1)^{2}}
    \end{gather}
}

\Formula
{Langrange polynom}
{
    $L(x) = \sum_{i=0}^{n} y_{i} l_{i} (x)$ \\
    $l_{i} (x) = \prod_{j=0,\ j \neq i}^{n} \frac{x - x_{j}}{x_{i} - x_{j}}$ \\
    Properties: $l_{i} (x_{i}) = 1; l_{i} (x_{j}) = 0, i \neq j$
}

\Formula
{Svyat formulas}
{
    $\int_{a}^{b} f(x) dx = \frac{b - a}{6} (f(a) + 4 f(\frac{a + b}{2}) + f(b)) $ \\
    Catalan numbers $C_{n} = \frac{1}{n+1} C_{2n}^{n} $ \\
    Stirling numbers of the $1^{st}$ kind: $s_{n, k} = s_{n - 1, k - 1} + (n - 1) s_{n - 1, k}$ \\
    Stirling numbers of the $2^{nd}$ kind: $s_{n, k} = s_{n - 1, k - 1} + k s_{n - 1, k}$, where $s_{n, 1} = s_{n, n} = 1$ \\
    Wilson's theore-MEMES $p$ - prime, $(p - 1)! = - 1,\ mod\ p$ \\
    Taylor XD Series: $f(x) = \sum_{k=0}^{\infty} \frac{(x - a)^{k}}{k!} f^{(k)}(a)$ 
}




% TODO: Serega, add your own shit here
\section{Geometry}

\Formula
{Pick's Theorem}
{$S = I + \frac{B}{2} - 1$, where $I$ - count of points strictly inside polygon, $B$ - count of points on boundary.}

\Formula
{Two circles intersection}
{$A = -2 x_{2}, B = - 2 y_{2}, C = x_{2}^{2} + y_{2}^{2} + r_{1}^{2} - r_{2}^{2}$}

\Formula
{Distance on sphere}
{$L = R \times cos^{-1}( sin(\phi_{a}) sin(-+ \phi_{b}) + cos(\phi_{a}) cos(-+ \phi_{b}) cos(\lambda_{a} -+ \lambda_{b}) ) $}

\Formula
{Rotation matrix 2d}
{$M = \left( \begin{smallmatrix} cos\theta & - sin\theta \\ sin\theta & cos\theta \end{smallmatrix} \right)$}

\Formula
{Sphere coordinates}
{
    $r = \sqrt{x^{2} + y^{2} + z^{2}}, \theta = arccos(\frac{z}{r}), \phi = \arctan(\frac{y}{x})$ \\
    $x = r sin \theta cos \phi, y = r sin \theta \sin \phi, z = r cos \theta$ \\ 
}

\Formula
{Rotation matrix by axis}
{ $ M = 
	\left ( 
		\begin{smallmatrix} 
			cos\theta + u_{x}^{2} (1 - cos\theta) \  & u_{x} u_{y} (1 - cos\theta) - u_{z} sin\theta \ & u_{x} u_{z} (1 - cos\theta) + u_{y} sin\theta \\ 
			u_{y} u_{x} (1 - cos\theta) + u_{z} sin\theta \ & cos\theta + u_{y}^{2} (1 - cos\theta) \ & u_{y} u_{z} (1 - cos\theta) - u_{x} sin\theta \\ 
			u_{z} u_{x} (1 - cos\theta) - u_{y} sin\theta \ & u_{z} u_{y} (1 - cos\theta) + u_{x} sin\theta \ & cos\theta + u_{z}^{2} (1 - cos\theta)
		\end{smallmatrix} 
	\right ) $
}

\Algorithm
{Minkovsky sum}
{Sort $V$ and $W$ by counterclockwise angle, leftmost bottommost first}
{$\mathcal{O}(n + m)$}
{cpp}{source/geometry/minkovsky.cpp}

\Algorithm
{Half plane intersection}
{Timon and Dimon never let it go}
{$\mathcal{O}(n logn)$}
{cpp}{source/geometry/half_plane_intersection.cpp}

\Algorithm
{Closest pair}
{Can be modificated to find triangle with minimal perimiter}
{$\mathcal{O}(n logn)$}
{cpp}{source/geometry/closest_pair.cpp}

\end{document}