From 7d443816db171b236a7c7e1cbdd87cf65b361d89 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Tue, 24 Oct 2017 21:45:22 +0200 Subject: Adding short description on Mo's Algorithm. --- other/other.tex | 10 +++++++++- tcr.pdf | Bin 317863 -> 318938 bytes 2 files changed, 9 insertions(+), 1 deletion(-) diff --git a/other/other.tex b/other/other.tex index b275c6e..9dbc018 100644 --- a/other/other.tex +++ b/other/other.tex @@ -126,7 +126,15 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. Berechnung: Maximales Matching in bipartitem Graphen. Dupliziere jedes $s \in S$ in $u_s$ und $v_s$. Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu. - Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. + Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. + + \item \textbf{\textsc{Mo}'s Algorithm:} + SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$. + Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$. + Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$. + Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls. + Laufzeit:~$\mathcal{O}(n\cdot\sqrt{n})$. + (Anzahl der Blöcke als Konstante in Code schreiben.) \end{itemize} \subsection{Tipps \& Tricks} diff --git a/tcr.pdf b/tcr.pdf index 67d568e..ecd2b57 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3