summaryrefslogtreecommitdiff
path: root/other/other.tex
diff options
context:
space:
mode:
authorMZuenni <michi.zuendorf@gmail.com>2023-02-14 16:53:47 +0100
committerMZuenni <michi.zuendorf@gmail.com>2023-02-14 16:53:47 +0100
commit9a6aeb3f3fa1c5442ef99118b3b93ae47b2c43c4 (patch)
tree1e2d44aed87ef2197f85503ac71ca3fd9776980b /other/other.tex
parenteb4bc75111da45a17604fdff2f9eed0977f93dff (diff)
moved even more
Diffstat (limited to 'other/other.tex')
-rw-r--r--other/other.tex56
1 files changed, 28 insertions, 28 deletions
diff --git a/other/other.tex b/other/other.tex
index 454cf5a..1097dc3 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -1,21 +1,5 @@
\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}{Sonstiges}
- \sourcecode{other/stuff.cpp}
-\end{algorithm}
-
\begin{algorithm}{Compiletime}
\begin{itemize}
\item überprüfen ob Compilezeit Berechnungen erlaubt sind!
@@ -24,11 +8,6 @@
\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|}
@@ -60,27 +39,32 @@
\end{expandtable}
\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}{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{\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}{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.
\paragraph{Sum over Subsets DP} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$
- \sourcecode{other/sos.cpp}
+ \sourcecode{other/sos.cpp}
\end{algorithm}
\begin{algorithm}{Parallel Binary Search}
@@ -95,7 +79,7 @@
(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$.
@@ -106,6 +90,22 @@
\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}{Pragmas}
+ \sourcecode{other/pragmas.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Sonstiges}
+ \sourcecode{other/stuff.cpp}
+\end{algorithm}
+
\clearpage
\subsection{Gemischtes}
\begin{itemize}