diff options
34 files changed, 468 insertions, 143 deletions
@@ -220,3 +220,7 @@ TSWLatexianTemp* *-tags.tex *~ + +# files produced by the testing system +*.test +*.ok @@ -1,5 +1,39 @@ -all: +TESTS = \ + datastructures/test/fenwickTree.test \ + datastructures/test/fenwickTree2.test \ + graph/test/binary_lifting.test \ + graph/test/LCA_sparse.test + +pdf: latexmk -pdf tcr -clean: + +all: pdf test + +test: $(TESTS:.test=.ok) + +clean: cleanpdf cleantest + +cleanpdf: latexmk -c tcr rm -f *.thm + +cleantest: + rm -f $(TESTS) $(TESTS:.test=.ok) + +%.ok: %.test + timeout -v 1 ./$< + @touch $@ +%.test: %.cpp test.h + g++ -include test.h -std=gnu++20 -Wall -Wextra -Wpedantic -Werror \ + -fsanitize=address,undefined -g -o $@ $< + +datastructures/test/fenwickTree.test: datastructures/test/fenwickTree.cpp \ + datastructures/fenwickTree.cpp +datastructures/test/fenwickTree2.test: datastructures/test/fenwickTree2.cpp \ + datastructures/fenwickTree2.cpp +graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ + graph/binary_lifting.cpp graph/test/util.cpp +graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ + graph/LCA_sparse.cpp datastructures/sparseTable.cpp graph/test/util.cpp + +.PHONY: all pdf test clean cleanpdf cleantest diff --git a/README.md b/README.md deleted file mode 100644 index 7a518c5..0000000 --- a/README.md +++ /dev/null @@ -1,3 +0,0 @@ -# Team Contest Reference
-a modified version of the team contest reference for team ChaosKITs from Karlsruhe, Germany.
-https://github.com/pjungeblut/ChaosKITs
diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp deleted file mode 100644 index 401cca4..0000000 --- a/datastructures/RMQ.cpp +++ /dev/null @@ -1,27 +0,0 @@ -vector<int> values; -vector<vector<int>> rmq; - -int select(int a, int b) { - return values[a] <= values[b] ? a : b; -} - -void build() { - for(int i = 0, s = 1, ss = 1; s <= sz(values); ss=s, s*=2, i++) { - for(int l = 0; l + s <= sz(values); l++) { - if(i == 0) rmq[0][l] = l; - else { - int r = l + ss; - rmq[i][l] = select(rmq[i-1][l], rmq[i-1][r]]); -}}}} - -void init(const vector<int>& v) { - values = v; - rmq = vector<vector<int>>(__lg(sz(values))+1, vector<int>(sz(values))); - build(); -} - -int query(int l, int r) { - if(l >= r) return l; - int s = __lg(r-l); r = r - (1 << s); - return select(rmq[s][l],rmq[s][r]); -} diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4139219..37a1dc2 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -17,14 +17,14 @@ \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{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} @@ -122,16 +122,6 @@ \sourcecode{datastructures/stlHashMap.cpp} \end{algorithm} - - -\begin{algorithm}[optional]{Range Minimum Query} - \begin{methods} - \method{init}{baut Struktur auf}{n\*\log(n)} - \method{query}{Index des Minimums in [l, r)}{1} - \end{methods} - \sourcecode{datastructures/RMQ.cpp} -\end{algorithm} - \begin{algorithm}[optional]{Erste unbenutzte natürliche Zahl} \begin{methods} \method{get\_first\_unused}{findet kleinste unbenutzte Zahl}{\log(n)} diff --git a/datastructures/fenwickTree.cpp b/datastructures/fenwickTree.cpp index cac3cf8..6c5ed91 100644 --- a/datastructures/fenwickTree.cpp +++ b/datastructures/fenwickTree.cpp @@ -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 & (-i))) sum += tree[i]; return sum; } diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp index ff87e2e..43c3a32 100644 --- a/datastructures/fenwickTree2.cpp +++ b/datastructures/fenwickTree2.cpp @@ -14,7 +14,7 @@ void init(vector<ll>& v) { } ll prefix_sum (int i) { - ll res = 0; i++; + ll res = 0; for (int ti = i; ti > 0; ti -= ti&(-ti)) res += add[ti] * i + mul[ti]; return res; diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp new file mode 100644 index 0000000..f9dd619 --- /dev/null +++ b/datastructures/test/fenwickTree.cpp @@ -0,0 +1,26 @@ +#include "../fenwickTree.cpp" + +void test(int n) { + vector<ll> naive(n); + init(n); + + for (int i = 0; i < 1000; i++) { + int p = util::randint(n); + ll delta = util::randint(); + update(p, delta); + naive[p] += delta; + + int r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp new file mode 100644 index 0000000..18ebcb7 --- /dev/null +++ b/datastructures/test/fenwickTree2.cpp @@ -0,0 +1,28 @@ +#include "../fenwickTree2.cpp" + +void test(int n) { + vector<ll> naive(n); + for (int i = 0; i < n; i++) naive[i] = util::randint(); + init(naive); + + for (int i = 0; i < 1000; i++) { + int l = util::randint(n), r = util::randint(n); + if (l > r) swap(l, r); + ll delta = util::randint(); + update(l, r, delta); + for (int i = l; i < r; i++) naive[i] += delta; + + r = util::randint(n+1); + + ll naive_result = 0; + for (int i = 0; i < r; i++) naive_result += naive[i]; + ll fenwick_result = prefix_sum(r); + assert(naive_result == fenwick_result); + } +} + +int main() { + test(1); + test(100); + test(1000); +} diff --git a/geometry/circle.cpp b/geometry/circle.cpp index 8ebc800..fab4150 100644 --- a/geometry/circle.cpp +++ b/geometry/circle.cpp @@ -1,4 +1,4 @@ -// berechnet die Schnittpunkte von zwei kreisen +// berechnet die Schnittpunkte von zwei Kreisen // (Kreise dürfen nicht gleich sein!) vector<pt> circleIntersection(pt c1, double r1, pt c2, double r2) { @@ -13,7 +13,7 @@ vector<pt> circleIntersection(pt c1, double r1, } // berechnet die Schnittpunkte zwischen -// einem Kreis(Kugel) und einer Grade 2d und 3d +// einem Kreis(Kugel) und einer Grade (2D und 3D) vector<pt> circleRayIntersection(pt center, double r, pt orig, pt dir) { vector<pt> result; @@ -22,7 +22,7 @@ vector<pt> circleRayIntersection(pt center, double r, double c = dot(orig - center, 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/geometry/geometry.tex b/geometry/geometry.tex index d3e1671..d740f46 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -7,12 +7,12 @@ \sourcecode{geometry/closestPair.cpp} \end{algorithm} -\begin{algorithm}{Konvexehülle} +\begin{algorithm}{Konvexe Hülle} \begin{methods} - \method{convexHull}{berechnet Konvexehülle}{n\*\log(n)} + \method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)} \end{methods} \begin{itemize} - \item Konvexehülle gegen den Uhrzeigersinn sortiert + \item konvexe Hülle gegen den Uhrzeigersinn sortiert \item nur Eckpunkte enthalten(für alle Punkte = im CCW Test entfernen) \item erster und letzter Punkt sind identisch \end{itemize} @@ -28,7 +28,7 @@ \sourcecode{geometry/antipodalPoints.cpp} \end{algorithm} -\subsection{Formeln~~--~\texttt{std::complex}} +\subsection{Formeln -- \texttt{std::complex}} \sourcecode{geometry/formulars.cpp} \sourcecode{geometry/linesAndSegments.cpp} \sourcecode{geometry/sortAround.cpp} @@ -37,7 +37,7 @@ \sourcecode{geometry/polygon.cpp} \sourcecode{geometry/circle.cpp} -\subsection{Formeln - 3D} +\subsection{Formeln -- 3D} \sourcecode{geometry/formulars3d.cpp} \optional{ diff --git a/geometry/spheres.cpp b/geometry/spheres.cpp index abffde5..b5d3644 100644 --- a/geometry/spheres.cpp +++ b/geometry/spheres.cpp @@ -1,4 +1,4 @@ -// Great Cirlce Distance mit Längen- und Breitengrad. +// Great Circle Distance mit Längen- und Breitengrad. double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) { pLat *= PI / 180; pLon *= PI / 180; @@ -10,7 +10,7 @@ double gcDist(double pLat, double pLon, sin(pLat) * sin(qLat)); } -// Great Cirlce Distance mit kartesischen Koordinaten. +// Great Circle Distance mit kartesischen Koordinaten. double gcDist(point p, point q) { return acos(p.x * q.x + p.y * q.y + p.z * q.z); } diff --git a/graph/LCA.cpp b/graph/LCA.cpp deleted file mode 100644 index 7debf8f..0000000 --- a/graph/LCA.cpp +++ /dev/null @@ -1,24 +0,0 @@ -vector<vector<int>> adj(); -vector<int> visited(); -vector<int> first(); -vector<int> depth(); - -void initLCA(int gi, int d, int& c) { - visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++; - for(int gn : adj[gi]) { - initLCA(gn, d+1, c); - visited[c] = gi, depth[c] = d, c++; -}} - -int getLCA(int a, int b) { - return visited[query(min(first[a], first[b]), max(first[a], first[b]))]; -} - -void exampleUse() { - int c = 0; - visited = vector<int>(2*sz(adj)); - first = vector<int>(sz(adj), 2*sz(adj)); - depth = vector<int>(2*sz(adj)); - initLCA(0, 0, c); - init(depth); -} diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 2a864c0..0f2fe22 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -13,13 +13,13 @@ struct LCA { st.init(&depth); } - void dfs(vector<vector<int>>& adj, int v, ll d=0, int p=-1) { + void dfs(vector<vector<int>>& adj, int v, ll d=0) { visited[idx] = v, depth[idx] = d; first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { if (first[u] == 2 * sz(adj)) { - dfs(adj, u, d + 1, v); + dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} diff --git a/graph/binary_lifting.cpp b/graph/binary_lifting.cpp new file mode 100644 index 0000000..0b8c218 --- /dev/null +++ b/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/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index 9772706..0df464b 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -1,12 +1,12 @@ constexpr int maxEdges = 128; using cycle = bitset<maxEdges>; -struct cylces { +struct cycles { vector<vector<pair<int, int>>> adj; vector<bool> seen; vector<cycle> paths, base; vector<pair<int, int>> edges; - cylces(int n) : adj(n), seen(n), paths(n) {} + cycles(int n) : adj(n), seen(n), paths(n) {} void addEdge(int u, int v) { adj[u].push_back({v, sz(edges)}); diff --git a/graph/graph.tex b/graph/graph.tex index 6fbdb74..4394192 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -15,7 +15,7 @@ \end{itemize} \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} @@ -24,6 +24,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}} @@ -60,7 +71,7 @@ Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. \end{algorithm} -\begin{algorithm}{Kruskal} +\begin{algorithm}{\textsc{Kruskal}} \begin{methods}[ll] berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ \end{methods} @@ -92,7 +103,7 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$ -\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})} @@ -212,9 +223,9 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/pushRelabel2.cpp} -\subsubsection{Dinic's Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} \begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} + \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} diff --git a/graph/test/LCA_sparse.cpp b/graph/test/LCA_sparse.cpp new file mode 100644 index 0000000..c45111c --- /dev/null +++ b/graph/test/LCA_sparse.cpp @@ -0,0 +1,61 @@ +#include "util.cpp" +#include "../../datastructures/sparseTable.cpp" +#include "../LCA_sparse.cpp" + +void test(vector<vector<int>> &adj, int root) { + int n = adj.size(); + + vector<int> parent(n); + function<void(int,int)> dfs = [&](int u, int p) { + parent[u] = p; + for (int v: adj[u]) if (v != p) dfs(v, u); + }; + dfs(root, -1); + + function<bool(int, int)> is_ancestor = [&](int u, int v) { + while (v != -1 && u != v) v = parent[v]; + return u == v; + }; + function<int(int)> depth = [&](int v) { + int r = 0; + while ((v = parent[v]) != -1) r++; + return r; + }; + + LCA lca; + lca.init(adj, root); + for (int i = 0; i < n; i++) assert(lca.getDepth(i) == depth(i)); + for (int i = 0; i < 1000; i++) { + int u = util::randint(n); + int v = util::randint(n); + int l = lca.getLCA(u, v); + assert(is_ancestor(l, u)); + assert(is_ancestor(l, v)); + for (int p = parent[l]; int c: adj[l]) { + if (c == p) continue; + assert(!is_ancestor(c, u) || !is_ancestor(c, v)); + } + } +} + +int main() { + { + // Single vertex + vector<vector<int>> adj(1); + test(adj, 0); + } + { + // Path + vector<vector<int>> adj = util::path(100); + int left = 0, mid = 40, right = 99; + util::shuffle_graph(adj, left, mid, right); + test(adj, left); + test(adj, mid); + test(adj, right); + } + { + // Random + vector<vector<int>> adj = util::random_tree(1000); + test(adj, 0); + } +} diff --git a/graph/test/binary_lifting.cpp b/graph/test/binary_lifting.cpp new file mode 100644 index 0000000..05b903a --- /dev/null +++ b/graph/test/binary_lifting.cpp @@ -0,0 +1,67 @@ +#include "util.cpp" +#include "../binary_lifting.cpp" + +void test(vector<vector<int>> &adj, int root) { + int n = adj.size(); + + vector<int> parent(n); + function<void(int,int)> dfs = [&](int u, int p) { + parent[u] = p; + for (int v: adj[u]) if (v != p) dfs(v, u); + }; + dfs(root, -1); + + function<bool(int, int)> is_ancestor = [&](int u, int v) { + while (v != -1 && u != v) v = parent[v]; + return u == v; + }; + function<int(int)> depth = [&](int v) { + int r = 0; + while ((v = parent[v]) != -1) r++; + return r; + }; + + Lift lift(adj, root); + for (int i = 0; i < n; i++) assert(lift.depth(i) == depth(i)); + for (int i = 0; i < 1000; i++) { + int v = util::randint(n); + int d = util::randint(n); + int u = lift.lift(v, d); + assert(is_ancestor(u, v)); + if (d <= depth(v)) assert(depth(u) == d); + else assert(u == v); + } + for (int i = 0; i < 1000; i++) { + int u = util::randint(n); + int v = util::randint(n); + int lca = lift.lca(u, v); + assert(is_ancestor(lca, u)); + assert(is_ancestor(lca, v)); + for (int p = parent[lca]; int c: adj[lca]) { + if (c == p) continue; + assert(!is_ancestor(c, u) || !is_ancestor(c, v)); + } + } +} + +int main() { + { + // Single vertex + vector<vector<int>> adj(1); + test(adj, 0); + } + { + // Path + vector<vector<int>> adj = util::path(100); + int left = 0, mid = 40, right = 99; + util::shuffle_graph(adj, left, mid, right); + test(adj, left); + test(adj, mid); + test(adj, right); + } + { + // Random + vector<vector<int>> adj = util::random_tree(1000); + test(adj, 0); + } +} diff --git a/graph/test/util.cpp b/graph/test/util.cpp new file mode 100644 index 0000000..8c14b5c --- /dev/null +++ b/graph/test/util.cpp @@ -0,0 +1,60 @@ + +namespace util { + +void shuffle_adj_lists(vector<vector<int>> &adj) { + for (auto &a: adj) ranges::shuffle(a, rd); +} + +vector<vector<int>> random_tree(int n) { + vector<vector<int>> adj(n); + + vector<vector<int>> components(n); + for (int i = 0; i < n; i++) components[i].push_back(i); + while (components.size() > 1) { + int c1 = randint(components.size()); + int c2 = randint(components.size()-1); + c2 += (c2 >= c1); + + int v1 = components[c1][randint(components[c1].size())]; + int v2 = components[c2][randint(components[c2].size())]; + + adj[v1].push_back(v2); + adj[v2].push_back(v1); + + if (components[c1].size() < components[c2].size()) swap(c1, c2); + for (int v: components[c2]) components[c1].push_back(v); + swap(components[c2], components.back()); + components.pop_back(); + } + + shuffle_adj_lists(adj); + return adj; +} + +vector<vector<int>> path(int n) { + vector<vector<int>> adj(n); + for (int i = 1; i < n; i++) { + adj[i-1].push_back(i); + adj[i].push_back(i-1); + } + return adj; +} + +template<typename... Ts> +void shuffle_graph(vector<vector<int>> &adj, Ts &...vertex) { + int n = adj.size(); + vector<int> perm(n); + iota(perm.begin(), perm.end(), 0); + ranges::shuffle(perm, rd); + + vector<vector<int>> new_adj(n); + for (int i = 0; i < n; i++) { + auto &a = new_adj[perm[i]] = move(adj[i]); + for (int &v: a) v = perm[v]; + } + adj = move(new_adj); + shuffle_adj_lists(adj); + ((vertex = perm[vertex]), ...); +} + +} diff --git a/latexHeaders/code.sty b/latexHeaders/code.sty index a889596..af7f817 100644 --- a/latexHeaders/code.sty +++ b/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/math/linearRecurence.cpp b/math/linearRecurrence.cpp index 2501e64..2501e64 100644 --- a/math/linearRecurence.cpp +++ b/math/linearRecurrence.cpp diff --git a/math/math.tex b/math/math.tex index 8ccc55e..a9e4c74 100644 --- a/math/math.tex +++ b/math/math.tex @@ -151,21 +151,21 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/discreteNthRoot.cpp}
\end{algorithm}
-\begin{algorithm}{Linearessieb 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.
\begin{methods}
\method{sieve}{berechnet Primzahlen und co.}{N}
- \method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1}
+ \method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1}
- \method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}}
+ \method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}}
\end{methods}
\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
\sourcecode{math/linearSieve.cpp}
- \textbf{\textsc{Möbius} Funtkion:}
+ \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
@@ -178,7 +178,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}$
@@ -282,18 +282,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{methods}
\sourcecode{math/piLehmer.cpp}
-\begin{algorithm}{Lineare-Recurenz}
+\begin{algorithm}{Lineare Rekurrenz}
\begin{methods}
- \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
+ \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2}
\method{}{aus den ersten $2n$ Werte}{}
\end{methods}
\sourcecode{math/berlekampMassey.cpp}
- Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
+ Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Rekurrenz.
\begin{methods}
- \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+ \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}
\end{methods}
- \sourcecode{math/linearRecurence.cpp}
+ \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}
@@ -375,7 +375,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \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\}$)
@@ -387,14 +387,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}
@@ -405,6 +405,7 @@ so gilt %\begin{algorithm}{Binomialkoeffizienten}
\paragraph{Binomialkoeffizienten}
Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
+
\begin{methods}
\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
\method{calc\_binom}{berechnet Binomialkoeffizient}{1}
diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp index 747eb7a..d5eaf07 100644 --- a/math/shortModInv.cpp +++ b/math/shortModInv.cpp @@ -1,3 +1,3 @@ -ll inv(ll a, ll b){ // a^{-1} mod b - return 1 < a ? b - inv(b % a, a) * b / a : 1; -}
\ No newline at end of file +ll multInv(ll a, ll b){ // a^{-1} mod b + return 1 < a ? b - multInv(b % a, a) * b / a : 1; +} diff --git a/math/tables.tex b/math/tables.tex index 53f3758..c422d73 100644 --- a/math/tables.tex +++ b/math/tables.tex @@ -1,8 +1,12 @@ \enlargethispage{0.2cm} \begin{multicols*}{2} + \refstepcounter{subsection} + \subsectionmark{Tables} + \addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables} + \input{math/tables/binom} \vfill - \input{math/tables/composite} + \input{math/tables/prime-composite} \vfill \input{math/tables/platonic} \vfill diff --git a/math/tables/composite.tex b/math/tables/composite.tex deleted file mode 100644 index b4c8294..0000000 --- a/math/tables/composite.tex +++ /dev/null @@ -1,26 +0,0 @@ -\begin{tabularx}{\linewidth}{|r|r|r|CICICICICICICICICICICIC|} - \hline - \multicolumn{15}{|c|}{Highly Composite Numbers} \\ - \hline - $10^x$ & Zahl & Teiler & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\ - \hline - 1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\ - 2 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\ - 3 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\ - 4 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\ - 5 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\ - 6 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\ - 7 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\ - 8 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\ - 9 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\ - 10 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\ - 11 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\ - 12 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\ - 13 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 14 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 15 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 16 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 17 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ - 18 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ - \hline -\end{tabularx} diff --git a/math/tables/prime-composite.tex b/math/tables/prime-composite.tex new file mode 100644 index 0000000..d969747 --- /dev/null +++ b/math/tables/prime-composite.tex @@ -0,0 +1,26 @@ +\begin{tabularx}{\linewidth}{|r|r|r|r|CICICICICICICICICICICIC|} + \hline + \multicolumn{16}{|c|}{Primes and Highly Composite Numbers} \\ + \hline + $10^x$ & Next Prime & Highly Composite & Divisors & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\ + \hline + 1 & +1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\ + 2 & +1 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\ + 3 & +9 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\ + 4 & +7 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\ + 5 & +3 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\ + 6 & +3 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\ + 7 & +19 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\ + 8 & +7 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\ + 9 & +7 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\ + 10 & +19 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\ + 11 & +3 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\ + 12 & +39 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\ + 13 & +37 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ + 14 & +31 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ + 15 & +37 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ + 16 & +61 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ + 17 & +3 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ + 18 & +3 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ + \hline +\end{tabularx} diff --git a/other/other.tex b/other/other.tex index 808d288..7e73260 100644 --- a/other/other.tex +++ b/other/other.tex @@ -9,7 +9,7 @@ \end{algorithm}
\begin{algorithm}{Timed}
- Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+ Kann benutzt werdem um randomisierte Algorithmen so lange wie möglich laufen zu lassen.
\sourcecode{other/timed.cpp}
\end{algorithm}
@@ -129,7 +129,7 @@ \item \textbf{System von Differenzbeschränkungen:}
Ändere alle Bedingungen in die Form $a-b \leq c$.
- Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gweicht \texttt{c} ein.
+ Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gewicht \texttt{c} ein.
Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden.
\texttt{d[v]} ist mögliche Lösung für \texttt{v}.
diff --git a/string/string.tex b/string/string.tex index c36ec69..aec50d5 100644 --- a/string/string.tex +++ b/string/string.tex @@ -60,21 +60,21 @@ \sourcecode{string/ahoCorasick.cpp} \end{algorithm} -\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/tcr.pdf b/tcr.pdf Binary files differdeleted file mode 100644 index e7330c0..0000000 --- a/tcr.pdf +++ /dev/null @@ -3,9 +3,12 @@ \documentclass[a4paper,fontsize=7.8pt]{scrartcl} % General information. -\newcommand{\teamname}{Let's party!} +\newcommand{\teamname}{Infinite Loopers} \newcommand{\university}{Karlsruhe Institute of Technology} +% Source code links (optional) +\newcommand{\srclink}[1]{https://git.gloria-mundi.eu/tcr/plain/#1} + % Options \newif\ifoptional %\optionaltrue diff --git a/template/console.cpp b/template/console.sh index 31885e9..31885e9 100644 --- a/template/console.cpp +++ b/template/console.sh diff --git a/template/template.tex b/template/template.tex index 3525ddf..bf82199 100644 --- a/template/template.tex +++ b/template/template.tex @@ -5,5 +5,5 @@ \end{algorithm} \begin{algorithm}{Console} - \sourcecode{template/console.cpp} + \sourcecode{template/console.sh} \end{algorithm} @@ -0,0 +1,33 @@ +#include <bits/stdc++.h> +using namespace std; +using ll = long long; +#define sz(x) ((int)(x).size()) +#define all(x) (x).begin(), (x).end() + +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); +} + +} |