13 files changed, 324 insertions, 198 deletions
diff --git a/other/bitOps.cpp b/other/bitOps.cpp
index ecb94fa..9666187 100644
--- a/other/bitOps.cpp
+++ b/other/bitOps.cpp
@@ -1,22 +1,18 @@
-// Bit an Position j auslesen.
-(a & (1 << j)) != 0
-// Bit an Position j setzen.
-a |= (1 << j)
-// Bit an Position j löschen.
-a &= ~(1 << j)
-// Bit an Position j umkehren.
-a ^= (1 << j)
-// Wert des niedrigsten gesetzten Bits.
-(a & -a)
-// Setzt alle Bits auf 1.
-a = -1
-// Setzt die ersten n Bits auf 1. Achtung: Overflows.
-a = (1 << n) - 1
-// Iteriert über alle Teilmengen einer Bitmaske (außer der leeren Menge).
-for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask)
-// Anzahl der gesetzten Bits.
-int __builtin_popcount(unsigned int x);
-int __builtin_popcountll(unsigned long long x);
-// Anzahl der führenden 0-Bits.
-int __builtin_clz(unsigned int x);
-int __builtin_clzll(unsigned long long x);
+// Iteriert über alle Teilmengen einer Bitmaske
+// (außer der leeren Menge).
+for (int subset = bitmask; subset > 0;
+		 subset = (subset - 1) & bitmask)
+
+// Zählt Anzahl der gesetzten Bits.
+int numberOfSetBits(int i) {
+	i = i - ((i >> 1) & 0x55555555);
+	i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
+	return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
+}
+
+// Nächste Permutation in Bitmaske
+// (z.B. 00111 => 01011 => 01101 => ...)
+ll nextPerm(ll v) {
+	ll t = v | (v - 1);
+	return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctzll(v) + 1));
+}
diff --git a/other/compiletime.cpp b/other/compiletime.cpp
new file mode 100644
index 0000000..7734806
--- /dev/null
+++ b/other/compiletime.cpp
@@ -0,0 +1,7 @@
+template<int N>
+struct Table {
+	int data[N];
+	constexpr Table() : data {} {
+		for (int i = 0; i < N; i++) data[i] = i;
+}};
+constexpr Table<100000> precalculated;
+\ No newline at end of file
diff --git a/other/divideAndConquer.cpp b/other/divideAndConquer.cpp
new file mode 100644
index 0000000..92ec0ef
--- /dev/null
+++ b/other/divideAndConquer.cpp
@@ -0,0 +1,27 @@
+vector<vector<ll>> dp;
+vector<vector<ll>> C;
+
+void rec(int i, int j0, int j1, int k0, int k1) {
+	if (j1 < j0) return;
+	int jmid = (j0 + j1) / 2;
+
+	dp[i][jmid] = inf;
+	int bestk = k0;
+	for (int k = k0; k < min(jmid, k1 + 1); ++k) {
+		if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) {
+			dp[i][jmid] = dp[i - 1][k] + C[k + 1][jmid];
+			bestk = k;
+	}}
+
+	rec(i, j0, jmid - 1, k0, bestk);
+	rec(i, jmid + 1, j1, bestk, k1);
+}
+
+ll calc(int n, int k) {
+	dp = vector<vector<ll>>(k, vector<ll>(n, inf));
+	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
+	for (int i = 1; i < k; i++) {
+		rec(i, 0, n - 1, 0, n - 1);
+	}
+	return dp[k - 1][n - 1];
+}
diff --git a/other/fastIO.cpp b/other/fastIO.cpp
index 0077ce2..63f9ede 100644
--- a/other/fastIO.cpp
+++ b/other/fastIO.cpp
@@ -1,24 +1,24 @@
-void fastscan(int* number) {
-  bool negative = false;
-  register int c;
-  *number = 0;
-  c = getchar();
-  while(c != '-' && (c < '0' || c > '9')) c = getchar();
-  if (c == '-') negative = true, c = getchar();
-  for (; c > 47 && c < 58; c = getchar()) *number = *number * 10 + c - 48;
-  if (negative) *number *= -1;
+void fastscan(int& number) {
+	bool negative = false;
+	register int c;
+	number = 0;
+	c = getchar();
+	while(c != '-' && (c < '0' || c > '9')) c = getchar();
+	if (c == '-') negative = true, c = getchar();
+	for (; c >= '0' && c <= '9'; c = getchar()) number = number * 10 + c - '0';
+	if (negative) number *= -1;
 }
 
 void printPositive(int n) {
-  if (n == 0) return;
-  print(n / 10);
-  putchar(n % 10 + '0');
+	if (n == 0) return;
+	printPositive(n / 10);
+	putchar(n % 10 + '0');
 }
 
 void fastprint(int n) {
-  if(n == 0) { putchar('0'); return; }
-  if (n < 0) {
-    putchar('-');
-    print(-n);
-  } else print(n);
+	if(n == 0) {putchar('0'); return;}
+	if (n < 0) {
+		putchar('-');
+		printPositive(-n);
+	} else printPositive(n);
 }
diff --git a/other/josephus2.cpp b/other/josephus2.cpp
index a973609..5086e13 100644
--- a/other/josephus2.cpp
+++ b/other/josephus2.cpp
@@ -1,8 +1,8 @@
 int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert.
-	for (int i = 31; i >= 0; i--)
+	for (int i = 31; i >= 0; i--) {
 		if (n & (1 << i)) {
 			n &= ~(1 << i);
 			break;
-		}
+	}}
 	n <<= 1; n++; return n;
 }
