diff options
| -rw-r--r-- | Makefile | 21 | ||||
| -rw-r--r-- | datastructures/datastructures.tex | 43 | ||||
| -rw-r--r-- | datastructures/dynamicConvexHull.cpp | 10 | ||||
| -rw-r--r-- | datastructures/monotonicConvexHull.cpp | 43 | ||||
| -rw-r--r-- | datastructures/test/monotonicConvexHull.cpp | 26 | ||||
| -rw-r--r-- | datastructures/unionFind2.cpp | 33 | ||||
| -rw-r--r-- | geometry/geometry.tex | 13 | ||||
| -rw-r--r-- | graph/graph.tex | 18 | ||||
| -rw-r--r-- | java/java.tex | 4 | ||||
| -rw-r--r-- | latexHeaders/commands.sty | 7 | ||||
| -rw-r--r-- | math/math.tex | 9 | ||||
| -rw-r--r-- | tcr.tex | 6 |
12 files changed, 168 insertions, 65 deletions
@@ -1,11 +1,19 @@ TESTS = \ datastructures/test/fenwickTree.test \ datastructures/test/fenwickTree2.test \ + datastructures/test/monotonicConvexHull.test \ graph/test/binary_lifting.test \ graph/test/LCA_sparse.test -pdf: - latexmk -pdf tcr +LATEXMK = latexmk -interaction=nonstopmode + +tcr.pdf: FORCE + $(LATEXMK) -pdf tcr + +pdf: tcr.pdf tcr-opt.pdf + +tcr-opt.pdf: FORCE + $(LATEXMK) -pdf -jobname=tcr-opt -usepretex="\def\OPTIONAL{}" tcr all: pdf test @@ -14,7 +22,8 @@ test: $(TESTS:.test=.ok) clean: cleanpdf cleantest cleanpdf: - latexmk -c tcr + $(LATEXMK) -C tcr + $(LATEXMK) -C -jobname=tcr-opt tcr rm -f *.thm cleantest: @@ -31,9 +40,13 @@ datastructures/test/fenwickTree.test: datastructures/test/fenwickTree.cpp \ datastructures/fenwickTree.cpp datastructures/test/fenwickTree2.test: datastructures/test/fenwickTree2.cpp \ datastructures/fenwickTree2.cpp +datastructures/test/monotonicConvexHull.test: \ + datastructures/test/monotonicConvexHull.cpp \ + datastructures/monotonicConvexHull.cpp graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ graph/binary_lifting.cpp graph/test/util.cpp graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ graph/LCA_sparse.cpp datastructures/sparseTable.cpp graph/test/util.cpp -.PHONY: all pdf test clean cleanpdf cleantest +FORCE: +.PHONY: all pdf test clean cleanpdf cleantest FORCE diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 37a1dc2..0285490 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -29,7 +29,7 @@ \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} \end{algorithm} -\clearpage +\columnbreak \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} \sourcecode{datastructures/stlRope.cpp} @@ -54,6 +54,14 @@ \sourcecode{datastructures/sparseTable.cpp} \end{algorithm} +\begin{algorithm}[optional]{Range Aggregate Query} + \begin{methods} + \method{init}{baut Struktur auf}{n\*\log(n)} + \method{query}{Aggregat über [l,r)}{1} + \end{methods} + \sourcecode{datastructures/sparseTableDisjoint.cpp} +\end{algorithm} + \begin{algorithm}{Wavelet Tree} \begin{methods} \method{Constructor}{baut den Baum auf}{n\*\log(n)} @@ -79,7 +87,7 @@ \end{methods} \sourcecode{datastructures/LCT.cpp} \end{algorithm} -\clearpage +\columnbreak \begin{algorithm}{Union-Find} \begin{methods} @@ -91,11 +99,37 @@ \sourcecode{datastructures/unionFind.cpp} \end{algorithm} -\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} - Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. +\begin{algorithm}[optional]{Union-Find with size} + \begin{methods} + \method{init}{legt $n$ einzelne Unions an}{n} + \method{findSet}{findet den Repräsentanten}{\log(n)} + \method{unionSets}{vereint 2 Mengen}{\log(n)} + \method{getSize}{zählt Elemente in Menge, die $i$ enthält}{\log(n)} + \method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)} + \end{methods} + \sourcecode{datastructures/unionFind2.cpp} +\end{algorithm} + +\begin{algorithm}{Lower Envelope (Convex Hull Optimization)} + Um aus einem Lower Envelope einen Upper Envelope zu machen (oder + umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. + \subsubsection{Monotonic} + \begin{methods} + \method{add}{add line $mx + b$, $m$ is decreasing}{1} + \method{query}{minimum value at $x$, $x$ is increasing}{1} + \end{methods} \sourcecode{datastructures/monotonicConvexHull.cpp} \columnbreak + \subsubsection{Dynamic} + \begin{methods} + \method{add}{add line $mx + b$}{\log(n)} + \method{query}{minimum value at $x$}{\log(n)} + \end{methods} \sourcecode{datastructures/dynamicConvexHull.cpp} + \optional{ + \subsubsection{Li Chao tree \opthint} + \sourcecode{datastructures/lichao.cpp} + } \end{algorithm} \begin{algorithm}{Persistent} @@ -105,6 +139,7 @@ \method{reset}{setzt die Datenstruktur auf Zeitpunkt $t$}{1} \end{methods} \sourcecode{datastructures/persistent.cpp} + \columnbreak \sourcecode{datastructures/persistentArray.cpp} \end{algorithm} diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index d669847..2bd67a6 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { auto x = insert({m, b, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { - x--; - if (isect(x, next(x))) { - erase(next(x)); - isect(x, next(x)); - }} + --x; + while (isect(x, next(x))) erase(next(x)); + } while (x != begin() && prev(x)->p >= x->p) { - x--; + --x; isect(x, erase(next(x))); }} diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 44bff83..e7b9b3e 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,26 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. -struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} -}; +struct Envelope { + struct Line { + ll m, b; + ll operator()(ll x) { return m*x+b; } + }; -vector<Line> ls; -int ptr = 0; + vector<Line> ls; + int ptr = 0; -bool bad(Line l1, Line l2, Line l3) { - return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); -} + static bool bad(Line l1, Line l2, Line l3) { + return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); + } -void add(ll m, ll b) { // Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { - ls.pop_back(); + void add(ll m, ll b) { + while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) { + ls.pop_back(); + } + ls.push_back({m, b}); + ptr = min(ptr, sz(ls) - 1); } - ls.push_back({m, b}); - ptr = min(ptr, sz(ls) - 1); -} -ll query(ll x) { // Laufzeit: O(1) amortisiert - ptr = min(ptr, sz(ls) - 1); - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; - return ls[ptr](x); -}
\ No newline at end of file + ll query(ll x) { + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); + } +}; diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp new file mode 100644 index 0000000..62ea4cd --- /dev/null +++ b/datastructures/test/monotonicConvexHull.cpp @@ -0,0 +1,26 @@ +#include "../monotonicConvexHull.cpp" + +int main() { + { + Envelope env; + env.add(10, 0); + assert(env.query(0) == 0); + assert(env.query(1) == 10); + env.add(8, 5); + assert(env.query(1) == 10); + assert(env.query(2) == 20); + assert(env.query(3) == 29); + env.add(7, 10); + assert(env.query(10) == 80); + env.add(0, 0); + assert(env.query(11) == 0); + } + + { + Envelope env; + env.add(1, 0); + env.add(0, 10); + env.add(-1, 10); + assert(env.query(7) == 3); + } +} diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp index 5362c4d..d1b9162 100644 --- a/datastructures/unionFind2.cpp +++ b/datastructures/unionFind2.cpp @@ -1,25 +1,26 @@ -vector<int> uf; +// unions[i] >= 0 => unions[i] = parent +// unions[i] < 0 => unions[i] = -size +vector<int> unions; -init(int N) { - uf.assign(N,-1); //-1 indicates that every subset has size 1 +init(int n) { + unions.assign(n, -1); } int findSet(int i) { - if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root - uf[i] = findSet(uf[i]); //Path-Compression - return uf[i]; + if (unions[i] < 0) return i; + return unions[i] = findSet(unions[i]); } -void linkSets(int i, int j) { - //Take |uf[i]|, where i must be a root, to get the size - //of the subset - if(abs(uf[i]) < abs(uf[j])) { //Union-by-size. - uf[j] += uf[i]; uf[i] = j; - } else { - uf[i] += uf[j]; uf[j] = i; - } +void linkSets(int a, int b) { // Union by size. + if (unions[b] > unions[a]) swap(a, b); + unions[b] += unions[a]; + unions[a] = b; } -void unionSets(int i, int j) { - if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j)); +void unionSets(int a, int b) { + if (findSet(a) != findSet(b)) linkSets(findSet(a),findSet(b)); +} + +void getSize(int i) { + return -unions[findSet(i)]; } diff --git a/geometry/geometry.tex b/geometry/geometry.tex index d740f46..75184df 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -41,7 +41,7 @@ \sourcecode{geometry/formulars3d.cpp} \optional{ - \subsection{3D-Kugeln} + \subsection{3D-Kugeln \opthint} \sourcecode{geometry/spheres.cpp} } @@ -49,15 +49,22 @@ \sourcecode{geometry/hpi.cpp} \end{algorithm} +\begin{algorithm}[optional]{Intersecting Segments} + \begin{methods} + \method{intersect}{finds ids of intersecting segments}{n\*\log(n)} + \end{methods} + \sourcecode{geometry/segmentIntersection.cpp} +\end{algorithm} + \begin{algorithm}[optional]{Delaunay Triangulierung} \begin{methods} \method{delaunay}{berechnet Triangulierung}{n\*\log(n)} \end{methods} - \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Traingulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. + \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Triangulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. \sourcecode{geometry/delaunay.cpp} \end{algorithm} \optional{ -\subsection{Geraden} +\subsection{Geraden \opthint} \sourcecode{geometry/lines.cpp} } diff --git a/graph/graph.tex b/graph/graph.tex index 4394192..bcfe689 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -51,7 +51,15 @@ Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. \sourcecode{graph/hld.cpp} \end{algorithm} -\clearpage +\columnbreak + +\begin{algorithm}[optional]{DP rerooting} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}[optional]{Virtual trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} \begin{algorithm}{Baum-Isomorphie} \begin{methods} @@ -139,6 +147,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/scc.cpp} \end{algorithm} +\columnbreak + \begin{algorithm}{2-SAT} \sourcecode{graph/2sat.cpp} \end{algorithm} @@ -150,7 +160,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\clearpage +\columnbreak \begin{algorithm}{Cycle Counting} \begin{methods} @@ -208,7 +218,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \subsection{Max-Flow} \optional{ -\subsubsection{Capacity Scaling} +\subsubsection{Capacity Scaling \opthint} \begin{methods} \method{maxFlow}{gut bei dünn besetzten Graphen.}{\abs{E}^2\*\log(C)} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} @@ -231,7 +241,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/dinicScaling.cpp} \optional{ -\subsubsection{Anwendungen} +\subsubsection{Anwendungen \opthint} \begin{itemize} \item \textbf{Maximum Edge Disjoint Paths}\newline Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. diff --git a/java/java.tex b/java/java.tex index bc656ff..9429106 100644 --- a/java/java.tex +++ b/java/java.tex @@ -3,7 +3,7 @@ \lstset{language=Java} \optional{ -\subsection{Introduction} +\subsection{Introduction \opthint} \begin{itemize} \item Compilen: \code{javac main.java} @@ -31,7 +31,7 @@ } \optional{ -\subsection{BigInteger} +\subsection{BigInteger \opthint} \sourcecode{java/bigInteger.java} } \endgroup diff --git a/latexHeaders/commands.sty b/latexHeaders/commands.sty index da78745..c39923c 100644 --- a/latexHeaders/commands.sty +++ b/latexHeaders/commands.sty @@ -7,6 +7,11 @@ \newcommand{\code}[1]{\lstinline[breaklines=true]{#1}} \let\codeSafe\lstinline +\ifoptional + \renewcommand{\columnbreak}{} + \newcommand\opthint{\textcolor{gray}{(optional)}} +\fi + \usepackage{tikz} \usetikzlibrary{angles,quotes} @@ -17,7 +22,7 @@ \ifthenelse{\equal{#1}{optional}}{% \optional{ \needspace{4\baselineskip}% - \subsection{#2\textcolor{gray}{(optional)}}% + \subsection{#2 \opthint}% #3% } }{% diff --git a/math/math.tex b/math/math.tex index a9e4c74..bae7bff 100644 --- a/math/math.tex +++ b/math/math.tex @@ -26,7 +26,7 @@ \end{methods}
\sourcecode{math/permIndex.cpp}
\end{algorithm}
-\clearpage
+\columnbreak
\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
%\vspace{-1.25em}
@@ -42,6 +42,11 @@ \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
\end{itemize}
+\begin{algorithm}[optional]{Square root modulo prime}
+ \sourcecode{math/modSqrt.cpp}
+ \sourcecode{math/sqrtModCipolla.cpp}
+\end{algorithm}
+
\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
\runtime{\log(a) + \log(b)}
\sourcecode{math/gcd-lcm.cpp}
@@ -272,7 +277,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{gauss}{löst LGS}{n^3}
\sourcecode{math/lgsFp.cpp}
-\clearpage
+\columnbreak
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\begin{methods}
@@ -11,7 +11,9 @@ % Options \newif\ifoptional -%\optionaltrue +\ifdefined\OPTIONAL + \optionaltrue +\fi % Font encoding. \usepackage[T1]{fontenc} @@ -43,6 +45,7 @@ % Content. \begin{multicols*}{3} + \raggedcolumns \input{datastructures/datastructures} \input{graph/graph} \input{geometry/geometry} @@ -51,6 +54,7 @@ \clearpage \input{math/tables} \begin{multicols*}{3} + \raggedcolumns \input{string/string} \input{java/java} \input{other/other} |