From ac2d9ad3f2c88bc12420fc439e8d0b4775a11169 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 30 Aug 2024 15:04:20 +0200
Subject: various small improvements

---
 content/other/other.tex | 34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)

(limited to 'content/other/other.tex')

diff --git a/content/other/other.tex b/content/other/other.tex
index b47893f..e8d8041 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -13,6 +13,19 @@
 	\sourcecode{other/timed.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+	\begin{expandtable}
+		\begin{tabularx}{\linewidth}{|lR|}
+			\hline
+			Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
+			Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
+			Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
+			\hline
+		\end{tabularx}
+	\end{expandtable}
+\end{algorithm}
+
 \begin{algorithm}{Bit Operations}
 	\begin{expandtable}
 	\begin{tabularx}{\linewidth}{|Ll|}
@@ -31,19 +44,6 @@
 	\sourcecode{other/bitOps.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Overflow-sichere arithmetische Operationen}
-	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
-	\begin{expandtable}
-		\begin{tabularx}{\linewidth}{|lR|}
-			\hline
-			Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
-			Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
-			Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
-			\hline
-		\end{tabularx}
-	\end{expandtable}
-\end{algorithm}
-
 \begin{algorithm}{Pragmas}
 	\sourcecode{other/pragmas.cpp}
 \end{algorithm}
@@ -95,6 +95,14 @@
 	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
 \end{algorithm}
 
+\vfill\null\columnbreak
+
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{other/recover.cpp}
+
+
 \begin{algorithm}[optional]{Zeileneingabe}
 	\sourcecode{other/split.cpp}
 \end{algorithm}
-- 
cgit v1.2.3


From facc5da35282ef30e5111cdc04942d118f4ae0c5 Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Tue, 10 Sep 2024 23:06:28 +0200
Subject: add fastSubsetSum

---
 content/other/fastSubsetSum.cpp |  21 +++++++++++++++++
 content/other/other.tex         |   4 ++++
 tcr.pdf                         | Bin 696332 -> 698834 bytes
 test/other/fastSubsetSum.cpp    |  49 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 74 insertions(+)
 create mode 100644 content/other/fastSubsetSum.cpp
 create mode 100644 test/other/fastSubsetSum.cpp

(limited to 'content/other/other.tex')

diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..84396f6
--- /dev/null
+++ b/content/other/fastSubsetSum.cpp
@@ -0,0 +1,21 @@
+int fastSubsetSum(vector<int> w, int t){
+	int a = 0, b = 0;
+	while(b < sz(w) && a + w[b] <= t) a += w[b++];
+	if(b == sz(w)) return a;
+	int m = *max_element(all(w));
+	vector<int> dp(2*m, -1), old;
+	dp[m+a-t] = b;
+	for(int i = b; i < sz(w); i++){
+		old = dp;
+		for(int j = 0; j < m; j++){
+			dp[j+w[i]] = max(dp[j+w[i]], old[j]);
+		}
+		for(int j = 2*m-1; j > m; j--){
+			for(int k = max(old[j], 0); k < dp[j]; k++){
+				dp[j-w[k]] = max(dp[j-w[k]], k);
+			}
+		}
+	}
+	for(a = t; dp[m+a-t] < 0; a--);
+	return a;
+}
\ No newline at end of file
diff --git a/content/other/other.tex b/content/other/other.tex
index e8d8041..368d0b3 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -102,6 +102,10 @@
 \textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
 \sourcecode{other/recover.cpp}
 
+\subsection{Fast Subset Sum}
+\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}
+Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+\sourcecode{other/fastSubsetSum.cpp}
 
 \begin{algorithm}[optional]{Zeileneingabe}
 	\sourcecode{other/split.cpp}
