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 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'other') 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} -- cgit v1.2.3