From ad8456f7c5d44d3c647b3a368050a5d2f39ae3c3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
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/other.tex')

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