diff --git a/other/josephusK.cpp b/other/josephusK.cpp
index 522b584..8d4df4d 100644
--- a/other/josephusK.cpp
+++ b/other/josephusK.cpp
@@ -1,4 +1,5 @@
-int josephus(int n, int k) { // Der letzte Überlebende, 0-basiert.
+// Der letzte Überlebende, 0-basiert.
+int josephus(int n, int k) {
 	if (n == 1) return 0;
 	return (josephus(n - 1, k) + k) % n;
 }
 \ No newline at end of file
diff --git a/other/knuth.cpp b/other/knuth.cpp
new file mode 100644
index 0000000..f47dbe0
--- /dev/null
+++ b/other/knuth.cpp
@@ -0,0 +1,15 @@
+ll calc(int n, int k, const vector<vector<ll>> &C) {
+	vector<vector<ll>> dp(k, vector<ll>(n, inf));
+	vector<vector<int>> opt(k, vector<int>(n + 1, n - 1));
+
+	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
+	for (int i = 1; i < k; i++) {
+		for (int j = n - 1; j >= 0; --j) {
+			opt[i][j] = i == 1 ? 0 : opt[i - 1][j];
+			for (int k = opt[i][j]; k <= min(opt[i][j + 1], j - 1); ++k) {
+				if (dp[i][j] <= dp[i - 1][k] + C[k + 1][j]) continue;
+				dp[i][j] = dp[i - 1][k] + C[k + 1][j];
+				opt[i][j] = k;
+	}}}
+	return dp[k - 1][n - 1];
+}
diff --git a/other/other.tex b/other/other.tex
index d9ac362..3a70a36 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -1,73 +1,137 @@
 \section{Sonstiges}
 
-\subsection{Zeileneingabe}
-\lstinputlisting{other/split.cpp}
-
-\subsection{Bit Operations}
-\lstinputlisting{other/bitOps.cpp}
-
-% \subsection{Fast IO}
-% \lstinputlisting{other/fastIO.cpp}
-
-\subsection{Rekursiver Abstieg und Abstrakter Syntaxbaum}
-\lstinputlisting{other/parser.cpp}
-
-\subsection{Sonstiges}
-\begin{lstlisting}
-// Alles-Header.
-#include <bits/stdc++.h>
-// Schnelle Ein-/Ausgabe mit cin/cout.
-ios::sync_with_stdio(false);
-cin.tie(NULL);
-// Set mit eigener Sortierfunktion.
-set<point2, decltype(comp)> set1(comp);
-// PI
-#define PI (2*acos(0))
-// STL-Debugging, Compiler flags.
--D_GLIBCXX_DEBUG
-// 128-Bit Integer/Float. Zum Einlesen/Ausgeben in long long casten.
-__int128, __float128
-\end{lstlisting}
-
-\subsection{Josephus-Problem}
-$n$ Personen im Kreis, jeder $k$-te wird erschossen.
-\begin{description}
-	\item[Spezialfall $k=2$:] Betrachte Binärdarstellung von $n$.
-	Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n1$ die Position des letzten Überlebenden.
-	(Rotiere $n$ um eine Stelle nach links)
-	\lstinputlisting{other/josephus2.cpp}
-	\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$. 
+\begin{algorithm}[optional]{Zeileneingabe}
+	\sourcecode{other/split.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Fast IO}
+	\sourcecode{other/fastIO.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Pragmas}
+	\sourcecode{other/pragmas.cpp}
+\end{algorithm}
+
+\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 werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+	\sourcecode{other/timed.cpp}
+\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 setzten & \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 bits & \code{__builtin_popcountll(x)} \\
+		\hline
+	\end{tabularx}\\
+	\end{expandtable}
+	\sourcecode{other/bitOps.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}{Sonstiges}
+	\sourcecode{other/stuff.cpp}
+\end{algorithm}
+
+\begin{algorithm}{DP Optimizations}
+	Aufgabe: Partitioniere Array in genau $k$ zusammenhängende Teile mit minimalen Kosten:
+	$dp[i][j] = \min_{k<j}\{dp[i-1][k]+C[k][j]\}$. Es sei $A[i][j]$ das \emph{minimale} optimale
+	$k$ bei der Berechnung von $dp[i][j]$.
+	
+	\paragraph{Divide and Conquer}
+	Vorbedingung: $A[i][j - 1] \leq A[i][j]$.
+	
+	\method{calc}{berechnet das DP}{k\*n\*\log(n)}
+	\sourcecode{other/divideAndConquer.cpp}
+	
+	\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{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.
+\end{algorithm}
+
+\begin{algorithm}{Parallel Binary Search}
+	\sourcecode{other/pbs.cpp}
+\end{algorithm}
+
+\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_n1$ die Position des letzten Überlebenden.
+		(Rotiere $n$ um eine Stelle nach links)
+	\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}
 	\lstinputlisting{other/josephusK.cpp}
-\end{description}
-\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $1, \ldots, n$ nummeriert sind, im zweiten Fall von $0, \ldots, n-1$!}
+	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
+\end{algorithm}
 
 \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{Dinic'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{Johnsons} Reweighting Algorithmus:}
-	Füge neue Quelle \lstinline{S} hinzu, mit Kanten mit Gewicht 0 zu allen Knoten.
-	Nutze \textsc{Bellmann-Ford} zum Betsimmen der Entfernungen \lstinline{d[i]} von \lstinline{S} zu allen anderen Knoten.
-	Stoppe, wenn es negative Zyklen gibt.
-	Sonst ändere die gewichte von allen Kanten \lstinline{(u,v)} im ursprünglichen Graphen zu \lstinline{d[u]+w[u,v]-d[v]}.
+	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 \lstinline{(b,a)} mit Gweicht \lstinline{c} ein.
-	Füge Quelle \lstinline{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
-	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \lstinline{s} aus zu finden.
-	\lstinline{d[v]} ist mögliche Lösung für \lstinline{v}.
-
-	\item \textbf{Min-Weight-Vertex-Cover im bipartiten Graph:}
-	Partitioniere in \lstinline{A, B} und füge Kanten \lstinline{s -> A} mit Gewicht \lstinline{w(A)} und Kanten  \lstinline{B -> t} mit Gewicht \lstinline{w(B)} hinzu.
-	Füge Kanten mit Kapazität $\infty$ von \lstinline{A} nach \lstinline{B} hinzu, wo im originalen Graphen Kanten waren.
+	Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gweicht \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}[nosep]
+	\begin{itemize}
 		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}
