From 52ba871e0de9399f77da4b5b0d2c33a2dd6eb6a1 Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 18 Jan 2025 03:05:17 +0100 Subject: changes to bitwise convolutions - modify or/and transform to remove unnecessary reversal - or transform is now sum over subsets, add note about this - remove old sum over subsets DP --- content/other/other.tex | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'content/other/other.tex') diff --git a/content/other/other.tex b/content/other/other.tex index 2519427..8896962 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -67,9 +67,7 @@ \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} + \paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}. \end{algorithm} \begin{algorithm}{Fast Subset Sum} @@ -82,6 +80,7 @@ \sourcecode{other/pbs.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Josephus-Problem} $n$ Personen im Kreis, jeder $k$-te wird erschossen. \begin{description} -- cgit v1.2.3