1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
\section{Sonstiges}
\subsection{Zeileneingabe}
\lstinputlisting{other/split.cpp}
\subsection{Bit Operations}
\lstinputlisting{other/bitOps.cpp}
% \subsection{Fast IO}
% \lstinputlisting{other/fastIO.cpp}
\subsection{Sonstiges}
\begin{lstlisting}
// Alles-Header.
#include <bits/stdc++.h>
// Setzt das deutsche Tastaturlayout.
setxkbmap de
// Schnelle Ein-/Ausgabe mit cin/cout.
ios::sync_with_stdio(false);
// Set mit eigener Sortierfunktion. Typ muss nicht explizit angegeben werden.
set<point2, decltype(comp)> set1(comp);
// PI
#define PI (2*acos(0))
// 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
\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$.
\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$!}
\subsection{Gemischtes}
\begin{itemize}
\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]}.
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.
Max-Flow ist die Lösung.\newline
Im Residualgraphen:
\begin{itemize}[nosep]
\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.
\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 Kanten, die alle Knoten berühren) = Max Matching.
\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})
\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{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{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: 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{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})$.
(Anzahl der Blöcke als Konstante in Code schreiben.)
\end{itemize}
\subsection{Tipps \& Tricks}
\begin{itemize}
\item Run Tim Error:
\begin{itemize}
\item Stack Overflow? Evtl. rekurisve 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 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 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 Einabegröß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}
|
