From ac2d9ad3f2c88bc12420fc439e8d0b4775a11169 Mon Sep 17 00:00:00 2001 From: mzuenni 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 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 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 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 + +int subsetSum(vector w, int t){ + vector 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(1, 20); + int t = Random::integer(1, 500); + vector w = Random::integers(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 w = Random::integers(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 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 intersect(vector 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 dq = {hp(pt{-lim, 1})}; + deque 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& f, const vector& c, ll k){ +ll kthTerm(const vector& f, const vector& c, ll k) { int n = sz(c); - vector q(n+1, 1); - for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod; + vector q(n + 1, 1); + for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod; vector p = mul(f, q); p.resize(n); p.push_back(0); - do{ + do { vector 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 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 recover(ll c, ll m) { + array 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 recover(ll c, ll m) { - array 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 - namespace details { + #include + // 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 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 +#include + +void stress_test() { + ll queries = 0; + timer t; + for (int i = 0; i < 500; i++) { + ll p = Random::prime(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 -#include - -void stress_test() { - ll queries = 0; - timer t; - for (int i = 0; i < 500; i++) { - ll p = Random::prime(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