diff --git a/tcr.pdf b/tcr.pdf
index 1bf4c26..d383dd9 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..c61b1ea
--- /dev/null
+++ b/test/other/fastSubsetSum.cpp
@@ -0,0 +1,49 @@
+#include "../util.h"
+#include <other/fastSubsetSum.cpp>
+
+int subsetSum(vector<int> w, int t){
+	vector<bool> dp(t+1);
+	dp[0] = true;
+	for(int x : w){
+		for(int i = t; i >= x; i--){
+			dp[i] = dp[i] || dp[i-x];
+		}
+	}
+	int ma = 0;
+	for(int i = 0; i <= t; i++){
+		if(dp[i]) ma = i;
+	}
+	return ma;
+}
+
+void stress_test() {
+	int queries = 0;
+	for (int test = 0; test < 10'000; test++) {
+		int n = Random::integer<int>(1, 20);
+		int t = Random::integer<int>(1, 500);
+		vector<int> w = Random::integers<int>(n, 0, 50);
+		int got = fastSubsetSum(w, t);
+		int expected = subsetSum(w, t);
+		if(got != expected) cerr << "got: " << got << " expected: " << expected << FAIL;
+		queries++;
+	}
+	cerr << "tested queries: " << queries << endl;
+}
+
+void performance_test() {
+	timer t;
+	int n = 10'000, a = 10'000;
+	vector<int> w = Random::integers<int>(n, 0, a);
+	int target = 10'000'000;
+	t.start();
+	hash_t hash = fastSubsetSum(w, target);
+	t.stop();
+	if (t.time > 750) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
+
-- 
cgit v1.2.3


From 0257f0b3c61f203f64c3817dfe19a08f6191517c Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Wed, 11 Sep 2024 00:29:27 +0200
Subject: moved stuff

---
 content/geometry/hpi.cpp          |  16 +++++++-------
 content/math/linearRecurrence.cpp |  14 ++++++------
 content/math/math.tex             |   7 +++++-
 content/math/recover.cpp          |  13 +++++++++++
 content/other/other.tex           |  18 ++++++----------
 content/other/recover.cpp         |  13 -----------
 tcr.pdf                           | Bin 698834 -> 695781 bytes
 test/geometry.h                   |   6 +++---
 test/math/recover.cpp             |  44 ++++++++++++++++++++++++++++++++++++++
 test/other/recover.cpp            |  44 --------------------------------------
 10 files changed, 87 insertions(+), 88 deletions(-)
 create mode 100644 content/math/recover.cpp
 delete mode 100644 content/other/recover.cpp
 create mode 100644 test/math/recover.cpp
 delete mode 100644 test/other/recover.cpp

(limited to 'content/other/other.tex')

diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index c58a6e7..f3dc08d 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -27,22 +27,22 @@ struct hp {
 			if (ort == 0) return cross(from, to, a.from) < 0;
 			return cross(b.dir(), a.dir()) * ort > 0;
 		}
-		ll y = cross(a.dir(), b.dir());
-		ll z = cross(b.from - a.from, b.dir());
-		ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b
-		// check if i is outside/right of x
-		return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0;
+		ll x = cross(a.dir(), b.dir());
+		ll y = cross(b.from - a.from, b.dir());
+		ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b
+		// check if i is outside/right of this
+		return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0;
 	}
 };
 
 constexpr ll lim = 2e9+7;
 
 deque<hp> intersect(vector<hp> hps) {
-	hps.push_back(hp(pt{lim+1,-1}));
-	hps.push_back(hp(pt{lim+1,1}));
+	hps.push_back(hp(pt{lim + 1, -1}));
+	hps.push_back(hp(pt{lim + 1, 1}));
 	sort(all(hps));
 
-	deque<hp> dq = {hp(pt{-lim, 1})};
+	deque<hp> dq = {hp(pt{-lim - 1, 1})};
 	for (auto x : hps) {
 		while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2]))
 			dq.pop_back();
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index c15c25c..ab86f71 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -10,21 +10,21 @@
 // 	return c;
 // }
 
-ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){
+ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) {
 	int n = sz(c);
-	vector<ll> q(n+1, 1);
-	for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod;
+	vector<ll> q(n + 1, 1);
+	for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod;
 	vector<ll> p = mul(f, q);
 	p.resize(n);
 	p.push_back(0);
-	do{
+	do {
 		vector<ll> q2 = q;
-		for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+		for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
 		vector<ll> x = mul(p, q2), y = mul(q, q2);
-		for(int i = 0; i <= n; i++){
+		for (int i = 0; i <= n; i++){
 			p[i] = i == n ? 0 : x[2*i + (k&1)];
 			q[i] = y[2*i];
 		}
-	}while(k /= 2);
+	} while (k /= 2);
 	return p[0];
 }
\ No newline at end of file
diff --git a/content/math/math.tex b/content/math/math.tex
index fb66110..4ac6c9e 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -544,6 +544,11 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 \subsection{Wichtige Zahlen}
 \input{math/tables/composite}
 
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
 \optional{
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \begin{methods}
@@ -552,10 +557,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
 \end{methods}
 \sourcecode{math/piLehmer.cpp}
-}
 
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \sourcecode{math/piLegendre.cpp}
+}
 
 \begin{algorithm}[optional]{Big Integers}
 	\sourcecode{math/bigint.cpp}
diff --git a/content/math/recover.cpp b/content/math/recover.cpp
new file mode 100644
index 0000000..1a593f0
--- /dev/null
+++ b/content/math/recover.cpp
@@ -0,0 +1,13 @@
+ll sq(ll x) {return x*x;}
+
+array<ll, 2> recover(ll c, ll m) {
+	array<ll, 2> u = {m, 0}, v = {c, 1};
+	while (m <= 2 * sq(v[0])) {
+		ll q = u[0] / v[0];
+		u[0] -= q * v[0];
+		u[1] -= q * v[1];
+		swap(u, v);
+	}
+	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return v;
+}
diff --git a/content/other/other.tex b/content/other/other.tex
index 368d0b3..191a6da 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -72,6 +72,12 @@
 	\sourcecode{other/sos.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Fast Subset Sum}
