From f1261bb7cd35840b9b5937a6260308f3839c6f3e Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:16:34 +0100 Subject: minor (mostly spacing) changes --- graph/reroot.cpp | 53 +++++++++++++++++++++++++++------------------------ graph/scc.cpp | 3 +-- graph/virtualTree.cpp | 13 +++++-------- 3 files changed, 34 insertions(+), 35 deletions(-) (limited to 'graph') diff --git a/graph/reroot.cpp b/graph/reroot.cpp index eeca43e..4c6a748 100644 --- a/graph/reroot.cpp +++ b/graph/reroot.cpp @@ -1,39 +1,39 @@ // Usual Tree DP can be broken down in 4 steps: // - Initialize dp[v] = identity // - Iterate over all children w and take a value for w -// by looking at dp[w] and possibly the edge label of v -> w +// by looking at dp[w] and possibly the edge label of v -> w // - combine the values of those children -// usually, this operation should be commutative and associative -// - finalize the value of dp[v] after iterating over all children -struct Reroot{ +// usually this operation should be commutative and associative +// - finalize the dp[v] after iterating over all children +struct Reroot { using T = ll; // identity element - T E(){} + T E() {} // x: dp value of child // e: index of edge going to child - T takeChild(T x, int e){} - T combine(T x, T y){} + T takeChild(T x, int e) {} + T comb(T x, T y) {} // called after combining all dp values of children - T finalize(T x, int v){} + T fin(T x, int v) {} vector>> g; vector ord, pae; vector dp; - T dfs(int v){ + T dfs(int v) { ord.push_back(v); - for(auto [w, e] : g[v]){ + for (auto [w, e] : g[v]) { g[w].erase(find(all(g[w]), pair(v, e^1))); pae[w] = e^1; - dp[v] = combine(dp[v], takeChild(dfs(w), e)); + dp[v] = comb(dp[v], takeChild(dfs(w), e)); } - return dp[v] = finalize(dp[v], v); + return dp[v] = fin(dp[v], v); } - vector solve(int n, vector> edges){ + vector solve(int n, vector> edges) { g.resize(n); - for(int i = 0; i < n-1; i++){ + for (int i = 0; i < n-1; i++) { g[edges[i].first].emplace_back(edges[i].second, 2*i); g[edges[i].second].emplace_back(edges[i].first, 2*i+1); } @@ -41,19 +41,22 @@ struct Reroot{ dp.assign(n, E()); dfs(0); vector updp(n, E()), res(n, E()); - for(int v : ord){ + for (int v : ord) { vector pref(sz(g[v])+1), suff(sz(g[v])+1); - if(v != 0) pref[0] = takeChild(updp[v], pae[v]); - for(int i = 0; i < sz(g[v]); i++){ - pref[i+1] = suff[i] = takeChild(dp[g[v][i].first], g[v][i].second); - pref[i+1] = combine(pref[i], pref[i+1]); + if (v != 0) pref[0] = takeChild(updp[v], pae[v]); + for (int i = 0; i < sz(g[v]); i++){ + auto [u, w] = g[v][i]; + pref[i+1] = suff[i] = takeChild(dp[u], w); + pref[i+1] = comb(pref[i], pref[i+1]); } - for(int i = sz(g[v])-1; i >= 0; i--) - suff[i] = combine(suff[i], suff[i+1]); - for(int i = 0; i < sz(g[v]); i++) - updp[g[v][i].first] = finalize(combine(pref[i], suff[i+1]), v); - res[v] = finalize(pref.back(), v); + for (int i = sz(g[v])-1; i >= 0; i--) { + suff[i] = comb(suff[i], suff[i+1]); + } + for (int i = 0; i < sz(g[v]); i++) { + updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); + } + res[v] = fin(pref.back(), v); } return res; } -}; \ No newline at end of file +}; diff --git a/graph/scc.cpp b/graph/scc.cpp index 1716add..5aa7cf2 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,8 +1,7 @@ vector> adj, sccs; int counter, sccCounter; vector inStack; -// idx enthält den Index der SCC pro Knoten. -vector low, idx, s; +vector low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp index f7a3cb1..2fcea80 100644 --- a/graph/virtualTree.cpp +++ b/graph/virtualTree.cpp @@ -1,10 +1,8 @@ // needs dfs in- and out- time and lca function vector in, out; -void virtualTree(const vector& a) { // takes indices of used nodes - auto ind = a; +void virtualTree(vector ind) { // indices of used nodes sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i=0; i& a) { // takes indices of used nodes int n = ind.size(); vector> tree(n); - stack st{{0}}; + vector st = {0}; for (int i=1; i= out[ind[st.top()]]) st.pop(); - tree[st.top()].push_back(i); + while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back(); + tree[st.back()].push_back(i); st.push(i); } - // virtual directed tree with n nodes, original indices in ind - // weights can be calculated if necessary, e.g. with binary lifting + // weights can be calculated, e.g. with binary lifting } -- cgit v1.2.3 From 5a6e689ffb206aab782102224fa64c6349c44aae Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:17:53 +0100 Subject: shorten hungarian --- graph/maxWeightBipartiteMatching.cpp | 37 ++++++++++++++---------------------- 1 file changed, 14 insertions(+), 23 deletions(-) (limited to 'graph') diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp index 5eda19b..a2b0a80 100644 --- a/graph/maxWeightBipartiteMatching.cpp +++ b/graph/maxWeightBipartiteMatching.cpp @@ -4,15 +4,14 @@ double costs[N_LEFT][N_RIGHT]; double match(int l, int r) { vector lx(l), ly(r); //xy is matching from l->r, yx from r->l, or -1 - vector xy(l, -1), yx(r, -1), augmenting(r); - vector s(l); + vector xy(l, -1), yx(r, -1); vector> slack(r); for (int x = 0; x < l; x++) lx[x] = *max_element(costs[x], costs[x] + r); for (int root = 0; root < l; root++) { - augmenting.assign(r, -1); - s.assign(l, false); + vector aug(r, -1); + vector s(l); s[root] = true; for (int y = 0; y < r; y++) { slack[y] = {lx[root] + ly[y] - costs[root][y], root}; @@ -22,38 +21,30 @@ double match(int l, int r) { double delta = INF; int x = -1; for (int yy = 0; yy < r; yy++) { - if (augmenting[yy] < 0) { - if (slack[yy].first < delta) { - delta = slack[yy].first; - x = slack[yy].second; - y = yy; - }}} + if (aug[yy] < 0 && slack[yy].first < delta) { + tie(delta, x) = slack[yy]; + y = yy; + }} if (delta > 0) { for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta; for (int y = 0; y < r; y++) { - if (augmenting[y] >= 0) ly[y] += delta; + if (aug[y] >= 0) ly[y] += delta; else slack[y].first -= delta; }} - augmenting[y] = x; + aug[y] = x; x = yx[y]; - if (x == -1) break; + if (x < 0) break; s[x] = true; for (int y = 0; y < r; y++) { - if (augmenting[y] < 0) { + if (aug[y] < 0) { double alt = lx[x] + ly[y] - costs[x][y]; if (slack[y].first > alt) { slack[y] = {alt, x}; }}}} while (y >= 0) { - // Jede Iteration vergrößert Matching um 1 - // (können 0-Kanten sein!) - int x = augmenting[y]; - int prec = xy[x]; - yx[y] = x; - xy[x] = y; - y = prec; + yx[y] = aug[y]; + swap(y, xy[aug[y]]); }} - // Wert des Matchings return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); + accumulate(all(ly), 0.0); // Wert des Matchings } -- cgit v1.2.3 From 188120837921f37ffc5c63906070cfe5f1ef601a Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:18:40 +0100 Subject: same interface as dinic + delete one push relabel --- graph/pushRelabel.cpp | 151 +++++++++++++++++-------------------------------- graph/pushRelabel2.cpp | 66 --------------------- 2 files changed, 53 insertions(+), 164 deletions(-) delete mode 100644 graph/pushRelabel2.cpp (limited to 'graph') diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp index 52ba8b1..904aec6 100644 --- a/graph/pushRelabel.cpp +++ b/graph/pushRelabel.cpp @@ -1,109 +1,64 @@ -constexpr ll inf = 1ll<<60; - struct Edge { - int from, to; + int to, rev; ll f, c; }; -vector edges; -vector> adj, llist; -vector height, ccount, que; -vector excess; -vector> dlist; -vector::iterator> iter; -int highest, highestActive; - -void addEdge(int from, int to, ll c) { - adj[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adj[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); -} +vector> adj; +vector> hs; +vector ec; +vector cur, H; -void globalRelabel(int n, int t) { - height.assign(n, n); - height[t] = 0; - ccount.assign(n, 0); - que.assign(n+1, 0); - int qh = 0, qt = 0; - for (que[qt++] = t; qh < qt;) { - int v = que[qh++], h = height[v] + 1; - for (int id : adj[v]) { - if (height[edges[id].to] == n && edges[id ^ 1].c - edges[id ^ 1].f > 0) { - ccount[height[edges[id].to] = h]++; - que[qt++] = edges[id].to; - }}} - llist.assign(n+1, {}); - dlist.assign(n+1, {}); - for (int v = 0; v < n; v++) { - if (height[v] < n) { - iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); - if (excess[v] > 0) llist[height[v]].push_back(v); - }} - highest = highestActive = height[que[qt - 1]]; +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)sz(adj[v]), 0, c}); + adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); } -void push(int v, int id) { - int u = edges[id].to; - ll df = min(excess[v], edges[id].c - edges[id].f); - edges[id].f += df; - edges[id^1].f -= df; - excess[v] -= df; - excess[u] += df; - if (0 < excess[u] && excess[u] <= df) llist[height[u]].push_back(u); +void addFlow(Edge& e, ll f) { + if (ec[e.to] == 0 && f > 0) + hs[H[e.to]].push_back(e.to); + e.f += f; + adj[e.to][e.rev].f -= f; + ec[e.to] += f; + ec[adj[e.to][e.rev].to] -= f; } -void discharge(int n, int v) { - int nh = n; - for (int id : adj[v]) { - if (edges[id].c - edges[id].f > 0) { - if (height[v] == height[edges[id].to] + 1) { - push(v, id); - if (!excess[v]) return; - } else { - nh = min(nh, height[edges[id].to] + 1); - }}} - int h = height[v]; - if (ccount[h] == 1) { - for (int i = h; i <= highest; i++) { - for (auto p : dlist[i]) --ccount[height[p]], height[p] = n; - dlist[i].clear(); - } - highest = h - 1; - } else { - --ccount[h], iter[v] = dlist[h].erase(iter[v]), height[v] = nh; - if (nh == n) return; - ++ccount[nh], iter[v] = dlist[nh].insert(dlist[nh].begin(), v); - highest = max(highest, highestActive = nh); - llist[nh].push_back(v); -}} - ll maxFlow(int s, int t) { int n = sz(adj); - llist.assign(n + 1, {}); - dlist.assign(n + 1, {}); - highestActive = highest = 0; - height.assign(n, 0); - height[s] = n; - iter.resize(n); - for (int v = 0; v < n; v++) { - if (v != s) iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); - } - ccount.assign(n, 0); - ccount[0] = n-1; - excess.assign(n, 0); - excess[s] = inf; - excess[t] = -inf; - for (int id : adj[s]) push(s, id); - globalRelabel(n, t); - while (highestActive >= 0) { - if (llist[highestActive].empty()) { - highestActive--; - continue; - } - int v = llist[highestActive].back(); - llist[highestActive].pop_back(); - discharge(n, v); - } - return excess[t] + inf; -} + hs.assign(2*n, {}); + ec.assign(n, 0); + cur.assign(n, 0); + H.assign(n, 0); + H[s] = n; + ec[t] = 1;//never set t to active... + vector co(2*n); + co[0] = n - 1; + for (Edge& e : adj[s]) addFlow(e, e.c); + for (int hi = 0;;) { + while (hs[hi].empty()) if (!hi--) return -ec[s]; + int v = hs[hi].back(); + hs[hi].pop_back(); + while (ec[v] > 0) { + if (cur[v] == sz(adj[v])) { + H[v] = 2*n; + for (int i = 0; i < sz(adj[v]); i++) { + Edge& e = adj[v][i]; + if (e.c - e.f > 0 && + H[v] > H[e.to] + 1) { + H[v] = H[e.to] + 1; + cur[v] = i; + }} + co[H[v]]++; + if (!--co[hi] && hi < n) { + for (int i = 0; i < n; i++) { + if (hi < H[i] && H[i] < n) { + co[H[i]]--; + H[i] = n + 1; + }}} + hi = H[v]; + } else { + Edge& e = adj[v][cur[v]]; + if (e.c - e.f > 0 && H[v] == H[e.to] + 1) { + addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f)); + } else { + cur[v]++; +}}}}} diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp deleted file mode 100644 index 7d7defd..0000000 --- a/graph/pushRelabel2.cpp +++ /dev/null @@ -1,66 +0,0 @@ -struct Edge { - int from, to; - ll f, c; -}; - -vector edges; -vector> adj, hs; -vector ec; -vector cur, H; - -void addEdge(int from, int to, ll c) { - adj[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adj[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); -} - -void addFlow(int id, ll f) { - if (ec[edges[id].to] == 0 && f > 0) - hs[H[edges[id].to]].push_back(edges[id].to); - edges[id].f += f; - edges[id^1].f -= f; - ec[edges[id].to] += f; - ec[edges[id].from] -= f; -} - -ll maxFlow(int s, int t) { - int n = sz(adj); - hs.assign(2*n, {}); - ec.assign(n, 0); - cur.assign(n, 0); - H.assign(n, 0); - H[s] = n; - ec[t] = 1;//never set t to active... - vector co(2*n); - co[0] = n - 1; - for (int id : adj[s]) addFlow(id, edges[id].c); - for (int hi = 0;;) { - while (hs[hi].empty()) if (!hi--) return -ec[s]; - int v = hs[hi].back(); - hs[hi].pop_back(); - while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { - H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { - int id = adj[v][i]; - if (edges[id].c - edges[id].f > 0 && - H[v] > H[edges[id].to] + 1) { - H[v] = H[edges[id].to] + 1; - cur[v] = i; - }} - co[H[v]]++; - if (!--co[hi] && hi < n) { - for (int i = 0; i < n; i++) { - if (hi < H[i] && H[i] < n) { - co[H[i]]--; - H[i] = n + 1; - }}} - hi = H[v]; - } else { - auto e = edges[adj[v][cur[v]]]; - if (e.c - e.f > 0 && H[v] == H[e.to] + 1) { - addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f)); - } else { - cur[v]++; -}}}}} -- cgit v1.2.3 From dbcd02da96922c2a667ec16e390ef8263580a66c Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:19:29 +0100 Subject: remove newlines --- graph/minCostMaxFlow.cpp | 3 --- 1 file changed, 3 deletions(-) (limited to 'graph') diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp index 3526b17..14a222c 100644 --- a/graph/minCostMaxFlow.cpp +++ b/graph/minCostMaxFlow.cpp @@ -8,7 +8,6 @@ struct MinCostFlow { vector> adj; vector pref, con; vector dist; - const int s, t; ll maxflow, mincost; @@ -27,12 +26,10 @@ struct MinCostFlow { dist.assign(sz(adj), INF); vector inqueue(sz(adj)); queue queue; - dist[s] = 0; queue.push(s); pref[s] = s; inqueue[s] = true; - while (!queue.empty()) { int cur = queue.front(); queue.pop(); inqueue[cur] = false; -- cgit v1.2.3 From 36ba8589fa0154d73354bd8e0101213f2d5f9ba4 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:21:56 +0100 Subject: reorder to improve spacing --- datastructures/datastructures.tex | 62 ++++++------- geometry/geometry.tex | 17 ++-- graph/graph.tex | 133 +++++++++++++++------------ math/math.tex | 189 +++++++++++++++++++------------------- string/string.tex | 1 + tcr.pdf | Bin 667178 -> 664992 bytes tcr.tex | 3 +- 7 files changed, 208 insertions(+), 197 deletions(-) (limited to 'graph') diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4139219..1ccefaa 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -14,6 +14,15 @@ \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} +\begin{algorithm}{Wavelet Tree} + \begin{methods} + \method{Constructor}{baut den Baum auf}{n\*\log(n)} + \method{kth}{sort $[l, r)[k]$}{\log(n)} + \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)} + \end{methods} + \sourcecode{datastructures/waveletTree.cpp} +\end{algorithm} + \begin{algorithm}{Fenwick Tree} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} @@ -29,11 +38,11 @@ \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} \end{algorithm} -\clearpage \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} \sourcecode{datastructures/stlRope.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{(Implicit) Treap (Cartesian Tree)} \begin{methods} @@ -54,15 +63,6 @@ \sourcecode{datastructures/sparseTable.cpp} \end{algorithm} -\begin{algorithm}{Wavelet Tree} - \begin{methods} - \method{Constructor}{baut den Baum auf}{n\*\log(n)} - \method{kth}{sort $[l, r)[k]$}{\log(n)} - \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)} - \end{methods} - \sourcecode{datastructures/waveletTree.cpp} -\end{algorithm} - \begin{algorithm}{STL-Bitset} \sourcecode{datastructures/bitset.cpp} \end{algorithm} @@ -81,6 +81,23 @@ \end{algorithm} \clearpage +\begin{algorithm}{Lichao} + \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} @@ -90,13 +107,7 @@ \end{methods} \sourcecode{datastructures/unionFind.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} - \columnbreak - \sourcecode{datastructures/dynamicConvexHull.cpp} -\end{algorithm} +\columnbreak \begin{algorithm}{Persistent} \begin{methods} @@ -108,22 +119,6 @@ \sourcecode{datastructures/persistentArray.cpp} \end{algorithm} -\begin{algorithm}{STL-Tree} - \sourcecode{datastructures/stlTree.cpp} -\end{algorithm} - -\begin{algorithm}{STL Priority Queue} - Nicht notwendig, wenn Smaller-Larger-Optimization greift. - \sourcecode{datastructures/stlPQ.cpp} -\end{algorithm} - -\begin{algorithm}{STL HashMap} - 3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map} - \sourcecode{datastructures/stlHashMap.cpp} -\end{algorithm} - - - \begin{algorithm}[optional]{Range Minimum Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} @@ -138,4 +133,3 @@ \end{methods} \sourcecode{datastructures/firstUnused.cpp} \end{algorithm} - diff --git a/geometry/geometry.tex b/geometry/geometry.tex index d3e1671..d753ed6 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -7,6 +7,14 @@ \sourcecode{geometry/closestPair.cpp} \end{algorithm} +\begin{algorithm}{Rotating calipers} + \begin{methods} + \method{antipodalPoints}{berechnet antipodale Punkte}{n} + \end{methods} + \textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden! + \sourcecode{geometry/antipodalPoints.cpp} +\end{algorithm} + \begin{algorithm}{Konvexehülle} \begin{methods} \method{convexHull}{berechnet Konvexehülle}{n\*\log(n)} @@ -19,15 +27,6 @@ \sourcecode{geometry/convexHull.cpp} \end{algorithm} -\columnbreak -\begin{algorithm}{Rotating calipers} - \begin{methods} - \method{antipodalPoints}{berechnet antipodale Punkte}{n} - \end{methods} - \textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden! - \sourcecode{geometry/antipodalPoints.cpp} -\end{algorithm} - \subsection{Formeln~~--~\texttt{std::complex}} \sourcecode{geometry/formulars.cpp} \sourcecode{geometry/linesAndSegments.cpp} diff --git a/graph/graph.tex b/graph/graph.tex index 6fbdb74..060d157 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,18 +1,31 @@ \section{Graphen} -\begin{algorithm}{Eulertouren} +\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: + Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. + ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) + + \paragraph{Kreiseigenschaft} + Für jeden Kreis $K$ im Graphen gilt: + Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. +\end{algorithm} + +\begin{algorithm}{Heavy-Light Decomposition} \begin{methods} - \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} + \method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})} \end{methods} - \sourcecode{graph/euler.cpp} - \begin{itemize} - \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). - \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). - \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} - \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector> adj} leichter - \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. - Die Existenz muss separat geprüft werden. - \end{itemize} + \textbf{Wichtig:} Intervalle sind halboffen + + Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. + \sourcecode{graph/hld.cpp} \end{algorithm} \begin{algorithm}{Lowest Common Ancestor} @@ -31,16 +44,20 @@ \sourcecode{graph/centroid.cpp} \end{algorithm} -\begin{algorithm}{Heavy-Light Decomposition} +\begin{algorithm}{Eulertouren} \begin{methods} - \method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})} + \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} \end{methods} - \textbf{Wichtig:} Intervalle sind halboffen - - Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. - \sourcecode{graph/hld.cpp} + \sourcecode{graph/euler.cpp} + \begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} + \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector> adj} leichter + \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. + Die Existenz muss separat geprüft werden. + \end{itemize} \end{algorithm} -\clearpage \begin{algorithm}{Baum-Isomorphie} \begin{methods} @@ -49,24 +66,6 @@ \sourcecode{graph/treeIsomorphism.cpp} \end{algorithm} -\begin{algorithm}{Minimale Spannbäume} - \paragraph{Schnitteigenschaft} - Für jeden Schnitt $C$ im Graphen gilt: - Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. - ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) - - \paragraph{Kreiseigenschaft} - Für jeden Kreis $K$ im Graphen gilt: - Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. -\end{algorithm} - -\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} - \subsection{Kürzeste Wege} \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} @@ -91,6 +90,14 @@ 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}{Dynamic Connectivity} + \begin{methods} + \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} + \method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)} + \method{eraseEdge}{entfernt Kante \code{id}}{\log(n)} + \end{methods} + \sourcecode{graph/connect.cpp} +\end{algorithm} \begin{algorithm}{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)$ @@ -100,13 +107,11 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/havelHakimi.cpp} \end{algorithm} -\begin{algorithm}{Dynamic Connectivity} +\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} \begin{methods} - \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} - \method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)} - \method{eraseEdge}{entfernt Kante \code{id}}{\log(n)} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} \end{methods} - \sourcecode{graph/connect.cpp} + \sourcecode{graph/scc.cpp} \end{algorithm} \begin{algorithm}{DFS} @@ -121,13 +126,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/articulationPoints.cpp} \end{algorithm} -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - \sourcecode{graph/scc.cpp} -\end{algorithm} - \begin{algorithm}{2-SAT} \sourcecode{graph/2sat.cpp} \end{algorithm} @@ -139,7 +137,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\clearpage \begin{algorithm}{Cycle Counting} \begin{methods} @@ -164,6 +161,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/blossom.cpp} \end{algorithm} +\begin{algorithm}{Rerooting Template} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}{Virtual Trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} + \begin{algorithm}{Maximal Cardinatlity Bipartite Matching} \label{kuhn} \begin{methods} @@ -179,13 +184,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/hopcroftKarp.cpp} \end{algorithm} -\begin{algorithm}{Maximum Weight Bipartite Matching} - \begin{methods} - \method{match}{berechnet Matching}{\abs{V}^3} - \end{methods} - \sourcecode{graph/maxWeightBipartiteMatching.cpp} -\end{algorithm} - \begin{algorithm}{Global Mincut} \begin{methods} \method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})} @@ -205,12 +203,21 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/capacityScaling.cpp} } +\optional{ \subsubsection{Push Relabel} \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} \end{methods} -\sourcecode{graph/pushRelabel2.cpp} +\sourcecode{graph/pushRelabel.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} \subsubsection{Dinic's Algorithm mit Capacity Scaling} \begin{methods} @@ -218,6 +225,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} +\vfill* +\columnbreak \optional{ \subsubsection{Anwendungen} @@ -241,12 +250,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{itemize} } -\begin{algorithm}{Min-Cost-Max-Flow} +\begin{algorithm}{Maximum Weight Bipartite Matching} \begin{methods} - \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} + \method{match}{berechnet Matching}{\abs{V}^3} \end{methods} - \sourcecode{graph/minCostMaxFlow.cpp} + \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} +\vfill* +\columnbreak + \begin{algorithm}[optional]{TSP} \begin{methods} @@ -261,3 +273,4 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bitonicTSPsimple.cpp} \end{algorithm} + diff --git a/math/math.tex b/math/math.tex index 8ccc55e..8a30b86 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,5 +1,12 @@ \section{Mathe} +\begin{algorithm}{Zykel Erkennung} + \begin{methods} + \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l} + \end{methods} + \sourcecode{math/cycleDetection.cpp} +\end{algorithm} + \begin{algorithm}{Longest Increasing Subsequence} \begin{itemize} \item \code{lower\_bound} $\Rightarrow$ streng monoton @@ -7,14 +14,6 @@ \end{itemize} \sourcecode{math/longestIncreasingSubsequence.cpp} \end{algorithm} -\columnbreak - -\begin{algorithm}{Zykel Erkennung} - \begin{methods} - \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l} - \end{methods} - \sourcecode{math/cycleDetection.cpp} -\end{algorithm} \begin{algorithm}{Permutationen} \begin{methods} @@ -44,21 +43,20 @@ \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} \runtime{\log(a) + \log(b)} - \sourcecode{math/gcd-lcm.cpp} \sourcecode{math/extendedEuclid.cpp} \end{algorithm} -\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$} -\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$ +\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$} +\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$ -\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:} +\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:} \begin{itemize} \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit - $\alpha n + \beta p = 1$. - \item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$. - \item $n^{-1} :\equiv \alpha \bmod p$ + $\alpha x + \beta m = 1$. + \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$. + \item $x^{-1} :\equiv \alpha \bmod m$ \end{itemize} -\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$. +\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. % \sourcecode{math/multInv.cpp} \sourcecode{math/shortModInv.cpp} @@ -121,19 +119,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/divisors.cpp} \end{algorithm} -\begin{algorithm}{Primitivwurzeln} - \begin{itemize} - \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$ - \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln - \item Sei $g$ Primitivwurzel modulo $n$. - Dann gilt:\newline - Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$. - \end{itemize} - \begin{methods} - \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)} - \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)} - \end{methods} - \sourcecode{math/primitiveRoot.cpp} +\begin{algorithm}{Numerisch Extremstelle bestimmen} + \sourcecode{math/goldenSectionSearch.cpp} +\end{algorithm} + +\begin{algorithm}{Numerisch Integrieren, Simpsonregel} + \sourcecode{math/simpson.cpp} \end{algorithm} \begin{algorithm}{Diskreter Logarithmus} @@ -151,6 +142,22 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/discreteNthRoot.cpp} \end{algorithm} + +\begin{algorithm}{Primitivwurzeln} + \begin{itemize} + \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$ + \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln + \item Sei $g$ Primitivwurzel modulo $n$. + Dann gilt:\newline + Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$. + \end{itemize} + \begin{methods} + \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)} + \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)} + \end{methods} + \sourcecode{math/primitiveRoot.cpp} +\end{algorithm} + \begin{algorithm}{Linearessieb 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$. @@ -185,7 +192,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{itemize} \end{algorithm} - \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} \begin{itemize} \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) @@ -216,33 +222,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\sourcecode{math/mobius.cpp} \end{algorithm} -%\columnbreak -%\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion} -%\begin{itemize} -% \item Zählt die relativ primen Zahlen $\leq n$. -% -% \item Multiplikativ: -% $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$ -% -% \item $p$ prim, $k \in \mathbb{N}$: -% $~\varphi(p^k) = p^k - p^{k - 1}$ -% -% \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}$ -%\end{itemize} -%\sourcecode{math/phi.cpp} - - -\begin{algorithm}{Numerisch Extremstelle bestimmen} - \sourcecode{math/goldenSectionSearch.cpp} -\end{algorithm} - - -\begin{algorithm}{Numerisch Integrieren, Simpsonregel} - \sourcecode{math/simpson.cpp} -\end{algorithm} +\optional{ +\columnbreak +\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion} +\begin{itemize} + \item Zählt die relativ primen Zahlen $\leq n$. + + \item Multiplikativ: + $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$ + + \item $p$ prim, $k \in \mathbb{N}$: + $~\varphi(p^k) = p^k - p^{k - 1}$ + + \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}$ +\end{itemize} +\sourcecode{math/phi.cpp} +} \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} Multipliziert Polynome $A$ und $B$. @@ -259,21 +257,53 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code \sourcecode{math/transforms/fft.cpp} \sourcecode{math/transforms/ntt.cpp} + \vfill* + \columnbreak \sourcecode{math/transforms/bitwiseTransforms.cpp} Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!) \sourcecode{math/transforms/fftMul.cpp} \end{algorithm} -\subsection{LGS über $\boldsymbol{\mathbb{R}}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/gauss.cpp} +\begin{algorithm}{Operations on Formal Power Series} + \sourcecode{math/transforms/seriesOperations.cpp} +\end{algorithm} \subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} \method{gauss}{löst LGS}{n^3} \sourcecode{math/lgsFp.cpp} -\clearpage +\subsection{LGS über $\boldsymbol{\mathbb{R}}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/gauss.cpp} + +\begin{algorithm}{\textsc{Legendre}-Symbol} + Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: + \begin{align*} + \legendre{a}{p} &= + \begin{cases*} + \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex] + \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex] + -1 & sonst + \end{cases*} \\ + \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &= + \begin{cases*} + \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex] + -1 & falls $p \equiv 3 \bmod 4$ + \end{cases*} \\ + \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &= + \begin{cases*} + \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex] + -1 & falls $p \equiv \pm 3 \bmod 8$ + \end{cases*} + \end{align*} + \begin{align*} + \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} && + \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p + \end{align*} + \sourcecode{math/legendre.cpp} +\end{algorithm} +\optional{ \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} \begin{methods} \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))} @@ -281,6 +311,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}} \end{methods} \sourcecode{math/piLehmer.cpp} +} \begin{algorithm}{Lineare-Recurenz} \begin{methods} @@ -331,33 +362,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/matrixPower.cpp} \end{algorithm} -\begin{algorithm}{\textsc{Legendre}-Symbol} - Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: - \begin{align*} - \legendre{a}{p} &= - \begin{cases*} - \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex] - \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex] - -1 & sonst - \end{cases*} \\ - \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex] - -1 & falls $p \equiv 3 \bmod 4$ - \end{cases*} \\ - \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex] - -1 & falls $p \equiv \pm 3 \bmod 8$ - \end{cases*} - \end{align*} - \begin{align*} - \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} && - \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p - \end{align*} - \sourcecode{math/legendre.cpp} -\end{algorithm} - \begin{algorithm}{Inversionszahl} \sourcecode{math/inversions.cpp} \end{algorithm} @@ -411,14 +415,13 @@ so gilt \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ -\columnbreak - - \begin{methods} + + \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} \end{methods} \sourcecode{math/binomial1.cpp} - - \begin{methods} + + \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} \end{methods} \sourcecode{math/binomial3.cpp} diff --git a/string/string.tex b/string/string.tex index 526faa2..393c2ad 100644 --- a/string/string.tex +++ b/string/string.tex @@ -47,6 +47,7 @@ \sourcecode{string/longestCommonSubsequence.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{\textsc{Aho-Corasick}-Automat} \begin{methods}[ll] sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}} diff --git a/tcr.pdf b/tcr.pdf index e7330c0..6342868 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/tcr.tex b/tcr.tex index 445f8b6..bfc73d1 100644 --- a/tcr.tex +++ b/tcr.tex @@ -3,7 +3,7 @@ \documentclass[a4paper,fontsize=7.8pt]{scrartcl} % General information. -\newcommand{\teamname}{Let's party!} +\newcommand{\teamname}{Kindergarten Timelimit} \newcommand{\university}{Karlsruhe Institute of Technology} % Options @@ -36,6 +36,7 @@ \tableofcontents \end{multicols*} } + \newpage % Content. -- cgit v1.2.3