diff options
| author | MZuenni <michi.zuendorf@gmail.com> | 2023-02-14 16:53:47 +0100 |
|---|---|---|
| committer | MZuenni <michi.zuendorf@gmail.com> | 2023-02-14 16:53:47 +0100 |
| commit | 9a6aeb3f3fa1c5442ef99118b3b93ae47b2c43c4 (patch) | |
| tree | 1e2d44aed87ef2197f85503ac71ca3fd9776980b /other/other.tex | |
| parent | eb4bc75111da45a17604fdff2f9eed0977f93dff (diff) | |
moved even more
Diffstat (limited to 'other/other.tex')
| -rw-r--r-- | other/other.tex | 56 |
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} |
