From 0ccedaad1cdfc6011b3f9ece036a1a0be2d379dd Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 5 Jun 2026 21:49:11 +0200 Subject: fix typo --- content/math/math.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index 162c7cc..cd2fd02 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -565,8 +565,8 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Wichtige Zahlen} \input{math/tables/composite} -\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } -\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)} +\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ } +\method{recover}{findet $x$ und $y$ für $c=x\*y^{-1}\bmod m$}{\log(m)} \textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein! \sourcecode{math/recover.cpp} -- cgit v1.2.3 From d697207cde39a5a26361d693d1ccb3d5e7616d81 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 21 Jun 2026 00:32:58 +0200 Subject: avoid overflow in ccw*ccw --- content/geometry/formulas.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/geometry/formulas.cpp b/content/geometry/formulas.cpp index 5d4e10d..f724398 100644 --- a/content/geometry/formulas.cpp +++ b/content/geometry/formulas.cpp @@ -24,7 +24,7 @@ auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);} // 1 => c links von a->b // 0 => a, b und c kolliniear // -1 => c rechts von a->b -int ccw(pt a, pt b, pt c) { +ll ccw(pt a, pt b, pt c) { auto orien = cross(b - a, c - a); return (orien > EPS) - (orien < -EPS); } -- cgit v1.2.3 From ee4a6e4a85be1811fedad0c188aad00ec322e5d6 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 14 Aug 2026 23:36:00 +0200 Subject: another comment --- content/graph/stoerWagner.cpp | 4 ++-- tcr.pdf | Bin 701906 -> 702008 bytes 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 97e667a..10f7327 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -44,10 +44,10 @@ ll stoer_wagner() { state.push_back({cur, c}); } int t = state.back().second; - state.pop_back(); + state.pop_back(); //cut between comp(t) and everything else if (state.empty()) return 0; //graph is not connected?! - merge(state.back().second, t); res = min(res, state.back().first); + merge(state.back().second, t); } return res; } diff --git a/tcr.pdf b/tcr.pdf index e5b898e..4e2a150 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From d720779f7039d96f2752a67cb6146a04fc78d062 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 24 Aug 2026 21:08:21 +0200 Subject: update flow runtimes --- content/graph/graph.tex | 4 ++-- tcr.pdf | Bin 702008 -> 702022 bytes 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'content') diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 7389ce6..c1a4e82 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -232,7 +232,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \begin{algorithm}{Min-Cost-Max-Flow} \begin{methods} - \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} + \method{mincostflow}{berechnet Fluss}{F\cdot\abs{V}\cdot\abs{E}} \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} @@ -241,7 +241,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \subsubsection{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 Ford Fulkerson}{min(\abs{V}^2\cdot\abs{E}, F\cdot\abs{E})} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} diff --git a/tcr.pdf b/tcr.pdf index 4e2a150..ca08ac2 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 2af51264dee73108fd57df46609106722ad0ddfc Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 28 Aug 2026 12:18:31 +0200 Subject: resolvew name conflict... --- content/math/legendre.cpp | 2 +- content/math/sqrtModCipolla.cpp | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'content') diff --git a/content/math/legendre.cpp b/content/math/legendre.cpp index b85ea2a..80825ea 100644 --- a/content/math/legendre.cpp +++ b/content/math/legendre.cpp @@ -1,4 +1,4 @@ -ll legendre(ll a, ll p) { // p prim >= 2 +ll legendreS(ll a, ll p) { // p prim >= 2 ll s = powMod(a, p / 2, p); return s < 2 ? s : -1ll; } diff --git a/content/math/sqrtModCipolla.cpp b/content/math/sqrtModCipolla.cpp index 1fac0c5..e0037fc 100644 --- a/content/math/sqrtModCipolla.cpp +++ b/content/math/sqrtModCipolla.cpp @@ -1,7 +1,7 @@ -ll sqrtMod(ll a, ll p) {// teste mit legendre ob lösung existiert +ll sqrtMod(ll a, ll p) {// test mit legendreS ob lösung existiert if (a < 2) return a; ll t = 0; - while (legendre((t*t-4*a) % p, p) >= 0) t = rng() % p; + while (legendreS((t*t-4*a) % p, p) >= 0) t = rng() % p; ll b = -t, c = -t, d = 1, m = p; for (m++; m /= 2; b = (a+a-b*b) % p, a = (a*a) % p) { if (m % 2) { -- cgit v1.2.3