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 ++--- content/other/sos.cpp | 6 ------ 2 files changed, 2 insertions(+), 9 deletions(-) delete mode 100644 content/other/sos.cpp (limited to 'content/other') 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} diff --git a/content/other/sos.cpp b/content/other/sos.cpp deleted file mode 100644 index 892a47c..0000000 --- a/content/other/sos.cpp +++ /dev/null @@ -1,6 +0,0 @@ -vector res(in); -for (int i = 1; i < ssize(res); i *= 2) { - for (int mask = 0; mask < ssize(res); mask++){ - if (mask & i) { - res[mask] += res[mask ^ i]; -}}} -- cgit v1.2.3