path: root/other/other.tex

\section{Sonstiges}

\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)} \\
		$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}{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}
	\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:}
	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 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}
		\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:
	\[
		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{\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{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 verhält sich periodisch alle $400$ Jahre.

	\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 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?
	\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. \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}

	\item 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 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 Polygon ist konkav/selbstschneidend.
		\end{itemize}
		\item Bei DP/Rekursion: Stimmt Basisfall?
		\item Unsicher bei benutzten STL-Funktionen?
	\end{itemize}
\end{itemize}