From 1a0fba268ca9ef390a45c86a94a27edf026a4f67 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Thu, 20 Nov 2025 17:58:00 +0100
Subject: normalize newlines

---
 content/other/other.tex | 652 ++++++++++++++++++++++++------------------------
 1 file changed, 326 insertions(+), 326 deletions(-)

(limited to 'content/other/other.tex')

diff --git a/content/other/other.tex b/content/other/other.tex
index d8726d4..a43aa35 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -1,326 +1,326 @@
-\section{Sonstiges}
-
-\begin{algorithm}{Compiletime}
-	\begin{itemize}
-		\item überprüfen ob Compilezeit Berechnungen erlaubt sind!
-		\item braucht \code{c++14} oder höher!
-	\end{itemize}
-	\sourcecode{other/compiletime.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Timed}
-	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.
-	\sourcecode{other/timed.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Overflow-sichere arithmetische Operationen}
-	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
-	\begin{expandtable}
-		\begin{tabularx}{\linewidth}{|lR|}
-			\hline
-			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
-			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
-			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
-			\hline
-		\end{tabularx}
-	\end{expandtable}
-\end{algorithm}
-
-\begin{algorithm}{Bit Operations}
-	\begin{expandtable}
-	\begin{tabularx}{\linewidth}{|Ll|}
-		\hline
-		Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\
-		Bit an Position j setzen & \code{x |= (1 << j)} \\
-		Bit an Position j löschen & \code{x \&= ~(1 << j)} \\
-		Bit an Position j flippen & \code{x ^= (1 << j)} \\
-		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\
-		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\
-		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\
-		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\
-		\hline
-	\end{tabularx}\\
-	\end{expandtable}
-	\sourcecode{other/bitOps.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Pragmas}
-	\sourcecode{other/pragmas.cpp}
-\end{algorithm}
-
-\begin{algorithm}{DP Optimizations}
-	Aufgabe: Partitioniere Array in genau $m$ zusammenhängende Teile mit minimalen Kosten:
-	$dp[i][j] = \min_{k<j}\{dp[i-1][k-1]+C[k][j]\}$. Es sei $A[i][j]$ das \emph{minimale} optimale
-	$k$ bei der Berechnung von $dp[i][j]$.
-	
-	\paragraph{\textsc{Knuth}-Optimization} Vorbedingung: $A[i - 1][j] \leq A[i][j] \leq A[i][j + 1]$
-	
-	\method{calc}{berechnet das DP}{n^2}
-	\sourcecode{other/knuth.cpp}
-	
-	\paragraph{Divide and Conquer}
-	Vorbedingung: $A[i][j - 1] \leq A[i][j]$.
-	
-	\method{calc}{berechnet das DP}{m\*n\*\log(n)}
-	\sourcecode{other/divideAndConquer.cpp}
-	
-	\paragraph{Quadrangle inequality} Die Bedingung  $\forall a\leq b\leq c\leq d:
-	C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.
-	
-	\paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}.
-\end{algorithm}
-
-\begin{algorithm}{Fast Subset Sum}
-	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
-	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
-	\sourcecode{other/fastSubsetSum.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Parallel Binary Search}
-	\sourcecode{other/pbs.cpp}
-\end{algorithm}
-
-\columnbreak
-\begin{algorithm}{Josephus-Problem}
-	$n$ Personen im Kreis, jeder $k$-te wird erschossen.
-	\begin{description}
-		\item[Spezialfall $\boldsymbol{k=2}$:] Betrachte $n$ Binär.
-		Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n0$ die Position des letzten Überlebenden.
-	\end{description}
-	\sourcecode{other/josephus2.cpp}
-	
-	\begin{description}
-		\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden.
-		Nummeriere die Personen mit $0, 1, \ldots, n-1$.
-		Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$.
-		Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$.
-	\end{description}
-	\sourcecode{other/josephusK.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Zeileneingabe}
-	\sourcecode{other/split.cpp}
-\end{algorithm}
-
-\begin{algorithm}[optional]{Fast IO}
-	\sourcecode{other/fastIO.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Sonstiges}
-	\sourcecode{other/stuff.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Stress Test}
-	\sourcecode{other/stress.sh}
-\end{algorithm}
-
-\clearpage
-\subsection{Gemischtes}
-\begin{itemize}
-	\item \textbf{(Minimum) Flow mit Demand \textit{d}:}
-	Erstelle neue Quelle $s'$ und Senke $t'$ und setzte die folgenden Kapazitäten:
-	\begin{align*}
-		c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]
-		c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
-	\end{align*}
-	Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
-	\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
-	Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
-	Falls es einen negativen Zyklus gibt abrrechen.
-	Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}.
-	Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden.
-
-	\item \textbf{System von Differenzbeschränkungen:}
-	Ändere alle Bedingungen in die Form $a-b \leq c$.
-	Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gewicht \texttt{c} ein.
-	Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
-	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden.
-	\texttt{d[v]} ist mögliche Lösung für \texttt{v}.
-
-	\item \textbf{Min-Weight-Vertex-Cover im Bipartiten Graph:}
-	Partitioniere in \texttt{A, B} und füge Kanten \texttt{s}\,$\rightarrow$\,\texttt{A} mit Gewicht \texttt{w(A)} und Kanten  \texttt{B}\,$\rightarrow$\,\texttt{t} mit Gewicht \texttt{w(B)} hinzu.
-	Füge Kanten mit Kapazität $\infty$ von \texttt{A} nach \texttt{B} hinzu, wo im originalen Graphen Kanten waren.
-	Max-Flow ist die Lösung.\newline
-	Im Residualgraphen:
-	\begin{itemize}
-		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}
-		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind.
-	\end{itemize}
-
-	\item \textbf{Allgemeiner Graph:}
-	Das Komplement eines Vertex-Cover ist ein Independent Set.
-	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
-
-	\item \textbf{Bipartiter Graph (Satz von \textsc{König}):}
-	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.
-	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.
-
-	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}
-	Minimiere Matchinggewicht.
-	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normalen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})
-
-	\item \textbf{Satz von \textsc{Pick}:}
-	Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand.
-	Es gilt:\vspace*{-\baselineskip}
-	\[
-		A = I + \frac{R}{2} - 1
-	\]
-
-	\item \textbf{Lemma von \textsc{Burnside}:}
-	Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert.
-	Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$.
-	Dann gilt für die Anzahl der Bahnen $[X/G]$ der Operation:
-	\[
-		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} \vert X^g \vert
-	\]
-
-	\item \textbf{\textsc{Polya} Counting:}
-	Sei $\pi$ eine Permutation der Menge $X$.
-	Die Elemente von $X$ können mit einer von $m$ Farben gefärbt werden.
-	Die Anzahl der Färbungen, die Fixpunkte von $\pi$ sind, ist $m^{\#(\pi)}$, wobei $\#(\pi)$ die Anzahl der Zyklen von $\pi$ ist.
-	Die Anzahl der Färbungen von Objekten einer Menge $X$ mit $m$ Farben unter einer Symmetriegruppe $G$ is gegeben durch:
-	\[
-		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)}
-	\]
-
-	\item \textbf{\textsc{Bertrand}sches Postulat:}
-	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.
-
-	\item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}
-	Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.
-	Sei $A$ die Adjazenzmatrix von~$G$.
-	Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.
-	Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.
-	Definiere $R = B - A$.
-	Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.
-	Das Ergebnis ist die Anzahl der Spannbäume von $G$.
-	\newline
-	Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man
-	berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.
-	Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,
-	sodass jeder Knoten einen Pfad zu $k$ hat.
-
-	\item \textbf{\textsc{Dilworth}'s Theorem:}
-	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
-	Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.
-	Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.
-	Eine \emph{Antikette} ist eine Menge von Elementen, die paarweise nicht vergleichbar sind.
-	\newline
-	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.
-	$\Rightarrow$ \emph{Weite} des Poset.
-	\newline
-	Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.
-	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
-	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
-	Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.
-	\newline
-	Berechnung der maximalen Antikette: Verwende Satz von König, um ein
-	minimales Vertexcover des bipartiten Graphen zu finden.
-	Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.
-	Das Komplement davon ist eine maximale Antikette.
-	
-	\item \textbf{\textsc{Tur\'an}'s Theorem:}
-	Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:
-	\begin{align*}
-	ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right)  \cdot \binom{\ceil{\frac{n}{x}}}{2}\right]
-	\end{align*}
-	
-	\item \textbf{\textsc{Euler}scher Polyedersatz:}
-	In planaren Graphen gilt $n-m+f-c=1$.
-	
-	\item \textbf{\textsc{Pythagoreische Tripel}:}
-	Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig:
-	\[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\]
-	
-	\item \textbf{Centroids of a Tree:}
-	Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted.
-	Es kann $2$ Centroids geben!
-	
-	\item \textbf{Centroid Decomposition:}
-	Wähle zufälligen Knoten und mache DFS.
-	Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}.
-	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich.
-
-	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}
-	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von
-	$\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern.
-	
-	\item \textbf{\textsc{Mo}'s Algorithm:}
-	SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$.
-	Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$.
-	Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$.
-	Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls.
-	Laufzeit:~\runtime{n\cdot\sqrt{n}}.
-	(Anzahl der Blöcke als Konstante in Code schreiben.)
-	
-	\item \textbf{SQRT Techniques:}
-	\begin{itemize}
-		\item Aufteilen in \emph{leichte} (wert $\leq\sqrt{x}$) und \emph{schwere} (höchsten $\sqrt{x}$ viele) Objekte.
-		\item Datenstruktur in Blöcke fester Größe (z.b. 256 oder 512) aufteilen.
-		\item Datenstruktur nach fester Anzahl Updates komplett neu bauen.
-		\item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{2X}$ verschiedene Werte von $x_i$ (z.b. Längen von Strings).
-		\item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min(w,h)\leq\sqrt{X}$.
-	\end{itemize}
-
-	\item \textbf{Partition:}
-	Gegeben Gewichte $w_0+w_1+\cdots+w_k=W$, existiert eine Teilmenge mit Gewicht $x$?
-	Drei gleiche Gewichte $w$ können zu $w$ und $2w$ kombiniert werden ohne die Lösung zu ändern $\Rightarrow$ nur $2\sqrt{W}$ unterschiedliche Gewichte.
-	Mit bitsets daher selbst für $10^5$ lösbar.
-\end{itemize}
-
-\subsection{Tipps \& Tricks}
-
-\begin{itemize}
-	\item \textbf{Run Time Error:}
-	\begin{itemize}
-		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?
-		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?
-		\item Abbruchbedingung bei Rekursion?
-		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).
-	\end{itemize}
-	
-	\item \textbf{Strings:}
-	\begin{itemize}
-		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?
-		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
-	\end{itemize}
-
-	\item \textbf{Zeilenbasierte Eingabe}:
-	\begin{itemize}
-		\item \code{getline(cin, str)} liest Zeile ein.
-		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.
-	\end{itemize}
-	
-	\item \textbf{Gleitkommazahlen:}
-	\begin{itemize}
-		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?
-		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!
-		\item genügend Präzision oder Output in wissenschaftlicher Notation (\code{1e-25})?
-		\item Kann \code{-0.000} ausgegeben werden?
-	\end{itemize}
-
-	\item \textbf{Wrong Answer:}
-	\begin{itemize}
-		\item Lies Aufgabe erneut. Sorgfältig!
-		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.
-		\item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung.
-		\item Ausgabeformat im 'unmöglich'-Fall überprüfen.
-		\item Ist das Ergebnis modulo einem Wert?
-		\item Integer Division rundet zur $0$ $\neq$ abrunden.
-		\item Eingabegrößen überprüfen. Sonderfälle ausprobieren.
-		\begin{itemize}
-			\item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$
-			\item $n$ gerade/ungerade
-			\item Graph ist leer/enthält nur einen Knoten.
-			\item Liste ist leer/enthält nur ein Element.
-			\item Graph ist Multigraph (enthält Schleifen/Mehrfachkanten).
-			\item Sind Kanten gerichtet/ungerichtet?
-			\item Kolineare Punkte existieren.
-			\item Polygon ist konkav/selbstschneidend.
-		\end{itemize}
-		\item Bei DP/Rekursion: Stimmt Basisfall?
-		\item Unsicher bei benutzten STL-Funktionen?
-	\end{itemize}
-\end{itemize}
-
-%\input{other/simd}
+\section{Sonstiges}
+
+\begin{algorithm}{Compiletime}
+	\begin{itemize}
+		\item überprüfen ob Compilezeit Berechnungen erlaubt sind!
+		\item braucht \code{c++14} oder höher!
+	\end{itemize}
+	\sourcecode{other/compiletime.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Timed}
+	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+	\sourcecode{other/timed.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+	\begin{expandtable}
+		\begin{tabularx}{\linewidth}{|lR|}
+			\hline
+			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
+			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
+			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
+			\hline
+		\end{tabularx}
+	\end{expandtable}
+\end{algorithm}
+
+\begin{algorithm}{Bit Operations}
+	\begin{expandtable}
+	\begin{tabularx}{\linewidth}{|Ll|}
+		\hline
+		Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\
+		Bit an Position j setzen & \code{x |= (1 << j)} \\
+		Bit an Position j löschen & \code{x \&= ~(1 << j)} \\
+		Bit an Position j flippen & \code{x ^= (1 << j)} \\
+		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\
+		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\
+		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\
+		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\
+		\hline
+	\end{tabularx}\\
+	\end{expandtable}
+	\sourcecode{other/bitOps.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Pragmas}
+	\sourcecode{other/pragmas.cpp}
+\end{algorithm}
+
+\begin{algorithm}{DP Optimizations}
+	Aufgabe: Partitioniere Array in genau $m$ zusammenhängende Teile mit minimalen Kosten:
+	$dp[i][j] = \min_{k<j}\{dp[i-1][k-1]+C[k][j]\}$. Es sei $A[i][j]$ das \emph{minimale} optimale
+	$k$ bei der Berechnung von $dp[i][j]$.
+	
+	\paragraph{\textsc{Knuth}-Optimization} Vorbedingung: $A[i - 1][j] \leq A[i][j] \leq A[i][j + 1]$
+	
+	\method{calc}{berechnet das DP}{n^2}
+	\sourcecode{other/knuth.cpp}
+	
+	\paragraph{Divide and Conquer}
+	Vorbedingung: $A[i][j - 1] \leq A[i][j]$.
+	
+	\method{calc}{berechnet das DP}{m\*n\*\log(n)}
+	\sourcecode{other/divideAndConquer.cpp}
+	
+	\paragraph{Quadrangle inequality} Die Bedingung  $\forall a\leq b\leq c\leq d:
+	C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.
+	
+	\paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}.
+\end{algorithm}
+
+\begin{algorithm}{Fast Subset Sum}
+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+	\sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Parallel Binary Search}
+	\sourcecode{other/pbs.cpp}
+\end{algorithm}
+
+\columnbreak
+\begin{algorithm}{Josephus-Problem}
+	$n$ Personen im Kreis, jeder $k$-te wird erschossen.
+	\begin{description}
+		\item[Spezialfall $\boldsymbol{k=2}$:] Betrachte $n$ Binär.
+		Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n0$ die Position des letzten Überlebenden.
+	\end{description}
+	\sourcecode{other/josephus2.cpp}
+	
+	\begin{description}
+		\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden.
+		Nummeriere die Personen mit $0, 1, \ldots, n-1$.
+		Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$.
+		Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$.
+	\end{description}
+	\sourcecode{other/josephusK.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Zeileneingabe}
+	\sourcecode{other/split.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Fast IO}
+	\sourcecode{other/fastIO.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Sonstiges}
+	\sourcecode{other/stuff.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Stress Test}
+	\sourcecode{other/stress.sh}
+\end{algorithm}
+
+\clearpage
+\subsection{Gemischtes}
+\begin{itemize}
+	\item \textbf{(Minimum) Flow mit Demand \textit{d}:}
+	Erstelle neue Quelle $s'$ und Senke $t'$ und setzte die folgenden Kapazitäten:
+	\begin{align*}
+		c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]
+		c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
+	\end{align*}
+	Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
+	\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
+	Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
+	Falls es einen negativen Zyklus gibt abrrechen.
+	Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}.
+	Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden.
+
+	\item \textbf{System von Differenzbeschränkungen:}
+	Ändere alle Bedingungen in die Form $a-b \leq c$.
+	Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gewicht \texttt{c} ein.
+	Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
+	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden.
+	\texttt{d[v]} ist mögliche Lösung für \texttt{v}.
+
+	\item \textbf{Min-Weight-Vertex-Cover im Bipartiten Graph:}
+	Partitioniere in \texttt{A, B} und füge Kanten \texttt{s}\,$\rightarrow$\,\texttt{A} mit Gewicht \texttt{w(A)} und Kanten  \texttt{B}\,$\rightarrow$\,\texttt{t} mit Gewicht \texttt{w(B)} hinzu.
+	Füge Kanten mit Kapazität $\infty$ von \texttt{A} nach \texttt{B} hinzu, wo im originalen Graphen Kanten waren.
+	Max-Flow ist die Lösung.\newline
+	Im Residualgraphen:
+	\begin{itemize}
+		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}
+		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind.
+	\end{itemize}
+
+	\item \textbf{Allgemeiner Graph:}
+	Das Komplement eines Vertex-Cover ist ein Independent Set.
+	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
+
+	\item \textbf{Bipartiter Graph (Satz von \textsc{König}):}
+	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.
+	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.
+
+	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}
+	Minimiere Matchinggewicht.
+	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normalen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})
+
+	\item \textbf{Satz von \textsc{Pick}:}
+	Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand.
+	Es gilt:\vspace*{-\baselineskip}
+	\[
+		A = I + \frac{R}{2} - 1
+	\]
+
+	\item \textbf{Lemma von \textsc{Burnside}:}
+	Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert.
+	Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$.
+	Dann gilt für die Anzahl der Bahnen $[X/G]$ der Operation:
+	\[
+		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} \vert X^g \vert
+	\]
+
+	\item \textbf{\textsc{Polya} Counting:}
+	Sei $\pi$ eine Permutation der Menge $X$.
+	Die Elemente von $X$ können mit einer von $m$ Farben gefärbt werden.
+	Die Anzahl der Färbungen, die Fixpunkte von $\pi$ sind, ist $m^{\#(\pi)}$, wobei $\#(\pi)$ die Anzahl der Zyklen von $\pi$ ist.
+	Die Anzahl der Färbungen von Objekten einer Menge $X$ mit $m$ Farben unter einer Symmetriegruppe $G$ is gegeben durch:
+	\[
+		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)}
+	\]
+
+	\item \textbf{\textsc{Bertrand}sches Postulat:}
+	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.
+
+	\item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}
+	Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.
+	Sei $A$ die Adjazenzmatrix von~$G$.
+	Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.
+	Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.
+	Definiere $R = B - A$.
+	Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.
+	Das Ergebnis ist die Anzahl der Spannbäume von $G$.
+	\newline
+	Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man
+	berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.
+	Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,
+	sodass jeder Knoten einen Pfad zu $k$ hat.
+
+	\item \textbf{\textsc{Dilworth}'s Theorem:}
+	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
+	Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.
+	Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.
+	Eine \emph{Antikette} ist eine Menge von Elementen, die paarweise nicht vergleichbar sind.
+	\newline
+	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.
+	$\Rightarrow$ \emph{Weite} des Poset.
+	\newline
+	Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.
+	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
+	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
+	Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.
+	\newline
+	Berechnung der maximalen Antikette: Verwende Satz von König, um ein
+	minimales Vertexcover des bipartiten Graphen zu finden.
+	Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.
+	Das Komplement davon ist eine maximale Antikette.
+	
+	\item \textbf{\textsc{Tur\'an}'s Theorem:}
+	Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:
+	\begin{align*}
+	ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right)  \cdot \binom{\ceil{\frac{n}{x}}}{2}\right]
+	\end{align*}
+	
+	\item \textbf{\textsc{Euler}scher Polyedersatz:}
+	In planaren Graphen gilt $n-m+f-c=1$.
+	
+	\item \textbf{\textsc{Pythagoreische Tripel}:}
+	Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig:
+	\[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\]
+	
+	\item \textbf{Centroids of a Tree:}
+	Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted.
+	Es kann $2$ Centroids geben!
+	
+	\item \textbf{Centroid Decomposition:}
+	Wähle zufälligen Knoten und mache DFS.
+	Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}.
+	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich.
+
+	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}
+	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von
+	$\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern.
+	
+	\item \textbf{\textsc{Mo}'s Algorithm:}
+	SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$.
+	Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$.
+	Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$.
+	Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls.
+	Laufzeit:~\runtime{n\cdot\sqrt{n}}.
+	(Anzahl der Blöcke als Konstante in Code schreiben.)
+	
+	\item \textbf{SQRT Techniques:}
+	\begin{itemize}
+		\item Aufteilen in \emph{leichte} (wert $\leq\sqrt{x}$) und \emph{schwere} (höchsten $\sqrt{x}$ viele) Objekte.
+		\item Datenstruktur in Blöcke fester Größe (z.b. 256 oder 512) aufteilen.
+		\item Datenstruktur nach fester Anzahl Updates komplett neu bauen.
+		\item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{2X}$ verschiedene Werte von $x_i$ (z.b. Längen von Strings).
+		\item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min(w,h)\leq\sqrt{X}$.
+	\end{itemize}
+
+	\item \textbf{Partition:}
+	Gegeben Gewichte $w_0+w_1+\cdots+w_k=W$, existiert eine Teilmenge mit Gewicht $x$?
+	Drei gleiche Gewichte $w$ können zu $w$ und $2w$ kombiniert werden ohne die Lösung zu ändern $\Rightarrow$ nur $2\sqrt{W}$ unterschiedliche Gewichte.
+	Mit bitsets daher selbst für $10^5$ lösbar.
+\end{itemize}
+
+\subsection{Tipps \& Tricks}
+
+\begin{itemize}
+	\item \textbf{Run Time Error:}
+	\begin{itemize}
+		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?
+		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?
+		\item Abbruchbedingung bei Rekursion?
+		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).
+	\end{itemize}
+	
+	\item \textbf{Strings:}
+	\begin{itemize}
+		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?
+		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
+	\end{itemize}
+
+	\item \textbf{Zeilenbasierte Eingabe}:
+	\begin{itemize}
+		\item \code{getline(cin, str)} liest Zeile ein.
+		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.
+	\end{itemize}
+	
+	\item \textbf{Gleitkommazahlen:}
+	\begin{itemize}
+		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?
+		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!
+		\item genügend Präzision oder Output in wissenschaftlicher Notation (\code{1e-25})?
+		\item Kann \code{-0.000} ausgegeben werden?
+	\end{itemize}
+
+	\item \textbf{Wrong Answer:}
+	\begin{itemize}
+		\item Lies Aufgabe erneut. Sorgfältig!
+		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.
+		\item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung.
+		\item Ausgabeformat im 'unmöglich'-Fall überprüfen.
+		\item Ist das Ergebnis modulo einem Wert?
+		\item Integer Division rundet zur $0$ $\neq$ abrunden.
+		\item Eingabegrößen überprüfen. Sonderfälle ausprobieren.
+		\begin{itemize}
+			\item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$
+			\item $n$ gerade/ungerade
+			\item Graph ist leer/enthält nur einen Knoten.
+			\item Liste ist leer/enthält nur ein Element.
+			\item Graph ist Multigraph (enthält Schleifen/Mehrfachkanten).
+			\item Sind Kanten gerichtet/ungerichtet?
+			\item Kolineare Punkte existieren.
+			\item Polygon ist konkav/selbstschneidend.
+		\end{itemize}
+		\item Bei DP/Rekursion: Stimmt Basisfall?
+		\item Unsicher bei benutzten STL-Funktionen?
+	\end{itemize}
+\end{itemize}
+
+%\input{other/simd}
-- 
cgit v1.2.3