notebook/main.tex

%!TEX TS-program = xelatex
%!TEX encoding = UTF-8 Unicode

% TODO
% factoriser les
% typedef vector<int> VI;
% typedef vector<VI> VVI;
% typedef long long L;
% typedef vector<L> VL;
% typedef vector<VL> VVL;
% typedef pair<int, int> PII;
% typedef vector<PII> VPII;

% enlever les #include, using namespace std

\documentclass[8pt]{extarticle}
\usepackage[a4paper]{geometry}
\usepackage[french]{babel}
\usepackage{amssymb,amsthm,amsmath}
\usepackage{xltxtra}
\usepackage{stmaryrd}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}
\lstset{
	extendedchars=true,
	showstringspaces=false,
	escapeinside=``,
	keywordstyle=\color{blue},
	commentstyle=\color[rgb]{0.133,0.545,0.133},
	columns=flexible,
	language=C++,
	tabsize=2,
	basicstyle=\normalsize\selectfont\ttfamily,
	numbers=left,
	frame=lines,
	breaklines=true
}
\geometry{
	left=15mm,
	right=7mm,
	top=7mm,
	bottom=15mm
}
\usepackage{multicol}
\setlength{\columnsep}{1cm}

\title{ACM Notebook}
\author{4chan:  Thomas Espitau -- Shendan Jin -- Olivier Marty}
\date\today

\begin{document}

\maketitle

\tableofcontents

\begin{multicols}{2}

%\chapter{ACM Cookbook}
\section{Algorithmique du texte}

\subsection{Tableaux de suffixes}
Temps de cuisson : $O(n \log^2 n)$
{\scriptsize\lstinputlisting{code/suffix.cpp}} % TODO

\subsection{Knuth-Morris-Pratt}
Temps de cuisson : $O(n)$
{\scriptsize\lstinputlisting{code/kmp.cpp}} % OK

\subsection{Rabin-Karp 2D}
{\scriptsize\lstinputlisting{code/RabinKarp.cpp}} % OK

\subsection{AC Automaton}
{\scriptsize\lstinputlisting{code/ACAutomaton.cpp}} % OK

\section{Optimisation}

\subsection{Sparse max-flow}
{\scriptsize\lstinputlisting{code/Dinic.cc}} % OK % à supprimer ?

\subsection{Min-cost max-flow}
{\scriptsize\lstinputlisting{code/MinCostMaxFlow.cc}} % OK

\subsection{Push-relabel max-flow}
{\scriptsize\lstinputlisting{code/PushRelabel.cc}} % OK

\subsection{Min-cost matching}
{\scriptsize\lstinputlisting{code/MinCostMatching.cc}} % OK

\subsection{Max bipartite matching $O(EV)$}
{\scriptsize\lstinputlisting{code/MaxBipartiteMatching.cc}}

\subsection{Max bipartite matching $O(E\sqrt V)$}
{\scriptsize\lstinputlisting{code/MaxBipartiteMatching_sqrt.cc}} % OK

\subsection{Stable matchings}
{\scriptsize\lstinputlisting{code/StableMatchings.cpp}}

\subsection{Global min cut}
{\scriptsize\lstinputlisting{code/MinCut.cc}}

\section{Géométrie}

\subsection{Convex hull}
{\scriptsize\lstinputlisting{code/ConvexHull.cc}} % OK

\subsection{Miscellaneous geometry}
{\scriptsize\lstinputlisting{code/Geometry.cc}}
% OK RotateCCW
% OK ComputeSignedArea

\subsection{Closest Pair}
{\scriptsize\lstinputlisting{code/ClosestPair.cpp}}

\subsection{Slow Delaunay triangulation}
{\scriptsize\lstinputlisting{code/Delaunay.cpp}} % TODO chercher algo en N (incremental flip)

\section{Algorithmes numériques}

\subsection{Number theoretic algorithms (modular, Chinese remainder, linear Diophantine)}
{\scriptsize\lstinputlisting{code/Euclid.cpp}}

\subsection{Discrete Logarithm $O(\sqrt n\log n)$}
{\scriptsize\lstinputlisting{code/DiscreteLog.cpp}}

