From ef95a81b809ec6fcaf53a870f7bc86bf613b42f8 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 30 Jul 2024 15:57:54 +0200 Subject: removed old slow code --- content/math/math.tex | 2 -- content/math/squfof.cpp | 89 ------------------------------------------------- 2 files changed, 91 deletions(-) delete mode 100644 content/math/squfof.cpp (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index f99d0d4..c15825f 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/millerRabin.cpp} \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}} \sourcecode{math/rho.cpp} - %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}} - %\sourcecode{math/squfof.cpp} \end{algorithm} \begin{algorithm}{Teiler} diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp deleted file mode 100644 index 1cb97de..0000000 --- a/content/math/squfof.cpp +++ /dev/null @@ -1,89 +0,0 @@ -using lll = __int128; - -constexpr lll multipliers[] = {1, 3, 5, 7, - 11, 3*5, 3*7, 3*11, - 5*7, 5*11, 7*11, - 3*5*7, 3*5*11, 3*7*11, - 5*7*11, 3*5*7*11}; - -lll root(lll x) { - lll r = sqrtl(x); - while(r*r < x) r++; - while(r*r > x) r--; - return r; -} - -lll croot(lll x) { - lll r = cbrtl(x); - while(r*r*r < x) r++; - while(r*r*r > x) r--; - return r; -} - -lll squfof(lll N) { - lll s = croot(N); - if (s*s*s == N) return s; - s = root(N); - if (s*s == N) return s; - for (lll k : multipliers) { - lll D = k * N; - lll Po, P, Pprev, q, b, r, i; - Po = Pprev = P = root(D); - lll Qprev = 1; - lll Q = D - Po*Po; - lll L = 2 * root(2 * s); - lll B = 3 * L; - for (i = 2; i < B; i++) { - b = (Po + P) / Q; - P = b*Q - P; - q = Q; - Q = Qprev + b * (Pprev - P); - r = root(Q); - if (!(i & 1) && r*r == Q) break; - Qprev = q; - Pprev = P; - } - if (i >= B) continue; - b = (Po - P) / r; - Pprev = P = b*r + P; - Qprev = r; - Q = (D-Pprev*Pprev)/Qprev; - i = 0; - do { - b = (Po + P) / Q; - Pprev = P; - P = b*Q - P; - q = Q; - Q = Qprev + b * (Pprev - P); - Qprev = q; - i++; - } while(P != Pprev); - r = gcd(N, Qprev); - if (r != 1 && r != N) return r; - } - exit(1);//try fallback to pollard rho -} - -constexpr lll trialLim = 5'000; - -void factor(lll n, map& facts) { - for (lll i = 2; i * i <= n && i <= trialLim; i++) { - while (n % i == 0) { - facts[i]++; - n /= i; - }} - if (n > 1 && n < trialLim * trialLim) { - facts[n]++; - } else { - vector todo = {n}; - while (!todo.empty()) { - lll c = todo.back(); - todo.pop_back(); - if (c == 1) continue; - if (isPrime(c)) { - facts[c]++; - } else { - lll d = squfof(c); - todo.push_back(d); - todo.push_back(c / d); -}}}} -- cgit v1.2.3 From d7905f7dec9e306d7d6f907ce35abc40f24af1c5 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 30 Jul 2024 23:58:19 +0200 Subject: more tests --- content/datastructures/persistent.cpp | 8 ++--- content/datastructures/persistentArray.cpp | 4 +-- tcr.pdf | Bin 691138 -> 691035 bytes test/datastructures/persistent.cpp | 35 +++++++++++++++++++++ test/datastructures/persistentArray.cpp | 48 +++++++++++++++++++++++++++++ 5 files changed, 89 insertions(+), 6 deletions(-) create mode 100644 test/datastructures/persistent.cpp create mode 100644 test/datastructures/persistentArray.cpp (limited to 'content') diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp index 4093cdc..7d15342 100644 --- a/content/datastructures/persistent.cpp +++ b/content/datastructures/persistent.cpp @@ -4,15 +4,15 @@ struct persistent { vector> data; persistent(int& time, T value = {}) - : time(time), data(1, {time, value}) {} + : time(time), data(1, {2*time, value}) {} T get(int t) { - return prev(upper_bound(all(data), pair{t+1, T{}}))->second; + return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second; } int set(T value) { - time += 2; - data.push_back({time, value}); + time++; + data.push_back({2*time, value}); return time; } }; diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp index 60d8b17..8326700 100644 --- a/content/datastructures/persistentArray.cpp +++ b/content/datastructures/persistentArray.cpp @@ -10,8 +10,8 @@ struct persistentArray { T get(int p, int t) {return data[p].get(t);} int set(int p, T value) { - mods.push_back({p, time}); - return data[p].set(value); + mods.push_back({p, data[p].set(value)}); + return mods.back().second; } void reset(int t) { diff --git a/tcr.pdf b/tcr.pdf index 608476d..f4b94cd 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/persistent.cpp b/test/datastructures/persistent.cpp new file mode 100644 index 0000000..4e304fa --- /dev/null +++ b/test/datastructures/persistent.cpp @@ -0,0 +1,35 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + + int timeRef = Random::integer(1, 30); + persistent got(timeRef); + map expected; + + for (int i = 0; i < n; i++) { + timeRef += Random::integer(1, 30); + double x = Random::real(-1'000, 1'000); + auto t = got.set(x); + + if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL; + expected[t] = x; + } + + double tmp = 0; + for (int i = expected.begin()->first; i < expected.rbegin()->first + 10; i++) { + if (expected.find(i) != expected.end()) tmp = expected[i]; + if (got.get(i) != tmp) cerr << "got: " << got.get(i) << ", " << "expected: " << tmp << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); +} diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp new file mode 100644 index 0000000..6712089 --- /dev/null +++ b/test/datastructures/persistentArray.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +#include +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 2'000; tries++) { + int n = Random::integer(1, 30)*1000; + int m = Random::integer(1, 30); + + persistentArray got(m); + vector cur(m); + vector>> expected; + for (int i = 0; i < n; i++) { + int op = Random::integer(0, 20); + if (op <= 10) { + int j = Random::integer(0, m); + double x = Random::real(-1'000, 1'000); + + auto t = got.set(j, x); + if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL; + + cur[j] = x; + expected.emplace_back(t, cur); + } else if (op <= 16) { + if (sz(expected) < 1) continue; + int j = Random::integer(0, sz(expected)); + for (int k = 0; k < m; k++) { + if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL; + } + } else { + if (sz(expected) < 1) continue; + int j = Random::integer(0, sz(expected)); + got.reset(expected[j].first); + expected.resize(j + 1); + cur = expected.back().second; + } + + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +int main() { + stress_test(); +} -- cgit v1.2.3 From 231a5826865f712e08f499c92594024728fd785d Mon Sep 17 00:00:00 2001 From: MZuenni Date: Thu, 1 Aug 2024 17:57:07 +0200 Subject: new tests --- content/graph/connect.cpp | 2 +- tcr.pdf | Bin 691035 -> 691201 bytes test/graph/connect.cpp | 124 ++++++++++++++++++++++++++++++++ test/graph/connectMinLCT.h | 173 +++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 298 insertions(+), 1 deletion(-) create mode 100644 test/graph/connect.cpp create mode 100644 test/graph/connectMinLCT.h (limited to 'content') diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp index ffcd6c2..7940b37 100644 --- a/content/graph/connect.cpp +++ b/content/graph/connect.cpp @@ -10,7 +10,7 @@ struct connect { } void addEdge(int u, int v, int id) { - lct.nodes[id + n] = LCT::Node(id + n, id + n); + lct.nodes[id + n] = LCT::Node(id + n, id); edges[id] = {u, v}; if (connected(u, v)) { int old = lct.query(&lct.nodes[u], &lct.nodes[v]); diff --git a/tcr.pdf b/tcr.pdf index f4b94cd..8440c54 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp new file mode 100644 index 0000000..065e21f --- /dev/null +++ b/test/graph/connect.cpp @@ -0,0 +1,124 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +#include "connectMinLCT.h" +constexpr ll INF = 0x3FFF'FFFF; +#include + +struct Naive { + vector> adj; + vector seen; + int counter; + Naive(int n) : adj(n), seen(n), counter(0) {} + + template + void dfs(int x, F&& f) { + counter++; + vector todo = {x}; + seen[x] = counter; + while (!todo.empty()) { + x = todo.back(); + todo.pop_back(); + f(x); + for (ll y : adj[x]) { + if (seen[y] != counter) { + seen[y] = counter; + todo.push_back(y); + } + } + } + } + + bool connected(int a, int b) { + bool res = false; + dfs(a, [&](int x){res |= x == b;}); + return res; + } + + void addEdge(int a, int b) { + adj[a].insert(b); + adj[b].insert(a); + } + + void eraseEdge(int a, int b) { + adj[a].erase(adj[a].find(b)); + adj[b].erase(adj[b].find(a)); + } +}; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 2'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(30, 300); + + vector insertOrder(m); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector> edges(m, {-1, -1}); + + connect con(n, m); + Naive naive(n); + + int deleted = 0; + for (int i = 0; i < m; i++) { + { + int a = Random::integer(0, n); + int b = a; + while (b == a) b = Random::integer(0, n); + edges[insertOrder[i]] = {a, b}; + + con.addEdge(a, b, insertOrder[i]); + naive.addEdge(a, b); + } + + while (deleted < m && edges[deleted] != pair{-1, -1} && Random::integer(2) == 0) { + auto [a, b] = edges[deleted]; + + con.eraseEdge(deleted); + naive.eraseEdge(a, b); + deleted++; + } + + for (int j = 0; j < n; j++) { + int a = Random::integer(0, n); + int b = Random::integer(0, n); + + auto got = con.connected(a, b); + auto expected = naive.connected(a, b); + + if (got != expected) cerr << "error" << FAIL; + } + + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 2'000'000; +void performance_test() { + /*timer t; + t.start(); + UF uf(N); + t.stop(); + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int i = Random::integer(0, N); + int j = Random::integer(0, N); + int k = Random::integer(0, N); + int l = Random::integer(0, N); + + t.start(); + uf.unionSets(i, j); + hash += uf.size(k); + hash += uf.size(l); + t.stop(); + } + if (t.time > 500) 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/graph/connectMinLCT.h b/test/graph/connectMinLCT.h new file mode 100644 index 0000000..4d509f7 --- /dev/null +++ b/test/graph/connectMinLCT.h @@ -0,0 +1,173 @@ +constexpr ll queryDefault = 0x3FFF'FFFF; +constexpr ll updateDefault = 0; +//modifiable: +ll _modify(ll x, ll y) { + return min(x, y); +} +ll _query(ll x, ll y) { + return min(x, y); +} +ll _update(ll delta, int /*length*/) { + return delta; +} + +//generic: +ll joinValueDelta(ll value, ll delta) { + if (delta == updateDefault) return value; + return _modify(value, delta); +} + +ll joinDeltas(ll delta1, ll delta2) { + if (delta1 == updateDefault) return delta2; + if (delta2 == updateDefault) return delta1; + return _modify(delta1, delta2); +} + +struct LCT { + struct Node { + ll nodeValue, subTreeValue, delta; + bool revert; + int id, size; + Node *left, *right, *parent; + + Node(int id = 0, int val = queryDefault) : + nodeValue(val), subTreeValue(val), delta(updateDefault), + revert(false), id(id), size(1), + left(nullptr), right(nullptr), parent(nullptr) {} + + bool isRoot() { + return !parent || (parent->left != this && + parent->right != this); + } + + void push() { + if (revert) { + revert = false; + swap(left, right); + if (left) left->revert ^= 1; + if (right) right->revert ^= 1; + } + nodeValue = joinValueDelta(nodeValue, delta); + subTreeValue = joinValueDelta(subTreeValue, + _update(delta, size)); + if (left) left->delta = joinDeltas(left->delta, delta); + if (right) right->delta = joinDeltas(right->delta, delta); + delta = updateDefault; + } + + ll getSubtreeValue() { + return joinValueDelta(subTreeValue, _update(delta, size)); + } + + void update() { + subTreeValue = joinValueDelta(nodeValue, delta); + size = 1; + if (left) { + subTreeValue = _query(subTreeValue, + left->getSubtreeValue()); + size += left->size; + } + if (right) { + subTreeValue = _query(subTreeValue, + right->getSubtreeValue()); + size += right->size; + }} + }; + + vector nodes; + + LCT(int n) : nodes(n) { + for (int i = 0; i < n; i++) nodes[i].id = i; + } + + void connect(Node* ch, Node* p, int isLeftChild) { + if (ch) ch->parent = p; + if (isLeftChild >= 0) { + if (isLeftChild) p->left = ch; + else p->right = ch; + }} + + void rotate(Node* x) { + Node* p = x->parent; + Node* g = p->parent; + bool isRootP = p->isRoot(); + bool leftChildX = (x == p->left); + + connect(leftChildX ? x->right : x->left, p, leftChildX); + connect(p, x, !leftChildX); + connect(x, g, isRootP ? -1 : p == g->left); + p->update(); + } + + void splay(Node* x) { + while (!x->isRoot()) { + Node* p = x->parent; + Node* g = p->parent; + if (!p->isRoot()) g->push(); + p->push(); + x->push(); + if (!p->isRoot()) rotate((x == p->left) == + (p == g->left) ? p : x); + rotate(x); + } + x->push(); + x->update(); + } + + Node* expose(Node* x) { + Node* last = nullptr; + for (Node* y = x; y; y = y->parent) { + splay(y); + y->left = last; + last = y; + } + splay(x); + return last; + } + + void makeRoot(Node* x) { + expose(x); + x->revert ^= 1; + } + + bool connected(Node* x, Node* y) { + if (x == y) return true; + expose(x); + expose(y); + return x->parent; + } + + void link(Node* x, Node* y) { + assert(!connected(x, y)); // not yet connected! + makeRoot(x); + x->parent = y; + } + + void cut(Node* x, Node* y) { + makeRoot(x); + expose(y); + //must be a tree edge! + assert(!(y->right != x || x->left != nullptr)); + y->right->parent = nullptr; + y->right = nullptr; + } + + Node* lca(Node* x, Node* y) { + assert(connected(x, y)); + expose(x); + return expose(y); + } + + ll query(Node* from, Node* to) { + makeRoot(from); + expose(to); + if (to) return to->getSubtreeValue(); + return queryDefault; + } + + void modify(Node* from, Node* to, ll delta) { + makeRoot(from); + expose(to); + to->delta = joinDeltas(to->delta, delta); + } +}; -- cgit v1.2.3 From e46ead1681b24c75624c33f167c530e633e40440 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 3 Aug 2024 00:14:36 +0200 Subject: more tests --- content/math/polynomial.cpp | 7 +- test/math/polynomial.cpp | 153 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 157 insertions(+), 3 deletions(-) create mode 100644 test/math/polynomial.cpp (limited to 'content') diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp index 44f6207..84f3aaa 100644 --- a/content/math/polynomial.cpp +++ b/content/math/polynomial.cpp @@ -1,7 +1,7 @@ struct poly { vector data; - poly(int deg = 0) : data(max(1, deg)) {} + poly(int deg = 0) : data(1 + deg) {} poly(initializer_list _data) : data(_data) {} int size() const {return sz(data);} @@ -40,17 +40,18 @@ struct poly { //return p(x+a) poly operator<<(ll a) const { - poly res(size()); + poly res(size() - 1); for (int i = size() - 1; i >= 0; i--) { for (int j = size() - i - 1; j >= 1; j--) res[j] = (res[j] * a + res[j - 1]) % mod; - res[0] = (res[0] * a + res[i]) % mod; + res[0] = (res[0] * a + data[i]) % mod; } return res; } pair divmod(const poly& d) const { int i = size() - d.size(); + if (i <= 0) return {{}, *this}; poly s(i + 1), r = *this; ll inv = multInv(d.data.back(), mod); for (; i >= 0; i--) { diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp new file mode 100644 index 0000000..f4a9486 --- /dev/null +++ b/test/math/polynomial.cpp @@ -0,0 +1,153 @@ +#include "../util.h" +#include +constexpr ll mod = 1'394'633'899; +#include + +poly randomPoly(int deg) { + poly p; + p.data = Random::integers(deg + 1, 0, mod); + return p; +} + +ll eval(const vector& p, ll x) { + ll res = 0; + for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) { + res += j * p[i]; + res %= mod; + } + return res; +} + +void test_eval() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int deg = Random::integer(1, 30); + vector tmp = Random::integers(deg + 1, 0, mod); + poly p(deg); + for (int i = 0; i <= deg; i++) p[i] = tmp[i]; + + for (int i = 0; i <= deg + 7; i++) { + ll x = Random::integer(0, mod); + + ll got = p(x); + ll expected = eval(tmp, x); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += deg + 1; + } + cerr << "tested eval: " << queries << endl; +} + +void test_add() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto c = a; + c += b; + + if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + m + 7; i++) { + ll x = Random::integer(0, mod); + + ll got = c(x); + ll expected = (a(x) + b(x)) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested add: " << queries << endl; +} + +void test_mul() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto c = a * b; + if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + m + 7; i++) { + ll x = Random::integer(0, mod); + + ll got = c(x); + ll expected = (a(x) * b(x)) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested mul: " << queries << endl; +} + +void test_shift() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(1, 30); + auto a = randomPoly(n); + + auto b = a << m; + if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl; + if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + 7; i++) { + ll x = Random::integer(0, mod); + + ll got = b(x); + ll expected = a((x + m) % mod); + + if (got != expected) { + for (ll y : b.data) cerr << y << " "; + cerr << endl; + } + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested shift: " << queries << endl; +} + +void test_divmod() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer(1, 30); + int m = Random::integer(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto [div, rem] = a.divmod(b); + if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL; + if (sz(div) > 1 + max(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL; + + for (int i = 0; i <= n + m; i++) { + ll x = Random::integer(0, mod); + ll d = multInv(b(x), mod); + + ll got = (div(x) + rem(x) * d) % mod; + ll expected = (a(x) * d) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested divmod: " << queries << endl; +} + +int main() { + test_eval(); + test_add(); + test_mul(); + test_shift(); + test_divmod(); +} + -- cgit v1.2.3 From 1ad495344f764e979e93f394f76716cf527c2940 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 4 Aug 2024 15:58:47 +0200 Subject: more tests --- content/datastructures/lichao.cpp | 6 ++-- tcr.pdf | Bin 691201 -> 691040 bytes test/datastructures/lichao.cpp | 73 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 76 insertions(+), 3 deletions(-) create mode 100644 test/datastructures/lichao.cpp (limited to 'content') diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index f66778e..646ad68 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -11,10 +11,10 @@ struct Lichao { static constexpr Fun id = {0, inf}; // {0, -inf} int n, cap; vector seg; - Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} + Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {} void _insert(Fun f, int l, int r, int i) { - while (i < 2*cap){ + while (i < 2 * cap) { int m = (l+r)/2; if (m >= n) {r = m; i = 2*i; continue;} Fun &g = seg[i]; @@ -26,7 +26,7 @@ struct Lichao { void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { if (l <= a && b <= r) _insert(f, a, b, i); - else if (a < r && l < b){ + else if (a < r && l < b) { int m = (a+b)/2; _segmentInsert(f, l, r, a, m, 2*i); _segmentInsert(f, l, r, m, b, 2*i+1); diff --git a/tcr.pdf b/tcr.pdf index 8440c54..1cb888a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp new file mode 100644 index 0000000..acd048f --- /dev/null +++ b/test/datastructures/lichao.cpp @@ -0,0 +1,73 @@ +#include "../util.h" +constexpr ll inf = LL::INF; +#include + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(1, 100); + xs = Random::distinct(n, -1000, 1000); + sort(all(xs)); + + vector naive(n, inf); + Lichao tree; + + for (int operations = 0; operations < 1000; operations++) { + { + ll m = Random::integer(-100, 100); + ll c = Random::integer(-1000, 1000); + ll l = Random::integer(-1000, 1000); + ll r = Random::integer(-1000, 1000); + Fun f{m, c}; + + tree.segmentInsert(f, l, r); + for (int i = 0; i < n; i++) { + if (l <= xs[i] && xs[i] < r) naive[i] = min(naive[i], f(i)); + } + } + { + queries++; + int i = Random::integer(0, n); + ll got = tree.query(xs[i]); + ll expected = naive[i]; + if (got != expected) cerr << xs[i] << endl; + if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << " tested random queries: " << queries << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + xs = Random::distinct(N, -1'000'000'000, 1'000'000'000); + sort(all(xs)); + + t.start(); + Lichao tree; + t.stop(); + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + + ll m = Random::integer(-1'000'000, 1'000'000); + ll c = Random::integer(-1'000'000, 1'000'000); + ll l = Random::integer(-1'000'000'000, 1'000'000'000); + ll r = Random::integer(-1'000'000'000, 1'000'000'000); + ll x = xs[Random::integer(N)]; + Fun f{m, c}; + + t.start(); + tree.segmentInsert(f, l, r); + hash ^= tree.query(x); + t.stop(); + } + if (t.time > 1000) 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 ff3b67478b1f08b0a2b83565de8a454e23441f3a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 15:41:25 +0200 Subject: more testcases --- content/datastructures/monotonicConvexHull.cpp | 18 +++--- tcr.pdf | Bin 691040 -> 691039 bytes test/datastructures/lichao.cpp | 22 +++---- test/datastructures/monotonicConvexHull.cpp | 79 +++++++++++++++++++++++++ 4 files changed, 100 insertions(+), 19 deletions(-) create mode 100644 test/datastructures/monotonicConvexHull.cpp (limited to 'content') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 44bff83..119015e 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,27 @@ -// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue +// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { - ll m, b; - ll operator()(ll x) {return m*x+b;} + ll m, c; + ll operator()(ll x) {return m*x+c;} }; vector ls; -int ptr = 0; +ll ptr = 0; bool bad(Line l1, Line l2, Line l3) { - return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); + return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll b) { // Laufzeit O(1) amortisiert - while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { +void add(ll m, ll c) { // Laufzeit O(1) amortisiert + while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } - ls.push_back({m, b}); + ls.push_back({m, c}); ptr = min(ptr, sz(ls) - 1); } ll query(ll x) { // Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); - while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); } \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index 1cb888a..48a07d7 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index acd048f..c8a56a3 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -2,11 +2,11 @@ constexpr ll inf = LL::INF; #include -void stress_test() { +void stress_test(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); - xs = Random::distinct(n, -1000, 1000); + xs = Random::distinct(n, -range, range); sort(all(xs)); vector naive(n, inf); @@ -15,9 +15,9 @@ void stress_test() { for (int operations = 0; operations < 1000; operations++) { { ll m = Random::integer(-100, 100); - ll c = Random::integer(-1000, 1000); - ll l = Random::integer(-1000, 1000); - ll r = Random::integer(-1000, 1000); + ll c = Random::integer(-range, range); + ll l = Random::integer(-range, range); + ll r = Random::integer(-range, range); Fun f{m, c}; tree.segmentInsert(f, l, r); @@ -31,11 +31,11 @@ void stress_test() { ll got = tree.query(xs[i]); ll expected = naive[i]; if (got != expected) cerr << xs[i] << endl; - if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } } - cerr << " tested random queries: " << queries << endl; + cerr << "tested random queries: " << queries << endl; } constexpr int N = 200'000; @@ -63,11 +63,13 @@ void performance_test() { hash ^= tree.query(x); t.stop(); } - if (t.time > 1000) cerr << " too slow: " << t.time << FAIL; - cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } int main() { - stress_test(); + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); performance_test(); } diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp new file mode 100644 index 0000000..0d4e10d --- /dev/null +++ b/test/datastructures/monotonicConvexHull.cpp @@ -0,0 +1,79 @@ +#include "../util.h" +struct MCH { + #include +}; + +struct Line { + ll m, c; + Line(ll m_, ll c_) : m(m_), c(c_) {} + ll operator()(ll x) {return m*x+c;} +}; + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(1, 100); + auto ms = Random::distinct(n, -range, range); + sort(all(ms), greater<>{}); + auto xs = Random::distinct(n*100, -range*n, range*n); + sort(all(xs)); + int i = 0; + + vector naive; + + MCH mch; + for (ll m : ms) { + ll c = Random::integer(-1000, 1000); + mch.add(m, c); + naive.emplace_back(m, c); + + for (int j = i + 100; i < j; i++) { + ll x = xs[i]; + + ll got = mch.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = min(expected, l(x)); + + if (got != expected) { + for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; + cerr << x << ": " << got << " " << expected << endl; + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + auto ms = Random::distinct(N, -1'000'000'000, 1'000'000'000); + sort(all(ms), greater<>{}); + auto xs = Random::distinct(N, -1'000'000'000, 1'000'000'000); + sort(all(xs)); + MCH mch; + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll c = Random::integer(-1'000'000'000, 1'000'000'000); + ll m = ms[operations]; + ll x = xs[operations]; + + t.start(); + mch.add(m, c); + hash += mch.query(x); + t.stop(); + } + if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); + performance_test(); +} -- cgit v1.2.3 From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 20:10:57 +0200 Subject: more tests --- content/datastructures/dynamicConvexHull.cpp | 2 +- content/datastructures/monotonicConvexHull.cpp | 6 +-- tcr.pdf | Bin 691039 -> 691129 bytes test/datastructures/dynamicConvexHull.cpp | 72 +++++++++++++++++++++++++ test/datastructures/monotonicConvexHull.cpp | 7 +-- 5 files changed, 77 insertions(+), 10 deletions(-) create mode 100644 test/datastructures/dynamicConvexHull.cpp (limited to 'content') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index d669847..dfcfe0b 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -4,7 +4,7 @@ struct Line { bool operator<(ll x) const {return p < x;} }; -struct HullDynamic : multiset> { +struct HullDynamic : multiset> { // max über Geraden // (for doubles, use inf = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 119015e..e84ad86 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,4 +1,4 @@ -// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue +// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { ll m, c; @@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) { return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll c) { // Laufzeit O(1) amortisiert +void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } @@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // Laufzeit: O(1) amortisiert +ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); diff --git a/tcr.pdf b/tcr.pdf index 48a07d7..1b58dc4 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp new file mode 100644 index 0000000..e0e56ef --- /dev/null +++ b/test/datastructures/dynamicConvexHull.cpp @@ -0,0 +1,72 @@ +#include "../util.h" +namespace dch { + constexpr ll INF = LL::INF; + #include +} + +struct Line { + ll m, c; + Line(ll m_, ll c_) : m(m_), c(c_) {} + ll operator()(ll x) {return m*x+c;} +}; + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(1, 100); + + vector naive; + + dch::HullDynamic hd; + for (int i = 0; i < n; i++) { + ll m = Random::integer(-range, range); + ll c = Random::integer(-range, range); + hd.add(m, c); + naive.emplace_back(m, c); + + for (int j = 0; j < 100; j++) { + ll x = Random::integer(-range, range); + + ll got = hd.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = max(expected, l(x)); + + if (got != expected) { + for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; + cerr << x << ": " << got << " " << expected << endl; + } + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + dch::HullDynamic hd; + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer(-1'000'000'000, 1'000'000'000); + ll c = Random::integer(-1'000'000'000, 1'000'000'000); + ll x = Random::integer(-1'000'000'000, 1'000'000'000); + + t.start(); + hd.add(m, c); + hash += hd.query(x); + t.stop(); + } + if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(100); + stress_test(1'000); + stress_test(1'000'000); + performance_test(); +} diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0d4e10d..4dafbd4 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -23,7 +23,7 @@ void stress_test(ll range) { MCH mch; for (ll m : ms) { - ll c = Random::integer(-1000, 1000); + ll c = Random::integer(-range, range); mch.add(m, c); naive.emplace_back(m, c); @@ -34,11 +34,6 @@ void stress_test(ll range) { ll expected = naive[0](x); for (auto l : naive) expected = min(expected, l(x)); - if (got != expected) { - for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; - cerr << x << ": " << got << " " << expected << endl; - } - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries++; } -- cgit v1.2.3 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/datastructures/dynamicConvexHull.cpp | 2 +- content/datastructures/lazyPropagation.cpp | 2 +- content/datastructures/lichao.cpp | 4 ++-- content/geometry/hpi.cpp | 2 +- content/other/divideAndConquer.cpp | 4 ++-- content/other/knuth.cpp | 2 +- tcr.pdf | Bin 691129 -> 691160 bytes test/datastructures/dynamicConvexHull.lichao.cpp | 1 - test/datastructures/lazyPropagation.cpp | 2 +- test/datastructures/lichao.cpp | 4 ++-- test/other/divideAndConquer.cpp | 8 ++++---- test/other/knuth.cpp | 8 ++++---- 12 files changed, 19 insertions(+), 20 deletions(-) (limited to 'content') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index dfcfe0b..27ec898 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -5,7 +5,7 @@ struct Line { }; struct HullDynamic : multiset> { // max über Geraden - // (for doubles, use inf = 1/.0, div(a,b) = a/b) + // (for doubles, use INF = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} bool isect(iterator x, iterator y) { diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp index 441590e..ab91364 100644 --- a/content/datastructures/lazyPropagation.cpp +++ b/content/datastructures/lazyPropagation.cpp @@ -2,7 +2,7 @@ struct SegTree { using T = ll; using U = ll; int n; static constexpr T E = 0; // Neutral element for combine - static constexpr U UF = inf; // Unused value by updates + static constexpr U UF = INF; // Unused value by updates vector tree; int h; vector lazy; diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index 646ad68..1318ca7 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -8,7 +8,7 @@ struct Fun { // Default: Linear function. Change as needed. // Default: Computes min. Change lines with comment for max. struct Lichao { - static constexpr Fun id = {0, inf}; // {0, -inf} + static constexpr Fun id = {0, INF}; // {0, -INF} int n, cap; vector seg; Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {} @@ -36,7 +36,7 @@ struct Lichao { } ll _query(int x) { - ll ans = inf; // -inf + ll ans = INF; // -INF for (int i = x + cap; i > 0; i /= 2) { ans = min(ans, seg[i](x)); // max } diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index 3509e0e..bd3ab1e 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,4 +1,4 @@ -constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP +constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} 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]; diff --git a/tcr.pdf b/tcr.pdf index 1b58dc4..649aa24 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp index 6ab55f0..d50ca60 100644 --- a/test/datastructures/dynamicConvexHull.lichao.cpp +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -1,6 +1,5 @@ #include "../util.h" constexpr ll INF = LL::INF; -constexpr ll inf = LL::INF; #include #include diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index 7002061..feb07f0 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include constexpr int N = 1000'000; diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index c8a56a3..f4b797b 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include void stress_test(ll range) { @@ -9,7 +9,7 @@ void stress_test(ll range) { xs = Random::distinct(n, -range, range); sort(all(xs)); - vector naive(n, inf); + vector naive(n, INF); Lichao tree; for (int operations = 0; operations < 1000; operations++) { diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp index a6fda9d..6d1b444 100644 --- a/test/other/divideAndConquer.cpp +++ b/test/other/divideAndConquer.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include vector> gen(int n) { @@ -43,7 +43,7 @@ vector> genQuick(int n) { } /*ll naive(int n, int m) { - vector> state(m+1, vector(n+1, inf)); + vector> state(m+1, vector(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector> genQuick(int n) { }*/ vector naive(int n) { - vector> state(n+1, vector(n+1, inf)); + vector> state(n+1, vector(n+1, INF)); state[0][0] = 0; - vector res(n+1, inf); + vector res(n+1, INF); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= j; k++) { diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp index d469ceb..3462c0a 100644 --- a/test/other/knuth.cpp +++ b/test/other/knuth.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll iINFnf = LL::INF; #include vector> gen(int n) { @@ -43,7 +43,7 @@ vector> genQuick(int n) { } /*ll naive(int n, int m, const vector>& C) { - vector> state(m+1, vector(n+1, inf)); + vector> state(m+1, vector(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector> genQuick(int n) { }*/ vector naive(int n, const vector>& C) { - vector> state(n+1, vector(n+1, inf)); + vector> state(n+1, vector(n+1, INF)); state[0][0] = 0; - vector res(n+1, inf); + vector res(n+1, INF); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= j; k++) { -- cgit v1.2.3 From 4fae4bbe35af1eb349623123dc8f7e5f40f772e2 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 10 Aug 2024 13:43:41 +0200 Subject: more tests --- content/math/transforms/seriesOperations.cpp | 2 +- test/math/transforms/seriesOperations.cpp | 145 +++++++++++++++++++++++++++ 2 files changed, 146 insertions(+), 1 deletion(-) create mode 100644 test/math/transforms/seriesOperations.cpp (limited to 'content') diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index 4743674..fc36f1e 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -4,7 +4,7 @@ vector poly_inv(const vector& a, int n) { vector a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for (int j : {0, 1}) { + for (int _ : {0, 1}) { ntt(a2); for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp new file mode 100644 index 0000000..ee30e00 --- /dev/null +++ b/test/math/transforms/seriesOperations.cpp @@ -0,0 +1,145 @@ +#include "../../util.h" +#include +#include +#include +#pragma GCC diagnostic ignored "-Wunused-variable" +#include + +namespace reference {//checked against yosupo + vector poly_inv(vector a, int n){ + vector q = {powMod(a[0], mod-2, mod)}; + for(int len = 1; len < n; len *= 2){ + vector a2 = a, q2 = q; + a2.resize(2*len), q2.resize(2*len); + ntt(q2); + for(int j = 0; j < 2; j++){ + ntt(a2); + for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod; + ntt(a2, true); + for(int i = 0; i < len; i++) a2[i] = 0; + } + for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod); + } + return q; + } + + vector poly_deriv(vector a){ + for(int i = 0; i < sz(a)-1; i++) + a[i] = a[i+1] * (i+1) % mod; + a.pop_back(); + return a; + } + + vector poly_integr(vector a){ + if(a.empty()) return {0}; + a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); + for(int i = sz(a)-2; i > 0; i--) + a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; + a[0] = 0; + return a; + } + + vector poly_log(vector a, int n){ + a = mul(poly_deriv(a), poly_inv(a, n)); + a.resize(n-1); + a = poly_integr(a); + return a; + } + + vector poly_exp(vector a, int n){ + vector q = {1}; + for(int len = 1; len < n; len *= 2){ + vector p = poly_log(q, 2*len); + for(int i = 0; i < 2*len; i++) + p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + vector q2 = q; + q2.resize(2*len); + ntt(p), ntt(q2); + for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + ntt(p, true); + for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + } + return q; + } +} + +void test_inv() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + vector a = Random::integers(n, 0, mod); + + auto got = poly_inv(a, m); + auto expected = reference::poly_inv(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested inv: " << queries << endl; +} + +void test_deriv() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer(1, 100); + vector a = Random::integers(n, 0, mod); + + auto got = poly_deriv(a); + auto expected = reference::poly_deriv(a); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested deriv: " << queries << endl; +} + +void test_integr() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer(1, 100); + vector a = Random::integers(n, 0, mod); + + auto got = poly_deriv(a); + auto expected = reference::poly_deriv(a); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested integr: " << queries << endl; +} + +void test_log() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + vector a = Random::integers(n, 0, mod); + + auto got = poly_log(a, m); + auto expected = reference::poly_log(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested log: " << queries << endl; +} + +void test_exp() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + vector a = Random::integers(n, 0, mod); + + auto got = poly_exp(a, m); + auto expected = reference::poly_exp(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested exp: " << queries << endl; +} + +int main() { + test_inv(); + test_deriv(); + test_integr(); + test_log(); + test_exp(); +} -- cgit v1.2.3 From fdb4d0c1b54c0987367069d57a0ee56d30243431 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 10 Aug 2024 21:29:15 +0200 Subject: more tests --- content/geometry/formulas3d.cpp | 16 +-- test/geometry/formulas3d.cpp | 236 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 244 insertions(+), 8 deletions(-) create mode 100644 test/geometry/formulas3d.cpp (limited to 'content') diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp index dee3ce8..63de2ce 100644 --- a/content/geometry/formulas3d.cpp +++ b/content/geometry/formulas3d.cpp @@ -26,23 +26,23 @@ int ccw(pt3 a, pt3 b, pt3 c, pt3 p) { return (orien > EPS) - (orien < -EPS); } -// Entfernung von Punkt p zur Ebene a,b,c. +// Entfernung von Punkt p zur Ebene a, b, c. double distToPlane(pt3 a, pt3 b, pt3 c, pt3 p) { - pt3 n = cross(b-a, c-a); - return (abs(dot(n, p)) - dot(n, a)) / abs(n); + pt3 n = cross(b - a, c - a); + return abs(dot(n, a - p)) / abs(n); } -// Liegt p in der Ebene a,b,c? +// Liegt p in der Ebene a, b, c? bool pointOnPlane(pt3 a, pt3 b, pt3 c, pt3 p) { return ccw(a, b, c, p) == 0; } -// Schnittpunkt von der Grade a-b und der Ebene c,d,e +// Schnittpunkt von der Grade a-b und der Ebene c, d, e // die Grade darf nicht parallel zu der Ebene sein! pt3 linePlaneIntersection(pt3 a, pt3 b, pt3 c, pt3 d, pt3 e) { - pt3 n = cross(d-c, e-c); - pt3 d = b - a; - return a - d * (dot(n, a) - dot(n, c)) / dot(n, d); + pt3 n = cross(d - c, e - c); + pt3 dir = b - a; + return a + dir * dot(n, c - a) / dot(n, dir); } // Abstand zwischen der Grade a-b und c-d diff --git a/test/geometry/formulas3d.cpp b/test/geometry/formulas3d.cpp new file mode 100644 index 0000000..f6c04b7 --- /dev/null +++ b/test/geometry/formulas3d.cpp @@ -0,0 +1,236 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +struct pt3 { + double x, y, z; + pt3 operator-(const pt3 o) const { + return {x-o.x, y-o.y, z-o.z}; + } + pt3 operator+(const pt3 o) const { + return {x+o.x, y+o.y, z+o.z}; + } + + pt3 operator*(double m) const { + return {x*m, y*m, z*m}; + } + + pt3 operator/(double d) const { + return {x/d, y/d, z/d}; + } + + friend ostream& operator<<(ostream& os, pt3 p) { + return os << "(" << p.x << ", " << p.y << ", " << p.z << ")"; + } +}; + +pt3 cross(pt3 a, pt3 b); +double abs(pt3 p); +double distToLine(pt3 a, pt3 b, pt3 p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +#include + +namespace Random { + pt3 point3d(ll l, ll r) { + return { + (double)integer(l, r), + (double)integer(l, r), + (double)integer(l, r), + }; + } + + template + std::array distinct(ll l, ll r) { + std::array res = {}; + for (size_t i = 0; i < C; i++) { + bool unqiue; + do { + res[i] = point3d(l, r); + unqiue = true; + for (size_t j = 0; j < i; j++) { + unqiue &= res[j].x != res[i].x || + res[j].y != res[i].y || + res[j].z != res[i].z; + } + } while (!unqiue); + } + return res; + } +} + +void test_dot(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto q = Random::point3d(-range, range); + + auto expected = p.x*q.x + p.y*q.y + p.z*q.z; + auto got = dot(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested dot: " << queries << endl; +} + +void test_cross(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto q = Random::point3d(-range, range); + + auto expected = pt3{p.y*q.z - p.z*q.y, + p.z*q.x - p.x*q.z, + p.x*q.y - p.y*q.x}; + auto got = cross(p, q); + + if (got.x != expected.x) cerr << "error: x" << FAIL; + if (got.y != expected.y) cerr << "error: y" << FAIL; + if (got.z != expected.z) cerr << "error: z" << FAIL; + queries++; + } + cerr << "tested cross: " << queries << endl; +} + +void test_abs(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + + auto expected = sqrt(p.x*p.x + p.y*p.y + p.z*p.z); + auto got = abs(p); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested abs: " << queries << endl; +} + +void test_mixed(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point3d(-range, range); + auto b = Random::point3d(-range, range); + auto c = Random::point3d(-range, range); + + auto expected = dot(cross(a, b), c); + auto got = mixed(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested mixed: " << queries << endl; +} + +void test_ccw(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point3d(-range, range); + auto b = Random::point3d(-range, range); + auto c = Random::point3d(-range, range); + auto d = Random::point3d(-range, range); + + ll expected = mixed(b - a, c - a, d - a); + if (expected < 0) expected = -1; + if (expected > 0) expected = 1; + auto got = ccw(a, b, c, d); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested ccw: " << queries << endl; +} + +void test_distToPlane(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + auto norm = cross(a - c, b - c); + norm = norm / abs(norm); + + auto gotA = distToPlane(a, b, c, p); + auto gotB = distToPlane(a, b, c, q); + auto got = ccw(a, b, c, p) * ccw(a, b, c, q) < 0 ? gotA + gotB : abs(gotA - gotB); + + auto expected = abs(dot(norm, p - q)); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested distToPlane: " << queries << endl; +} + +void stress_pointOnPlane(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + bool expected = ccw(a, b, c, p) == 0; + bool got = pointOnPlane(a, b, c, p); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointOnPlane: " << queries << endl; +} + +void test_linePlaneIntersection(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + if (abs(dot(p - q, cross(a-c, b-c))) < 1e-6) continue; + + auto got = linePlaneIntersection(p, q, a, b, c); + + if (distToLine(p, q, got) > 1e-6) cerr << "error: 1" << FAIL; + if (distToPlane(a, b, c, got) > 1e-6) cerr << "error: 2" << FAIL; + queries++; + } + cerr << "tested linePlaneIntersection: " << queries << endl; +} + +void test_lineLineDist(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b] = Random::distinct<2>(-range, range); + + double expected = 0; + if (ccw(a, b, p, q) != 0) { + pt3 c = a + p - q; + expected = distToPlane(a, b, c, p); + } + auto got = lineLineDist(p, q, a, b); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested lineLineDist: " << queries << endl; +} + +int main() { + test_dot(100); + test_dot(1'000'000); + test_cross(100); + test_cross(1'000'000); + test_abs(100); + test_abs(1'000'000); + test_mixed(100); + test_mixed(1'000'000); + test_ccw(100); + test_ccw(1'000'000); + + test_distToPlane(100); + test_distToPlane(1'000'000); + stress_pointOnPlane(100); + stress_pointOnPlane(1'000'000); + test_linePlaneIntersection(100); + test_linePlaneIntersection(1'000);//can be far away + test_lineLineDist(100); + test_lineLineDist(1'000'000); +} -- cgit v1.2.3 From 6285c377d819cbcf1883d3496e7f7d461b29e171 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 10 Aug 2024 22:41:19 +0200 Subject: more tests --- content/geometry/lines.cpp | 16 ++--- content/geometry/linesAndSegments.cpp | 2 +- tcr.pdf | Bin 691160 -> 691136 bytes test/geometry/lines.cpp | 107 ++++++++++++++++++++++++++++++++++ test/geometry/linesAndSegments.cpp | 2 +- 5 files changed, 117 insertions(+), 10 deletions(-) create mode 100644 test/geometry/lines.cpp (limited to 'content') diff --git a/content/geometry/lines.cpp b/content/geometry/lines.cpp index 95536a4..36de1db 100644 --- a/content/geometry/lines.cpp +++ b/content/geometry/lines.cpp @@ -1,10 +1,10 @@ struct line { - double a, b, c; // ax + by + c = 0; vertikale Line: b = 0, sonst: b = 1 - line(pt p, pt q) : a(-imag(q-p)), b(real(q-p)), c(cross({b, -a},p)) {} + double a, b, c; // ax + by + c = 0; vertikale Gerade: b = 0 + line(pt p, pt q) : a(imag(p-q)), b(real(q-p)), c(cross({-b, a}, p)) {} }; -line pointsToLine(pt p1, pt p2) { - line l; +line pointsToLine(pt p1, pt p2) { // vertikale Gerade: b = 1 oder b = 0 + line l(0, 0); if (abs(real(p1 - p2)) < EPS) { l.a = 1; l.b = 0.0; l.c = -real(p1); } else { @@ -15,19 +15,19 @@ line pointsToLine(pt p1, pt p2) { return l; } -bool parallel(line l1, line l2) { +bool parallel(line l1, line l2) { // braucht b in {0, 1} return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS); } -bool same(line l1, line l2) { +bool same(line l1, line l2) { // braucht b in {0, 1} return parallel(l1, l2) && (abs(l1.c - l2.c) < EPS); } -bool intersect(line l1, line l2, pt& p) { +bool intersect(line l1, line l2, pt& res) { // braucht b in {0, 1} if (parallel(l1, l2)) return false; double y, x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b); if (abs(l1.b) > EPS) y = -(l1.a * x + l1.c); else y = -(l2.a * x + l2.c); - p = {x, y}; + res = {x, y}; return true; } diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index 1e21cba..ddab554 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -5,7 +5,7 @@ bool pointOnLine(pt a, pt b, pt p) { // Test auf Linienschnitt zwischen a-b und c-d. (nicht identisch) bool lineIntersection(pt a, pt b, pt c, pt d) { - return abs(cross(a - b, c - d)) < EPS; + return abs(cross(a - b, c - d)) > EPS; } // Berechnet den Schnittpunkt der Graden a-b und c-d. diff --git a/tcr.pdf b/tcr.pdf index 649aa24..5ebfcb9 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/geometry/lines.cpp b/test/geometry/lines.cpp new file mode 100644 index 0000000..7b1b99a --- /dev/null +++ b/test/geometry/lines.cpp @@ -0,0 +1,107 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +#undef ll +#include +#include + +#include "../geometry.h" + +void stress_pointsToLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + + line gotA(a, b); + if (real(a) != real(b)) { + gotA.a /= gotA.b; + gotA.c /= gotA.b; + gotA.b /= gotA.b; + } else { + gotA.c /= gotA.a; + gotA.a /= gotA.a; + } + line gotB = pointsToLine(a, b); + + if (!same(gotA, gotB)) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointsToLine: " << queries << endl; +} + +void stress_same(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + auto got = same(lAB, lCD); + auto expected = pointOnLine(a, b, c) && pointOnLine(a, b, d); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested same: " << queries << endl; +} + +void stress_parallel(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + auto got = parallel(lAB, lCD); + auto expected = cross(b-a, d-c) == 0; + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested parallel: " << queries << endl; +} + +void stress_intersect(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + if (same(lAB, lCD)) continue; + + pt gotPT; + auto got = intersect(lAB, lCD, gotPT); + auto expected = lineIntersection(a, b, c, d); + + if (got != expected) cerr << "error: 1" << FAIL; + if (got) { + pt expectedPt = lineIntersection2(a, b, c, d); + if (float_error(real(gotPT), real(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(imag(gotPT), imag(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL; + } + queries++; + } + cerr << "tested intersect: " << queries << endl; +} + +int main() { + stress_pointsToLine(100); + stress_pointsToLine(100'000); + stress_same(10); + stress_same(100); + stress_same(1'000'000'000);//no precision issue since this will alwas be false... + stress_parallel(10); + stress_parallel(100); + stress_parallel(1'000'000'000); + stress_intersect(100); + stress_intersect(1'000'000'000); +} diff --git a/test/geometry/linesAndSegments.cpp b/test/geometry/linesAndSegments.cpp index 233546b..a2da3ba 100644 --- a/test/geometry/linesAndSegments.cpp +++ b/test/geometry/linesAndSegments.cpp @@ -30,7 +30,7 @@ void stress_lineIntersection(ll range) { auto [c, d] = Random::line(range); if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) continue; - bool expected = ccw(0, a-b, c-d) == 0; + bool expected = ccw(0, a-b, c-d) != 0; bool got = lineIntersection(a, b, c, d); if (got != expected) cerr << "error" << FAIL; -- cgit v1.2.3 From 497dc5e137b908e694c55bdd7a18842484939e7b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 10 Aug 2024 23:38:14 +0200 Subject: more tests --- content/geometry/spheres.cpp | 30 +++++++++++++++--------------- test/geometry/spheres.cpp | 28 ++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+), 15 deletions(-) create mode 100644 test/geometry/spheres.cpp (limited to 'content') diff --git a/content/geometry/spheres.cpp b/content/geometry/spheres.cpp index ec22262..d34bca9 100644 --- a/content/geometry/spheres.cpp +++ b/content/geometry/spheres.cpp @@ -1,3 +1,16 @@ +// 3D Punkt in kartesischen Koordinaten. +struct point{ + double x, y, z; + point() {} + point(double x, double y, double z) : x(x), y(y), z(z) {} + point(double lat, double lon) { + lat *= PI / 180.0; lon *= PI / 180.0; + x = cos(lat) * sin(lon); + y = cos(lat) * cos(lon); + z = sin(lat); + } +}; + // Great Circle Distance mit Längen- und Breitengrad. double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) { @@ -11,19 +24,6 @@ double gcDist(double pLat, double pLon, } // Great Circle Distance mit kartesischen Koordinaten. -double gcDist(point p, point q) { +double gcDist(point p, point q) { // radius = 1 return acos(p.x * q.x + p.y * q.y + p.z * q.z); -} - -// 3D Punkt in kartesischen Koordinaten. -struct point{ - double x, y, z; - point() {} - point(double x, double y, double z) : x(x), y(y), z(z) {} - point(double lat, double lon) { - lat *= PI / 180.0; lon *= PI / 180.0; - x = cos(lat) * sin(lon); - y = cos(lat) * cos(lon); - z = sin(lat); - } -}; +} \ No newline at end of file diff --git a/test/geometry/spheres.cpp b/test/geometry/spheres.cpp new file mode 100644 index 0000000..16e0ebd --- /dev/null +++ b/test/geometry/spheres.cpp @@ -0,0 +1,28 @@ +#include "../util.h" +constexpr double PI = acos(-1.0); +#pragma GCC diagnostic ignored "-Wshadow" +#include + +void test_consistent() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto pLat = Random::real(-180, 180); + auto pLon = Random::real(0, 360); + auto qLat = Random::real(-180, 180); + auto qLon = Random::real(0, 360); + + point p(pLat, pLon); + point q(qLat, qLon); + + auto gotA = gcDist(pLat, pLon, qLat, qLon, 1); + auto gotB = gcDist(p, q); + + if (abs(gotA - gotB) > 1e-6) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL; + queries++; + } + cerr << "tested random: " << queries << endl; +} + +int main() { + test_consistent(); +} -- cgit v1.2.3 From 22536b7fbc050075a1420c0f1a7125b9185c9519 Mon Sep 17 00:00:00 2001 From: Yidi Date: Mon, 12 Aug 2024 13:22:34 +0200 Subject: add treap test --- content/datastructures/datastructures.tex | 2 +- content/datastructures/treap.cpp | 140 +++++++++++++++--------------- content/datastructures/treap2.cpp | 79 ----------------- test/datastructures/treap.cpp | 85 ++++++++++++++++++ 4 files changed, 156 insertions(+), 150 deletions(-) delete mode 100644 content/datastructures/treap2.cpp create mode 100644 test/datastructures/treap.cpp (limited to 'content') diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex index 40132a9..c9f3d2a 100644 --- a/content/datastructures/datastructures.tex +++ b/content/datastructures/datastructures.tex @@ -50,7 +50,7 @@ \method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)} \method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)} \end{methods} - \sourcecode{datastructures/treap2.cpp} + \sourcecode{datastructures/treap.cpp} \end{algorithm} \begin{algorithm}{Range Minimum Query} diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp index c96e36a..c5a60e9 100644 --- a/content/datastructures/treap.cpp +++ b/content/datastructures/treap.cpp @@ -1,79 +1,79 @@ -struct node { - int key, prio, left, right, size; - node(int key, int prio) : key(key), prio(prio), left(-1), - right(-1), size(1) {}; -}; +mt19937 rng(0xc4bd5dad); +struct Treap { + struct Node { + ll val; + int prio, size = 1, l = -1, r = -1; + Node(ll x) : val(x), prio(rng()) {} + }; -vector treap; + vector treap; + int root = -1; -int getSize(int root) { - return root < 0 ? 0 : treap[root].size; -} + int getSize(int v) { + return v < 0 ? 0 : treap[v].size; + } -void update(int root) { - if (root < 0) return; - treap[root].size = 1 + getSize(treap[root].left) - + getSize(treap[root].right); -} + void upd(int v) { + if (v < 0) return; + auto& V = treap[v]; + V.size = 1 + getSize(V.l) + getSize(V.r); + // Update Node Code + } -pair split(int root, int minKeyRight) { - if (root < 0) return {-1, -1}; - if (treap[root].key >= minKeyRight) { - auto leftSplit = split(treap[root].left, minKeyRight); - treap[root].left = leftSplit.second; - update(root); - leftSplit.second = root; - return leftSplit; - } else { - auto rightSplit = split(treap[root].right, minKeyRight); - treap[root].right = rightSplit.first; - update(root); - rightSplit.first = root; - return rightSplit; -}} + void push(int v) { + if (v < 0) return; + //auto& V = treap[v]; + //if (V.lazy) { + // Lazy Propagation Code + // if (V.l >= 0) treap[V.l].lazy = true; + // if (V.r >= 0) treap[V.r].lazy = true; + // V.lazy = false; + //} + } -int merge (int left, int right) { - if (left < 0) return right; - if (right < 0) return left; - if (treap[left].prio < treap[right].prio) { //min priority heap - treap[left].right = merge(treap[left].right, right); - update(left); - return left; - } else { - treap[right].left = merge(left, treap[right].left); - update(right); - return right; -}} + pair split(int v, int k) { + if (v < 0) return {-1, -1}; + auto& V = treap[v]; + push(v); + if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k) + auto [left, right] = split(V.l, k); + V.l = right; + upd(v); + return {left, v}; + } else { + // and only "k" + auto [left, right] = split(V.r, k - getSize(V.l) - 1); + V.r = left; + upd(v); + return {v, right}; + }} -//insert values with high priority first -int insert(int root, int key, int prio) { - int next = sz(treap); - treap.emplace_back(key, prio); - auto t = split(root, key); - //returns new root - return merge(merge(t.first, next), t.second); -} + int merge(int left, int right) { + if (left < 0) return right; + if (right < 0) return left; + if (treap[left].prio < treap[right].prio) { + push(left); + treap[left].r = merge(treap[left].r, right); + upd(left); + return left; + } else { + push(right); + treap[right].l = merge(left, treap[right].l); + upd(right); + return right; + }} -int remove(int root, int key) { - if (root < 0) return -1; - if (key < treap[root].key) { - treap[root].left = remove(treap[root].left, key); - update(root); - return root; - } else if (key > treap[root].key) { - treap[root].right = remove(treap[root].right, key); - update(root); - return root; - } else { //check prio? - return merge(treap[root].left, treap[root].right); -}} + void insert(int i, ll val) { // and i = val + auto [left, right] = split(root, i); + treap.emplace_back(val); + left = merge(left, sz(treap) - 1); + root = merge(left, right); + } -int kth(int root, int k) { - if (root < 0) return -1; - int leftSize = getSize(treap[root].left); - if (k < leftSize) return kth(treap[root].left, k); - else if (k > leftSize) { - return kth(treap[root].right, k - 1 - leftSize); + void remove(int i, int count = 1) { + auto [left, t_right] = split(root, i); + auto [middle, right] = split(t_right, count); + root = merge(left, right); } - return root; -} + // for query use remove and read middle BEFORE remerging +}; diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp deleted file mode 100644 index c5a60e9..0000000 --- a/content/datastructures/treap2.cpp +++ /dev/null @@ -1,79 +0,0 @@ -mt19937 rng(0xc4bd5dad); -struct Treap { - struct Node { - ll val; - int prio, size = 1, l = -1, r = -1; - Node(ll x) : val(x), prio(rng()) {} - }; - - vector treap; - int root = -1; - - int getSize(int v) { - return v < 0 ? 0 : treap[v].size; - } - - void upd(int v) { - if (v < 0) return; - auto& V = treap[v]; - V.size = 1 + getSize(V.l) + getSize(V.r); - // Update Node Code - } - - void push(int v) { - if (v < 0) return; - //auto& V = treap[v]; - //if (V.lazy) { - // Lazy Propagation Code - // if (V.l >= 0) treap[V.l].lazy = true; - // if (V.r >= 0) treap[V.r].lazy = true; - // V.lazy = false; - //} - } - - pair split(int v, int k) { - if (v < 0) return {-1, -1}; - auto& V = treap[v]; - push(v); - if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k) - auto [left, right] = split(V.l, k); - V.l = right; - upd(v); - return {left, v}; - } else { - // and only "k" - auto [left, right] = split(V.r, k - getSize(V.l) - 1); - V.r = left; - upd(v); - return {v, right}; - }} - - int merge(int left, int right) { - if (left < 0) return right; - if (right < 0) return left; - if (treap[left].prio < treap[right].prio) { - push(left); - treap[left].r = merge(treap[left].r, right); - upd(left); - return left; - } else { - push(right); - treap[right].l = merge(left, treap[right].l); - upd(right); - return right; - }} - - void insert(int i, ll val) { // and i = val - auto [left, right] = split(root, i); - treap.emplace_back(val); - left = merge(left, sz(treap) - 1); - root = merge(left, right); - } - - void remove(int i, int count = 1) { - auto [left, t_right] = split(root, i); - auto [middle, right] = split(t_right, count); - root = merge(left, right); - } - // for query use remove and read middle BEFORE remerging -}; diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp new file mode 100644 index 0000000..ebab34d --- /dev/null +++ b/test/datastructures/treap.cpp @@ -0,0 +1,85 @@ +#include "../util.h" +#include + +void add(Treap& t, vector& ans, int v) { + if (v < 0) return; + add(t, ans, t.treap[v].l); + ans.push_back(t.treap[v].val); + add(t, ans, t.treap[v].r); +} + +vector to_vec(Treap& t) { + vector ans; + add(t, ans, t.root); + return ans; +} + +void stress_test(int T, int n) { + for (int tries = 0; tries < T; tries++) { + int ins = Random::integer(1, n); + int rem = Random::integer(0, ins+1); + + vector a; + Treap t; + while (ins + rem > 0) { + bool is_ins = Random::integer(0, ins+rem) < ins; + if (a.empty()) is_ins = true; + + if (is_ins) { + int ind = Random::integer(0, (int)sz(a)+1); + ll val = Random::integer((ll)-1e18, (ll)1e18+1); + t.insert(ind, val); + a.insert(a.begin() + ind, val); + ins--; + } else { + int ind = Random::integer(0, (int)sz(a)); + int cnt = Random::integer(1, 1 + min({(int)sz(a)-ind, rem, (int)sqrt(n)})); + t.remove(ind, cnt); + a.erase(a.begin() + ind, a.begin() + ind + cnt); + rem -= cnt; + } + } + if (to_vec(t) != a) cerr << "Failed stress test" << endl; + } + cerr << "Tested " << T << " random tests with n<=" << n << endl; +} + +constexpr int N = 200'000; +void performance_test() { + timer t; + + t.start(); + Treap tr; + t.stop(); + + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + int ind = Random::integer(0, operations+1); + ll val = Random::integer((ll)-1e18, (ll)1e18+1); + + t.start(); + tr.insert(ind, val); + hash ^= tr.root; + t.stop(); + } + while (tr.root != -1) { + t.start(); + int sz = tr.getSize(tr.root); + t.stop(); + + int ind = Random::integer(0, sz); + int cnt = Random::integer(1, 1 + min(sz-ind, 10)); + t.start(); + tr.remove(ind, cnt); + t.stop(); + } + if (t.time > 1000) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(10000, 10); + stress_test(1000, 100); + stress_test(100, 10000); + performance_test(); +} -- cgit v1.2.3 From f33aca8fca567c9f318bdd120f20765414ecdf0d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 13 Aug 2024 01:51:19 +0200 Subject: change style --- content/datastructures/persistent.cpp | 2 +- content/graph/virtualTree.cpp | 6 +++--- tcr.pdf | Bin 691136 -> 691284 bytes 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'content') diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp index 7d15342..f26680d 100644 --- a/content/datastructures/persistent.cpp +++ b/content/datastructures/persistent.cpp @@ -7,7 +7,7 @@ struct persistent { : time(time), data(1, {2*time, value}) {} T get(int t) { - return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second; + return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second; } int set(T value) { diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 27d2d6c..6233b27 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -3,13 +3,13 @@ vector in, out; void virtualTree(vector ind) { // indices of used nodes sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i = 0, n = sz(ind); i < n - 1; i++) { - ind.push_back(lca(ind[i], ind[i + 1])); + for (int i = 1, n = sz(ind); i < n; i++) { + ind.push_back(lca(ind[i - 1], ind[i])); } sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); ind.erase(unique(all(ind)), ind.end()); - int n = ind.size(); + int n = sz(ind); vector> tree(n); vector st = {0}; for (int i = 1; i < n; i++) { diff --git a/tcr.pdf b/tcr.pdf index 5ebfcb9..b096438 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From f32a00178f0d3b2152a6fc1dc492c987aaede85f Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 13 Aug 2024 17:14:17 +0200 Subject: small improvements --- content/datastructures/dynamicConvexHull.cpp | 16 ++++++++-------- content/datastructures/pbds.cpp | 4 ++-- content/geometry/convexHull.cpp | 4 ++-- content/geometry/hpi.cpp | 2 +- content/graph/bitonicTSP.cpp | 2 +- content/graph/bitonicTSPsimple.cpp | 2 +- content/graph/pushRelabel.cpp | 2 +- tcr.pdf | Bin 691284 -> 691101 bytes test/datastructures/fenwickTree2.cpp | 2 +- test/geometry/delaunay.cpp | 6 +++--- test/math/gauss.cpp | 2 +- test/math/inversionsMerge.cpp | 2 +- 12 files changed, 22 insertions(+), 22 deletions(-) (limited to 'content') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 27ec898..abae1d7 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,22 +1,22 @@ struct Line { - mutable ll m, b, p; + mutable ll m, c, p; bool operator<(const Line& o) const {return m < o.m;} bool operator<(ll x) const {return p < x;} }; struct HullDynamic : multiset> { // max über Geraden - // (for doubles, use INF = 1/.0, div(a,b) = a/b) - ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} + // (for doubles, use INF = 1/.0, div(a,c) = a/c) + ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} - if (x->m == y->m) x->p = x->b > y->b ? INF : -INF; - else x->p = div(y->b - x->b, x->m - y->m); + if (x->m == y->m) x->p = x->c > y->c ? INF : -INF; + else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; } - void add(ll m, ll b) { - auto x = insert({m, b, 0}); + void add(ll m, ll c) { + auto x = insert({m, c, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { x--; @@ -31,6 +31,6 @@ struct HullDynamic : multiset> { // max über Geraden ll query(ll x) { auto l = *lower_bound(x); - return l.m * x + l.b; + return l.m * x + l.c; } }; diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp index f0889a2..de0ace6 100644 --- a/content/datastructures/pbds.cpp +++ b/content/datastructures/pbds.cpp @@ -6,11 +6,11 @@ using Tree = tree, rb_tree_tag, // T.order_of_key(x): number of elements strictly less than x // *T.find_by_order(k): k-th element +constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd template struct chash { - static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd size_t operator()(T o) const { - return __builtin_bswap64(hash()(o) * C); + return __builtin_bswap64(hash()(o) * RNG); }}; template using hashMap = gp_hash_table>; diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 6d89e05..1173924 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -11,8 +11,8 @@ vector convexHull(vector pts){ while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--; h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index bd3ab1e..c58a6e7 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,4 +1,4 @@ -constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP +constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index 6470232..eee5082 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -27,5 +27,5 @@ auto bitonicTSP() { (lt.back() == 1 ? lt : ut).push_back(0); reverse(all(lt)); lt.insert(lt.end(), all(ut)); - return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp index 8b6e6c5..cacfb9c 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -23,5 +23,5 @@ auto bitonicTSP() { rl.push_back(v); p2 = v; }} lr.insert(lr.end(), rl.rbegin(), rl.rend()); - return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index 73a9eae..ec36026 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -29,7 +29,7 @@ ll maxFlow(int s, int t) { cur.assign(n, 0); H.assign(n, 0); H[s] = n; - ec[t] = 1;//never set t to active... + ec[t] = 1; //never set t to active... vector co(2*n); co[0] = n - 1; for (Edge& e : adj[s]) addFlow(e, e.c); diff --git a/tcr.pdf b/tcr.pdf index b096438..57691c5 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index aa99576..89d5b0f 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -9,7 +9,7 @@ void stress_test() { ll queries = 0; for (int tries = 0; tries < 100; tries++) { int n = Random::integer(10, 100); - vector naive(n);// = Random::integers(n, -1000, 1000); + vector naive = Random::integers(n, -1000, 1000); init(naive); for (int operations = 0; operations < 1000; operations++) { { diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index 7f8ec30..5740b95 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -16,11 +16,11 @@ vector convexHull(vector pts){ vector h(2 * sz(pts)); auto half = [&](auto begin, auto end, int t) { for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points! + while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points! h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index 37bacce..6e4759d 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -14,7 +14,7 @@ vector> inverseMat(const vector>& m) { mat[i].resize(2*n); mat[i][n+i] = 1; } - gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs... + gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs... vector> res(m); for (int i = 0; i < n; i++) { res[i] = vector(mat[i].begin() + n, mat[i].end()); diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 85ab0d2..acdc555 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -16,7 +16,7 @@ void stress_test() { for (ll i = 0; i < 100'000; i++) { int n = Random::integer(1, 100); vector v(n); - for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer(0, 10000);//values must be unique ): + for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer(0, 10000); //values must be unique ): shuffle(all(v), Random::rng); ll expected = naive(v); ll got = mergeSort(v); -- cgit v1.2.3 From 39190436d167414b5853730e91a173fa2affea6a Mon Sep 17 00:00:00 2001 From: MZuenni Date: Tue, 13 Aug 2024 17:15:57 +0200 Subject: small improvements --- content/datastructures/dynamicConvexHull.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index abae1d7..63e0e13 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -6,7 +6,7 @@ struct Line { struct HullDynamic : multiset> { // max über Geraden // (for doubles, use INF = 1/.0, div(a,c) = a/c) - ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);} + ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} -- cgit v1.2.3 From 915bbaea690d3d352b06d5a2660166de7fd9cd21 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 17 Aug 2024 20:07:14 +0200 Subject: improve series operations --- content/math/transforms/seriesOperations.cpp | 14 ++++++++------ tcr.pdf | Bin 691101 -> 691092 bytes 2 files changed, 8 insertions(+), 6 deletions(-) (limited to 'content') diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index fc36f1e..b405698 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -24,10 +24,13 @@ vector poly_deriv(vector a) { } vector poly_integr(vector a) { - if (a.empty()) return {0}; - a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for (int i = sz(a)-2; i > 0; i--) - a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; + static vector inv = {0, 1}; + for (static int i = 2; i <= sz(a); i++) + inv.push_back(mod - mod / i * inv[mod % i] % mod); + + a.push_back(0); + for (int i = sz(a) - 1; i > 0; i--) + a[i] = a[i-1] * inv[i] % mod; a[0] = 0; return a; } @@ -35,8 +38,7 @@ vector poly_integr(vector a) { vector poly_log(vector a, int n) { a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); - a = poly_integr(a); - return a; + return poly_integr(a); } vector poly_exp(vector a, int n) { diff --git a/tcr.pdf b/tcr.pdf index 57691c5..d107dab 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 17 Aug 2024 20:30:08 +0200 Subject: improved monotonic onvex hull --- content/datastructures/monotonicConvexHull.cpp | 4 +-- tcr.pdf | Bin 691092 -> 691111 bytes test/datastructures/monotonicConvexHull.cpp | 41 ++++++++++++++++++++----- 3 files changed, 35 insertions(+), 10 deletions(-) (limited to 'content') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index e84ad86..f1721ae 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,5 +1,5 @@ // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. +// Gerade hat kleineres pair(m, c) als alle vorherigen. struct Line { ll m, c; ll operator()(ll x) {return m*x+c;} @@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert +ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); diff --git a/tcr.pdf b/tcr.pdf index d107dab..199c3de 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 9edfb4b..0415068 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -13,17 +13,30 @@ void stress_test(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); - auto ms = Random::distinct(n, -range, range); + auto ms = Random::integers(n, -range, range); sort(all(ms), greater<>{}); - auto xs = Random::distinct(n*100, -range*n, range*n); + auto cs = ms; + for (int l = 0, r = 0; l < n;) { + while (r < n && ms[l] == ms[r]) r++; + auto tmp = Random::distinct(r - l, -range, range); + sort(all(tmp), greater<>{}); + for (int c : tmp) { + cs[l] = c; + l++; + } + } + + auto xs = Random::integers(n*100, -range*n, range*n); sort(all(xs)); int i = 0; vector naive; MCH mch; - for (ll m : ms) { - ll c = Random::integer(-range, range); + for (int k = 0; k < n; k++) { + ll m = ms[k]; + ll c = cs[k]; + mch.add(m, c); naive.emplace_back(m, c); @@ -46,18 +59,30 @@ void stress_test_independent(ll range) { ll queries = 0; for (int tries = 0; tries < 1000; tries++) { int n = Random::integer(1, 100); - auto ms = Random::distinct(n, -range, range); + auto ms = Random::integers(n, -range, range); sort(all(ms), greater<>{}); + auto cs = ms; + for (int l = 0, r = 0; l < n;) { + while (r < n && ms[l] == ms[r]) r++; + auto tmp = Random::distinct(r - l, -range, range); + sort(all(tmp), greater<>{}); + for (int c : tmp) { + cs[l] = c; + l++; + } + } vector naive; MCH mch; - for (ll m : ms) { - ll c = Random::integer(-range, range); + for (int i = 0; i < n; i++) { + ll m = ms[i]; + ll c = cs[i]; + mch.add(m, c); naive.emplace_back(m, c); - auto xs = Random::distinct(100, -range, range); + auto xs = Random::integers(100, -range, range); sort(all(xs)); auto tmp = mch; -- cgit v1.2.3 From e1803aee4e150088b0865954de476edf182a9ffe Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 22 Aug 2024 22:20:14 +0200 Subject: improve segmentIntersection --- content/geometry/segmentIntersection.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index 4262ddc..acce7cc 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -18,8 +18,8 @@ struct event { int id, type; bool operator<(const event& o) const { if (real(p) != real(o.p)) return real(p) < real(o.p); - if (type != o.type) return type > o.type; - return imag(p) < imag(o.p); + if (imag(p) != imag(o.p)) return imag(p) < imag(o.p); + return type > o.type; } }; -- cgit v1.2.3 From 961706d93af4daf58d5991deea88981a01f962b0 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 23 Aug 2024 21:36:51 +0200 Subject: more stuff --- content/geometry/segmentIntersection.cpp | 2 +- content/graph/dinic.cpp | 55 +++++++++++++++++++++++++++ content/string/duval.cpp | 8 ++-- tcr.pdf | Bin 691111 -> 691029 bytes test/graph/dinic.cpp | 62 +++++++++++++++++++++++++++++++ 5 files changed, 121 insertions(+), 6 deletions(-) create mode 100644 content/graph/dinic.cpp create mode 100644 test/graph/dinic.cpp (limited to 'content') diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index acce7cc..afc01b2 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) { } bool intersect(const seg& a, const seg& b) { - return lineSegmentIntersection(a.a, a.b, b.a, b.b); + return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@ } pair intersect(vector& segs) { diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp new file mode 100644 index 0000000..2e58a2d --- /dev/null +++ b/content/graph/dinic.cpp @@ -0,0 +1,55 @@ +struct Edge { + int to, rev; + ll f, c; +}; + +vector> adj; +int s, t; +vector pt, dist; + +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)sz(adj[v]), 0, c}); + adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); +} + +bool bfs() { + dist.assign(sz(adj), -1); + dist[s] = 0; + queue q({s}); + while (!q.empty() && dist[t] < 0) { + int v = q.front(); q.pop(); + for (Edge& e : adj[v]) { + if (dist[e.to] < 0 && e.c - e.f > 0) { + dist[e.to] = dist[v] + 1; + q.push(e.to); + }}} + return dist[t] >= 0; +} + +ll dfs(int v, ll flow = INF) { + if (v == t || flow == 0) return flow; + for (; pt[v] < sz(adj[v]); pt[v]++) { + Edge& e = adj[v][pt[v]]; + if (dist[e.to] != dist[v] + 1) continue; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; + }} + return 0; +} + +ll maxFlow(int source, int target) { + s = source, t = target; + ll flow = 0; + while (bfs()) { + pt.assign(sz(adj), 0); + ll cur; + do { + cur = dfs(s); + flow += cur; + } while (cur > 0); + } + return flow; +} diff --git a/content/string/duval.cpp b/content/string/duval.cpp index bf36cce..253bae1 100644 --- a/content/string/duval.cpp +++ b/content/string/duval.cpp @@ -6,9 +6,8 @@ vector> duval(const string& s) { if (s[k] < s[j]) k = i; else k++; } - while (i <= k) { + for (; i <= k; i += j - k) { res.push_back({i, i + j - k}); - i += j - k; }} return res; } @@ -16,6 +15,5 @@ vector> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); for (auto [l, r] : parts) { - if (l < sz(s) && r >= sz(s)) { - return l; -}}} + if (r >= sz(s)) return l; +}} diff --git a/tcr.pdf b/tcr.pdf index 199c3de..2f24510 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp new file mode 100644 index 0000000..5af7c6f --- /dev/null +++ b/test/graph/dinic.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +namespace dinic { +#include +} + +namespace pushRelabel { +#include +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer(2, 30); + int m = Random::integer(n-1, max(n, min(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer(1, 1'000'000'000'000ll); + dinic::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = dinic::maxFlow(0, n - 1); + ll expected = pushRelabel::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace dinic; + timer t; + Graph g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer(1, 1'000'000'000'000ll); + ll w2 = Random::integer(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + t.stop(); + if (t.time > 2000) 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 00b01a954304e50904de97b25639c535e16f259e Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 25 Aug 2024 19:43:11 +0200 Subject: no spaces --- content/math/shortModInv.cpp | 2 +- content/template/template.cpp | 4 ++-- content/tests/gcc5bug.cpp | 2 +- 3 files changed, 4 insertions(+), 4 deletions(-) (limited to 'content') diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp index f696cce..cf91ca0 100644 --- a/content/math/shortModInv.cpp +++ b/content/math/shortModInv.cpp @@ -1,3 +1,3 @@ ll multInv(ll x, ll m) { // x^{-1} mod m - return 1 < x ? m - multInv(m % x, x) * m / x : 1; + return 1 < x ? m - multInv(m % x, x) * m / x : 1; } diff --git a/content/template/template.cpp b/content/template/template.cpp index c9a492c..7430d23 100644 --- a/content/template/template.cpp +++ b/content/template/template.cpp @@ -7,9 +7,9 @@ using namespace std; using ll = long long; using ld = long double; - + void solve() {} - + int main() { cin.tie(0)->sync_with_stdio(false); cout << setprecision(16); diff --git a/content/tests/gcc5bug.cpp b/content/tests/gcc5bug.cpp index f49603e..6aaeea9 100644 --- a/content/tests/gcc5bug.cpp +++ b/content/tests/gcc5bug.cpp @@ -1,4 +1,4 @@ //https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68203 struct A { - pair values[1000000]; + pair values[1000000]; }; -- cgit v1.2.3 From 28d701cc11a510f1d5102490d93eb681e1ac31a5 Mon Sep 17 00:00:00 2001 From: florian Date: Thu, 29 Aug 2024 17:01:39 +0200 Subject: shorter rerooting (tested on https://codeforces.com/gym/532576/submission/278656979) --- content/graph/reroot.cpp | 99 ++++++++++++++++++++---------------------------- 1 file changed, 42 insertions(+), 57 deletions(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 4c6a748..59fea94 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -1,62 +1,47 @@ -// Usual Tree DP can be broken down in 4 steps: -// - Initialize dp[v] = identity -// - Iterate over all children w and take a value for w -// by looking at dp[w] and possibly the edge label of v -> w -// - combine the values of those children -// usually this operation should be commutative and associative -// - finalize the dp[v] after iterating over all children +// input: undirected (un)weighted tree as +// adjacency list containing pairs +// (To remove weights, remove every "w" and fix errors) +// output[r] = dp[r], where dp[v] := +// fin(Sum_{child c of v, regarding root r} from_child( dp[c] )) struct Reroot { - using T = ll; + using D = todo; // dp value + using A = todo (often D); // value from a vertex's child(ren) + // (A,agg,e) commutative monoid - // identity element - T E() {} - // x: dp value of child - // e: index of edge going to child - T takeChild(T x, int e) {} - T comb(T x, T y) {} - // called after combining all dp values of children - T fin(T x, int v) {} + A e = todo; + A from_child(z v, z c, auto w, D dp_c) { todo } + static A agg(A a, A b) { todo } + D fin(z v, A chils_agg) { todo } - vector>> g; - vector ord, pae; - vector dp; + vector dp; - T dfs(int v) { - ord.push_back(v); - for (auto [w, e] : g[v]) { - g[w].erase(find(all(g[w]), pair(v, e^1))); - pae[w] = e^1; - dp[v] = comb(dp[v], takeChild(dfs(w), e)); - } - return dp[v] = fin(dp[v], v); - } + D dfs0(z v, z p, auto& g) { + A ca = e; + for (auto [c, w] : g[v]) if(c-p) { + ca = agg(ca, from_child(v, c, w, dfs0(c, v, g))); + } + return dp[v] = fin(v, ca); + } + void dfs1(z v, z p, auto& g) { + vector ps = {e}; + for (auto [c, w] : g[v]) { + ps.push_back(from_child(v, c, w, dp[c])); + } + auto ss = ps; + exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg); + exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg); + z i = 0; + for (auto [c, w] : g[v]) if(++i, c-p) { + dp[v] = fin(v, agg(ss[i], ps[i])); + dfs1(c, v, g); + } + dp[v] = fin(v, ss[0]); + } - vector solve(int n, vector> edges) { - g.resize(n); - for (int i = 0; i < n-1; i++) { - g[edges[i].first].emplace_back(edges[i].second, 2*i); - g[edges[i].second].emplace_back(edges[i].first, 2*i+1); - } - pae.assign(n, -1); - dp.assign(n, E()); - dfs(0); - vector updp(n, E()), res(n, E()); - for (int v : ord) { - vector pref(sz(g[v])+1), suff(sz(g[v])+1); - if (v != 0) pref[0] = takeChild(updp[v], pae[v]); - for (int i = 0; i < sz(g[v]); i++){ - auto [u, w] = g[v][i]; - pref[i+1] = suff[i] = takeChild(dp[u], w); - pref[i+1] = comb(pref[i], pref[i+1]); - } - for (int i = sz(g[v])-1; i >= 0; i--) { - suff[i] = comb(suff[i], suff[i+1]); - } - for (int i = 0; i < sz(g[v]); i++) { - updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); - } - res[v] = fin(pref.back(), v); - } - return res; - } -}; + auto solve(auto g) { + dp.resize(sz(g)); + dfs0(0, 0, g); + dfs1(0, 0, g); + return dp; + } +}; \ No newline at end of file -- cgit v1.2.3 From 3328e0fd09ce1cca46ade4a492edff92a3edb8ac Mon Sep 17 00:00:00 2001 From: florian Date: Thu, 29 Aug 2024 17:25:34 +0200 Subject: code style --- content/graph/reroot.cpp | 44 ++++++++++++++++++++++++-------------------- 1 file changed, 24 insertions(+), 20 deletions(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 59fea94..6c9551e 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -1,47 +1,51 @@ -// input: undirected (un)weighted tree as -// adjacency list containing pairs -// (To remove weights, remove every "w" and fix errors) // output[r] = dp[r], where dp[v] := -// fin(Sum_{child c of v, regarding root r} from_child( dp[c] )) +// fin(Sum_{child c of v, regarding root r} fromChild( dp[c] )) + +// To remove weights, remove every "w" and "W" and fix errors struct Reroot { - using D = todo; // dp value - using A = todo (often D); // value from a vertex's child(ren) + using D = /todo/; // dp value + using A = /todo/ (often D); // value from a vertex's child(ren) // (A,agg,e) commutative monoid - A e = todo; - A from_child(z v, z c, auto w, D dp_c) { todo } - static A agg(A a, A b) { todo } - D fin(z v, A chils_agg) { todo } + A e = /todo/; + A fromChild(int v, int c, auto w, D dp_c) { /todo/ } + static A agg(A a, A b) { /todo/ } + D fin(int v, A chilsAgg) { /todo/ } vector dp; - D dfs0(z v, z p, auto& g) { + D dfs0(auto& g, int v, int from = -1) { A ca = e; - for (auto [c, w] : g[v]) if(c-p) { - ca = agg(ca, from_child(v, c, w, dfs0(c, v, g))); + for (auto [c, w] : g[v]) { + if (c == from) continue; + ca = agg(ca, fromChild(v, c, w, dfs0(c, v, g))); } return dp[v] = fin(v, ca); } - void dfs1(z v, z p, auto& g) { + + void dfs1(auto& g, int v, int from = -1) { vector ps = {e}; for (auto [c, w] : g[v]) { - ps.push_back(from_child(v, c, w, dp[c])); + ps.push_back(fromChild(v, c, w, dp[c])); } auto ss = ps; exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg); exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg); - z i = 0; - for (auto [c, w] : g[v]) if(++i, c-p) { + int i = 0; + for (auto [c, w] : g[v]) { + ++i; + if (c == from) continue; dp[v] = fin(v, agg(ss[i], ps[i])); dfs1(c, v, g); } dp[v] = fin(v, ss[0]); } - auto solve(auto g) { + template + auto solve(vector>> g) { dp.resize(sz(g)); - dfs0(0, 0, g); - dfs1(0, 0, g); + dfs0(g, 0); + dfs1(g, 0); return dp; } }; \ No newline at end of file -- cgit v1.2.3 From 4d8f28ec2dceff1eed72c86463235407dc23d42b Mon Sep 17 00:00:00 2001 From: florian Date: Thu, 29 Aug 2024 17:34:18 +0200 Subject: be --- content/graph/reroot.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 6c9551e..f908d52 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -29,8 +29,8 @@ struct Reroot { ps.push_back(fromChild(v, c, w, dp[c])); } auto ss = ps; - exclusive_scan(ps.begin(), ps.end(), ps.begin(), e, agg); - exclusive_scan(ss.rbegin(),ss.rend(),ss.rbegin(),e, agg); + exclusive_scan(be(ps), ps.begin(), e, agg); + exclusive_scan(ss.rbegin(), ss.rend(), ss.rbegin(), e, agg); int i = 0; for (auto [c, w] : g[v]) { ++i; -- cgit v1.2.3 From 8ba51e146ad9805f3e2c7e1698a9e604f1dd2379 Mon Sep 17 00:00:00 2001 From: florian Date: Thu, 29 Aug 2024 17:39:06 +0200 Subject: todos --- content/graph/reroot.cpp | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index f908d52..b3571f1 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -3,14 +3,14 @@ // To remove weights, remove every "w" and "W" and fix errors struct Reroot { - using D = /todo/; // dp value - using A = /todo/ (often D); // value from a vertex's child(ren) - // (A,agg,e) commutative monoid + using D = /*todo*/; // dp value + using A = /*todo(often D)*/; //value from a vertex's child(ren) + //(A,agg,e) commutative monoid - A e = /todo/; - A fromChild(int v, int c, auto w, D dp_c) { /todo/ } - static A agg(A a, A b) { /todo/ } - D fin(int v, A chilsAgg) { /todo/ } + A e = /*todo*/; + A fromChild(int v, int c, auto w, D dp_c) { /*todo*/ } + static A agg(A a, A b) { /*todo*/ } + D fin(int v, A chilsAgg) { /*todo*/ } vector dp; -- 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') 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') 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') 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 96f899b7350fe05232d906478e9ca9d26f558969 Mon Sep 17 00:00:00 2001 From: Yidi Date: Mon, 2 Sep 2024 16:35:15 +0200 Subject: fix style --- content/graph/reroot.cpp | 85 +++++++++++++++++++++++------------------------- 1 file changed, 41 insertions(+), 44 deletions(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index b3571f1..cd63b3d 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -1,51 +1,48 @@ -// output[r] = dp[r], where dp[v] := -// fin(Sum_{child c of v, regarding root r} fromChild( dp[c] )) +using W = ll; // edge weight type +vector>> adj; -// To remove weights, remove every "w" and "W" and fix errors struct Reroot { - using D = /*todo*/; // dp value - using A = /*todo(often D)*/; //value from a vertex's child(ren) - //(A,agg,e) commutative monoid + using T = ll; // dp type - A e = /*todo*/; - A fromChild(int v, int c, auto w, D dp_c) { /*todo*/ } - static A agg(A a, A b) { /*todo*/ } - D fin(int v, A chilsAgg) { /*todo*/ } + static constexpr T E = 0; // neutral element + T takeChild(int v, int c, W w, T x) {} // move child along edge + static T comb(T x, T y) {} + T fin(int v, T x) {} // add v to own dp value x - vector dp; + vector dp; - D dfs0(auto& g, int v, int from = -1) { - A ca = e; - for (auto [c, w] : g[v]) { - if (c == from) continue; - ca = agg(ca, fromChild(v, c, w, dfs0(c, v, g))); - } - return dp[v] = fin(v, ca); - } + T dfs0(int v, int from = -1) { + T val = E; + for (auto& [u, w] : adj[v]) { + if (u == from) continue; + val = comb(val, takeChild(v, u, w, dfs0(u, v))); + } + return dp[v] = fin(v, val); + } - void dfs1(auto& g, int v, int from = -1) { - vector ps = {e}; - for (auto [c, w] : g[v]) { - ps.push_back(fromChild(v, c, w, dp[c])); - } - auto ss = ps; - exclusive_scan(be(ps), ps.begin(), e, agg); - exclusive_scan(ss.rbegin(), ss.rend(), ss.rbegin(), e, agg); - int i = 0; - for (auto [c, w] : g[v]) { - ++i; - if (c == from) continue; - dp[v] = fin(v, agg(ss[i], ps[i])); - dfs1(c, v, g); - } - dp[v] = fin(v, ss[0]); - } + void dfs1(int v, int from = -1) { + vector pref = {E}; + for (auto [u, w] : adj[v]) { + pref.push_back(takeChild(v, u, w, dp[u])); + } + auto suf = pref; + partial_sum(all(pref), pref.begin(), comb); + exclusive_scan(suf.rbegin(), suf.rend(), + suf.rbegin(), E, comb); - template - auto solve(vector>> g) { - dp.resize(sz(g)); - dfs0(g, 0); - dfs1(g, 0); - return dp; - } -}; \ No newline at end of file + for (int i = 0; i < sz(adj[v]); i++) { + auto [u, w] = adj[v][i]; + if (u == from) continue; + dp[v] = fin(v, comb(pref[i], suf[i + 1])); + dfs1(u, v); + } + dp[v] = fin(v, suf[0]); + } + + auto solve() { + dp.assign(sz(adj), E); + dfs0(0); + dfs1(0); + return dp; + } +}; -- cgit v1.2.3 From 24db7e1f387b458e8a48c3b773860e32f897017c Mon Sep 17 00:00:00 2001 From: Yidi Date: Mon, 2 Sep 2024 16:54:30 +0200 Subject: remove inconsistent reference --- content/graph/reroot.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index cd63b3d..379c839 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -13,7 +13,7 @@ struct Reroot { T dfs0(int v, int from = -1) { T val = E; - for (auto& [u, w] : adj[v]) { + for (auto [u, w] : adj[v]) { if (u == from) continue; val = comb(val, takeChild(v, u, w, dfs0(u, v))); } -- cgit v1.2.3 From 943d96c5f7cde38e5ec02b1cdb29bb7c8766574c Mon Sep 17 00:00:00 2001 From: f1or1an <110727007+f1or1an@users.noreply.github.com> Date: Tue, 3 Sep 2024 22:15:06 +0200 Subject: remove static constexpr --- content/graph/reroot.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 379c839..3ed19d0 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -4,7 +4,7 @@ vector>> adj; struct Reroot { using T = ll; // dp type - static constexpr T E = 0; // neutral element + T E = 0; // neutral element T takeChild(int v, int c, W w, T x) {} // move child along edge static T comb(T x, T y) {} T fin(int v, T x) {} // add v to own dp value x -- cgit v1.2.3 From 568329cab9a64d8059fe58142d35c43dfc08355e Mon Sep 17 00:00:00 2001 From: f1or1an <110727007+f1or1an@users.noreply.github.com> Date: Fri, 6 Sep 2024 00:20:38 +0200 Subject: Update content/graph/reroot.cpp --- content/graph/reroot.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 3ed19d0..379c839 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -4,7 +4,7 @@ vector>> adj; struct Reroot { using T = ll; // dp type - T E = 0; // neutral element + static constexpr T E = 0; // neutral element T takeChild(int v, int c, W w, T x) {} // move child along edge static T comb(T x, T y) {} T fin(int v, T x) {} // add v to own dp value x -- 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') 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') 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 322480404c722098cc09826c4e6daa8e2c1e9343 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 6 Sep 2024 21:43:30 +0200 Subject: small latex changes --- content/latexHeaders/layout.sty | 7 +++---- content/tcr.tex | 10 +++++++--- tcr.pdf | Bin 691692 -> 673187 bytes 3 files changed, 10 insertions(+), 7 deletions(-) (limited to 'content') diff --git a/content/latexHeaders/layout.sty b/content/latexHeaders/layout.sty index 096cf23..01915f3 100644 --- a/content/latexHeaders/layout.sty +++ b/content/latexHeaders/layout.sty @@ -10,9 +10,8 @@ % Headline and bottomline. \usepackage{scrlayer-scrpage} \pagestyle{scrheadings} -\clearscrheadfoot -\ihead{\university} -\chead{\teamname} +\clearpairofpagestyles +\ihead{\university{} -- \teamname{}} \ohead{\pagemark} % Shift the title up to waste less space. @@ -43,7 +42,7 @@ % use less space... %\usepackage[subtle, sections, indent, leading, charwidths]{savetrees} -\usepackage[moderate,sections]{savetrees} +\usepackage[moderate]{savetrees} \RedeclareSectionCommands[ beforeskip=1pt plus 5pt, afterskip=0.1pt plus 1.5pt diff --git a/content/tcr.tex b/content/tcr.tex index b327b37..4e4353b 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -1,6 +1,9 @@ - -%maybe size 9pt if too many pages -\documentclass[a4paper,fontsize=7.8pt]{scrartcl} +\documentclass[ + paper=a4, + DIV=calc, + fontsize=7.8pt, + usegeometry +]{scrartcl} % General information. \newcommand{\teamname}{Kindergarten Timelimit} @@ -14,6 +17,7 @@ \usepackage[T1]{fontenc} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} +\usepackage[nopatch=footnote]{microtype} \usepackage[hidelinks,pdfencoding=auto]{hyperref} % Include headers. diff --git a/tcr.pdf b/tcr.pdf index e349ca0..488ac70 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 6ae1d00fca78145c73f826c5490452726b9bf161 Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Sat, 7 Sep 2024 22:02:34 +0200 Subject: add divSum (sum of floor linear) --- content/math/divSum.cpp | 9 +++++++++ test/math/divSum.cpp | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+) create mode 100644 content/math/divSum.cpp create mode 100644 test/math/divSum.cpp (limited to 'content') diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp new file mode 100644 index 0000000..dc4bc4d --- /dev/null +++ b/content/math/divSum.cpp @@ -0,0 +1,9 @@ +// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n)) +// Note that b should not be negative! +ll divSum(ll n, ll m, ll a, ll b){ + if(m == 0) return 0; + ll ans = a/m * n*(n-1) / 2 + b/m * n; + a %= m, b %= m; + ll y = (a*(n-1)+b)/m; + return ans + y*(n-1) - divSum(y, a, m, m-b-1); +} \ No newline at end of file diff --git a/test/math/divSum.cpp b/test/math/divSum.cpp new file mode 100644 index 0000000..1f82387 --- /dev/null +++ b/test/math/divSum.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#include + +ll naive(ll n, ll m, ll a, ll b){ + ll ans = 0; + for(ll i = 0; i < n; i++){ + ans += (a*i+b)/m; + } + return ans; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + int a = Random::integer(0, 100); + int b = Random::integer(0, 100); + ll expected = naive(n, m, a, b); + ll got = divSum(n, m, a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll n = Random::integer(1, 1'000'000'000); + ll m = Random::integer(1, 1'000'000'000); + ll a = Random::integer(0, 1'000'000'000); + ll b = Random::integer(0, 1'000'000'000); + t.start(); + hash += divSum(n, m, a, b); + 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 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 7 Sep 2024 23:41:49 +0200 Subject: insert divsum --- content/graph/dinicScaling.cpp | 21 +++++++++++++-------- content/graph/graph.tex | 4 ++-- content/math/divSum.cpp | 15 +++++++-------- content/math/gauss.cpp | 12 +++++------- content/math/lgsFp.cpp | 3 +-- content/math/math.tex | 14 ++++++++++---- content/tcr.tex | 1 - tcr.pdf | Bin 673187 -> 691497 bytes 8 files changed, 38 insertions(+), 32 deletions(-) (limited to 'content') diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index f4e833a..0974b78 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -26,17 +26,18 @@ bool bfs(ll lim) { return dist[t] >= 0; } -bool dfs(int v, ll flow) { - if (v == t) return true; +ll dfs(int v, ll flow) { + if (v == t || flow == 0) return flow; for (; pt[v] < sz(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; - if (e.c - e.f >= flow && dfs(e.to, flow)) { - e.f += flow; - adj[e.to][e.rev].f -= flow; - return true; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; }} - return false; + return 0; } ll maxFlow(int source, int target) { @@ -45,7 +46,11 @@ ll maxFlow(int source, int target) { for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { pt.assign(sz(adj), 0); - while (dfs(s, lim)) flow += lim; + ll cur; + do { + cur = dfs(s, lim); + flow += cur; + } while (cur > 0); }} return flow; } diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 831f4e5..213c597 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} +\vfill\null +\columnbreak \subsubsection{Dinic's Algorithm mit Capacity Scaling} \begin{methods} @@ -218,8 +220,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} -\vfill\null -\columnbreak \optional{ \subsubsection{Anwendungen} diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp index dc4bc4d..48302b5 100644 --- a/content/math/divSum.cpp +++ b/content/math/divSum.cpp @@ -1,9 +1,8 @@ -// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n)) -// Note that b should not be negative! ll divSum(ll n, ll m, ll a, ll b){ - if(m == 0) return 0; - ll ans = a/m * n*(n-1) / 2 + b/m * n; - a %= m, b %= m; - ll y = (a*(n-1)+b)/m; - return ans + y*(n-1) - divSum(y, a, m, m-b-1); -} \ No newline at end of file + if (m == 0) return 0; + ll ans = a/m * n*(n-1)/2 + b/m * n; + a %= m; + b %= m; + ll y = (a*(n-1)+b) / m; + return ans + y * (n-1) - divSum(y, a, m, m-b-1); +} diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index 8129fd2..d431e52 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -14,19 +14,17 @@ void takeAll(int n, int line) { int gauss(int n) { vector done(n, false); for (int i = 0; i < n; i++) { - int swappee = i; // Sucht Pivotzeile für bessere Stabilität. - for (int j = 0; j < n; j++) { - if (done[j]) continue; - if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; + int j = i; // Sucht Pivotzeile für bessere Stabilität. + for (int k = 0; k < n; k++) { + if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k; } - swap(mat[i], mat[swappee]); + swap(mat[i], mat[j]); if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); done[i] = true; }} - // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung. - for (int i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS; if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT; diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 0241742..bf18c86 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -22,5 +22,4 @@ void gauss(int n, ll mod) { normalLine(i, mod); takeAll(n, i, mod); done[i] = true; -}} -// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ +}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ diff --git a/content/math/math.tex b/content/math/math.tex index c15825f..fffdf37 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{gauss}{löst LGS}{n^3} \sourcecode{math/gauss.cpp} -\vfill\null\columnbreak +\begin{algorithm}{Inversionszahl} + \vspace{-2pt} + \sourcecode{math/inversions.cpp} +\end{algorithm} \begin{algorithm}{Numerisch Extremstelle bestimmen} \sourcecode{math/goldenSectionSearch.cpp} @@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/simpson.cpp} \end{algorithm} - \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} Multipliziert Polynome $A$ und $B$. \begin{itemize} @@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp} \end{algorithm} -\begin{algorithm}{Inversionszahl} - \sourcecode{math/inversions.cpp} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} \end{algorithm} \subsection{Satz von \textsc{Sprague-Grundy}} @@ -394,6 +399,7 @@ so gilt \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ + \columnbreak \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} diff --git a/content/tcr.tex b/content/tcr.tex index 4e4353b..b3cfb17 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -17,7 +17,6 @@ \usepackage[T1]{fontenc} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} -\usepackage[nopatch=footnote]{microtype} \usepackage[hidelinks,pdfencoding=auto]{hyperref} % Include headers. diff --git a/tcr.pdf b/tcr.pdf index 488ac70..c16c3cc 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From df963645ca0c5d0bed4fb9c02e93233dcfd53dae Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Sun, 8 Sep 2024 14:57:14 +0200 Subject: add min mod (mimumum of linear function modulo m) --- content/math/math.tex | 9 ++++- content/math/minMod.cpp | 18 ++++++++++ tcr.pdf | Bin 691497 -> 693864 bytes test/math/minMod.cpp | 92 ++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 118 insertions(+), 1 deletion(-) create mode 100644 content/math/minMod.cpp create mode 100644 test/math/minMod.cpp (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index fffdf37..6b765ca 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -344,11 +344,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \begin{algorithm}{Div Sum} - \method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} \textbf{Wichtig:} $b$ darf nicht negativ sein! \sourcecode{math/divSum.cpp} \end{algorithm} +\begin{algorithm}{Min Mod} + \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)} + \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} + \textbf{Wichtig:} $0 \leq a, b, l, r < m$ + \sourcecode{math/minMod.cpp} +\end{algorithm} + \subsection{Satz von \textsc{Sprague-Grundy}} Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: \[ diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp new file mode 100644 index 0000000..2db060a --- /dev/null +++ b/content/math/minMod.cpp @@ -0,0 +1,18 @@ +ll firstVal(ll a, ll m, ll l, ll r){ + if(l == 0) return 0; + if(a == 0) return -1; + if((l-1)/a < r/a) return (l+a-1)/a*a; + ll s = (r+a-1)/a*a; + ll v = firstVal(m%a, a, s-r, s-l); + return v == -1 ? -1 : s - v; +} + +ll minMod(ll n, ll m, ll a, ll b){ + if(a == 0) return b; + ll g = gcd(m, a), c = b%g; + m /= g, a /= g, b /= g; + ll ai = multInv(a, m); + ll l = ai*b % m, r = (n-1 + ai*b) % m; + if(n >= m || l > r) return c; + return a * firstVal(ai, m, l, r) % m * g + c; +} \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index c16c3cc..7dc830e 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/math/minMod.cpp b/test/math/minMod.cpp new file mode 100644 index 0000000..e49da11 --- /dev/null +++ b/test/math/minMod.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include +#include + +ll naiveMinMod(ll n, ll m, ll a, ll b){ + ll ans = m; + for(ll i = 0; i < n; i++){ + ans = min(ans, (a*i+b)%m); + } + return ans; +} + +ll naiveFirstVal(ll a, ll m, ll l, ll r){ + for(ll i = 0; i < m; i++){ + ll v = a*i % m; + if(l <= v && v <= r) return v; + } + return -1; +} + +void stress_test_minMod() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer(1, 100); + int m = Random::integer(1, 100); + int a = Random::integer(0, m); + int b = Random::integer(0, m); + ll expected = naiveMinMod(n, m, a, b); + ll got = minMod(n, m, a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void stress_test_firstVal() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int m = Random::integer(1, 100); + int a = Random::integer(0, m); + int l = Random::integer(0, m); + int r = Random::integer(0, m); + if(l > r) swap(l, r); + ll expected = naiveFirstVal(a, m, l, r); + ll got = firstVal(a, m, l, r); + if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test_minMod() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll n = Random::integer(1, 1'000'000'000); + ll m = Random::integer(1, 1'000'000'000); + ll a = Random::integer(0, m); + ll b = Random::integer(0, m); + t.start(); + hash += minMod(n, m, a, b); + t.stop(); + } + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +void performance_test_firstVal() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer(1, 1'000'000'000); + ll a = Random::integer(1, m); + ll l = Random::integer(0, m); + ll r = Random::integer(0, m); + if(l > r) swap(l, r); + t.start(); + hash += firstVal(a, m, l, r); + 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_minMod(); + stress_test_firstVal(); + performance_test_minMod(); + performance_test_firstVal(); +} + -- cgit v1.2.3 From 45d95c45013bf4ff73570c94c58b7f0212ccdf26 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 8 Sep 2024 22:16:36 +0200 Subject: moved stuff --- content/math/math.tex | 79 ++++++++++++++++++++++++------------ content/math/minMod.cpp | 26 +++++++----- content/math/tables.tex | 18 -------- content/math/tables/binom.tex | 31 +++++++------- content/math/tables/composite.tex | 45 ++++++++++---------- content/math/tables/nim.tex | 5 ++- content/math/tables/numbers.tex | 59 --------------------------- content/math/tables/platonic.tex | 26 ++++++------ content/math/tables/probability.tex | 17 ++++---- content/math/tables/series.tex | 32 +++++++-------- content/math/tables/stuff.tex | 9 ++-- content/tcr.tex | 3 -- tcr.pdf | Bin 693864 -> 696377 bytes 13 files changed, 148 insertions(+), 202 deletions(-) delete mode 100644 content/math/tables.tex delete mode 100644 content/math/tables/numbers.tex (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index 6b765ca..c07a41e 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -342,31 +342,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp} \end{algorithm} - -\begin{algorithm}{Div Sum} - \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} - \textbf{Wichtig:} $b$ darf nicht negativ sein! - \sourcecode{math/divSum.cpp} -\end{algorithm} - -\begin{algorithm}{Min Mod} - \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$, der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{\log(m)} - \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} - \textbf{Wichtig:} $0 \leq a, b, l, r < m$ - \sourcecode{math/minMod.cpp} -\end{algorithm} - -\subsection{Satz von \textsc{Sprague-Grundy}} -Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: -\[ -g\left(X\right) := \min\left\{ -\mathbb{Z}_0^+ \setminus -\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\} -\right\} -\] -$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\ -Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. - \subsection{Kombinatorik} \paragraph{Wilsons Theorem} @@ -400,13 +375,14 @@ so gilt \paragraph{Binomialkoeffizienten} Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge. + \input{math/tables/binom} + \begin{methods} \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}} \method{calc\_binom}{berechnet Binomialkoeffizient}{1} \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ - \columnbreak \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} @@ -519,6 +495,54 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}} \input{math/tables/twelvefold} +\subsection{Platonische Körper} +\input{math/tables/platonic} + +\input{math/tables/probability} + +\subsection{Satz von \textsc{Sprague-Grundy}} +Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: +\[ +g\left(X\right) := \min\left\{ +\mathbb{Z}_0^+ \setminus +\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\} +\right\} +\] +$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\ +Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. + +\subsection{Nim-Spiele} +\begin{itemize} + \item[\ding{182}] letzter gewinnt (normal) + \item[\ding{183}] letzter verliert +\end{itemize} +\input{math/tables/nim} + +\subsection{Verschiedenes} +\input{math/tables/stuff} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} +\end{algorithm} + +\begin{algorithm}{Min Mod} + \begin{methods} + \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)} + \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{} + \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)} + \end{methods} + \textbf{Wichtig:} $0 \leq a, b, l, r < m$ + \sourcecode{math/minMod.cpp} +\end{algorithm} + +\subsection{Reihen} +\input{math/tables/series} + +\subsection{Wichtige Zahlen} +\input{math/tables/composite} + \optional{ \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} \begin{methods} @@ -529,7 +553,8 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \sourcecode{math/piLehmer.cpp} } -%\input{math/tables/numbers} +\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} +\sourcecode{math/piLegendre.cpp} \begin{algorithm}[optional]{Big Integers} \sourcecode{math/bigint.cpp} diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp index 2db060a..91f31d0 100644 --- a/content/math/minMod.cpp +++ b/content/math/minMod.cpp @@ -1,18 +1,22 @@ -ll firstVal(ll a, ll m, ll l, ll r){ - if(l == 0) return 0; - if(a == 0) return -1; - if((l-1)/a < r/a) return (l+a-1)/a*a; - ll s = (r+a-1)/a*a; - ll v = firstVal(m%a, a, s-r, s-l); +ll firstVal(ll a, ll m, ll l, ll r) { + if (l == 0) return 0; + if (a == 0) return -1; + if ((l-1)/a < r/a) return (l+a-1) / a*a; + ll s = (r+a-1) / a*a; + ll v = firstVal(m % a, a, s-r, s-l); return v == -1 ? -1 : s - v; } -ll minMod(ll n, ll m, ll a, ll b){ - if(a == 0) return b; - ll g = gcd(m, a), c = b%g; - m /= g, a /= g, b /= g; +ll minMod(ll n, ll m, ll a, ll b) { + if (a == 0) return b; + ll g = gcd(m, a); + c = b%g; + m /= g; + a /= g; + b /= g; ll ai = multInv(a, m); - ll l = ai*b % m, r = (n-1 + ai*b) % m; + ll l = ai*b % m; + ll r = (n-1 + ai*b) % m; if(n >= m || l > r) return c; return a * firstVal(ai, m, l, r) % m * g + c; } \ No newline at end of file diff --git a/content/math/tables.tex b/content/math/tables.tex deleted file mode 100644 index 53f3758..0000000 --- a/content/math/tables.tex +++ /dev/null @@ -1,18 +0,0 @@ -\enlargethispage{0.2cm} -\begin{multicols*}{2} - \input{math/tables/binom} - \vfill - \input{math/tables/composite} - \vfill - \input{math/tables/platonic} - \vfill - \input{math/tables/series} - - \columnbreak - - \input{math/tables/probability} - \vfill - \input{math/tables/stuff} - \vfill - \input{math/tables/nim} -\end{multicols*} diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex index 878a6b0..9fc9ae3 100644 --- a/content/math/tables/binom.tex +++ b/content/math/tables/binom.tex @@ -1,28 +1,27 @@ -\begin{tabularx}{\linewidth}{|XXXX|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|C|} \hline - \multicolumn{4}{|c|}{Binomialkoeffizienten} \\ - \hline - \multicolumn{4}{|c|}{ $\frac{n!}{k!(n - k)!} \hfill=\hfill \binom{n}{k} \hfill=\hfill \binom{n}{n - k} \hfill=\hfill \frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill \frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill - \binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill + \frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\ + + $\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill + \binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill (-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill - 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$ - } \\ + 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\ \grayhline - $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ & - $\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ & - $\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ & - $\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ + $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill + \sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill + \sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill + \sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ - $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ & - $\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ - }\\ + $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill + \sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill + \sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/composite.tex b/content/math/tables/composite.tex index c261db1..7a6ab09 100644 --- a/content/math/tables/composite.tex +++ b/content/math/tables/composite.tex @@ -1,27 +1,26 @@ - -\begin{tabularx}{\linewidth}{|r||r||r|r||r|r|r||C|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|r||r|R||r||r|} \hline - \multicolumn{8}{|c|}{Important Numbers} \\ + $10^x$ & Highly Composite & \# Divs & \# prime Divs & \# Primes \\ \hline - $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & primorial & \\ - \hline - 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 & \\ - 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 & \\ - 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 & \\ - 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 & \\ - 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 & \\ - 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 & \\ - 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 & \\ - 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 & \\ - 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 & \\ - 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 & \\ - 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 & \\ - 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 & \\ - 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 & \\ - 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 & \\ - 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 & \\ - 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 & \\ - 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 & \\ - 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 & \\ + 1 & 6 & 4 & 2 & 4 \\ + 2 & 60 & 12 & 3 & 25 \\ + 3 & 840 & 32 & 4 & 168 \\ + 4 & 7\,560 & 64 & 5 & 1\,229 \\ + 5 & 83\,160 & 128 & 6 & 9\,592 \\ + 6 & 720\,720 & 240 & 7 & 78\,498 \\ + 7 & 8\,648\,640 & 448 & 8 & 664\,579 \\ + 8 & 73\,513\,440 & 768 & 8 & 5\,761\,455 \\ + 9 & 735\,134\,400 & 1\,344 & 9 & 50\,847\,534 \\ + 10 & 6\,983\,776\,800 & 2\,304 & 10 & 455\,052\,511 \\ + 11 & 97\,772\,875\,200 & 4\,032 & 10 & 4\,118\,054\,813 \\ + 12 & 963\,761\,198\,400 & 6\,720 & 11 & 37\,607\,912\,018 \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & 12 & 346\,065\,536\,839 \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & 12 & 3\,204\,941\,750\,802 \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & 13 & 29\,844\,570\,422\,669 \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & 13 & 279\,238\,341\,033\,925 \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & 14 & 2\,623\,557\,157\,654\,233 \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & 16 & 24\,739\,954\,287\,740\,860 \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex index 8490d42..66e289e 100644 --- a/content/math/tables/nim.tex +++ b/content/math/tables/nim.tex @@ -1,6 +1,5 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|} - \hline - \multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\ \hline Beschreibung & Strategie \\ @@ -94,3 +93,5 @@ Periode ab $n = 72$ der Länge $12$.\\ \hline \end{tabularx} +\end{expandtable} + \ No newline at end of file diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex deleted file mode 100644 index 1dc9f38..0000000 --- a/content/math/tables/numbers.tex +++ /dev/null @@ -1,59 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|l|X|} - \hline - \multicolumn{2}{|c|}{Berühmte Zahlen} \\ - \hline - \textsc{Fibonacci} & - $f(0) = 0 \quad - f(1) = 1 \quad - f(n+2) = f(n+1) + f(n)$ \\ - \grayhline - - \textsc{Catalan} & - $C_0 = 1 \qquad - C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = - \frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\ - \grayhline - - \textsc{Euler} I & - $\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad - \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\ - \grayhline - - \textsc{Euler} II & - $\eulerII{n}{0} = 1 \quad - \eulerII{n}{n} = 0 \quad$\\ - & $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\ - \grayhline - - \textsc{Stirling} I & - $\stirlingI{0}{0} = 1 \qquad - \stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad - \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\ - \grayhline - - \textsc{Stirling} II & - $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad - \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = - \frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\ - \grayhline - - \textsc{Bell} & - $B_1 = 1 \qquad - B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} - = \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\ - \grayhline - - \textsc{Partitions} & - $p(0,0) = 1 \quad - p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\ - & $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\ - \grayhline - - \textsc{Partitions} & - $f(0) = 1 \quad f(n) = 0~(n < 0)$ \\ - & $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\ - - \hline -\end{tabularx} -\end{expandtable} diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex index f4ee554..2866ccf 100644 --- a/content/math/tables/platonic.tex +++ b/content/math/tables/platonic.tex @@ -1,39 +1,39 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|X|CCCX|} \hline - \multicolumn{5}{|c|}{Platonische Körper} \\ - \hline - Übersicht & Seiten & Ecken & Kanten & dual zu \\ + Übersicht & |F| & |V| & |E| & dual zu \\ \hline Tetraeder & 4 & 4 & 6 & Tetraeder \\ - Würfel/Hexaeder & 6 & 8 & 12 & Oktaeder \\ - Oktaeder & 8 & 6 & 12 & Würfel/Hexaeder\\ + Würfel & 6 & 8 & 12 & Oktaeder \\ + Oktaeder & 8 & 6 & 12 & Würfel\\ Dodekaeder & 12 & 20 & 30 & Ikosaeder \\ Ikosaeder & 20 & 12 & 30 & Dodekaeder \\ \hline \multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\ \hline - \multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} & + \multicolumn{3}{|l}{|V| vom Oktaeder/|F| vom Würfel} & \multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\ - \multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} & + \multicolumn{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} & \multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\ - \multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} & + \multicolumn{3}{|l}{|E| vom Würfel/Oktaeder} & \multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\ - \multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} & + \multicolumn{3}{|l}{|V|/|F| vom Tetraeder} & \multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\ - \multicolumn{3}{|l}{Kanten vom Tetraeder} & + \multicolumn{3}{|l}{|E| vom Tetraeder} & \multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\ - \multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} & + \multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} & \multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\ - \multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} & + \multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} & \multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\ - \multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} & + \multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} & \multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex index f265d10..29f92e1 100644 --- a/content/math/tables/probability.tex +++ b/content/math/tables/probability.tex @@ -1,19 +1,15 @@ -\begin{tabularx}{\linewidth}{|LICIR|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|LIR|} \hline - \multicolumn{3}{|c|}{ + \multicolumn{2}{|c|}{ Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) } \\ \hline - $\E(X + Y) = \E(X) + \E(Y)$ & - $\E(\alpha X) = \alpha \E(X)$ & - $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\ - - $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ & - $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ & - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $\E(X + Y) = \E(X) + \E(Y)$ & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + $\E(\alpha X) = \alpha \E(X)$ & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\ \hline \end{tabularx} -\vfill \begin{tabularx}{\linewidth}{|Xlr|lrX|} \hline \multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ @@ -25,3 +21,4 @@ $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex index 3042781..9618c2b 100644 --- a/content/math/tables/series.tex +++ b/content/math/tables/series.tex @@ -1,33 +1,33 @@ -\begin{tabularx}{\linewidth}{|XIXIXIX|} - \hline - \multicolumn{4}{|c|}{Reihen} \\ +\begin{expandtable} +\begin{tabularx}{\linewidth}{|XIXIX|} \hline $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & - $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ & - $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ + $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\ \grayhline - $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ & - $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ + $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ & + $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ & + $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\ \grayhline - + \multicolumn{2}{|lI}{ $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ } & - \multicolumn{2}{l|}{ + $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\ + \grayhline + + \multicolumn{2}{|lI}{ $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ - } \\ + } & + $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ \grayhline \multicolumn{2}{|lI}{ - $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ - } & - \multicolumn{2}{l|}{ $\sum\limits_{i = 1}^n \binom{i}{m}H_i = \binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$ - } \\ + } & + $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex index 3cf8b4c..82f2d3f 100644 --- a/content/math/tables/stuff.tex +++ b/content/math/tables/stuff.tex @@ -1,6 +1,7 @@ -\begin{tabularx}{\linewidth}{|ll|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|Ll|} \hline - \multicolumn{2}{|C|}{Verschiedenes} \\ + \multicolumn{2}{|c|}{Verschiedenes} \\ \hline Türme von Hanoi, minimale Schirttzahl: & $T_n = 2^n - 1$ \\ @@ -20,7 +21,7 @@ \#Wälder mit $k$ gewurzelten Bäumen & $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ - \#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten& + \#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten& $\frac{k}{n}n^{n-k}$ \\ Derangements & @@ -29,4 +30,4 @@ $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \hline \end{tabularx} - +\end{expandtable} diff --git a/content/tcr.tex b/content/tcr.tex index b3cfb17..6d849d5 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -48,10 +48,7 @@ \input{graph/graph} \input{geometry/geometry} \input{math/math} -\end{multicols*} \clearpage - \input{math/tables} -\begin{multicols*}{3} \input{string/string} \input{python/python} \input{other/other} diff --git a/tcr.pdf b/tcr.pdf index 7dc830e..dbd1055 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From fb5d046c4e4ab2bec7b0642626e11cff5680f63f Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 8 Sep 2024 23:21:15 +0200 Subject: fix minMod --- content/math/minMod.cpp | 6 +++--- tcr.pdf | Bin 696377 -> 696378 bytes 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'content') diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp index 91f31d0..a80e783 100644 --- a/content/math/minMod.cpp +++ b/content/math/minMod.cpp @@ -4,19 +4,19 @@ ll firstVal(ll a, ll m, ll l, ll r) { if ((l-1)/a < r/a) return (l+a-1) / a*a; ll s = (r+a-1) / a*a; ll v = firstVal(m % a, a, s-r, s-l); - return v == -1 ? -1 : s - v; + return v < 0 ? -1 : s - v; } ll minMod(ll n, ll m, ll a, ll b) { if (a == 0) return b; ll g = gcd(m, a); - c = b%g; + ll c = b % g; m /= g; a /= g; b /= g; ll ai = multInv(a, m); ll l = ai*b % m; ll r = (n-1 + ai*b) % m; - if(n >= m || l > r) return c; + if (n >= m || l > r) return c; return a * firstVal(ai, m, l, r) % m * g + c; } \ No newline at end of file diff --git a/tcr.pdf b/tcr.pdf index dbd1055..f97121c 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From cf3bf7ef7a3c4899b31041b15bcc67f6607f5cf4 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 10 Sep 2024 16:03:27 +0200 Subject: fix pentagonal number theorem --- content/math/math.tex | 2 +- tcr.pdf | Bin 696378 -> 696416 bytes 2 files changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index c07a41e..bad3bad 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -485,7 +485,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \begin{align*} p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\ p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt] - p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \end{align*} \begin{itemize} \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. diff --git a/tcr.pdf b/tcr.pdf index f97121c..d5cd7b1 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From d12405003fcbe53c26f024bbe1999fc59491046a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 10 Sep 2024 16:10:54 +0200 Subject: fix pentagonal number theorem --- content/math/math.tex | 2 +- tcr.pdf | Bin 696416 -> 696418 bytes 2 files changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index bad3bad..dd88a5b 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -485,7 +485,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \begin{align*} p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\ p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt] - p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] + p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \end{align*} \begin{itemize} \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. diff --git a/tcr.pdf b/tcr.pdf index d5cd7b1..9ed6eae 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 36fa19a38cf9a357f04d4ed76f25b1cbf44deedb Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Tue, 10 Sep 2024 21:50:42 +0200 Subject: new linear recurrence kthTerm code --- content/math/linearRecurence.cpp | 33 ----------------- content/math/linearRecurrence.cpp | 30 +++++++++++++++ content/math/linearRecurrenceOld.cpp | 33 +++++++++++++++++ content/math/math.tex | 5 ++- tcr.pdf | Bin 696418 -> 696332 bytes test/math/linearRecurence.cpp | 54 --------------------------- test/math/linearRecurenceOld.cpp | 54 +++++++++++++++++++++++++++ test/math/linearRecurrence.cpp | 57 +++++++++++++++++++++++++++++ test/math/linearRecurrenceSlowMul.cpp | 67 ++++++++++++++++++++++++++++++++++ 9 files changed, 244 insertions(+), 89 deletions(-) delete mode 100644 content/math/linearRecurence.cpp create mode 100644 content/math/linearRecurrence.cpp create mode 100644 content/math/linearRecurrenceOld.cpp delete mode 100644 test/math/linearRecurence.cpp create mode 100644 test/math/linearRecurenceOld.cpp create mode 100644 test/math/linearRecurrence.cpp create mode 100644 test/math/linearRecurrenceSlowMul.cpp (limited to 'content') diff --git a/content/math/linearRecurence.cpp b/content/math/linearRecurence.cpp deleted file mode 100644 index 2501e64..0000000 --- a/content/math/linearRecurence.cpp +++ /dev/null @@ -1,33 +0,0 @@ -constexpr ll mod = 1'000'000'007; -vector modMul(const vector& a, const vector& b, - const vector& c) { - ll n = sz(c); - vector res(n * 2 + 1); - for (int i = 0; i <= n; i++) { //a*b - for (int j = 0; j <= n; j++) { - res[i + j] += a[i] * b[j]; - res[i + j] %= mod; - }} - for (int i = 2 * n; i > n; i--) { //res%c - for (int j = 0; j < n; j++) { - res[i - 1 - j] += res[i] * c[j]; - res[i - 1 - j] %= mod; - }} - res.resize(n + 1); - return res; -} - -ll kthTerm(const vector& f, const vector& c, ll k) { - assert(sz(f) == sz(c)); - vector tmp(sz(c) + 1), a(sz(c) + 1); - tmp[0] = a[1] = 1; //tmp = (x^k) % c - - for (k++; k > 0; k /= 2) { - if (k & 1) tmp = modMul(tmp, a, c); - a = modMul(a, a, c); - } - - ll res = 0; - for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; - return res % mod; -} diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp new file mode 100644 index 0000000..c15c25c --- /dev/null +++ b/content/math/linearRecurrence.cpp @@ -0,0 +1,30 @@ +// constexpr ll mod = 998244353; +// vector mul(const vector &a, const vector &b){ +// vector c(sz(a) + sz(b) - 1); +// for(int i = 0; i < sz(a); i++){ +// for(int j = 0; j < sz(b); j++){ +// c[i+j] += a[i]*b[j] % mod; +// } +// } +// for(ll &x : c) x %= mod; +// return c; +// } + +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 p = mul(f, q); + p.resize(n); + p.push_back(0); + do{ + vector q2 = q; + 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++){ + p[i] = i == n ? 0 : x[2*i + (k&1)]; + q[i] = y[2*i]; + } + }while(k /= 2); + return p[0]; +} \ No newline at end of file diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp new file mode 100644 index 0000000..2501e64 --- /dev/null +++ b/content/math/linearRecurrenceOld.cpp @@ -0,0 +1,33 @@ +constexpr ll mod = 1'000'000'007; +vector modMul(const vector& a, const vector& b, + const vector& c) { + ll n = sz(c); + vector res(n * 2 + 1); + for (int i = 0; i <= n; i++) { //a*b + for (int j = 0; j <= n; j++) { + res[i + j] += a[i] * b[j]; + res[i + j] %= mod; + }} + for (int i = 2 * n; i > n; i--) { //res%c + for (int j = 0; j < n; j++) { + res[i - 1 - j] += res[i] * c[j]; + res[i - 1 - j] %= mod; + }} + res.resize(n + 1); + return res; +} + +ll kthTerm(const vector& f, const vector& c, ll k) { + assert(sz(f) == sz(c)); + vector tmp(sz(c) + 1), a(sz(c) + 1); + tmp[0] = a[1] = 1; //tmp = (x^k) % c + + for (k++; k > 0; k /= 2) { + if (k & 1) tmp = modMul(tmp, a, c); + a = modMul(a, a, c); + } + + ll res = 0; + for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; + return res % mod; +} diff --git a/content/math/math.tex b/content/math/math.tex index dd88a5b..fb66110 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -136,9 +136,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz. \begin{methods} - \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2} + \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)} \end{methods} - \sourcecode{math/linearRecurence.cpp} + Die Polynom-Multiplikation kann auch mit NTT gemacht werden! + \sourcecode{math/linearRecurrence.cpp} Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} diff --git a/tcr.pdf b/tcr.pdf index 9ed6eae..1bf4c26 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/math/linearRecurence.cpp b/test/math/linearRecurence.cpp deleted file mode 100644 index a5290e5..0000000 --- a/test/math/linearRecurence.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include "../util.h" -#include - -struct RandomRecurence { - vector f, c, cache; - RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} - - ll operator()(ll k){ - while (sz(cache) <= k) { - ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; - } - cur %= mod; - cache.push_back(cur); - } - return cache[k]; - } -}; - -void stress_test() { - int queries = 0; - for (int i = 0; i < 10'000; i++) { - int n = Random::integer(1, 10); - RandomRecurence f(n); - for (int j = 0; j < 100; j++) { - ll k = Random::integer(0, 1000); - - ll got = kthTerm(f.f, f.c, k); - ll expected = f(k); - - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries++; - } - } - cerr << "tested random queries: " << queries << endl; -} - -constexpr int N = 1'000; -void performance_test() { - timer t; - RandomRecurence f(N); - t.start(); - hash_t hash = kthTerm(f.f, f.c, 1e18); - t.stop(); - if (t.time > 500) 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/math/linearRecurenceOld.cpp b/test/math/linearRecurenceOld.cpp new file mode 100644 index 0000000..dab2256 --- /dev/null +++ b/test/math/linearRecurenceOld.cpp @@ -0,0 +1,54 @@ +#include "../util.h" +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 500) 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/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp new file mode 100644 index 0000000..50e98a0 --- /dev/null +++ b/test/math/linearRecurrence.cpp @@ -0,0 +1,57 @@ +#include "../util.h" +#include +#include +#include +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 8000) 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/math/linearRecurrenceSlowMul.cpp b/test/math/linearRecurrenceSlowMul.cpp new file mode 100644 index 0000000..205e584 --- /dev/null +++ b/test/math/linearRecurrenceSlowMul.cpp @@ -0,0 +1,67 @@ +#include "../util.h" + +constexpr ll mod = 998244353; +vector mul(const vector &a, const vector &b){ + vector c(sz(a) + sz(b) - 1); + for(int i = 0; i < sz(a); i++){ + for(int j = 0; j < sz(b); j++){ + c[i+j] += a[i]*b[j] % mod; + } + } + for(ll &x : c) x %= mod; + return c; +} + +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 500) 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 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') 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') 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 From a898bac55c6cd7c51fef5e6735aa3a316a18da7b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Wed, 11 Sep 2024 10:39:00 +0200 Subject: change tests --- content/math/linearRecurrence.cpp | 26 ++++---- tcr.pdf | Bin 695781 -> 695518 bytes test/geometry/hpi.cpp | 109 ++++++++++++++++++++++++++++++++++ test/math/linearRecurenceOld.cpp | 54 ----------------- test/math/linearRecurrence.cpp | 15 +++-- test/math/linearRecurrence.cpp.awk | 4 ++ test/math/linearRecurrenceNTT.cpp | 60 +++++++++++++++++++ test/math/linearRecurrenceOld.cpp | 54 +++++++++++++++++ test/math/linearRecurrenceSlowMul.cpp | 67 --------------------- 9 files changed, 249 insertions(+), 140 deletions(-) create mode 100644 test/geometry/hpi.cpp delete mode 100644 test/math/linearRecurenceOld.cpp create mode 100644 test/math/linearRecurrence.cpp.awk create mode 100644 test/math/linearRecurrenceNTT.cpp create mode 100644 test/math/linearRecurrenceOld.cpp delete mode 100644 test/math/linearRecurrenceSlowMul.cpp (limited to 'content') diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index ab86f71..a8adacd 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,19 +1,19 @@ -// constexpr ll mod = 998244353; -// vector mul(const vector &a, const vector &b){ -// vector c(sz(a) + sz(b) - 1); -// for(int i = 0; i < sz(a); i++){ -// for(int j = 0; j < sz(b); j++){ -// c[i+j] += a[i]*b[j] % mod; -// } -// } -// for(ll &x : c) x %= mod; -// return c; -// } +constexpr ll mod = 998244353; +// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ +vector mul(const vector& a, const vector& b) { + vector c(sz(a) + sz(b) - 1); + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + c[i+j] += a[i]*b[j] % mod; + }} + for (ll& x : c) x %= mod; + return c; +} ll kthTerm(const vector& f, const vector& c, ll k) { int n = sz(c); vector q(n + 1, 1); - for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod; + 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); @@ -27,4 +27,4 @@ ll kthTerm(const vector& f, const vector& c, ll k) { } } while (k /= 2); return p[0]; -} \ No newline at end of file +} diff --git a/tcr.pdf b/tcr.pdf index 6f156e4..47a96a2 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp new file mode 100644 index 0000000..e61178a --- /dev/null +++ b/test/geometry/hpi.cpp @@ -0,0 +1,109 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double +#include "../geometry.h" +ll sgn(ll x) { + return (x > 0) - (x < 0); +} +#include + +using ptd = complex; +ptd convert(pt x) {return ptd(real(x), imag(x));} +auto cross(ptd a, ptd b) {return imag(conj(a) * b);} +auto cross(ptd p, ptd a, ptd b) {return cross(a - p, b - p);} +ptd lineIntersection2(ptd a, ptd b, ptd c, ptd d) { + ld x = cross(b - a, d - c); + ld y = cross(c - a, d - c); + return a + y/x*(b - a); +} + +//check if a is dominated by b and c +bool naiveCheck(array a, array b, array c) { + //https://cp-algorithms.com/geometry/halfplane-intersection.html + //intersect b and c + //check cross of a and intersection + ptd intersection = lineIntersection2( + convert(b[0]), + convert(b[1]), + convert(c[0]), + convert(c[1]) + ); + return cross(convert(a[0]), convert(a[1]), intersection) <= -1e-12; +} +//real(a - p)*imag(b - p)-imag(a - p)*real(b - p) + +void test_check(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::line(range); + auto b = Random::line(range); + auto c = b; + while ( + cross(b[0] - b[1], c[0] - c[1]) == 0 + //||cross(a[0] - a[1], b[0] - b[1], c[0] - c[1]) >= 0 + ) c = Random::line(range); + + bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); + bool expected = naiveCheck(a, b, c); + + if (got != expected) { + cout << tries << endl; + cout << a[0] << " " << a[1] << endl; + cout << b[0] << " " << b[1] << endl; + cout << c[0] << " " << c[1] << endl; + cout << boolalpha << got << " " << expected << endl; + cerr << "error" << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +/*void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto centre = Random::point(n, -range / 2, range / 2); + + } + cerr << "tested random queries: " << queries << endl; +}*/ + +/*constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + double maxTime = 0; + + vector ps; + for (int i = 0; i*i <= N; i++) { + for (int j = 0; j*j <= N; j++) { + ps.emplace_back(i, j); + } + } + t.start(); + hash = shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + ps = Random::points(N, -1'000'000'000, 1'000'000'000); + t.reset(); + t.start(); + hash += shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL; + cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl; +}*/ + +int main() { + test_check(10); + test_check(100); + test_check(1000); + test_check(10000); + //performance_test(); +} diff --git a/test/math/linearRecurenceOld.cpp b/test/math/linearRecurenceOld.cpp deleted file mode 100644 index dab2256..0000000 --- a/test/math/linearRecurenceOld.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include "../util.h" -#include - -struct RandomRecurence { - vector f, c, cache; - RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} - - ll operator()(ll k){ - while (sz(cache) <= k) { - ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; - } - cur %= mod; - cache.push_back(cur); - } - return cache[k]; - } -}; - -void stress_test() { - int queries = 0; - for (int i = 0; i < 10'000; i++) { - int n = Random::integer(1, 10); - RandomRecurence f(n); - for (int j = 0; j < 100; j++) { - ll k = Random::integer(0, 1000); - - ll got = kthTerm(f.f, f.c, k); - ll expected = f(k); - - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries++; - } - } - cerr << "tested random queries: " << queries << endl; -} - -constexpr int N = 1'000; -void performance_test() { - timer t; - RandomRecurence f(N); - t.start(); - hash_t hash = kthTerm(f.f, f.c, 1e18); - t.stop(); - if (t.time > 500) 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/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 50e98a0..f0ebe76 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -1,9 +1,12 @@ #include "../util.h" -#include -#include -#include +vector mul(const vector& a, const vector& b); #include +vector mul(const vector& a, const vector& b) { + return mulSlow(a, b); +} + + struct RandomRecurence { vector f, c, cache; RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} @@ -23,7 +26,7 @@ struct RandomRecurence { void stress_test() { int queries = 0; - for (int i = 0; i < 1'000; i++) { + for (int i = 0; i < 10'000; i++) { int n = Random::integer(1, 10); RandomRecurence f(n); for (int j = 0; j < 100; j++) { @@ -39,14 +42,14 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 100'000; +constexpr int N = 1'000; void performance_test() { timer t; RandomRecurence f(N); t.start(); hash_t hash = kthTerm(f.f, f.c, 1e18); t.stop(); - if (t.time > 8000) cerr << "too slow: " << t.time << FAIL; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/math/linearRecurrence.cpp.awk b/test/math/linearRecurrence.cpp.awk new file mode 100644 index 0000000..902fd4b --- /dev/null +++ b/test/math/linearRecurrence.cpp.awk @@ -0,0 +1,4 @@ +/vector mul/ { + sub(/mul/, "mulSlow") +} +{ print } diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp new file mode 100644 index 0000000..e03c27e --- /dev/null +++ b/test/math/linearRecurrenceNTT.cpp @@ -0,0 +1,60 @@ +#include "../util.h" +#include +#include +#include +#define mod mod2 +#include +#undef mod +static_assert(mod == mod2); + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 8000) 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/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp new file mode 100644 index 0000000..dab2256 --- /dev/null +++ b/test/math/linearRecurrenceOld.cpp @@ -0,0 +1,54 @@ +#include "../util.h" +#include + +struct RandomRecurence { + vector f, c, cache; + RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 500) 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/math/linearRecurrenceSlowMul.cpp b/test/math/linearRecurrenceSlowMul.cpp deleted file mode 100644 index 205e584..0000000 --- a/test/math/linearRecurrenceSlowMul.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include "../util.h" - -constexpr ll mod = 998244353; -vector mul(const vector &a, const vector &b){ - vector c(sz(a) + sz(b) - 1); - for(int i = 0; i < sz(a); i++){ - for(int j = 0; j < sz(b); j++){ - c[i+j] += a[i]*b[j] % mod; - } - } - for(ll &x : c) x %= mod; - return c; -} - -#include - -struct RandomRecurence { - vector f, c, cache; - RandomRecurence(int n) : f(Random::integers(n, 0, mod)), c(Random::integers(n, 0, mod)), cache(f) {} - - ll operator()(ll k){ - while (sz(cache) <= k) { - ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; - } - cur %= mod; - cache.push_back(cur); - } - return cache[k]; - } -}; - -void stress_test() { - int queries = 0; - for (int i = 0; i < 10'000; i++) { - int n = Random::integer(1, 10); - RandomRecurence f(n); - for (int j = 0; j < 100; j++) { - ll k = Random::integer(0, 1000); - - ll got = kthTerm(f.f, f.c, k); - ll expected = f(k); - - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - queries++; - } - } - cerr << "tested random queries: " << queries << endl; -} - -constexpr int N = 1'000; -void performance_test() { - timer t; - RandomRecurence f(N); - t.start(); - hash_t hash = kthTerm(f.f, f.c, 1e18); - t.stop(); - if (t.time > 500) 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 900d941a9cf28cdda8dbdb1e4fe2c0fe0dbe7682 Mon Sep 17 00:00:00 2001 From: Yidi Date: Wed, 11 Sep 2024 22:54:37 +0200 Subject: improve aho corasick --- content/string/ahoCorasick.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'content') diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp index eac312c..390d16d 100644 --- a/content/string/ahoCorasick.cpp +++ b/content/string/ahoCorasick.cpp @@ -4,7 +4,7 @@ struct AhoCorasick { int suffix = 0, ch, cnt = 0; array nxt = {}; - vert(int p, int c) : suffix(-p), ch(c) {} + vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);} }; vector aho = {{0, -1}}; @@ -12,7 +12,7 @@ struct AhoCorasick { int v = 0; for (auto c : s) { int idx = c - OFFSET; - if (!aho[v].nxt[idx]) { + if (aho[v].nxt[idx] == -1) { aho[v].nxt[idx] = sz(aho); aho.emplace_back(v, idx); } @@ -30,8 +30,8 @@ struct AhoCorasick { } int go(int v, int idx) { // Root is v=0, idx is char - OFFSET - if (aho[v].nxt[idx]) return aho[v].nxt[idx]; - else return v == 0 ? 0 : go(getSuffix(v), idx); + if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx]; + return v == 0 ? 0 : aho[v].nxt[idx] = go(getSuffix(v), idx); } vector> adj; -- cgit v1.2.3 From a6f428e91457dae36efda91fbdc1eb4f0617132d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 12 Sep 2024 00:25:38 +0200 Subject: improve halfplane intersection tests --- content/geometry/hpi.cpp | 2 +- tcr.pdf | Bin 695518 -> 695511 bytes test/geometry/hpi.cpp | 240 +++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 212 insertions(+), 30 deletions(-) (limited to 'content') diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index f3dc08d..02c71e3 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -60,7 +60,7 @@ deque intersect(vector hps) { while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2])) dq.pop_back(); - while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1])) + while (sz(dq) > 2 && dq.back().check(dq[0], dq[1])) dq.pop_front(); if (sz(dq) < 3) return {}; diff --git a/tcr.pdf b/tcr.pdf index 47a96a2..7147158 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp index e61178a..a2326bc 100644 --- a/test/geometry/hpi.cpp +++ b/test/geometry/hpi.cpp @@ -11,30 +11,168 @@ ll sgn(ll x) { } #include -using ptd = complex; -ptd convert(pt x) {return ptd(real(x), imag(x));} -auto cross(ptd a, ptd b) {return imag(conj(a) * b);} -auto cross(ptd p, ptd a, ptd b) {return cross(a - p, b - p);} -ptd lineIntersection2(ptd a, ptd b, ptd c, ptd d) { - ld x = cross(b - a, d - c); - ld y = cross(c - a, d - c); - return a + y/x*(b - a); +//https://cp-algorithms.com/geometry/halfplane-intersection.html +namespace cpalgo { + // Redefine epsilon and infinity as necessary. Be mindful of precision errors. + const long double eps = 1e-9, inf = 1e9; + + // Basic point/vector struct. + struct Point { + + long double x, y; + explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {} + Point(pt p) : x(real(p)), y(imag(p)) {} + + // Addition, substraction, multiply by constant, dot product, cross product. + + friend Point operator + (const Point& p, const Point& q) { + return Point(p.x + q.x, p.y + q.y); + } + + friend Point operator - (const Point& p, const Point& q) { + return Point(p.x - q.x, p.y - q.y); + } + + friend Point operator * (const Point& p, const long double& k) { + return Point(p.x * k, p.y * k); + } + + friend long double dot(const Point& p, const Point& q) { + return p.x * q.x + p.y * q.y; + } + + friend long double cross(const Point& p, const Point& q) { + return p.x * q.y - p.y * q.x; + } + + friend std::ostream& operator<<(std::ostream& os, const Point& p) { + return os << "(" << p.x << ", " << p.y << ")"; + } + + + }; + + // Basic half-plane struct. + struct Halfplane { + + // 'p' is a passing point of the line and 'pq' is the direction vector of the line. + Point p, pq; + long double angle; + + Halfplane() {} + Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) { + angle = atan2l(pq.x, -pq.y);//patched to get same sort + } + Halfplane(array ps) : Halfplane(ps[0], ps[1]) {} + Halfplane(hp h) : Halfplane(h.from, h.to) {} + + // Check if point 'r' is outside this half-plane. + // Every half-plane allows the region to the LEFT of its line. + bool out(const Point& r) { + return cross(pq, r - p) < -eps; + } + + // Comparator for sorting. + bool operator < (const Halfplane& e) const { + return angle < e.angle; + } + + // Intersection point of the lines of two half-planes. It is assumed they're never parallel. + friend Point inter(const Halfplane& s, const Halfplane& t) { + long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq); + return s.p + (s.pq * alpha); + } + + friend std::ostream& operator<<(std::ostream& os, const Halfplane& hp) { + return os << hp.p << " " << hp.p+hp.pq; + } + }; + + // Actual algorithm + vector hp_intersect(vector& H) { + + /*Point box[4] = { // Bounding box in CCW order + Point(inf, inf), + Point(-inf, inf), + Point(-inf, -inf), + Point(inf, -inf) + }; + + for(int i = 0; i<4; i++) { // Add bounding box half-planes. + Halfplane aux(box[i], box[(i+1) % 4]); + H.push_back(aux); + }*/ + // Add bounding box half-planes, fixed: + H.push_back({pt( 1e9, 1e9), pt( 1e9-1, 1e9 )}); + H.push_back({pt(-1e9, 1e9), pt(-1e9 , 1e9-1)}); + H.push_back({pt(-1e9, -1e9), pt(-1e9+1, -1e9 )}); + H.push_back({pt( 1e9, -1e9), pt( 1e9 , -1e9+1)}); + + // Sort by angle and start algorithm + sort(H.begin(), H.end()); + deque dq; + int len = 0; + for(int i = 0; i < int(H.size()); i++) { + + // Remove from the back of the deque while last half-plane is redundant + while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) { + dq.pop_back(); + --len; + } + + // Remove from the front of the deque while first half-plane is redundant + while (len > 1 && H[i].out(inter(dq[0], dq[1]))) { + dq.pop_front(); + --len; + } + + // Special case check: Parallel half-planes + if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) { + // Opposite parallel half-planes that ended up checked against each other. + if (dot(H[i].pq, dq[len-1].pq) < 0.0) + return vector(); + + // Same direction half-plane: keep only the leftmost half-plane. + if (H[i].out(dq[len-1].p)) { + dq.pop_back(); + --len; + } + else continue; + } + + // Add new half-plane + dq.push_back(H[i]); + ++len; + } + + // Final cleanup: Check half-planes at the front against the back and vice-versa + while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) { + dq.pop_back(); + --len; + } + + while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) { + dq.pop_front(); + --len; + } + + // Report empty intersection if necessary + if (len < 3) return vector(); + + // Reconstruct the convex polygon from the remaining half-planes. + vector ret(len); + for(int i = 0; i+1 < len; i++) { + ret[i] = inter(dq[i], dq[i+1]); + } + ret.back() = inter(dq[len-1], dq[0]); + return ret; + } } //check if a is dominated by b and c -bool naiveCheck(array a, array b, array c) { - //https://cp-algorithms.com/geometry/halfplane-intersection.html - //intersect b and c - //check cross of a and intersection - ptd intersection = lineIntersection2( - convert(b[0]), - convert(b[1]), - convert(c[0]), - convert(c[1]) - ); - return cross(convert(a[0]), convert(a[1]), intersection) <= -1e-12; +bool naiveCheck(cpalgo::Halfplane a, cpalgo::Halfplane b, cpalgo::Halfplane c) { + return a.out(inter(b, c)); } -//real(a - p)*imag(b - p)-imag(a - p)*real(b - p) void test_check(ll range) { ll queries = 0; @@ -42,10 +180,7 @@ void test_check(ll range) { auto a = Random::line(range); auto b = Random::line(range); auto c = b; - while ( - cross(b[0] - b[1], c[0] - c[1]) == 0 - //||cross(a[0] - a[1], b[0] - b[1], c[0] - c[1]) >= 0 - ) c = Random::line(range); + while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range); bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); bool expected = naiveCheck(a, b, c); @@ -63,14 +198,61 @@ void test_check(ll range) { cerr << "tested random queries: " << queries << endl; } -/*void stress_test(ll range) { +void stress_test(ll range) { ll queries = 0; for (int tries = 0; tries < 100'000; tries++) { - auto centre = Random::point(n, -range / 2, range / 2); + auto centre = Random::point(-range / 2, range / 2); + int n = Random::integer(3, 30); + + vector hps1 = {//+cpalgo bounding box + {pt( 1e9, 1e9), pt(-1e9, 1e9)}, + {pt(-1e9, 1e9), pt(-1e9, -1e9)}, + {pt(-1e9, -1e9), pt( 1e9, -1e9)}, + {pt( 1e9, -1e9), pt( 1e9, 1e9)}, + }; + + vector hps2; + for (int i = 0; i < n; i++) { + auto [a, b] = Random::line(range); + if (cross(a, b, centre) < 0) swap(a, b); + hps1.emplace_back(a, b); + hps2.emplace_back(a, b); + } + + auto expected = cpalgo::hp_intersect(hps2); + auto gotHp = intersect(hps1); + if (sz(gotHp) == 1) cerr << "WHAT?" << FAIL; + for (hp h : gotHp) { + if (h.dummy()) cerr << "DUMMY!" << FAIL;//we added a bounding box... + } + vector got; + if (!gotHp.empty()) { + gotHp.push_back(gotHp[0]); + for (int i = 0; i + 1 < sz(gotHp); i++) { + got.push_back(inter(cpalgo::Halfplane(gotHp[i]), cpalgo::Halfplane(gotHp[i + 1]))); + } + } + + bool eq = sz(got) == sz(expected); + for (ll i = 0; eq && i < sz(got); i++) { + eq &= float_error(got[i].x, expected[i].x) < 1e-6; + eq &= float_error(got[i].y, expected[i].y) < 1e-6; + } + if (!eq) { + cerr << tries << endl; + cerr << setprecision(20) << endl; + for (auto tmp : hps2) cerr << tmp << endl; + cerr << endl; + for (auto tmp : expected) cerr << tmp << endl; + cerr << endl; + for (auto tmp : got) cerr << tmp << endl; + cerr << FAIL; + } + queries += n; } cerr << "tested random queries: " << queries << endl; -}*/ +} /*constexpr int N = 1'000'000; void performance_test() { @@ -103,7 +285,7 @@ void performance_test() { int main() { test_check(10); test_check(100); - test_check(1000); - test_check(10000); + stress_test(10); + stress_test(100); //performance_test(); } -- cgit v1.2.3 From 3574ba309674d4a1969153e13f781a320ee1d8ad Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 22 Sep 2024 23:13:05 +0200 Subject: remove sccs from sccs --- content/graph/scc.cpp | 19 ++++++++++--------- test/graph/scc.cpp | 12 ------------ 2 files changed, 10 insertions(+), 21 deletions(-) (limited to 'content') diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index ac9a40b..32f1099 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -1,11 +1,12 @@ -vector> adj, sccs; -int counter; +vector> adj; +int counter, sccCounter; vector inStack; vector low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; - s.push_back(v); inStack[v] = true; + s.push_back(v); + inStack[v] = true; for (auto u : adj[v]) { if (low[u] < 0) visit(u); @@ -13,20 +14,20 @@ void visit(int v) { } if (old == low[v]) { - sccs.push_back({}); + sccCounter++; for (int u = -1; u != v;) { - u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sz(sccs) - 1; - sccs.back().push_back(u); + u = s.back(); + s.pop_back(); + inStack[u] = false; + idx[u] = sccCounter - 1; }}} void scc() { inStack.assign(sz(adj), false); low.assign(sz(adj), -1); idx.assign(sz(adj), -1); - sccs.clear(); - counter = 0; + counter = sccCounter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 123050f..9ab7051 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -16,18 +16,6 @@ void stress_test() { }); scc(); - vector tmp(n); - for (int i = 0; i < sz(sccs); i++) { - for (int x : sccs[i]) { - if (tmp[x]) cerr << "error: duclicate" << FAIL; - if (idx[x] != i) cerr << "error: inconsistent" << FAIL; - tmp[x] = true; - } - } - for (int i = 0; i < n; i++) { - if (!tmp[i]) cerr << "error: missing" << FAIL; - } - init(n); vector seen(n); int tmpCounter = 0; -- cgit v1.2.3 From 35d485bcf6a9ed0a9542628ce4aa94a3326d0884 Mon Sep 17 00:00:00 2001 From: Yidi Date: Wed, 25 Sep 2024 20:18:42 +0200 Subject: fix function name --- content/geometry/polygon.cpp | 2 +- test/geometry/polygon.cpp | 6 +++--- 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'content') diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 3178290..064d81f 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -29,7 +29,7 @@ bool inside(pt p, const vector& poly) { bool in = false; for (int i = 0; i + 1 < sz(poly); i++) { pt a = poly[i], b = poly[i + 1]; - if (pointOnLineSegment(a, b, p)) return false; + if (pointOnSegment(a, b, p)) return false; if (real(a) > real(b)) swap(a,b); if (real(a) <= real(p) && real(p) < real(b) && cross(p, a, b) < 0) { diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp index 1dd46ca..643ea70 100644 --- a/test/geometry/polygon.cpp +++ b/test/geometry/polygon.cpp @@ -10,7 +10,7 @@ double abs(pt p) { return hypot(real(p), imag(p)); } // Liegt p auf der Strecke a-b? -bool pointOnLineSegment(pt a, pt b, pt p) { +bool pointOnSegment(pt a, pt b, pt p) { if (cross(a, b, p) != 0) return false; auto dist = norm(a - b); return norm(a - p) <= dist && norm(b - p) <= dist; @@ -65,7 +65,7 @@ void test_windingNumber(ll range) { int cur = details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); if (ptLess(ps[j], ps[j+1])) expected -= cur; else expected += cur; - onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + onBorder |= pointOnSegment(ps[j], ps[j+1], p); } if (onBorder) continue; if (area(ps) < 0) expected = -expected; @@ -93,7 +93,7 @@ void test_inside(ll range) { bool onBorder = false; for (int j = 0; j < n; j++) { count += details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); - onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + onBorder |= pointOnSegment(ps[j], ps[j+1], p); } bool expected = (count % 2) && !onBorder; bool got = inside(p, ps); -- cgit v1.2.3