+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+	\sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Parallel Binary Search}
 	\sourcecode{other/pbs.cpp}
 \end{algorithm}
@@ -95,18 +101,6 @@
 	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
 \end{algorithm}
 
-\vfill\null\columnbreak
-
-\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
-\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
-\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
-\sourcecode{other/recover.cpp}
-
-\subsection{Fast Subset Sum}
-\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}
-Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
-\sourcecode{other/fastSubsetSum.cpp}
-
 \begin{algorithm}[optional]{Zeileneingabe}
 	\sourcecode{other/split.cpp}
 \end{algorithm}
diff --git a/content/other/recover.cpp b/content/other/recover.cpp
deleted file mode 100644
index 1a593f0..0000000
--- a/content/other/recover.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-ll sq(ll x) {return x*x;}
-
-array<ll, 2> recover(ll c, ll m) {
-	array<ll, 2> u = {m, 0}, v = {c, 1};
-	while (m <= 2 * sq(v[0])) {
-		ll q = u[0] / v[0];
-		u[0] -= q * v[0];
-		u[1] -= q * v[1];
-		swap(u, v);
-	}
-	if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
-	return v;
-}
diff --git a/tcr.pdf b/tcr.pdf
index d383dd9..6f156e4 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/geometry.h b/test/geometry.h
index 7886fe2..0167d5c 100644
--- a/test/geometry.h
+++ b/test/geometry.h
@@ -1,6 +1,6 @@
-#include <geometry/sortAround.cpp>
-
 namespace details {
+	#include <geometry/sortAround.cpp>
+
 	// Liegt p auf der Strecke a-b?
 	bool pointInLineSegment(pt a, pt b, pt p) {
 		if (cross(a, b, p) != 0) return false;
@@ -59,7 +59,7 @@ namespace Random {
 			for (size_t i = 0; i < dirs.size(); i++) {
 				dirs[i] = pt(x[i], y[i]);
 			}
-			sortAround(0, dirs);
+			details::sortAround(0, dirs);
 
 			vector<pt> res = {{0, 0}};
 			ll maxX = 0;
diff --git a/test/math/recover.cpp b/test/math/recover.cpp
new file mode 100644
index 0000000..72853e5
--- /dev/null
+++ b/test/math/recover.cpp
@@ -0,0 +1,44 @@
+#include "../util.h"
+#include <other/recover.cpp>
+#include <math/shortModInv.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	timer t;
+	for (int i = 0; i < 500; i++) {
+		ll p = Random::prime<ll>(10000);
+		for (ll j = 0; 2*j*j < p; j++) {
+			for (ll b = 1; 2*b*b < p; b++) {
+				if (gcd(j, b) != 1) continue;
+				for (ll a : {-j, j}) {
+					ll c = a * multInv(b, p);
+					
+					t.start();
+					auto [x, y] = recover(c, p);
+					t.stop();
+
+					if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
+					queries++;
+				}
+			}
+		}
+		for (ll c = 0; c < p; c++) {
+			t.start();
+			auto [x, y] = recover(c, p);
+			t.stop();
+
+			if (y < 0) continue;
+			if (y == 0) cerr << "error: y=0" << FAIL;
+			ll got = (((x * multInv(y, p)) % p) + p) % p;
+			if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms" << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/other/recover.cpp b/test/other/recover.cpp
deleted file mode 100644
index 72853e5..0000000
--- a/test/other/recover.cpp
+++ /dev/null
@@ -1,44 +0,0 @@
-#include "../util.h"
-#include <other/recover.cpp>
-#include <math/shortModInv.cpp>
-
-void stress_test() {
-	ll queries = 0;
-	timer t;
-	for (int i = 0; i < 500; i++) {
-		ll p = Random::prime<ll>(10000);
-		for (ll j = 0; 2*j*j < p; j++) {
-			for (ll b = 1; 2*b*b < p; b++) {
-				if (gcd(j, b) != 1) continue;
-				for (ll a : {-j, j}) {
-					ll c = a * multInv(b, p);
-					
-					t.start();
-					auto [x, y] = recover(c, p);
-					t.stop();
-
-					if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL;
-					queries++;
-				}
-			}
-		}
-		for (ll c = 0; c < p; c++) {
-			t.start();
-			auto [x, y] = recover(c, p);
-			t.stop();
-
-			if (y < 0) continue;
-			if (y == 0) cerr << "error: y=0" << FAIL;
-			ll got = (((x * multInv(y, p)) % p) + p) % p;
-			if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL;
-			queries++;
-		}
-	}
-	cerr << "tested random queries: " << queries << endl;
-	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
-	cerr << "tested performance: " << t.time << "ms" << endl;
-}
-
-int main() {
-	stress_test();
-}
-- 
cgit v1.2.3

