mzuenni tests

15 files changed, 496 insertions, 0 deletions

diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp
new file mode 100644
index 0000000..8079305
--- /dev/null
+++ b/content/other/bitOps.cpp
@@ -0,0 +1,18 @@
+// 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) & 0x5555'5555);
+	i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333);
+	return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 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/content/other/compiletime.cpp b/content/other/compiletime.cpp
new file mode 100644
index 0000000..b71f83b
--- /dev/null
+++ b/content/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<100'000> precalculated;
diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp
new file mode 100644
index 0000000..830dc7f
--- /dev/null
+++ b/content/other/divideAndConquer.cpp
@@ -0,0 +1,27 @@
+vector<vector<ll>> dp;
+vector<vector<ll>> C;
+
+void rec(int i, int j0, int j1, int m0, int m1) {
+	if (j1 < j0) return;
+	int jmid = (j0 + j1) / 2;
+
+	dp[i][jmid] = inf;
+	int bestk = m0;
+	for (int k = m0; k < min(jmid, m1 + 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, m0, bestk);
+	rec(i, jmid + 1, j1, bestk, m1);
+}
+
+ll calc(int n, int m) {
+	dp = vector<vector<ll>>(m, vector<ll>(n, inf));
+	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
+	for (int i = 1; i < m; i++) {
+		rec(i, 0, n - 1, 0, n - 1);
+	}
+	return dp[m - 1][n - 1];
+}
diff --git a/content/other/fastIO.cpp b/content/other/fastIO.cpp
new file mode 100644
index 0000000..9badcc7
--- /dev/null
+++ b/content/other/fastIO.cpp
@@ -0,0 +1,24 @@
+void fastscan(int& number) {
+	bool negative = false;
+	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;
+	printPositive(n / 10);
+	putchar(n % 10 + '0');
+}
+
+void fastprint(int n) {
+	if(n == 0) {putchar('0'); return;}
+	if (n < 0) {
+		putchar('-');
+		printPositive(-n);
+	} else printPositive(n);
+}
diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp
new file mode 100644
index 0000000..5086e13
--- /dev/null
+++ b/content/other/josephus2.cpp
@@ -0,0 +1,8 @@
+int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert.
+	for (int i = 31; i >= 0; i--) {
+		if (n & (1 << i)) {
+			n &= ~(1 << i);
+			break;
+	}}
+	n <<= 1; n++; return n;
+}
diff --git a/content/other/josephusK.cpp b/content/other/josephusK.cpp
new file mode 100644
index 0000000..5025f89
--- /dev/null
+++ b/content/other/josephusK.cpp
@@ -0,0 +1,5 @@
+// Der letzte Überlebende, 0-basiert.
+int josephus(int n, int k) {
+	if (n == 1) return 0;
+	return (josephus(n - 1, k) + k) % n;
+}
diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp
new file mode 100644
index 0000000..1d513c8
--- /dev/null
+++ b/content/other/knuth.cpp
@@ -0,0 +1,15 @@
+ll calc(int n, int m, const vector<vector<ll>>& C) {
+	vector<vector<ll>> dp(m, vector<ll>(n, inf));
+	vector<vector<int>> opt(m, vector<int>(n + 1, n - 1));
+
+	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
+	for (int i = 1; i < m; 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[m - 1][n - 1];
+}
diff --git a/content/other/other.tex b/content/other/other.tex
new file mode 100644
index 0000000..7a3c52b
--- /dev/null
+++ b/content/other/other.tex
@@ -0,0 +1,312 @@
+\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}{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 \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}{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}{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} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$.

+	Für Summe über Supersets \code{res} einmal vorher und einmal nachher reversen.

+	\sourcecode{other/sos.cpp}

+\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}

+	\sourcecode{other/josephusK.cpp}

+	\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}

+

+\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{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:}

+	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{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:}

+	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 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{Verteilung von Primzahlen:}

+	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$.

+

+	\item \textbf{Satz von \textsc{Kirchhoff}:}

