merge mzuenni changes

26 files changed, 64 insertions, 115 deletions

diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp
index 3d3ea6b..2202a6f 100644
--- a/datastructures/lazyPropagation.cpp
+++ b/datastructures/lazyPropagation.cpp
@@ -65,14 +65,13 @@ struct SegTree {
 	// Optional:
 	ll lower_bound(int l, int r, T x) {
 		l += n, r += n;
-		push(l), push(r);
-		vector<int> a, st;
+		push(l), push(r - 1);
+		int a[64] = {}, lp = 0, rp = 64;
 		for (; l < r; l /= 2, r /= 2) {
-			if (l&1) a.push_back(l++);
-			if (r&1) st.push_back(--r);
+			if (l&1) a[lp++] = l++;
+			if (r&1) a[--rp] = --r;
 		}
-		a.insert(a.end(), st.rbegin(), st.rend());
-		for (int i : a) if (tree[i] >= x) { // Modify this
+		for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this
 			while (i < n) {
 				push_down(i);
 				if (tree[2 * i] >= x) i = 2 * i; // And this
diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
index 35843cd..68eef86 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -1,5 +1,5 @@
 // unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -height
+// unions[i]  < 0 => unions[i] = -size
 vector<int> unions;
 
 void init(int n) { //Initialisieren
@@ -11,12 +11,16 @@ int findSet(int n) { // Pfadkompression
 	return unions[n] = findSet(unions[n]);
 }
 
-void linkSets(int a, int b) { // Union by rank.
+void linkSets(int a, int b) { // Union by size.
 	if (unions[b] > unions[a]) swap(a, b);
-	if (unions[b] == unions[a]) unions[b]--;
+	unions[b] += unions[a];
 	unions[a] = b;
 }
 
 void unionSets(int a, int b) { // Diese Funktion aufrufen.
 	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
 }
+
+int size(int a) {
+	return -unions[findSet(a)];
+}
diff --git a/geometry/formulas.cpp b/geometry/formulas.cpp
index e34b3c6..22e9e32 100644
--- a/geometry/formulas.cpp
+++ b/geometry/formulas.cpp
@@ -34,7 +34,7 @@ bool isCoplanar(pt a, pt b, pt c, pt d) {
 	return abs((b - a) * (c - a) * (d - a)) < EPS;
 }
 
-// identifiziert winkel zwischen Vektoren u und v
+// charakterisiert winkel zwischen Vektoren u und v
 pt uniqueAngle(pt u, pt v) {
 	pt tmp = v * conj(u);
 	ll g = abs(gcd(real(tmp), imag(tmp)));
diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp
index c3c09f7..98fe4dc 100644
--- a/geometry/linesAndSegments.cpp
+++ b/geometry/linesAndSegments.cpp
@@ -36,7 +36,7 @@ double distToLine(pt a, pt b, pt p) {
 	return abs(cross(p - a, b - a)) / abs(b - a);
 }
 
-// Projektiert p auf die Gerade a-b
+// Projiziert p auf die Gerade a-b
 pt projectToLine(pt a, pt b, pt p) {
 	return a + (b - a) * dot(p - a, b - a) / norm(b - a);
 }
diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp
index 06b294f..3e87cde 100644
--- a/graph/LCA_sparse.cpp
+++ b/graph/LCA_sparse.cpp
@@ -2,7 +2,7 @@ struct LCA {
 	vector<ll> depth;
 	vector<int> visited, first;
 	int idx;
-	SparseTable st; //sparse table von oben
+	SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@
 
 	void init(vector<vector<int>>& adj, int root) {
 		depth.assign(2 * sz(adj), 0);
diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index 0df464b..00ecc3a 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -39,7 +39,7 @@ struct cycles {
 	//cycle must be constrcuted from base
 	bool isCycle(cycle cur) {
 		if (cur.none()) return false;
-		init(sz(adj)); // union find
+		init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@
 		for (int i = 0; i < sz(edges); i++) {
 			if (cur[i]) {
 				cur[i] = false;
diff --git a/graph/graph.tex b/graph/graph.tex
index c6b2248..9a0dc24 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -98,7 +98,7 @@
 Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} \cdot b_{k\smash{j}}\}$
 
 
-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}}$
+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} \cdot b_{k\smash{j}}$
 
 \begin{algorithm}{Dynamic Connectivity}
 	\begin{methods}
@@ -185,7 +185,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
 	\end{methods}
 	\begin{itemize}
-		\item die ersten [0..n) Knoten in \code{adj} sind die linke Seite des Graphen
+		\item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen
 	\end{itemize}
 	\sourcecode{graph/maxCarBiMatch.cpp}
 	\begin{methods}
@@ -265,7 +265,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
 \end{algorithm}
-\vfill*
+\vfill\null
 \columnbreak
 
 
diff --git a/graph/matching.cpp b/graph/matching.cpp
index f059351..2513604 100644
--- a/graph/matching.cpp
+++ b/graph/matching.cpp
@@ -12,7 +12,7 @@ int max_matching() {
 					mat[v][u] = rand() % (MOD - 1) + 1;
 					mat[u][v] = MOD - mat[v][u];
 		}}}
-		gauss(sz(adj), MOD); //LGS unten
+		gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@
 		int rank = 0;
 		for (auto& row : mat) {
 			if (*min_element(all(row)) != 0) rank++;
diff --git a/java/bigInteger.java b/java/bigInteger.java
deleted file mode 100644
index 7aeb885..0000000
--- a/java/bigInteger.java
+++ /dev/null
@@ -1,25 +0,0 @@
-// Berechnet this +,*,/,- val.
-BigInteger add(BigInteger val), multiply(BigInteger val),
-           divide(BigInteger val), substract(BigInteger val)
-
-// Bit-Operationen.
-BigInteger and(BigInteger val), or(BigInteger val), xor(BigInteger val),
-           not(), shiftLeft(int n), shiftRight(int n)
-
-// Berechnet den ggT von abs(this) und abs(val).
-BigInteger gcd(BigInteger val)
-
-// Berechnet this^e.
-BigInteger pow(BigInteger e)
-
-// Berechnet this mod m, this^-1 mod m, this^e mod m.
-BigInteger mod(BigInteger m), modInverse(BigInteger m),
-           modPow(BigInteger e, BigInteger m)
-
-// Berechnet die nächste Zahl, die größer und wahrscheinlich prim ist.
-BigInteger  nextProbablePrime()
-
-// Berechnet int/long/float/double-Wert.
-// Ist die Zahl zu großen werden die niedrigsten Bits konvertiert.
-int intValue(), long longValue(),
-float floatValue(), double doubleValue()
diff --git a/java/inputA.java b/java/inputA.java
deleted file mode 100644
index 4aa5008..0000000
--- a/java/inputA.java
+++ /dev/null
@@ -1,4 +0,0 @@
-Scanner in = new Scanner(System.in); // java.util.Scanner
-String line = in.nextLine(); // Die nächste Zeile.
-int num1 = in.nextInt(); // Das nächste Token als int.
-double num2 = in.nextDouble(); // Das nächste Token als double.
diff --git a/java/inputB.java b/java/inputB.java
deleted file mode 100644
index 93de1c1..0000000
--- a/java/inputB.java
+++ /dev/null
@@ -1,7 +0,0 @@
-BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
-String line = in.readLine(); // Die nächste Zeile.
-String[] parts = line.split(" "); // Zeile in Tokens aufspalten.
-int num1 = Integer.parseInt(in.readLine);
-int num2 = Integer.parseInt(parts[0]);
-double num3 = Double.parseDouble(in.readLine);
-double num4 = Double.parseDouble(parts[0]);
diff --git a/java/java.tex b/java/java.tex
deleted file mode 100644
index 9429106..0000000
--- a/java/java.tex
+++ /dev/null
@@ -1,37 +0,0 @@
-\begingroup
-\section{Java}
-\lstset{language=Java}
-
-\optional{
-\subsection{Introduction \opthint}
-
-\begin{itemize}
-	\item Compilen: \code{javac main.java}
-	\item Ausführen: \code{java main < sample.in}
-\end{itemize}
-}
-
-\subsection{Input}
-\begin{itemize}
-	\item \code{Scanner} ist sehr langsam. Nicht für lange Eingaben verwenden
-\end{itemize}
-\optional{
-\sourcecode{java/inputA.java}
-\sourcecode{java/inputB.java}
-}
-
-\subsection{Output}
-\begin{itemize}
-	\item \code{System.out} flusht nach jeder newline $\Rightarrow$ langsam
-	\item \code{String.format} langsam
-	\item \code{+} auf \code{String} benutzt \code{StringBuilder}  $\Rightarrow$ schnell und leicht \\(bei vielen \code{+}-Operationen an unterschiedlichen Stellen doch explizit \code{StringBuilder} nutzen)
-\end{itemize}
-\optional{
-\sourcecode{java/output.java}
-}
-
-\optional{
-\subsection{BigInteger \opthint}
-\sourcecode{java/bigInteger.java}
-}
-\endgroup
diff --git a/java/output.java b/java/output.java
deleted file mode 100644
index f046731..0000000
--- a/java/output.java
+++ /dev/null
@@ -1,7 +0,0 @@
-//gepufferter nicht autoatischer flushender output
-PrintWriter out = new PrintWriter(new BufferedWriter(
-                  new OutputStreamWriter(new FileOutputStream(
-                  FileDescriptor.out), StandardCharsets.UTF_8), 4096));
-out.println("blub" + "a" + "b"); //zeile Ausgeben
-out.println(String.format("%d %s", 5, "a")) // wie printf
-out.close();//WICHTIG!
diff --git a/latexHeaders/commands.sty b/latexHeaders/commands.sty
index c39923c..73a7dca 100644
--- a/latexHeaders/commands.sty
+++ b/latexHeaders/commands.sty
@@ -35,12 +35,17 @@
 %\ifthenelse{\equal{#3}{}}{}{\runtime{#3}}
 
 \newcommand{\sourcecode}[1]{%
+	\label{code:#1}%
 	\nobreak%
 %	\needspace{3\baselineskip}%
 %	\nopagebreak%
 	\lstinputlisting{#1}%
 	\penalty -1000%
 }
+\newcommand{\sourceref}[1]{{%
+	\color{comment}\bfseries\itshape{}Seite \pageref{code:#1}%
+}}
+
 \newcommand{\method}[4][]{\texttt{#2}~~#3~~\runtime{#4}#1\par}
 
 \newenvironment{methods}[1][lll]{%
diff --git a/math/discreteNthRoot.cpp b/math/discreteNthRoot.cpp
index 9249f73..7201b2b 100644
--- a/math/discreteNthRoot.cpp
+++ b/math/discreteNthRoot.cpp
@@ -1,5 +1,5 @@
 ll root(ll a, ll b, ll m) {
 	ll g = findPrimitive(m);
-	ll c = dlog(powMod(g, a, m), b, m); //diskreter logarithmus
+	ll c = dlog(powMod(g, a, m), b, m); //dLog @\sourceref{math/discreteLogarithm.cpp}@
 	return c < 0 ? -1 : powMod(g, c, m);
 }
diff --git a/math/inversions.cpp b/math/inversions.cpp
index 051408c..9e47f9b 100644
--- a/math/inversions.cpp
+++ b/math/inversions.cpp
@@ -1,5 +1,5 @@
 ll inversions(const vector<ll>& v) {
-	Tree<pair<ll, ll>> t; //ordered statistics tree
+	Tree<pair<ll, ll>> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@
 	ll res = 0;
 	for (ll i = 0; i < sz(v); i++) {
 		res += i - t.order_of_key({v[i], i});
diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
index 7dcd354..7081fea 100644
--- a/math/lgsFp.cpp
+++ b/math/lgsFp.cpp
@@ -23,4 +23,4 @@ void gauss(int n, ll mod) {
 		takeAll(n, i, mod);
 		done[i] = true;
 }}
-// für Eindeutigkeit, Existenz etc. siehe LGS
+// für Eindeutigkeit, Existenz etc. siehe LGS über R
diff --git a/math/math.tex b/math/math.tex
index a4cbde8..f5fbdca 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -261,6 +261,7 @@ 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\null

     \columnbreak

 	\sourcecode{math/transforms/bitwiseTransforms.cpp}

 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)

@@ -335,7 +336,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\

 		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\

 		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\

-		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\

+		\smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\

 		0 & \smash{\cdots} & 0 & 1 & 0 \\

 	\end{pmatrix}^k

 	\times~~

diff --git a/math/tables/prime-composite.tex b/math/tables/prime-composite.tex
index 5274cbe..4c32c7d 100644
--- a/math/tables/prime-composite.tex
+++ b/math/tables/prime-composite.tex
@@ -2,7 +2,7 @@
 	\hline
 	\multicolumn{7}{|c|}{Important Numbers} \\
 	\hline
-	$10^x$ &             Highly Composite &  \# Divs & $<$ Prime & $>$ Prime &              \# Primes & \\
+	$10^x$ &             Highly Composite &  \# Divs & $<$ Prime & $>$ Prime &                   \# Primes & \\
 	\hline
 	     1 &                            6 &        4 &      $-3$ &      $+1$ &                           4 & \\
 	     2 &                           60 &       12 &      $-3$ &      $+1$ &                          25 & \\
diff --git a/other/other.tex b/other/other.tex
index 044ad02..1760b01 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -9,7 +9,7 @@
 \end{algorithm}

 

 \begin{algorithm}{Timed}

-	Kann benutzt werdem um randomisierte Algorithmen so lange wie möglich laufen zu lassen.

+	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.

 	\sourcecode{other/timed.cpp}

 \end{algorithm}

 

@@ -23,7 +23,7 @@
 		Bit an Position j flippen & \code{x ^= (1 << j)} \\

 		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\

 		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\

-		Anzahl an bits & \code{__builtin_popcountll(x)} \\

+		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\

 		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\

 		\hline

 	\end{tabularx}\\

@@ -227,7 +227,7 @@
 	\item \textbf{Centroid Decomposition:}

 	Wähle zufälligen Knoten und mache DFS.

 	Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}.

-	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres verhält sich periodisch alle $400$ Jahre.

+	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich.

 

 	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}

 	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von

@@ -259,7 +259,7 @@
 \subsection{Tipps \& Tricks}

 

 \begin{itemize}

-	\item Run Time Error:

+	\item \textbf{Run Time Error:}

 	\begin{itemize}

 		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?

 		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?

@@ -267,13 +267,19 @@
 		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).

 	\end{itemize}

 	

-	\item Strings:

+	\item \textbf{Strings:}

 	\begin{itemize}

 		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?

 		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.

 	\end{itemize}

+

+	\item \textbf{Zeilenbasierte Eingabe}:

+	\begin{itemize}

+		\item \code{getline(cin, str)} liest Zeile ein.

+		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.

+	\end{itemize}

 	

-	\item Gleitkommazahlen:

+	\item \textbf{Gleitkommazahlen:}

 	\begin{itemize}

 		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?

 		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!

@@ -281,7 +287,7 @@
 		\item Kann \code{-0.000} ausgegeben werden?

 	\end{itemize}

 

-	\item Wrong Answer:

+	\item \textbf{Wrong Answer:}

 	\begin{itemize}

 		\item Lies Aufgabe erneut. Sorgfältig!

 		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.

diff --git a/python/io.py b/python/io.py
new file mode 100644
index 0000000..aa16d4c
--- /dev/null
+++ b/python/io.py
@@ -0,0 +1,3 @@
+n, m = map(int, input().split())
+A = list(map(int, input().split()))
+print(n, m, *A)
diff --git a/python/python.tex b/python/python.tex
new file mode 100644
index 0000000..e4346bf
--- /dev/null
+++ b/python/python.tex
@@ -0,0 +1,10 @@
+\section{Python}
+\lstset{language=Python}
+
+\subsection{IO}
+\lstinputlisting{python/io.py}
+
+\subsection{Recursion}
+\lstinputlisting{python/recursion.py}
+
+\lstset{language=C++}
diff --git a/python/recursion.py b/python/recursion.py
new file mode 100644
index 0000000..45e0147
--- /dev/null
+++ b/python/recursion.py
@@ -0,0 +1,2 @@
+import sys
+sys.setrecursionlimit(1000_007)
diff --git a/string/string.tex b/string/string.tex
index fe8e40c..4b8a880 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -35,7 +35,7 @@
 \begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome}
 	\begin{methods}
 		\method{init}{transformiert \code{string a}}{n}
-		\method{manacher}{berechnet Länge der Palindrome}{n}
+		\method{manacher}{berechnet Längen der Palindrome in longest}{n}
 	\end{methods}
 	\sourcecode{string/manacher.cpp}
 \end{algorithm}
@@ -90,7 +90,7 @@
 \begin{algorithm}{Suffix-Array}
 \begin{methods}
 	\method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})}
-	\method{lcp}{berechnet den longest common prefix}{\log(\abs{s})}
+	\method{lcp}{berechnet Länge des longest common prefix}{\log(\abs{s})}
 	\method{}{von \code{s[x]} und \code{s[y]}}{}
 \end{methods}
 \sourcecode{string/suffixArray.cpp}
diff --git a/tcr.tex b/tcr.tex
index eb428d6..369aaa8 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -57,7 +57,7 @@
 \begin{multicols*}{3}
   \raggedcolumns
   \input{string/string}
-  \input{java/java}
+  \input{python/python}
   \input{other/other}
   \input{template/template}
   \clearpage
diff --git a/tests/test.tex b/tests/test.tex
index 3e5f19b..80ac037 100644
--- a/tests/test.tex
+++ b/tests/test.tex
@@ -18,10 +18,9 @@ Dieser Abschnitt enthält lediglich Dinge die während der Practicesession getes
 	\item funktioniert \code{clock()}?
 \end{itemize}
 
-\subsection{Java}
+\subsection{Python}
 \begin{itemize}
-	\item startet eclipse?
-	\item funktionieren Java8 feature (lambdas)?
+	\item Rekursionslimit?
 \end{itemize}
 
 \subsection{Judge}