From ad8456f7c5d44d3c647b3a368050a5d2f39ae3c3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 28 Feb 2023 23:31:11 +0100 Subject: added another sqrt trick --- other/other.tex | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'other') diff --git a/other/other.tex b/other/other.tex index c4ee383..b0e480b 100644 --- a/other/other.tex +++ b/other/other.tex @@ -244,6 +244,11 @@ \item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{2X}$ verschiedene Werte von $x_i$ (z.b. Längen von Strings). \item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min(w,h)\leq\sqrt{X}$. \end{itemize} + + \item \textbf{Partition:} + Gegeben Gewichte $w_0+w_1+\cdots+w_k=W$, existiert eine Teilmenge mit Gewicht $x$? + Drei gleiche Gewichte $w$ können zu $w$ und $2w$ kombiniert werden ohne die Lösung zu ändern $\Rightarrow$ nur $2\sqrt{W}$ unterschiedliche Gewichte. + Mit bitsets daher selbst für $10^5$ lösbar. \end{itemize} \subsection{Tipps \& Tricks} -- cgit v1.2.3