+	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, $b_{ii}$ sei der Grad von Knoten $i$.

+	Definiere $R = B - A$.

+	Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.

+	\newline

+	Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.

+

+	\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.

+	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: 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.

+	

+	\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{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}

diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp
new file mode 100644
index 0000000..7cb60e5
--- /dev/null
+++ b/content/other/pbs.cpp
@@ -0,0 +1,19 @@
+// Q = # of queries, bucket sort is sometimes faster
+vector<int> low(Q, 0), high(Q, MAX_OPERATIONS);
+while (true) {
+	vector<pair<int, int>> focus;
+	for (int i = 0; i < Q; i++) if (low[i] < high[i]) {
+		focus.emplace_back((low[i] + high[i]) / 2, i);
+	}
+	if (focus.empty()) break;
+	sort(all(focus));
+
+	// reset simulation
+	for (int step = 0; auto [mid, i] : focus) {
+		while (step <= mid) {
+			// simulation step
+			step++;
+		}
+		if (/* requirement already fulfilled */) high[i] = mid;
+		else low[i] = mid + 1;
+}} // answer in low (and high)
diff --git a/content/other/pragmas.cpp b/content/other/pragmas.cpp
new file mode 100644
index 0000000..a39c850
--- /dev/null
+++ b/content/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
diff --git a/content/other/sos.cpp b/content/other/sos.cpp
new file mode 100644
index 0000000..01bc44c
--- /dev/null
+++ b/content/other/sos.cpp
@@ -0,0 +1,6 @@
+vector<ll> res(in);
+for (int i = 1; i < sz(res); i *= 2) {
+	for (int mask = 0; mask < sz(res); mask++){
+		if (mask & i) {
+			res[mask] += res[mask ^ i];
+}}}
diff --git a/content/other/split.cpp b/content/other/split.cpp
new file mode 100644
index 0000000..5519f60
--- /dev/null
+++ b/content/other/split.cpp
@@ -0,0 +1,10 @@
+// Zerlegt s anhand aller Zeichen in delim (verändert s).
+vector<string> split(string& s, string delim) {
+	vector<string> result; char *token;
+	token = strtok(s.data(), delim.c_str());
+	while (token != nullptr) {
+		result.emplace_back(token);
+		token = strtok(nullptr, delim.c_str());
+	}
+	return result;
+}
diff --git a/content/other/stress.sh b/content/other/stress.sh
new file mode 100644
index 0000000..d264c2a
--- /dev/null
+++ b/content/other/stress.sh
@@ -0,0 +1,7 @@
+for i in {1..1000}; do
+	printf "\r$i"
+	python3 gen.py > input      # generate test with gen.py
+	./a.out < input > out       # execute ./a.out
+	./b.out < input > out2      # execute ./b.out
+	diff out out2 || break
+done
diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp
new file mode 100644
index 0000000..41543ad
--- /dev/null
+++ b/content/other/stuff.cpp
@@ -0,0 +1,29 @@
+// Alles-Header.
+#include <bits/stdc++.h>
+
+// Setzt deutsche Tastaturlayout / toggle mit alt + space
+setxkbmap de
+setxkbmap de,us -option grp:alt_space_toggle
+
+// Schnelle Ein-/Ausgabe mit cin/cout.
+cin.tie(nullptr)->ios::sync_with_stdio(false);
+
+// Set mit eigener Sortierfunktion.
+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 ll INF = 0x3FFF'FFFF'FFFF'FFFFll;
+// 1e9 < INF < Max_Value / 2
+constexpr int INF = 0x3FFF'FFFF;
diff --git a/content/other/timed.cpp b/content/other/timed.cpp
new file mode 100644
index 0000000..b3ed4ef
--- /dev/null
+++ b/content/other/timed.cpp
@@ -0,0 +1,3 @@
+int times = clock();
+//run for 900ms
+while (1000*(clock()-times)/CLOCKS_PER_SEC < 900) {...}