added another sqrt trick

2 files changed, 5 insertions, 0 deletions

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}
diff --git a/tcr.pdf b/tcr.pdf
index 218538b..7d58575 100644
--- a/tcr.pdf
+++ b/tcr.pdf