-		\item Die Knoten in \lstinline{A}, die \emph{nicht} von \lstinline{s} erreichber sind und die Knoten in \lstinline{B}, die von \lstinline{erreichber} sind.
+		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{erreichbar} sind.
 	\end{itemize}
 
 	\item \textbf{Allgemeiner Graph:}
@@ -75,11 +139,12 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
 
 	\item \textbf{Bipartiter Graph:}
-	Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching.
+	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$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten Knoten aus $A$.
 
 	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}
 	Minimiere Matchinggewicht.
-	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normlen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})
+	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.
@@ -118,7 +183,7 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 	\newline
 	Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
 
-	\item \textbf{\textsc{Dilworth}'s-Theorem:}
+	\item \textbf{\textsc{Dilworths}-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.
@@ -130,62 +195,65 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 	Berechnung: 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 Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden.
-
+	Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. 
+	
+	\item \textbf{\textsc{Turan}'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}'s-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{\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:~$\mathcal{O}(n\cdot\sqrt{n})$.
+	Laufzeit:~\runtime{n\cdot\sqrt{n}}.
 	(Anzahl der Blöcke als Konstante in Code schreiben.)
-
+	
 	\item \textbf{Centroids of a Tree:}
-	Ein \emph{Centroid} ist ein Konten, der einen Baum in Komponenten der maximalen Größe $\frac{\vert V \vert}{2}$ splitted.
+	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!
-	\textbf{Centroid Decomposition:}
+	
+	\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:~$\mathcal{O}(\vert V \vert \log(\vert V \vert))$.
+	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 verhält sich periodisch alle $400$ Jahre.
 
-	\item \textbf{Kreuzprodukt}
-	\[
-		a \times b =
-		\begin{pmatrix}
-			a_1 \\
-			a_2 \\
-			a_3
-		\end{pmatrix}
-		\times
-		\begin{pmatrix}
-			b_1 \\
-			b_2 \\
-			b_3
-		\end{pmatrix}
-		=
-		\begin{pmatrix}
-				a_2b_3 - a_3b_2 \\
-				a_3b_1 - a_1b_3 \\
-				a_1b_2 - a_2b_1
-		\end{pmatrix}
-	\]
+	\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.
 \end{itemize}
 
 \subsection{Tipps \& Tricks}
 
 \begin{itemize}
-	\item Run Tim Error:
+	\item 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?
-		\item $n$ und $m$ verwechselt?
 	\end{itemize}
-
+	
+	\item Strings:
+	\begin{itemize}
+		\item Soll \lstinline{"aa"} kleiner als \lstinline{"z"} sein oder nicht?
+		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
+	\end{itemize}
+	
 	\item Gleitkommazahlen:
 	\begin{itemize}
-		\item \lstinline{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \lstinline{acos(1.00000000000001)}?
-		\item Flasches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!
-		\item Output in wissenschaftlicher Notation (\lstinline{1e-25})?
+		\item \lstinline{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\lstinline{acos(1.00000000000001)}}?
+		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!
+		\item genügend Präzision oder Output in wissenschaftlicher Notation (\lstinline{1e-25})?
 		\item Kann \lstinline{-0.000} ausgegeben werden?
 	\end{itemize}
 
@@ -194,11 +262,13 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 		\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 Einabegrößen überprüfen. Sonderfälle ausprobieren.
+		\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} = 2147483648$
+			\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 Polygon ist konkav/selbstschneidend.
diff --git a/other/parser.cpp b/other/parser.cpp
deleted file mode 100644
index 94b7829..0000000
--- a/other/parser.cpp
+++ /dev/null
@@ -1,61 +0,0 @@
-struct Token { // In globalem Vektor, Zugriff über globale Variable.
-  int type; // Definiere Konstanten.
-  double value;
-  Token(int type) : type(type) {}
-  Token(int type, int value) : type(type), value(value) {}
-};
-
-struct Expression { // Die folgenden Klassen nur für den AST.
-  virtual ~Expression() {};
-  virtual double getValue() = 0;
-};
-
-struct Atom : public Expression {
-  double value;
-  Atom(int value) : value(value) {};
-  double getValue() { return value; }
-};
-
-struct BinaryExpression : public Expression {
-  Expression *lhs, *rhs;
-  BinaryExpression(Expression *lhs, Expression *rhs) : lhs(lhs), rhs(rhs) {}
-  ~BinaryExpression() { delete lhs; delete rhs; }
-};
-
-struct Addition : public BinaryExpression {
-  Addition(Expression *lhs, Expression *rhs) : BinaryExpression(lhs, rhs) {}
-  double getValue() { return lhs->getValue() + rhs->getValue(); }
-};
-
-Expression* parseF() {
-  Expression *lhs;
-  switch(tokens[token].type) {
-    case NUMBER: return new Atom(tokens[token++].value);
-    case LEFT_PAR:
-      token++;
-      lhs = parseA();
-      token++;
-      return lhs;
-    default:
-      return NULL;
-}}
-
-Expression* parseA_(Expression *lhs) {
-  Expression *plus, *minus;
-  if (token >= (int)tokens.size()) return lhs;
-  switch(tokens[token].type) {
-    case ADDITION:
-      token++;
-      plus = new Addition(lhs, parseS());
-      return parseA_(plus);
-    case SUBTRACTION:
-      token++;
-      minus = new Subtraction(lhs, parseS());
-      return parseA_(minus);
-    default:
-      return lhs;
-}}
-
-Expression* parseA() {
-  Expression *lhs = parseS(); return parseA_(lhs);
-}
diff --git a/other/pbs.cpp b/other/pbs.cpp
new file mode 100644
index 0000000..45577e2
--- /dev/null
+++ b/other/pbs.cpp
@@ -0,0 +1,32 @@
+// Q = Anzahl der Anfragen
+// C = Anzahl der Schritte der Operation
+
+vector<vector<int>> focus;
+vector<int> low, high, ans;
+
+ans.assign(Q, C + 1);
+low.assign(Q, 0);
+high.assign(Q, C);
+focus.assign(C + 1, vector<int>());
+for (bool changed = true; changed;) {
+	changed = false;
+	for (int i = 0; i <= C; i++) focus[i].clear();
+	for (int i = 0; i < Q; i++) {
+		if (low[i] > high[i]) continue;
+		focus[(low[i] + high[i]) / 2].pb(i);
+	}
+
+	// Simulation zurücksetzen
+
+	for (int k = 0; k <= C; k++) {
+		// Simulationsschritt
+
+		for (int q : focus[k]) {
+			changed = true;
+			if (/* Eigenschaft schon erfüllt */) {
+				// Antwort updaten
+				high[q] = k - 1;
+				ans[q] = min(ans[q], k);
+			} else {
+				low[q] = k + 1;
+}}}}
diff --git a/other/pragmas.cpp b/other/pragmas.cpp
new file mode 100644
index 0000000..f8cf060
--- /dev/null
+++ b/other/pragmas.cpp
@@ -0,0 +1,6 @@
+#pragma GCC optimize("Ofast")
+#pragma GCC optimize ("unroll-loops")
+#pragma GCC target("sse,sse2,sse3,ssse3,sse4,"
+									 "popcnt,abm,mmx,avx,tune=native")
+#pragma GCC target("fpmath=sse,sse2")	// no excess precision
+#pragma GCC target("fpmath=387") 			// force excess precision
+\ No newline at end of file
diff --git a/other/stuff.cpp b/other/stuff.cpp
new file mode 100644
index 0000000..81286d8
--- /dev/null
+++ b/other/stuff.cpp
@@ -0,0 +1,30 @@
+// Alles-Header.
+#include <bits/stdc++.h>
+
+// Setzt das deutsche Tastaturlayout.
+setxkbmap de
+
+// Schnelle Ein-/Ausgabe mit cin/cout.
+ios::sync_with_stdio(false);
+cin.tie(nullptr);
+
+// Set mit eigener Sortierfunktion.
+// Typ muss nicht explizit angegeben werden.
+set<point2, decltype(comp)> set1(comp);
+
+// STL-Debugging, Compiler flags.
+-D_GLIBCXX_DEBUG
+#define _GLIBCXX_DEBUG
+
+// 128-Bit Integer/Float. Muss zum Einlesen/Ausgeben 
+// in einen int oder long long gecastet werden.
+__int128, __float128
+
+// float mit Decimaldarstellung
+#include <decimal/decimal>
+std::decimal::decimal128
+
+// 1e18 < INF < Max_Value / 2
+constexpr long long INF = 0x3FFF_FFFF_FFFF_FFFFll;
+// 1e9 < INF < Max_Value / 2
+constexpr int INF = 0x3FFF_FFFF;
diff --git a/other/timed.cpp b/other/timed.cpp
new file mode 100644
index 0000000..20eec70
--- /dev/null
+++ b/other/timed.cpp
@@ -0,0 +1,3 @@
+int times = clock();
+//run for 900ms
+while (clock()-times < 900) {...}