diff options
60 files changed, 524 insertions, 485 deletions
@@ -221,9 +221,9 @@ TSWLatexianTemp* *~ -# ignore build dir -build/* -# dont ignore build tcr -!tcr.pdf +# files produced by the testing system +*.test +*.ok +*.d # ignore build test awk files test/awk/* @@ -1,4 +1,26 @@ -all: - cd content; latexmk -pdf tcr -output-directory=.. -aux-directory=../build/ -usepretex="\newcommand{\gitorigin}{https://github.com/mzuenni/ContestReference/tree/$(shell git branch --show-current)/content/}" -clean: - rm -r build/* +LATEXMK = latexmk -interaction=nonstopmode + +tcr.pdf: FORCE + cd content && $(LATEXMK) + +tcr-opt.pdf: FORCE + cd content && $(LATEXMK) -r latexmk.opt + +pdf: tcr.pdf tcr-opt.pdf + +all: pdf test + +test: + +gmake -C test + +clean: cleanpdf cleantest + +cleanpdf: + cd content && $(LATEXMK) -C + cd content && $(LATEXMK) -r latexmk.opt -C + +cleantest: + +-gmake -C clean + +FORCE: +.PHONY: all pdf test clean cleanpdf cleantest FORCE diff --git a/README.md b/README.md deleted file mode 100644 index 7edf67b..0000000 --- a/README.md +++ /dev/null @@ -1,38 +0,0 @@ -# KIT Team Contest Reference
-> [!TIP]
-> You can use this [pdf.js link](https://mozilla.github.io/pdf.js/web/viewer.html?file=https://raw.githubusercontent.com/mzuenni/ContestReference/new-master/tcr.pdf) to watch the commited pdf with working links,
-> or [this one](https://mozilla.github.io/pdf.js/web/viewer.html?file=https://gist.githubusercontent.com/mzuenni/73fb3c58350c58b623f221fc237def62/raw/tcr.pdf) to look at the current build.
-
-The KIT teams have used this document for ICPC-style contests since roughly 2019.
-It consists of 25 pages of copy-pasteable C++ code and one extra page with a checklist for the practice session.
-
-## Testing
-To make this document as useful as possible we try to (automatically) stress test all code in this repository.
-Nonetheless, not all code is tested and tests might not catch every bug.
-If you find a bug please [open an issue](https://github.com/mzuenni/ContestReference/issues/new).
-If you think code can be changed, improved or replaced also feel free to open an issue or make open a pull request.
-
-[](https://github.com/mzuenni/ContestReference/actions/workflows/test_all.yml/)
-[](https://github.com/mzuenni/ContestReference/actions/workflows/test_pdf.yml/)
-[](https://github.com/mzuenni/ContestReference/actions/workflows/list_missing.yml)
-## Other Resources
-The code in this repo has been accumulated over many years and the origin of the code is unfortunately unknown for most of the snippets.
-Even though much code is written from scratch, plenty of code has been copied from others and just adjusted to our coding style.
-Here is an (incomplete) list of resources that we use (besides those from previous versions):
- - https://github.com/indy256/codelibrary
- - https://github.com/spaghetti-source/algorithm
- - https://github.com/kth-competitive-programming/kactl
-
-## Previous Versions
-- https://github.com/mzuenni/ContestReference/tree/master (2018-2019)
-- https://github.com/pjungeblut/ChaosKITs (2016-2018)
-- https://github.com/niklasb/contest-algos (2012-2016)
-
-## Testing Status
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_datastructures.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_geometry.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_graph.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_math.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_other.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_string.yml/)
- - [](https://github.com/mzuenni/ContestReference/actions/workflows/test_template.yml/)
diff --git a/TestMakefile b/TestMakefile new file mode 100644 index 0000000..58d2678 --- /dev/null +++ b/TestMakefile @@ -0,0 +1,61 @@ +with-defines-subsets = $(if $2,$(call with-defines-subsets,$1,$(call dropfirst,$2)) $(call with-defines-subsets,$1.$(firstword $2),$(call dropfirst,$2)),$1) +dropfirst = $(wordlist 2,$(words $1),$1) + +source = $(dir $*)$(firstword $(subst ., ,$(notdir $*))) +flags = $(call dropfirst,$(subst ., -D,$(notdir $*))) $(CPPFLAGS) +predep = $(patsubst $(source)=%,%,$(filter $(source)=%,$(PREDEPS))) + +TESTS := \ + $(call with-defines-subsets,datastructures/test/segmentTree,SEGTREE_MUL SEGTREE_INIT_DEFAULT SEGTREE_RANGE_UPDATE) \ + $(call with-defines-subsets,datastructures/test/segmentTree.SEGTREE_FIRST_NEG,SEGTREE_INIT_DEFAULT) \ + $(call with-defines-subsets,datastructures/test/lazyPropagation,SEGTREE_FIRST_NEG SEGTREE_INIT_DEFAULT) \ + $(call with-defines-subsets,datastructures/test/lazyPropagation.SEGTREE_MAX,SEGTREE_INIT_DEFAULT) \ + datastructures/test/waveletTree \ + datastructures/test/fenwickTree \ + datastructures/test/fenwickTree2 \ + datastructures/test/treap2 \ + datastructures/test/sparseTable \ + datastructures/test/sparseTableDisjoint \ + datastructures/test/monotonicConvexHull \ + datastructures/test/persistent \ + graph/test/binary_lifting \ + graph/test/LCA_sparse \ + math/test/binomial0 + +# Dependencies which must be present before generating the .d file. +PREDEPS := \ + datastructures/test/segmentTree=datastructures/test/segmentTree.tmp.cpp \ + datastructures/test/lazyPropagation=datastructures/test/lazyPropagation.tmp.cpp + +CPPFLAGS := -include test.h -std=gnu++20 -Wall -Wextra \ + -Werror -fsanitize=address,undefined -fno-sanitize-recover -g + +test: $(TESTS:=.ok) + +cleantest: + rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) \ + datastructures/test/segmentTree.tmp.cpp + +%.ok: %.test + timeout -v 2 ./$< + @touch $@ + +.SECONDEXPANSION: +%.test: $$(source).cpp + g++ $(flags) -o $@ $< + +%.d: $$(source).cpp $$(predep) + g++ -MM -MT '$*.test $*.d' -MF '$@' $(flags) $< + +datastructures/test/segmentTree.tmp.cpp: datastructures/segmentTree.cpp \ + datastructures/test/segmentTree.awk + awk -f datastructures/test/segmentTree.awk $< > $@ +datastructures/test/lazyPropagation.tmp.cpp: \ + datastructures/lazyPropagation.cpp datastructures/test/lazyPropagation.awk + awk -f datastructures/test/lazyPropagation.awk $< > $@ + +.PHONY: test cleantest +.SECONDARY: $(TESTS:=.test) + +include $(TESTS:=.d) + diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex index c9f3d2a..4bbe507 100644 --- a/content/datastructures/datastructures.tex +++ b/content/datastructures/datastructures.tex @@ -10,7 +10,7 @@ \subsubsection{Lazy Propagation} Assignment modifications, sum queries \\ - \method{lower\_bound}{erster Index in $[l, r)$ $\geq$ x (erfordert max-combine)}{\log(n)} + \method{lower\_bound}{erster Index in $[l, r)$ $\geq x$ (erfordert max-combine)}{\log(n)} \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} @@ -20,6 +20,8 @@ \method{kth}{sort $[l, r)[k]$}{\log(\Sigma)} \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(\Sigma)} \end{methods} + $\Sigma$ ist die Gr\"o\ss e des Eingabebereichs, d.h. + $\mathit{max} - \mathit{min}$. \sourcecode{datastructures/waveletTree.cpp} \end{algorithm} \columnbreak @@ -27,15 +29,15 @@ \begin{algorithm}{Fenwick Tree} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von $[0, i]$}{\log(n)} + \method{prefix\_sum}{summe von $[0, i)$}{\log(n)} \method{update}{addiert ein Delta zu einem Element}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree.cpp} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} - \method{prefix\_sum}{summe von [$0, i]$}{\log(n)} - \method{update}{addiert ein Delta zu allen Elementen $[l, r)$. $l\leq r$!}{\log(n)} + \method{prefix\_sum}{summe von $[0, i)$}{\log(n)} + \method{update}{addiert ein Delta zu allen Elementen $[l, r)$}{\log(n)} \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} \end{algorithm} @@ -56,7 +58,7 @@ \begin{algorithm}{Range Minimum Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} - \method{queryIdempotent}{Index des Minimums in $[l, r)$. $l<r$!}{1} + \method{queryIdempotent}{Index des Minimums in $[l, r)$}{1} \end{methods} \begin{itemize} \item \code{better}-Funktion muss idempotent sein! @@ -64,6 +66,14 @@ \sourcecode{datastructures/sparseTable.cpp} \end{algorithm} +\begin{algorithm}[optional]{Range Aggregate Query} + \begin{methods} + \method{init}{baut Struktur auf}{n\*\log(n)} + \method{query}{Aggregat über $[l,r)$}{1} + \end{methods} + \sourcecode{datastructures/sparseTableDisjoint.cpp} +\end{algorithm} + \begin{algorithm}{STL-Bitset} \sourcecode{datastructures/bitset.cpp} \end{algorithm} @@ -80,30 +90,43 @@ \end{methods} \sourcecode{datastructures/LCT.cpp} \end{algorithm} -\clearpage +\columnbreak -\begin{algorithm}{Lichao} - \sourcecode{datastructures/lichao.cpp} +\begin{algorithm}{Lower Envelope (Convex Hull Optimization)} + Um aus einem Lower Envelope einen Upper Envelope zu machen (oder + umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. + \subsubsection{Monotonic} + \begin{methods} + \method{add}{add line $mx + b$, $m$ is decreasing}{1} + \method{query}{minimum value at $x$, $x$ is increasing}{1} + \end{methods} + \sourcecode{datastructures/monotonicConvexHull.cpp} + \subsubsection{Dynamic} + \begin{methods} + \method{add}{add line $mx + b$}{\log(n)} + \method{query}{minimum value at $x$}{\log(n)} + \end{methods} + \sourcecode{datastructures/dynamicConvexHull.cpp} + \subsubsection{Li Chao Tree} + Every pair of functions has at most one intersection. + + \begin{methods} + \method{insert}{add function}{\log(|xs|)} + \method{query}{minimum value at $x$, $x \in xs$}{\log(|xs|)} + \end{methods} + \sourcecode{datastructures/lichao.cpp} \end{algorithm} \begin{algorithm}{Policy Based Data Structures} - \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}! - \sourcecode{datastructures/stlPriorityQueue.cpp} - \columnbreak \sourcecode{datastructures/pbds.cpp} \end{algorithm} -\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} - Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. - \sourcecode{datastructures/monotonicConvexHull.cpp} - \sourcecode{datastructures/dynamicConvexHull.cpp} -\end{algorithm} - \begin{algorithm}{Union-Find} \begin{methods} \method{init}{legt $n$ einzelne Unions an}{n} \method{findSet}{findet den Repräsentanten}{\log(n)} \method{unionSets}{vereint 2 Mengen}{\log(n)} + \method{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)} \method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)} \end{methods} \sourcecode{datastructures/unionFind.cpp} diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 63e0e13..7148e31 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -19,13 +19,11 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden auto x = insert({m, c, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { - x--; - if (isect(x, next(x))) { - erase(next(x)); - isect(x, next(x)); - }} + --x; + while (isect(x, next(x))) erase(next(x)); + } while (x != begin() && prev(x)->p >= x->p) { - x--; + --x; isect(x, erase(next(x))); }} diff --git a/content/datastructures/fenwickTree.cpp b/content/datastructures/fenwickTree.cpp index eb5cd73..7013613 100644 --- a/content/datastructures/fenwickTree.cpp +++ b/content/datastructures/fenwickTree.cpp @@ -1,7 +1,7 @@ vector<ll> tree; void update(int i, ll val) { - for (i++; i < sz(tree); i += i & -i) tree[i] += val; + for (i++; i < ssize(tree); i += i & -i) tree[i] += val; } void init(int n) { @@ -10,6 +10,6 @@ void init(int n) { ll prefix_sum(int i) { ll sum = 0; - for (i++; i > 0; i -= i & -i) sum += tree[i]; + for (; i > 0; i &= i-1) sum += tree[i]; return sum; } diff --git a/content/datastructures/fenwickTree2.cpp b/content/datastructures/fenwickTree2.cpp index 9384e3c..7fcdbb9 100644 --- a/content/datastructures/fenwickTree2.cpp +++ b/content/datastructures/fenwickTree2.cpp @@ -1,21 +1,21 @@ vector<ll> add, mul; void update(int l, int r, ll val) { - for (int tl = l + 1; tl < sz(add); tl += tl & -tl) + for (int tl = l + 1; tl < ssize(add); tl += tl & -tl) add[tl] += val, mul[tl] -= val * l; - for (int tr = r + 1; tr < sz(add); tr += tr & -tr) + for (int tr = r + 1; tr < ssize(add); tr += tr & -tr) add[tr] -= val, mul[tr] += val * r; } -void init(vector<ll>& v) { - mul.assign(sz(v) + 1, 0); - add.assign(sz(v) + 1, 0); - for(int i = 0; i < sz(v); i++) update(i, i + 1, v[i]); +void init(vector<ll> &v) { + mul.assign(size(v) + 1, 0); + add.assign(size(v) + 1, 0); + for(int i = 0; i < ssize(v); i++) update(i, i + 1, v[i]); } ll prefix_sum(int i) { - ll res = 0; i++; - for (int ti = i; ti > 0; ti -= ti & -ti) + ll res = 0; + for (int ti = i; ti > 0; ti &= ti-1) res += add[ti] * i + mul[ti]; return res; } diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp index ab91364..82176cb 100644 --- a/content/datastructures/lazyPropagation.cpp +++ b/content/datastructures/lazyPropagation.cpp @@ -1,23 +1,22 @@ 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 - vector<T> tree; + static constexpr U UF = 1e18; // Unused value by updates + int n; + vector<T> tree; vector<U> lazy; int h; - vector<U> lazy; - vector<int> k; // size of segments (optional) + vector<ll> k; // size of segments (optional) - SegTree(const vector<T>& a) : n(sz(a) + 1), tree(2 * n, E), + SegTree(const vector<T>& a) : n(ssize(a) + 1), tree(2 * n, E), //SegTree(int size, T def = E) : n(size + 1), tree(2 * n, def), - h(__lg(2 * n)), lazy(n, UF), k(2 * n, 1) { - copy(all(a), tree.begin() + n); + lazy(n, UF), h(__lg(2 * n)), k(2 * n, 1) { + ranges::copy(a, tree.begin() + n); for (int i = n - 1; i > 0; i--) { k[i] = 2 * k[2 * i]; tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - T comb(T a, T b) {return a + b;} // Modify this + E + T comb(T a, T b) { return a + b; } // Modify this + E void apply(int i, U val) { // And this + UF tree[i] = val * k[i]; @@ -44,17 +43,17 @@ struct SegTree { void update(int l, int r, U val) { l += n, r += n; int l0 = l, r0 = r; - push(l0), push(r0 - 1); + push(l0), push(r0); for (; l < r; l /= 2, r /= 2) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } - build(l0), build(r0 - 1); + build(l0), build(r0); } T query(int l, int r) { l += n, r += n; - push(l), push(r - 1); + push(l), push(r); T resL = E, resR = E; for (; l < r; l /= 2, r /= 2) { if (l&1) resL = comb(resL, tree[l++]); diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index f1721ae..2bdeccf 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,27 +1,26 @@ -// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue -// Gerade hat kleineres pair(m, c) als alle vorherigen. -struct Line { - ll m, c; - ll operator()(ll x) {return m*x+c;} -}; +struct Envelope { + struct Line { + ll m, b; + ll operator()(ll x) { return m*x+b; } + }; -vector<Line> ls; -ll ptr = 0; + vector<Line> ls; + int ptr = 0; -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); -} + static 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); + } -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(); + void add(ll m, ll b) { + while (sz(ls) > 1 && bad(ls.end()[-2], ls.back(), {m, b})) { + ls.pop_back(); + } + ls.push_back({m, b}); + ptr = min(ptr, (int)sz(ls) - 1); } - ls.push_back({m, c}); - ptr = min(ptr, sz(ls) - 1); -} -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); -}
\ No newline at end of file + ll query(ll x) { + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); + } +}; diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp index de0ace6..734bf91 100644 --- a/content/datastructures/pbds.cpp +++ b/content/datastructures/pbds.cpp @@ -1,14 +1,22 @@ +#include <ext/pb_ds/priority_queue.hpp> +template<typename T> +using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> +auto it = pq.push(5); // O(1) +pq.modify(it, 6); // O(log n) +pq.erase(it); // O(log n) +pq.join(pq2); // O(1) +pq.swap(pq2); // O(1) + #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; -// T.order_of_key(x): number of elements strictly less than x -// *T.find_by_order(k): k-th element +T.order_of_key(x); // number of elements strictly less than x +auto it = T.find_by_order(k); // k-th element constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd -template<typename T> -struct chash { +template<typename T> struct chash { size_t operator()(T o) const { return __builtin_bswap64(hash<T>()(o) * RNG); }}; diff --git a/content/datastructures/segmentTree.cpp b/content/datastructures/segmentTree.cpp index 6b69d0b..1fbf886 100644 --- a/content/datastructures/segmentTree.cpp +++ b/content/datastructures/segmentTree.cpp @@ -4,14 +4,15 @@ struct SegTree { vector<T> tree; static constexpr T E = 0; // Neutral element for combine - SegTree(vector<T>& a) : n(sz(a)), tree(2 * n) { - //SegTree(int size, T val = E) : n(size), tree(2 * n, val) { - copy(all(a), tree.begin() + n); + SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) { + ranges::copy(a, tree.begin() + n); + //SegTree(int size, T val = E) : n(size), tree(2 * n, E) { + // fill(tree.begin() + n, tree.end(), val); for (int i = n - 1; i > 0; i--) { // remove for range update tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - T comb(T a, T b) {return a + b;} // modify this + neutral + T comb(T a, T b) { return a + b; } // modify this + neutral void update(int i, T val) { tree[i += n] = val; // apply update code diff --git a/content/datastructures/sparseTable.cpp b/content/datastructures/sparseTable.cpp index b3f946e..5e84236 100644 --- a/content/datastructures/sparseTable.cpp +++ b/content/datastructures/sparseTable.cpp @@ -6,9 +6,9 @@ struct SparseTable { return a[lidx] <= a[ridx] ? lidx : ridx; } - void init(vector<ll>* vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); st.assign(__lg(n) + 1, vector<int>(n)); iota(all(st[0]), 0); for (int j = 0; (2 << j) <= n; j++) { diff --git a/content/datastructures/sparseTableDisjoint.cpp b/content/datastructures/sparseTableDisjoint.cpp index 55165d4..39c7caa 100644 --- a/content/datastructures/sparseTableDisjoint.cpp +++ b/content/datastructures/sparseTableDisjoint.cpp @@ -7,16 +7,16 @@ struct DisjointST { return x + y; } - void init(vector<ll>* vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral)); for (int h = 0, l = 1; l <= n; h++, l *= 2) { for (int c = l; c < n + l; c += 2 * l) { for (int i = c; i < min(n, c + l); i++) - dst[h][i + 1] = combine(dst[h][i], vec->at(i)); + dst[h][i + 1] = combine(dst[h][i], vec[i]); for (int i = min(n, c); i > c - l; i--) - dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]); + dst[h][i - 1] = combine(vec[i - 1], dst[h][i]); }}} ll query(int l, int r) { diff --git a/content/datastructures/stlHashMap.cpp b/content/datastructures/stlHashMap.cpp deleted file mode 100644 index b107dde..0000000 --- a/content/datastructures/stlHashMap.cpp +++ /dev/null @@ -1,17 +0,0 @@ -#include <ext/pb_ds/assoc_container.hpp> -using namespace __gnu_pbds; - -template<typename T> -struct betterHash { - size_t operator()(T o) const { - size_t h = hash<T>()(o) ^ 42394245; //random value - h = ((h >> 16) ^ h) * 0x45d9f3b; - h = ((h >> 16) ^ h) * 0x45d9f3b; - h = ((h >> 16) ^ h); - return h; -}}; - -template<typename K, typename V, typename H = betterHash<K>> -using hashMap = gp_hash_table<K, V, H>; -template<typename K, typename H = betterHash<K>> -using hashSet = gp_hash_table<K, null_type, H>; diff --git a/content/datastructures/stlPriorityQueue.cpp b/content/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 32b2455..0000000 --- a/content/datastructures/stlPriorityQueue.cpp +++ /dev/null @@ -1,8 +0,0 @@ -#include <ext/pb_ds/priority_queue.hpp> -template<typename T> -using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> - -auto it = pq.push(5); -pq.modify(it, 6); -pq.join(pq2); -// push, join are O(1), pop, modify, erase O(log n) amortized diff --git a/content/datastructures/stlTree.cpp b/content/datastructures/stlTree.cpp deleted file mode 100644 index fbb68b9..0000000 --- a/content/datastructures/stlTree.cpp +++ /dev/null @@ -1,13 +0,0 @@ -#include <ext/pb_ds/assoc_container.hpp> -#include <ext/pb_ds/tree_policy.hpp> -using namespace std; using namespace __gnu_pbds; -template<typename T> -using Tree = tree<T, null_type, less<T>, rb_tree_tag, - tree_order_statistics_node_update>; - -int main() { - Tree<int> X; - for (int i : {1, 2, 4, 8, 16}) X.insert(i); - *X.find_by_order(3); // => 8 - X.order_of_key(10); // => 4 = min i, mit X[i] >= 10 -} diff --git a/content/datastructures/waveletTree.cpp b/content/datastructures/waveletTree.cpp index 090cdb2..55167b6 100644 --- a/content/datastructures/waveletTree.cpp +++ b/content/datastructures/waveletTree.cpp @@ -1,25 +1,20 @@ struct WaveletTree { - using it = vector<ll>::iterator; - WaveletTree *ln = nullptr, *rn = nullptr; + unique_ptr<WaveletTree> ln, rn; vector<int> b = {0}; ll lo, hi; - WaveletTree(vector<ll> in) : WaveletTree(all(in)) {} - - WaveletTree(it from, it to) : // call above one - lo(*min_element(from, to)), hi(*max_element(from, to) + 1) { + WaveletTree(auto in) : lo(*ranges::min_element(in)), + hi(*ranges::max_element(in) + 1) { ll mid = (lo + hi) / 2; - auto f = [&](ll x) {return x < mid;}; - for (it c = from; c != to; c++) { - b.push_back(b.back() + f(*c)); - } + auto f = [&](ll x) { return x < mid; }; + for (ll x: in) b.push_back(b.back() + f(x)); if (lo + 1 >= hi) return; - it pivot = stable_partition(from, to, f); - ln = new WaveletTree(from, pivot); - rn = new WaveletTree(pivot, to); + auto right = ranges::stable_partition(in, f); + ln = make_unique<WaveletTree>( + ranges::subrange(begin(in), begin(right))); + rn = make_unique<WaveletTree>(right); } - // kth element in sort[l, r) all 0-indexed ll kth(int l, int r, int k) { if (k < 0 || l + k >= r) return -1; if (lo + 1 >= hi) return lo; @@ -28,13 +23,10 @@ struct WaveletTree { else return rn->kth(l-b[l], r-b[r], k-inLeft); } - // count elements in[l, r) smaller than k int countSmaller(int l, int r, ll k) { if (l >= r || k <= lo) return 0; if (hi <= k) return r - l; return ln->countSmaller(b[l], b[r], k) + rn->countSmaller(l-b[l], r-b[r], k); } - - ~WaveletTree() {delete ln; delete rn;} }; diff --git a/content/geometry/circle.cpp b/content/geometry/circle.cpp index 6789c52..155b55c 100644 --- a/content/geometry/circle.cpp +++ b/content/geometry/circle.cpp @@ -22,7 +22,7 @@ vector<pt> circleRayIntersection(pt center, double r, double c = norm(orig - center) - r * r; double discr = b * b - 4 * a * c; if (discr >= 0) { - //t in [0, 1] => schnitt mit Segment [orig, orig + dir] + //t in [0, 1] => Schnitt mit Segment [orig, orig + dir] double t1 = -(b + sqrt(discr)) / (2 * a); double t2 = -(b - sqrt(discr)) / (2 * a); if (t1 >= 0) result.push_back(t1 * dir + orig); diff --git a/content/geometry/geometry.tex b/content/geometry/geometry.tex index 92285c4..019a264 100644 --- a/content/geometry/geometry.tex +++ b/content/geometry/geometry.tex @@ -7,7 +7,7 @@ \sourcecode{geometry/closestPair.cpp} \end{algorithm} -\begin{algorithm}{Konvexehülle} +\begin{algorithm}{Konvexe Hülle} \begin{methods} \method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)} \end{methods} @@ -40,7 +40,7 @@ \sourcecode{geometry/formulas3d.cpp} \optional{ - \subsection{3D-Kugeln} + \subsection{3D-Kugeln \opthint} \sourcecode{geometry/spheres.cpp} } @@ -48,15 +48,22 @@ \sourcecode{geometry/hpi.cpp} \end{algorithm} +\begin{algorithm}[optional]{Intersecting Segments} + \begin{methods} + \method{intersect}{finds ids of intersecting segments}{n\*\log(n)} + \end{methods} + \sourcecode{geometry/segmentIntersection.cpp} +\end{algorithm} + \begin{algorithm}[optional]{Delaunay Triangulierung} \begin{methods} \method{delaunay}{berechnet Triangulierung}{n\*\log(n)} \end{methods} - \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Traingulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. + \textbf{WICHTIG:} Wenn alle Punkte kollinear sind gibt es keine Triangulierung! Wenn 4 Punkte auf einem Kreis liegen ist die Triangulierung nicht eindeutig. \sourcecode{geometry/delaunay.cpp} \end{algorithm} \optional{ -\subsection{Geraden} +\subsection{Geraden \opthint} \sourcecode{geometry/lines.cpp} } diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index 221b5ed..3e87cde 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -10,7 +10,7 @@ struct LCA { first.assign(sz(adj), 2 * sz(adj)); idx = 0; dfs(adj, root); - st.init(&depth); + st.init(depth); } void dfs(vector<vector<int>>& adj, int v, ll d=0) { diff --git a/content/graph/binary_lifting.cpp b/content/graph/binary_lifting.cpp new file mode 100644 index 0000000..0b8c218 --- /dev/null +++ b/content/graph/binary_lifting.cpp @@ -0,0 +1,28 @@ +struct Lift { + vector<int> dep, par, jmp; + + Lift(vector<vector<int>> &adj, int root): + dep(adj.size()), par(adj.size()), jmp(adj.size(), root) { + function<void(int,int,int)> dfs = [&](int u, int p, int d) { + dep[u] = d, par[u] = p; + jmp[u] = dep[p] + dep[jmp[jmp[p]]] == 2*dep[jmp[p]] + ? jmp[jmp[p]] : p; + for (int v: adj[u]) if (v != p) dfs(v, u, d+1); + }; + dfs(root, root, 0); + } + + int depth(int v) { return dep[v]; } + int lift(int v, int d) { + while (dep[v] > d) v = dep[jmp[v]] < d ? par[v] : jmp[v]; + return v; + } + int lca(int u, int v) { + v = lift(v, dep[u]), u = lift(u, dep[v]); + while (u != v) { + auto &a = jmp[u] == jmp[v] ? par : jmp; + u = a[u], v = a[v]; + } + return u; + } +}; diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 213c597..b38e96e 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -1,12 +1,5 @@ \section{Graphen} -\begin{algorithm}{Kruskal} - \begin{methods}[ll] - berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ - \end{methods} - \sourcecode{graph/kruskal.cpp} -\end{algorithm} - \begin{algorithm}{Minimale Spannbäume} \paragraph{Schnitteigenschaft} Für jeden Schnitt $C$ im Graphen gilt: @@ -16,6 +9,12 @@ \paragraph{Kreiseigenschaft} Für jeden Kreis $K$ im Graphen gilt: Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. + + \subsection{\textsc{Kruskal}} + \begin{methods}[ll] + berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ + \end{methods} + \sourcecode{graph/kruskal.cpp} \end{algorithm} \begin{algorithm}{Heavy-Light Decomposition} @@ -28,7 +27,7 @@ \sourcecode{graph/hld.cpp} \end{algorithm} -\begin{algorithm}{Lowest Common Ancestor} +\begin{algorithm}[optional]{Lowest Common Ancestor} \begin{methods} \method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})} \method{getLCA}{findet LCA}{1} @@ -37,6 +36,17 @@ \sourcecode{graph/LCA_sparse.cpp} \end{algorithm} +\begin{algorithm}{Binary Lifting} + % https://codeforces.com/blog/entry/74847 + \begin{methods} + \method{Lift}{constructor}{\abs{V}} + \method{depth}{distance to root of vertex $v$}{1} + \method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})} + \method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})} + \end{methods} + \sourcecode{graph/binary_lifting.cpp} +\end{algorithm} + \begin{algorithm}{Centroids} \begin{methods} \method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}} @@ -99,7 +109,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/connect.cpp} \end{algorithm} -\begin{algorithm}{Erd\H{o}s-Gallai} +\begin{algorithm}{\textsc{Erd\H{o}s-Gallai}} Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$ \begin{methods} \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} @@ -170,7 +180,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/virtualTree.cpp} \end{algorithm} -\begin{algorithm}{Maximum Cardinatlity Bipartite Matching} +\begin{algorithm}{Maximum Cardinality Bipartite Matching} \label{kuhn} \begin{methods} \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} @@ -197,7 +207,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \subsection{Max-Flow} \optional{ -\subsubsection{Push Relabel} +\subsubsection{Push Relabel \opthint} \begin{methods} \method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} @@ -205,24 +215,23 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/pushRelabel.cpp} } +\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} +\begin{methods} + \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} + \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} +\end{methods} +\sourcecode{graph/dinicScaling.cpp} + \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} -\vfill\null \columnbreak -\subsubsection{Dinic's Algorithm mit Capacity Scaling} -\begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} - \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} -\end{methods} -\sourcecode{graph/dinicScaling.cpp} - \optional{ -\subsubsection{Anwendungen} +\subsubsection{Anwendungen \opthint} \begin{itemize} \item \textbf{Maximum Edge Disjoint Paths}\newline Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. diff --git a/content/latexHeaders/code.sty b/content/latexHeaders/code.sty index 3ebdda3..8a600c5 100644 --- a/content/latexHeaders/code.sty +++ b/content/latexHeaders/code.sty @@ -1,3 +1,6 @@ +\usepackage{ocgx2} +\usepackage{fontawesome} + % Colors, used for syntax highlighting. % To print this document, set all colors to black! \usepackage{xcolor} @@ -101,6 +104,32 @@ % \addtocounter{lstnumber}{-1}% %} +\ifthenelse{\isundefined{\srclink}}{}{ + \lst@AddToHook{Init}{% + \ifthenelse{\equal{\lst@name}{}}{}{% + \begin{minipage}[t][0pt]{\linewidth}% + \vspace{0pt}% + \hfill% + \begin{ocg}[printocg=never]{Source links}{srclinks}{1}% + \hfill\href{\srclink{\lst@name}}{\faExternalLink}% + \end{ocg}% + \end{minipage}% + }% + } +} + +\lst@AddToHook{DeInit}{% + \ifthenelse{\equal{\lst@name}{}}{}{% + \begin{minipage}[b][0pt]{\linewidth}% + \vspace{0pt}% + \hfill% + \begin{ocg}[printocg=never]{Source file names}{srcfiles}{0}% + \hfill\textcolor{gray}{\lst@name}% + \end{ocg}% + \end{minipage}% + }% +} + \newenvironment{btHighlight}[1][] {\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}} {\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup} diff --git a/content/latexHeaders/commands.sty b/content/latexHeaders/commands.sty index edbba1b..73a7dca 100644 --- a/content/latexHeaders/commands.sty +++ b/content/latexHeaders/commands.sty @@ -7,6 +7,11 @@ \newcommand{\code}[1]{\lstinline[breaklines=true]{#1}} \let\codeSafe\lstinline +\ifoptional + \renewcommand{\columnbreak}{} + \newcommand\opthint{\textcolor{gray}{(optional)}} +\fi + \usepackage{tikz} \usetikzlibrary{angles,quotes} @@ -17,7 +22,7 @@ \ifthenelse{\equal{#1}{optional}}{% \optional{ \needspace{4\baselineskip}% - \subsection{#2\textcolor{gray}{(optional)}}% + \subsection{#2 \opthint}% #3% } }{% diff --git a/content/latexmk.opt b/content/latexmk.opt new file mode 100644 index 0000000..88d3463 --- /dev/null +++ b/content/latexmk.opt @@ -0,0 +1,2 @@ +$jobname = 'tcr-opt'; +$pre_tex_code .= '\def\OPTIONAL{}' diff --git a/content/latexmkrc b/content/latexmkrc new file mode 100644 index 0000000..c1a56ab --- /dev/null +++ b/content/latexmkrc @@ -0,0 +1,13 @@ +@default_files = qw(tcr); +$pdf_mode = 1; +$aux_dir = "."; +$out_dir = ".."; +{ + my $commit = `git rev-parse HEAD`; + chomp $commit; + $pre_tex_code .= + '\newcommand{\srclink}[1]' + .'{https://git.gloria-mundi.eu/tcr/plain/content/#1?'.$commit.'}'; +} +&alt_tex_cmds; +$jobname = 'tcr'; diff --git a/content/math/binomial0.cpp b/content/math/binomial0.cpp index 5f2ccaa..f37aea5 100644 --- a/content/math/binomial0.cpp +++ b/content/math/binomial0.cpp @@ -10,5 +10,5 @@ void precalc() { ll calc_binom(ll n, ll k) { if (n < 0 || n < k || k < 0) return 0; - return (inv[k] * inv[n-k] % mod) * fac[n] % mod; + return (fac[n] * inv[n-k] % mod) * inv[k] % mod; } diff --git a/content/math/math.tex b/content/math/math.tex index 4ac6c9e..644fbc8 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -26,7 +26,7 @@ \end{methods}
\sourcecode{math/permIndex.cpp}
\end{algorithm}
-\clearpage
+\columnbreak
\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
%\vspace{-1.25em}
@@ -100,8 +100,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: wenn $a\equiv~b \bmod \ggT(m, n)$.
In diesem Fall sind keine Faktoren
auf der linken Seite erlaubt.
- \end{itemize}
- \sourcecode{math/chineseRemainder.cpp}
+ \end{itemize}
+ \sourcecode{math/chineseRemainder.cpp}
\end{algorithm}
\begin{algorithm}{Primzahltest \& Faktorisierung}
@@ -236,7 +236,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/legendre.cpp}
\end{algorithm}
-\begin{algorithm}{Lineares Sieb und Multiplikative Funktionen}
+\begin{algorithm}{Lineares Sieb und multiplikative Funktionen}
Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.
$\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.
@@ -250,7 +250,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
\sourcecode{math/linearSieve.cpp}
- \textbf{\textsc{Möbius}-Funktion:}
+ \textbf{\textsc{Möbius} Funktion:}
\begin{itemize}
\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat
\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat
@@ -263,7 +263,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \item $p$ prim, $k \in \mathbb{N}$:
$~\varphi(p^k) = p^k - p^{k - 1}$
- \item \textbf{Euler's Theorem:}
+ \item \textbf{\textsc{Euler}'s Theorem:}
Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
$a^{m} \equiv a \pmod{m}$
@@ -345,7 +345,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \subsection{Kombinatorik}
-\paragraph{Wilsons Theorem}
+\paragraph{\textsc{Wilson}'s Theorem}
A number $n$ is prime if and only if
$(n-1)!\equiv -1\bmod{n}$.\\
($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)
@@ -357,14 +357,14 @@ $(n-1)!\equiv -1\bmod{n}$.\\ \end{cases}
\end{align*}
-\paragraph{\textsc{Zeckendorfs} Theorem}
+\paragraph{\textsc{Zeckendorf}'s Theorem}
Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\
\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
hineinpasst.
-\paragraph{\textsc{Lucas}-Theorem}
+\paragraph{\textsc{Lucas}'s Theorem}
Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),
so gilt
\vspace{-0.75\baselineskip}
@@ -542,7 +542,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \input{math/tables/series}
\subsection{Wichtige Zahlen}
-\input{math/tables/composite}
+\input{math/tables/prime-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)}
diff --git a/content/math/tables/composite.tex b/content/math/tables/composite.tex deleted file mode 100644 index 7a6ab09..0000000 --- a/content/math/tables/composite.tex +++ /dev/null @@ -1,26 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|r||r|R||r||r|} - \hline - $10^x$ & Highly Composite & \# Divs & \# prime Divs & \# Primes \\ - \hline - 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/prime-composite.tex b/content/math/tables/prime-composite.tex new file mode 100644 index 0000000..073b4ba --- /dev/null +++ b/content/math/tables/prime-composite.tex @@ -0,0 +1,31 @@ +\begin{expandtable} +\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|} + \hline + \multirow{2}{*}{$10^x$} + & \multirow{2}{*}{Highly Composite} + & \multirow{2}{*}{\# Divs} + & \multicolumn{2}{|c|}{Prime} + & \multirow{2}{*}{\# Primes} & \multirow{2}{*}{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 \\ + \hline +\end{tabularx} +\end{expandtable} diff --git a/content/other/other.tex b/content/other/other.tex index 191a6da..59b5790 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -18,9 +18,9 @@ \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)} \\
+ 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}
@@ -30,9 +30,9 @@ \begin{expandtable}
\begin{tabularx}{\linewidth}{|Ll|}
\hline
- Bit an Position j lesen & \code{(x & (1 << j)) != 0} \\
+ Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\
Bit an Position j setzten & \code{x |= (1 << j)} \\
- Bit an Position j löschen & \code{x &= ~(1 << j)} \\
+ Bit an Position j löschen & \code{x \&= ~(1 << j)} \\
Bit an Position j flippen & \code{x ^= (1 << j)} \\
Anzahl an führenden nullen ($x \neq 0$) & \code{__builtin_clzll(x)} \\
Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\
diff --git a/content/string/string.tex b/content/string/string.tex index bedabfb..0e482bf 100644 --- a/content/string/string.tex +++ b/content/string/string.tex @@ -63,21 +63,21 @@ \end{algorithm} \clearpage -\begin{algorithm}{Lyndon und De-Bruijn} +\begin{algorithm}{\textsc{Lyndon} und \textsc{De-Bruijn}} \begin{itemize} - \item \textbf{Lyndon-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen. - \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von Lyndon-Worten zerlegt werden. - \item Für Lyndon-Worte $u, v$ mit $u<v$ gilt, dass $uv$ auch ein Lyndon-Wort ist. + \item \textbf{\textsc{Lyndon}-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen. + \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von \textsc{Lyndon}-Worten zerlegt werden. + \item Für \textsc{Lyndon}-Worte $u, v$ mit $u<v$ gilt, dass $uv$ auch ein \textsc{Lyndon}-Wort ist. \end{itemize} \begin{methods} - \method[, Durchschnitt $\Theta(1)$]{next}{lexikographisch nächstes Lyndon-Wort}{n} - \method{duval}{zerlegt $s$ in Lyndon-Worte}{n} + \method[, Durchschnitt $\Theta(1)$]{next}{lexikographisch nächstes \textsc{Lyndon}-Wort}{n} + \method{duval}{zerlegt $s$ in \textsc{Lyndon}-Worte}{n} \method{minrotation}{berechnet kleinste Rotation von $s$}{n} \end{methods} \sourcecode{string/lyndon.cpp} \sourcecode{string/duval.cpp} \begin{itemize} - \item \textbf{De-Bruijn-Sequenze $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird. + \item \textbf{\textsc{De-Bruijn}-Sequenz $\boldsymbol{B(\Sigma, n)}$:}~~~ein Wort das jedes Wort der Länge $n$ genau einmal als substring enthält (und minimal ist). Wobei $B(\Sigma, n)$ zyklisch betrachtet wird. \item es gibt $\frac{(k!)^{k^{n-1}}}{k^{n}}$ verschiedene $B(\Sigma, n)$ \item $B(\Sigma, n)$ hat Länge $\abs{\Sigma}^n$ \end{itemize} diff --git a/content/tcr.tex b/content/tcr.tex index 6d849d5..3b686ef 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -6,12 +6,20 @@ ]{scrartcl} % General information. -\newcommand{\teamname}{Kindergarten Timelimit} +\newcommand{\teamname}{Infinite Loopers} \newcommand{\university}{Karlsruhe Institute of Technology} +% Source code links (optional) +\ifdefined\srclink +\else + \newcommand{\srclink}[1]{https://git.gloria-mundi.eu/tcr/plain/#1} +\fi + % Options \newif\ifoptional -%\optionaltrue +\ifdefined\OPTIONAL + \optionaltrue +\fi % Font encoding. \usepackage[T1]{fontenc} @@ -44,6 +52,7 @@ % Content. \begin{multicols*}{3} + \raggedcolumns \input{datastructures/datastructures} \input{graph/graph} \input{geometry/geometry} @@ -54,12 +63,6 @@ \input{other/other} \input{template/template} \clearpage - \ifodd\value{page} - \else - \null - \thispagestyle{empty} - \clearpage - \fi \input{tests/test} \end{multicols*} \end{document} diff --git a/tcr.pdf b/tcr.pdf Binary files differdeleted file mode 100644 index 157dbc4..0000000 --- a/tcr.pdf +++ /dev/null @@ -0,0 +1,33 @@ +#define _GLIBCXX_DEBUG 1 +#define _GLIBCXX_SANITIZE_VECTOR 1 +#include <bits/stdc++.h> +using namespace std; +using ll = long long; + +template<typename T> +T _lg_check(T n) { + assert(n > 0); + return __lg(n); +} + +#define __lg _lg_check + +namespace util { + +mt19937 rd(0); + +int randint(int l, int r) { + assert(l <= r); + return uniform_int_distribution<int>(l, r)(rd); +} + +int randint(int x) { + assert(x > 0); + return randint(0, x-1); +} + +int randint() { + return randint(-1'000'000, +1'000'000); +} + +} diff --git a/test/GNUmakefile b/test/GNUmakefile new file mode 100644 index 0000000..5e57930 --- /dev/null +++ b/test/GNUmakefile @@ -0,0 +1,36 @@ + +TESTS = $(basename $(shell find . -path ./awk -prune -o -type f -name '*.cpp' -print)) +AWK = $(basename $(shell find . -type f -name '*.awk')) +CXX = g++ -std=gnu++20 -I awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror + +test: $(TESTS:=.ok) + +missing: + @find ../content -name '*.cpp' | sed 's|^../content/||' \ + | while read -r f ; do [ -e "$$f" ] || echo "$$f" ; done \ + | sort > missing.tmp + @sort missing.ignore | comm -3 missing.tmp - + @rm missing.tmp + +clean: + rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) + rm -rf awk/ + +%.ok: %.test + timeout --foreground --verbose 60 prlimit -s$$((1<<32)) ./$< + @touch $@ + +%.test: %.cpp + $(CXX) -o $@ $< + +awk/%: %.awk ../content/% + @mkdir -p $(dir $@) + awk -f $*.awk < ../content/$* > $@ + +%.d: %.cpp $(addprefix awk/,$(AWK)) + $(CXX) -M -MT '$*.test $*.d' -MF $@ $< + +.PHONY: test clean +.SECONDARY: $(TESTS:=.test) $(addprefix awk/,$(AWK)) + +include $(TESTS:=.d) diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp index c1ef6bf..f2a490a 100644 --- a/test/datastructures/fenwickTree.cpp +++ b/test/datastructures/fenwickTree.cpp @@ -23,7 +23,7 @@ void stress_test() { int i = Random::integer<int>(0, n); ll got = prefix_sum(i); ll expected = 0; - for (int j = 0; j <= i; j++) expected += naive[j]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -42,7 +42,7 @@ void performance_test() { int i = Random::integer<int>(0, N); int j = Random::integer<int>(0, N); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); update(i, x); hash ^= prefix_sum(j); diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index 89d5b0f..bc0753f 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -23,7 +23,7 @@ void stress_test() { int i = Random::integer<int>(0, n); ll got = prefix_sum(i); ll expected = 0; - for (int j = 0; j <= i; j++) expected += naive[j]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -44,7 +44,7 @@ void performance_test() { int j = Random::integer<int>(0, N); int k = Random::integer<int>(0, N); ll x = Random::integer<ll>(-1000, 1000); - + t.start(); update(i, j, x); hash ^= prefix_sum(k); diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index feb07f0..3030e1c 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -45,7 +45,7 @@ void performance_test() { auto [l1, r1] = Random::pair<int>(0, N + 1); auto [l2, r2] = Random::pair<int>(0, N + 1); ll x1 = Random::integer<ll>(-1000, 1000); - + t.start(); tree.update(l1, r1, x1); hash ^= tree.query(l2, r2); diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0415068..3ae7c4d 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -1,7 +1,5 @@ #include "../util.h" -struct MCH { - #include <datastructures/monotonicConvexHull.cpp> -}; +#include <datastructures/monotonicConvexHull.cpp> struct Line { ll m, c; @@ -32,7 +30,7 @@ void stress_test(ll range) { vector<Line> naive; - MCH mch; + Envelope mch; for (int k = 0; k < n; k++) { ll m = ms[k]; ll c = cs[k]; @@ -74,7 +72,7 @@ void stress_test_independent(ll range) { vector<Line> naive; - MCH mch; + Envelope mch; for (int i = 0; i < n; i++) { ll m = ms[i]; ll c = cs[i]; @@ -106,14 +104,14 @@ void performance_test() { sort(all(ms), greater<>{}); auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); sort(all(xs)); - MCH mch; + Envelope mch; hash_t hash = 0; for (int operations = 0; operations < N; operations++) { ll c = Random::integer<ll>(-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); diff --git a/test/datastructures/pbds.cpp b/test/datastructures/pbds.cpp deleted file mode 100644 index 9080332..0000000 --- a/test/datastructures/pbds.cpp +++ /dev/null @@ -1,11 +0,0 @@ -#include "../util.h" -#include <datastructures/pbds.cpp> - -int main() { - Tree<int> t1, t2; - swap(t1, t2); - hashSet<int> s1, s2; - swap(s1, s2); - hashMap<int, int> m1, m2; - swap(m1, m2); -}
\ No newline at end of file diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp index 7577694..2cfded9 100644 --- a/test/datastructures/sparseTable.cpp +++ b/test/datastructures/sparseTable.cpp @@ -8,7 +8,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); SparseTable st; - st.init(&naive); + st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); @@ -31,12 +31,12 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); SparseTable st; - st.init(&naive); + st.init(naive); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { auto [l, r] = Random::pair<int>(0, N+1); - + t.start(); hash += st.queryIdempotent(l, r); t.stop(); diff --git a/test/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp index 77bb005..258f4db 100644 --- a/test/datastructures/sparseTableDisjoint.cpp +++ b/test/datastructures/sparseTableDisjoint.cpp @@ -7,7 +7,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); DisjointST st; - st.init(&naive); + st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); @@ -28,12 +28,12 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); DisjointST st; - st.init(&naive); + st.init(naive); t.stop(); hash_t hash = 0; for (int operations = 0; operations < N; operations++) { auto [l, r] = Random::pair<int>(0, N+1); - + t.start(); hash += st.query(l, r); t.stop(); diff --git a/test/datastructures/stlHashMap.cpp b/test/datastructures/stlHashMap.cpp deleted file mode 100644 index 77976fd..0000000 --- a/test/datastructures/stlHashMap.cpp +++ /dev/null @@ -1,4 +0,0 @@ -#include "../util.h" -#include <datastructures/stlHashMap.cpp> - -int main() {}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 669f4d4..0000000 --- a/test/datastructures/stlPriorityQueue.cpp +++ /dev/null @@ -1,6 +0,0 @@ -#include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> - -int main() { - test(); -}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk deleted file mode 100644 index 99d0fb9..0000000 --- a/test/datastructures/stlPriorityQueue.cpp.awk +++ /dev/null @@ -1,37 +0,0 @@ -/auto/ { - print "void test() {" - print "pQueue<ll> pq, pq2;" - print "pq.push(1);" - print "pq.push(5);" - print "pq.push(7);" - print "pq2.push(2);" - print "pq2.push(4);" - print "pq2.push(8);" -} -END { - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;" - print "pq.pop();" - print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;" - print "cerr << \"testes example\" << endl;" - print "}" -} -{ print } diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp index 669f4d4..7405e4e 100644 --- a/test/datastructures/stlRope.cpp +++ b/test/datastructures/stlRope.cpp @@ -1,6 +1,6 @@ #include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> +#include <datastructures/stlRope.cpp> int main() { test(); -}
\ No newline at end of file +} diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk index e19b8fd..df7c361 100644 --- a/test/datastructures/stlRope.cpp.awk +++ b/test/datastructures/stlRope.cpp.awk @@ -20,7 +20,7 @@ print "vector<int> got, expected = {0,1,6,2,3,4,5,7};" } END { - print " got.push_back(*it)" + print " got.push_back(*it);" print "if (got != expected) cerr << \"error\" << endl;" print "}" } diff --git a/test/datastructures/stlTree.cpp b/test/datastructures/stlTree.cpp deleted file mode 100644 index 7bacbee..0000000 --- a/test/datastructures/stlTree.cpp +++ /dev/null @@ -1,2 +0,0 @@ -#include "../util.h" -#include <datastructures/stlTree.cpp> diff --git a/test/fuzz.sh b/test/fuzz.sh deleted file mode 100755 index c166506..0000000 --- a/test/fuzz.sh +++ /dev/null @@ -1,14 +0,0 @@ -#!/bin/bash -set -e -cd "$(dirname "$0")" - -while true -do - seed="0" - while [[ $seed == 0* ]]; do - seed=$(tr -dc '0-9' </dev/random | head -c 18) - done - echo "Fuzz using seed: $seed" - echo - ./test.sh --seed=$seed "$@" -done diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp index bf57aed..1694589 100644 --- a/test/math/cycleDetection.cpp +++ b/test/math/cycleDetection.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/cycleDetection.cpp> pair<ll, ll> naive(ll x0, function<ll(ll)> f) { diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp index d2a54b7..bd362eb 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/inversions.cpp> ll naive(const vector<ll>& v) { diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp index 16691b9..8115356 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> void stress_test() { diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp index d84524e..5e05c73 100644 --- a/test/math/kthperm_permIndex.cpp +++ b/test/math/kthperm_permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> #include <math/permIndex.cpp> diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index f0ebe76..8640980 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -6,7 +6,6 @@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { return mulSlow(a, b); } - struct RandomRecurence { vector<ll> f, c, cache; RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp index 61d34c8..6c77d74 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/permIndex.cpp> void stress_test() { diff --git a/test/missing.ignore b/test/missing.ignore new file mode 100644 index 0000000..c5f97bc --- /dev/null +++ b/test/missing.ignore @@ -0,0 +1,7 @@ +datastructures/pbds.cpp +other/pragmas.cpp +other/stuff.cpp +other/timed.cpp +tests/gcc5bug.cpp +tests/precision.cpp +tests/whitespace.cpp diff --git a/test/test.sh b/test/test.sh deleted file mode 100755 index 6609f1a..0000000 --- a/test/test.sh +++ /dev/null @@ -1,114 +0,0 @@ -#!/bin/bash -set -e -cd "$(dirname "$0")" -ulimit -s 4000000 -export MALLOC_PERTURB_="$((2#01011001))" -shopt -s lastpipe - -declare -A cppstandard -cppstandard["string/suffixArray.cpp"]="gnu++20" -cppstandard["other/pbs.cpp"]="gnu++20" -seedmacro="" - -process_awk() { - awk_file=$(realpath --relative-to="${PWD}" "${1}") - cpp_file=${awk_file%.awk} - folder=$(dirname $awk_file) - #echo "$awk_file" - mkdir -p "./awk/$folder" - awk -f "$awk_file" < "../content/$cpp_file" > "./awk/$cpp_file" -} - -test_file() { - file=$(realpath --relative-to="${PWD}" "${1}") - echo "$file:" - echo "compiling..." - std="gnu++17" - if [[ -v cppstandard[$file] ]]; then - std=${cppstandard[$file]} - fi - g++ -std=$std "$file" -I ./awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro - echo "running..." - timeout --foreground 60s ./a.out - echo "" - rm ./a.out -} - -list_missing() { - declare -A ignore - ignore["other/bitOps.cpp"]=1 - ignore["other/pragmas.cpp"]=1 - ignore["other/stuff.cpp"]=1 - ignore["other/timed.cpp"]=1 - ignore["tests/gcc5bug.cpp"]=1 - ignore["tests/precision.cpp"]=1 - ignore["tests/whitespace.cpp"]=1 - - total=0 - missing=0 - - if [[ ! -v $1 ]]; then - echo "missing tests:" - fi - find ../content/ -type f -name '*.cpp' -print0 | sort -z | while read -d $'\0' file - do - total=$((total+1)) - file=${file#../content/} - if [ ! -f "$file" ] && [[ ! -v ignore["$file"] ]]; then - missing=$((missing+1)) - if [[ ! -v $1 ]]; then - echo " $file" - fi - fi - done - if [[ -v $1 ]]; then - covered=$((total-missing)) - coverage=$((100*covered/total)) - echo "REQUIRED=$(( total < 4 ? 0 : total - 4 ))" - echo "TOTAL=$total" - echo "COVERED=$covered" - echo "MISSING=$missing" - fi -} - -coverage() { - list_missing 1 -} - -rm -rf ./awk/ -find . -type f -path '*.awk' -print0 | sort -z | while read -d $'\0' file -do - process_awk "$file" -done - -if [ "$#" -ne 0 ]; then - for arg in "$@" - do - if [[ $arg == "--awk" ]]; then - echo "processed all awk files" - elif [[ $arg == "--missing" ]]; then - list_missing - elif [[ $arg == "--coverage" ]]; then - coverage - elif [[ $arg == --seed=* ]]; then - seedmacro="-DSEED=${arg:7}ll" - elif [ -d "$arg" ]; then - dir=$(realpath --relative-to="${PWD}" "$arg") - find . -type f -path "./${dir}/*.cpp" -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file - do - test_file "$file" - done - elif [ -f "$arg" ]; then - test_file "$arg" - else - echo "did not recognize: $arg" - fi - done -else - find . -type f -path '*.cpp' -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file - do - test_file "$file" - done - list_missing -fi - diff --git a/test/util.h b/test/util.h index 6f23b82..e123fc2 100644 --- a/test/util.h +++ b/test/util.h @@ -168,6 +168,30 @@ namespace Random { exit(1); } +namespace detail { + double benchmark() { + mt19937 rng(734820734); + vector<unsigned> a(10000000); + for (unsigned &x: a) x = rng(); + chrono::steady_clock::time_point start = chrono::steady_clock::now(); + vector<unsigned> dp(ssize(a)+1, numeric_limits<unsigned>::max()); + int res = 0; + for (unsigned x: a) { + auto it = ranges::upper_bound(dp, x); + res = max(res, (int)(it - begin(dp))); + *it = x; + } + chrono::steady_clock::time_point end = chrono::steady_clock::now(); + assert(res == 6301); + double t = + chrono::duration_cast<chrono::duration<double, milli>>(end - start) + .count(); + return 30/t; + } + + double speed = benchmark(); +} + struct timer { bool running = false; double time = 0; @@ -183,7 +207,7 @@ struct timer { auto end = chrono::steady_clock::now(); if (!running) cerr << "timer not running!" << FAIL; running = false; - time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count(); + time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count() * detail::speed; } void reset() { @@ -208,7 +232,7 @@ namespace c20 { return {{a[I]...}}; } } - + template<class T, std::size_t N> constexpr std::array<std::remove_cv_t<T>, N> to_array(T (&a)[N]) { return c20::detail::to_array_impl(a, std::make_index_sequence<N>{}); @@ -413,3 +437,10 @@ ld float_error(ld given, ld expected) { } return numeric_limits<ld>::infinity(); } + +#include <ext/pb_ds/assoc_container.hpp> +template<typename T> +using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, + __gnu_pbds::rb_tree_tag, + __gnu_pbds::tree_order_statistics_node_update>; + |