diff options
| -rw-r--r-- | .github/workflows/test_all.yml | 2 | ||||
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | README.md | 24 | ||||
| -rw-r--r-- | content/latexHeaders/math.sty | 1 | ||||
| -rw-r--r-- | content/other/bitOps.cpp | 7 | ||||
| -rw-r--r-- | content/other/josephus2.cpp | 9 | ||||
| -rw-r--r-- | content/other/other.tex | 34 | ||||
| -rw-r--r-- | content/other/pbs.cpp | 14 | ||||
| -rw-r--r-- | content/other/recover.cpp | 13 | ||||
| -rw-r--r-- | content/other/stuff.cpp | 6 | ||||
| -rw-r--r-- | tcr.pdf | bin | 691029 -> 691692 bytes | |||
| -rw-r--r-- | test/datastructures/dynamicConvexHull.cpp | 2 | ||||
| -rw-r--r-- | test/datastructures/stlPriorityQueue.cpp | 6 | ||||
| -rw-r--r-- | test/datastructures/stlPriorityQueue.cpp.awk | 37 | ||||
| -rw-r--r-- | test/datastructures/stlRope.cpp | 6 | ||||
| -rw-r--r-- | test/datastructures/stlRope.cpp.awk | 27 | ||||
| -rw-r--r-- | test/other/bitOps.cpp | 59 | ||||
| -rw-r--r-- | test/other/bitOps.cpp.awk | 9 | ||||
| -rw-r--r-- | test/other/josephus2.cpp | 2 | ||||
| -rw-r--r-- | test/other/recover.cpp | 44 | ||||
| -rwxr-xr-x | test/test.sh | 28 |
21 files changed, 277 insertions, 55 deletions
diff --git a/.github/workflows/test_all.yml b/.github/workflows/test_all.yml index eddc002..55c33ab 100644 --- a/.github/workflows/test_all.yml +++ b/.github/workflows/test_all.yml @@ -8,7 +8,7 @@ jobs: os: [ubuntu-latest, ubuntu-22.04] name: Test all (${{ matrix.os }}) runs-on: ${{ matrix.os }} - timeout-minutes: 10 + timeout-minutes: 20 steps: - uses: actions/checkout@v4 - run: ./test/test.sh @@ -225,3 +225,5 @@ TSWLatexianTemp* build/* # dont ignore build tcr !tcr.pdf +# ignore build test awk files +test/awk/* @@ -2,18 +2,21 @@ > [!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 pdf with working links.
-This document is used by the KIT teams for ICPC style contests since roughly 2019.
+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 usefull as possible we try to (automatically) stress test all code in this repository.
-Non the less not all code is tested and tests might not catch every bug.
-If you happen to 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 oben a pull request.
+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/)
## 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 many code is written from scratch there is also plenty of code that has been copied from others and just been adjusted to our coding style.
+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
@@ -23,3 +26,12 @@ Here is an (incomplete) list of resources that we use (besides those from previo - 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/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..6cf872a 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,19 +1,19 @@ // Q = # of queries, bucket sort is sometimes faster -vector<int> low(Q, 0), high(Q, MAX_OPERATIONS); +vector<int> low(Q, 0), high(Q, MAX_OPERATIONS + 1); while (true) { vector<pair<int, int>> 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)); // 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; + else low[i] = mid; }} // answer in low (and high) diff --git a/content/other/recover.cpp b/content/other/recover.cpp new file mode 100644 index 0000000..1a593f0 --- /dev/null +++ b/content/other/recover.cpp @@ -0,0 +1,13 @@ +ll sq(ll x) {return x*x;} + +array<ll, 2> recover(ll c, ll m) { + array<ll, 2> u = {m, 0}, v = {c, 1}; + while (m <= 2 * sq(v[0])) { + ll q = u[0] / v[0]; + u[0] -= q * v[0]; + u[1] -= q * v[1]; + swap(u, v); + } + if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1}; + return v; +} diff --git a/content/other/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 <bits/stdc++.h> - // 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<point2, decltype(comp)> set1(comp); diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index f163397..e0345af 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -55,7 +55,7 @@ void performance_test() { hash += hd.query(x); t.stop(); } - if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + if (t.time > 200) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp new file mode 100644 index 0000000..669f4d4 --- /dev/null +++ b/test/datastructures/stlPriorityQueue.cpp @@ -0,0 +1,6 @@ +#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 new file mode 100644 index 0000000..99d0fb9 --- /dev/null +++ b/test/datastructures/stlPriorityQueue.cpp.awk @@ -0,0 +1,37 @@ +/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 new file mode 100644 index 0000000..669f4d4 --- /dev/null +++ b/test/datastructures/stlRope.cpp @@ -0,0 +1,6 @@ +#include "../util.h" +#include <datastructures/stlPriorityQueue.cpp> + +int main() { + test(); +}
\ No newline at end of file diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk new file mode 100644 index 0000000..e19b8fd --- /dev/null +++ b/test/datastructures/stlRope.cpp.awk @@ -0,0 +1,27 @@ +/rope<int> v;/ { + print "void test() {" + print "ll num = 5;" + print "ll start = 2;" + print "ll length = 4;" + print "ll offset = 3;" +} +/v.push_back(num);/ { + print "v.push_back(0);" + print "v.push_back(1);" + print "v.push_back(2);" + print "v.push_back(3);" + print "v.push_back(4);" +} +/rope<int> sub/ { + print "v.push_back(6);" + print "v.push_back(7);" +} +/for\(auto it/ { + print "vector<int> got, expected = {0,1,6,2,3,4,5,7};" +} +END { + print " got.push_back(*it)" + print "if (got != expected) cerr << \"error\" << endl;" + print "}" +} +{ print } diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp new file mode 100644 index 0000000..44f6297 --- /dev/null +++ b/test/other/bitOps.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#include <other/bitOps.cpp> + +void test_subsets() { + int queries = 0; + for (int i = 0; i < 1000'000; i++) { + int mask = 0; + int limBits = Random::integer<int>(1, 15); + for (int j = 0; j < limBits; j++) { + mask |= 1 << Random::integer<int>(0, 31); + } + + int expeced = 1 << __builtin_popcount(mask); + int last = -1; + int seen = 1; + subsets(mask, [&](int active){ + if (active <= 0) cerr << "error active: " << active << FAIL; + if (last >= 0 && active >= last) cerr << "error active: " << active << ", last: " << last << FAIL; + last = active; + seen++; + }); + if (expeced != seen) cerr << "got: " << seen << ", expeced: " << expeced << FAIL; + queries++; + } + cerr << "tested subsets queries: " << queries << endl; +} + +ll naive(ll x) { + vector<ll> bits; + for (ll i = 0; i < 64; i++) { + bits.push_back(x & 1); + x >>= 1; + } + reverse(all(bits)); + next_permutation(all(bits)); + reverse(all(bits)); + x = 0; + for (ll i = 0, j = 1; i < 64; i++, j <<= 1) { + if (bits[i] != 0) x |= j; + } + return x; +} + +void test_nextPerm() { + int queries = 0; + for (int i = 0; i < 1000'000; i++) { + ll x = 4;//Random::integer<ll>(1, LL::INF); + ll got = nextPerm(x); + ll expeced = naive(x); + if (got != expeced) cerr << x << ": got: " << got << ", expeced: " << expeced << FAIL; + queries++; + } + cerr << "tested nextPerm queries: " << queries << endl; +} + +int main() { + test_subsets(); + test_nextPerm(); +}
\ No newline at end of file diff --git a/test/other/bitOps.cpp.awk b/test/other/bitOps.cpp.awk new file mode 100644 index 0000000..f1abcfb --- /dev/null +++ b/test/other/bitOps.cpp.awk @@ -0,0 +1,9 @@ +/for \(int subset/ { + print "template<typename F>" + print "void subsets(int bitmask, F&& f) {" +} +/\/\/ Nächste Permutation/ { + print " {f(subset);}" + print "}" +} +{ print } diff --git a/test/other/josephus2.cpp b/test/other/josephus2.cpp index d28fe0d..85a9d28 100644 --- a/test/other/josephus2.cpp +++ b/test/other/josephus2.cpp @@ -31,7 +31,7 @@ void performance_test() { hash += rotateLeft(1'000'000'000'000'000'000ll + i); } t.stop(); - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/other/recover.cpp b/test/other/recover.cpp new file mode 100644 index 0000000..72853e5 --- /dev/null +++ b/test/other/recover.cpp @@ -0,0 +1,44 @@ +#include "../util.h" +#include <other/recover.cpp> +#include <math/shortModInv.cpp> + +void stress_test() { + ll queries = 0; + timer t; + for (int i = 0; i < 500; i++) { + ll p = Random::prime<ll>(10000); + for (ll j = 0; 2*j*j < p; j++) { + for (ll b = 1; 2*b*b < p; b++) { + if (gcd(j, b) != 1) continue; + for (ll a : {-j, j}) { + ll c = a * multInv(b, p); + + t.start(); + auto [x, y] = recover(c, p); + t.stop(); + + if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL; + queries++; + } + } + } + for (ll c = 0; c < p; c++) { + t.start(); + auto [x, y] = recover(c, p); + t.stop(); + + if (y < 0) continue; + if (y == 0) cerr << "error: y=0" << FAIL; + ll got = (((x * multInv(y, p)) % p) + p) % p; + if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} diff --git a/test/test.sh b/test/test.sh index d34c446..3cb5c9c 100755 --- a/test/test.sh +++ b/test/test.sh @@ -8,6 +8,15 @@ declare -A cppstandard cppstandard["string/suffixArray.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:" @@ -16,7 +25,7 @@ test_file() { if [[ -v cppstandard[$file] ]]; then std=${cppstandard[$file]} fi - g++ -std=$std "$file" -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro + g++ -std=$std "$file" -I ./awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro echo "running..." timeout --foreground 60s ./a.out echo "" @@ -25,10 +34,7 @@ test_file() { list_missing() { declare -A ignore - ignore["datastructures/stlPriorityQueue.cpp"]=1 - ignore["datastructures/stlRope.cpp"]=1 ignore["other/bitOps.cpp"]=1 - ignore["other/pbs.cpp"]=1 ignore["other/pragmas.cpp"]=1 ignore["other/stuff.cpp"]=1 ignore["other/timed.cpp"]=1 @@ -46,16 +52,24 @@ list_missing() { done } +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 == "--missing" ]]; then + if [[ $arg == "--awk" ]]; then + echo "processed all awk files" + elif [[ $arg == "--missing" ]]; then list_missing 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" -print0 | sort -z | while read -d $'\0' file + find . -type f -path "./${dir}/*.cpp" -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file do test_file "$file" done @@ -66,7 +80,7 @@ if [ "$#" -ne 0 ]; then fi done else - find . -type f -path '*.cpp' -print0 | sort -z | while read -d $'\0' file + find . -type f -path '*.cpp' -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file do test_file "$file" done |