From 19436370fb48bc0a5e356d1ba713dc39b1a35d3a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 6 Aug 2024 16:54:13 +0200 Subject: upper case INF --- content/other/divideAndConquer.cpp | 4 ++-- content/other/knuth.cpp | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'content/other') diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp index 830dc7f..9bd5f0c 100644 --- a/content/other/divideAndConquer.cpp +++ b/content/other/divideAndConquer.cpp @@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { if (j1 < j0) return; int jmid = (j0 + j1) / 2; - dp[i][jmid] = inf; + dp[i][jmid] = INF; int bestk = m0; for (int k = m0; k < min(jmid, m1 + 1); ++k) { if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) { @@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { } ll calc(int n, int m) { - dp = vector>(m, vector(n, inf)); + dp = vector>(m, vector(n, INF)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; for (int i = 1; i < m; i++) { rec(i, 0, n - 1, 0, n - 1); diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp index 1d513c8..aa54924 100644 --- a/content/other/knuth.cpp +++ b/content/other/knuth.cpp @@ -1,5 +1,5 @@ ll calc(int n, int m, const vector>& C) { - vector> dp(m, vector(n, inf)); + vector> dp(m, vector(n, INF)); vector> opt(m, vector(n + 1, n - 1)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; -- cgit v1.2.3 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/latexHeaders/math.sty | 1 + content/other/bitOps.cpp | 7 ------- content/other/josephus2.cpp | 9 +++------ content/other/other.tex | 34 +++++++++++++++++++++------------- content/other/pbs.cpp | 3 +-- content/other/recover.cpp | 12 ++++++++++++ content/other/stuff.cpp | 6 ------ tcr.pdf | Bin 691029 -> 691903 bytes test/other/recover.cpp | 34 ++++++++++++++++++++++++++++++++++ 9 files changed, 72 insertions(+), 34 deletions(-) create mode 100644 content/other/recover.cpp create mode 100644 test/other/recover.cpp (limited to 'content/other') diff --git a/content/latexHeaders/math.sty b/content/latexHeaders/math.sty index c34cc99..d758f71 100644 --- a/content/latexHeaders/math.sty +++ b/content/latexHeaders/math.sty @@ -6,6 +6,7 @@ \usepackage{mathtools} \usepackage{amssymb} \usepackage{ntheorem} +\usepackage{nicefrac} %\usepackage{pxfonts} \usepackage[scaled=0.945,largesc,looser]{newpxtext}%better than pxfonts... diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp index 8079305..6230c86 100644 --- a/content/other/bitOps.cpp +++ b/content/other/bitOps.cpp @@ -3,13 +3,6 @@ for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) -// Zählt Anzahl der gesetzten Bits. -int numberOfSetBits(int i) { - i = i - ((i >> 1) & 0x5555'5555); - i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333); - return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24; -} - // Nächste Permutation in Bitmaske // (z.B. 00111 => 01011 => 01101 => ...) ll nextPerm(ll v) { diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp index 5086e13..33544ea 100644 --- a/content/other/josephus2.cpp +++ b/content/other/josephus2.cpp @@ -1,8 +1,5 @@ int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert. - for (int i = 31; i >= 0; i--) { - if (n & (1 << i)) { - n &= ~(1 << i); - break; - }} - n <<= 1; n++; return n; + int bits = __lg(n); + n ^= 1 << bits; + return 2 * n + 1; } 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} diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 7cb60e5..5508d6c 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -10,9 +10,8 @@ while (true) { // reset simulation for (int step = 0; auto [mid, i] : focus) { - while (step <= mid) { + for (; step <= mid; step++) { // simulation step - step++; } if (/* requirement already fulfilled */) high[i] = mid; else low[i] = mid + 1; diff --git a/content/other/recover.cpp b/content/other/recover.cpp new file mode 100644 index 0000000..0d3c3ea --- /dev/null +++ b/content/other/recover.cpp @@ -0,0 +1,12 @@ +ll sq(ll x) {return x*x;} + +pair recover(ll c, ll m) { + array u = {1, 0, m}, v = {0, 1, c}; + while (m <= 2 * sq(v[2])) { + ll q = u[2] / v[2]; + for (int i : {0, 1, 2}) u[i] -= q * v[i]; + swap(u, v); + } + if (v[1] < 0 || 2 * sq(v[1]) >= m) return {-1, -1}; + return {v[2], v[1]}; +} diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp index 41543ad..e4e37e2 100644 --- a/content/other/stuff.cpp +++ b/content/other/stuff.cpp @@ -1,13 +1,7 @@ -// Alles-Header. -#include - // Setzt deutsche Tastaturlayout / toggle mit alt + space setxkbmap de setxkbmap de,us -option grp:alt_space_toggle -// Schnelle Ein-/Ausgabe mit cin/cout. -cin.tie(nullptr)->ios::sync_with_stdio(false); - // Set mit eigener Sortierfunktion. set set1(comp); diff --git a/tcr.pdf b/tcr.pdf index 2f24510..c6fc0ce 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/other/recover.cpp b/test/other/recover.cpp new file mode 100644 index 0000000..fa491e8 --- /dev/null +++ b/test/other/recover.cpp @@ -0,0 +1,34 @@ +#include "../util.h" +#include +#include + +void stress_test() { + ll queries = 0; + timer t; + for (int i = 0; i < 1000; 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++; + } + } + } + + } + 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 From ca5de48d6431cd1321b60718b900712918176911 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 30 Aug 2024 15:35:58 +0200 Subject: shortened code --- content/other/recover.cpp | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'content/other') diff --git a/content/other/recover.cpp b/content/other/recover.cpp index 0d3c3ea..1a593f0 100644 --- a/content/other/recover.cpp +++ b/content/other/recover.cpp @@ -1,12 +1,13 @@ ll sq(ll x) {return x*x;} -pair recover(ll c, ll m) { - array u = {1, 0, m}, v = {0, 1, c}; - while (m <= 2 * sq(v[2])) { - ll q = u[2] / v[2]; - for (int i : {0, 1, 2}) u[i] -= q * v[i]; +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[2], v[1]}; + if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1}; + return v; } -- cgit v1.2.3 From 1abc08be606b7379bb1b9c5150bf73841a4b9c66 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 30 Aug 2024 16:46:50 +0200 Subject: improve pbs --- content/other/pbs.cpp | 11 ++++++----- tcr.pdf | Bin 691903 -> 691692 bytes 2 files changed, 6 insertions(+), 5 deletions(-) (limited to 'content/other') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 5508d6c..6cf872a 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,10 +1,11 @@ // Q = # of queries, bucket sort is sometimes faster -vector low(Q, 0), high(Q, MAX_OPERATIONS); +vector low(Q, 0), high(Q, MAX_OPERATIONS + 1); while (true) { vector> focus; - for (int i = 0; i < Q; i++) if (low[i] < high[i]) { - focus.emplace_back((low[i] + high[i]) / 2, i); - } + for (int i = 0; i < Q; i++) { + if (low[i] + 1 < high[i]) { + focus.emplace_back((low[i] + high[i]) / 2, i); + }} if (focus.empty()) break; sort(all(focus)); @@ -14,5 +15,5 @@ while (true) { // simulation step } if (/* requirement already fulfilled */) high[i] = mid; - else low[i] = mid + 1; + else low[i] = mid; }} // answer in low (and high) diff --git a/tcr.pdf b/tcr.pdf index c6fc0ce..e349ca0 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 77997253fb0978c2f45b73982eb0926756747882 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Sep 2024 18:03:19 +0200 Subject: more tests --- content/other/pbs.cpp | 2 +- test/other/pbs.cpp | 103 +++++++++++++++++++++++++++++++++++++++++++++++++ test/other/pbs.cpp.awk | 8 ++++ test/test.sh | 1 + 4 files changed, 113 insertions(+), 1 deletion(-) create mode 100644 test/other/pbs.cpp create mode 100644 test/other/pbs.cpp.awk (limited to 'content/other') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 6cf872a..e6ef07d 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,5 +1,5 @@ // Q = # of queries, bucket sort is sometimes faster -vector low(Q, 0), high(Q, MAX_OPERATIONS + 1); +vector low(Q, -1), high(Q, MAX_OPERATIONS); while (true) { vector> focus; for (int i = 0; i < Q; i++) { diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp new file mode 100644 index 0000000..ba3b9d0 --- /dev/null +++ b/test/other/pbs.cpp @@ -0,0 +1,103 @@ +#include "../util.h" + +struct Union { + vector a; + + Union(int n) : a(n, -1) {} + + int find(int i) { + return a[i] < 0 ? i : a[i] = find(a[i]); + } + + void join(int i, int j) { + i = find(i), j = find(j); + if (i == j) return; + a[j] = i; + } + + bool same(int i, int j) { + return find(i) == find(j); + } +}; + +int n; +Union un(0); +void reset() { + un = Union(n); +} + +vector> edges; +void do_step(int i) { + auto [u, v] = edges[i]; + un.join(u, v); +} + +vector> queries; +bool test(int i) { + auto [u, v] = queries[i]; + return un.same(u, v); +} + +#include +void stress_test() { + for (int it = 0; it < 100'000; it++) { + n = Random::integer(2, 31); + int Q = Random::integer(2, 31); + int MAX_OPERATIONS = n-1; + + edges.clear(); + for (int i=1; i ans = pbs(Q, MAX_OPERATIONS); + + vector correct(Q, -1); + Union un2(n); + for (int j=0; j ans = pbs(Q, MAX_OPERATIONS); + t.stop(); + ll hash = accumulate(all(ans), 0LL); + + if (t.time > 700) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} diff --git a/test/other/pbs.cpp.awk b/test/other/pbs.cpp.awk new file mode 100644 index 0000000..3084ebd --- /dev/null +++ b/test/other/pbs.cpp.awk @@ -0,0 +1,8 @@ +BEGIN { print "vector pbs(int Q, int MAX_OPERATIONS) {" } +{ + sub(/\/\* requirement already fulfilled \*\//, "test(i)") + sub(/\/\/ simulation step/, "do_step(step);") + sub(/\/\/ reset simulation/, "reset();") +} +{ print } +END { print "return high; }" } diff --git a/test/test.sh b/test/test.sh index 3cb5c9c..e4eecee 100755 --- a/test/test.sh +++ b/test/test.sh @@ -6,6 +6,7 @@ export MALLOC_PERTURB_="$((2#01011001))" declare -A cppstandard cppstandard["string/suffixArray.cpp"]="gnu++20" +cppstandard["other/pbs.cpp"]="gnu++20" seedmacro="" process_awk() { -- cgit v1.2.3 From d4352adae52b2606e5f5db069b2899d444e85e77 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Sep 2024 18:04:58 +0200 Subject: fix comment --- content/other/pbs.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/other') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index e6ef07d..f4db2fd 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -16,4 +16,4 @@ while (true) { } if (/* requirement already fulfilled */) high[i] = mid; else low[i] = mid; -}} // answer in low (and high) +}} // answer in low (MAX_OPERATIONS if never ok) -- 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') 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') 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