\subsection{Euler's function}
{\scriptsize\lstinputlisting{code/Euler.cpp}}

\subsection{Systems of linear equations, matrix inverse, determinant}
{\scriptsize\lstinputlisting{code/GaussJordan.cc}}

\subsection{Reduced row echelon form, matrix rank}
{\scriptsize\lstinputlisting{code/ReducedRowEchelonForm.cc}}

\subsection{Fast Fourier transform}
{\scriptsize\lstinputlisting{code/FFT.cpp}} % OK

\subsection{Simplex algorithm}
{\scriptsize\lstinputlisting{code/Simplex.cc}} % OK

\section{Graphes}

\subsection{Fast Dijkstra's algorithm}
{\scriptsize\lstinputlisting{code/FastDijkstra.cc}}

\subsection{Strongly connected components}
{\scriptsize\lstinputlisting{code/SCC.cc}}

\subsection{DFS/BFS}
{\scriptsize\lstinputlisting{code/BFS_DFS.cpp}} % OK

\subsection{Bellman-Ford}
{\scriptsize\lstinputlisting{code/BellmanFord.cpp}} % OK

\subsection{Topological Sort}
{\scriptsize\lstinputlisting{code/TopologicalSort.cpp}}

\section{Structures de données}

\subsection{Suffix arrays}
{\scriptsize\lstinputlisting{code/SuffixArray.cpp}}

\subsection{Binary Indexed Tree}
{\scriptsize\lstinputlisting{code/BIT.cc}}

\subsection{Union-Find Set}
{\scriptsize\lstinputlisting{code/UnionFind.cc}}

\subsection{KD-tree}
{\scriptsize\lstinputlisting{code/KDTree.cc}}

\subsection{Segment Tree}
{\scriptsize\lstinputlisting{code/SegmentTree.cpp}} % OK

\subsection{Treap}
{\scriptsize\lstinputlisting{code/Treap.cpp}} % OK

\subsection{Bits Sets}
{\scriptsize\lstinputlisting{code/BitSet.cpp}} % OK

\section{Divers}

\subsection{Longest increasing subsequence}
{\scriptsize\lstinputlisting{code/LongestIncreasingSubsequence.cpp}}

\subsection{Maximum rectangle under an histogram / in a matrix}
{\scriptsize\lstinputlisting{code/BiggestRectangle.cpp}}

\subsection{Number of inversions}
{\scriptsize\lstinputlisting{code/Inversion.cpp}} % OK


\subsection{Dichotomie}
{\scriptsize\lstinputlisting{code/Dichotomie.cpp}} % regarder

\subsection{Dates}
{\scriptsize\lstinputlisting{code/Dates.cpp}}

\subsection{Prime numbers}
{\scriptsize\lstinputlisting{code/Primes.cc}}

\subsection{Tips}
{\scriptsize\lstinputlisting{code/Tips.cpp}}

\subsection{Skeleton}
{\scriptsize\lstinputlisting{code/Skeleton.cpp}}

\section{Oppa Shendan Style}

\subsection{Eulerian Circuit}
{\scriptsize\lstinputlisting{code/EulerCircuit.cpp}}

\subsection{Test Bipartite Graph}
{\scriptsize\lstinputlisting{code/BipartiteTest.cpp}}

\subsection{Cut vertex / Bridge}
{\scriptsize\lstinputlisting{code/CutVertexBridge.cpp}}

\subsection{Biconnected component}
{\scriptsize\lstinputlisting{code/BCC.cpp}}

\subsection{2 SAT}
{\scriptsize\lstinputlisting{code/2SAT.cpp}}

\subsection{Binomial coefficient}
{\scriptsize\lstinputlisting{code/Binom.cpp}}

\subsection{Exact Cover}
{\scriptsize\lstinputlisting{code/ExactCover.cpp}}

\subsection{RMQ Offline}
{\scriptsize\lstinputlisting{code/RMQ_offline.cpp}}

\subsection{Trie}
{\scriptsize\lstinputlisting{code/Trie.cpp}}

\subsection{Z-function}
{\scriptsize\lstinputlisting{code/ZFunction.cpp}}

\subsection{Floyd-Warshall (all shortest path)}
{\scriptsize\lstinputlisting{code/FloydWarshall.cpp}}

\subsection{Hash function for string}
{\scriptsize\lstinputlisting{code/Hash.cpp}}

\subsection{Rank Tree}
{\scriptsize\lstinputlisting{code/RankTree.cpp}}


\end{multicols}
\end{document}