note-seaweed

A-README.md

Additional notes for https://codeforces.com/blog/entry/111625 "[Tutorial] On Range LIS Queries, Part 1 - Codeforces".

note-seaweed.pdf

note-seaweed.tex

%! TEX program = pdflatex
\documentclass{article}
\usepackage{personal}
\begin{typstmathinputaddextrapreamble}
#let match="match"
\end{typstmathinputaddextrapreamble}
\usepackage{hyperref}
\usepackage{cleveref}
\begin{document}
\typstmathinputprepare{\$}

\section{Seaweed}

Instead of visualizing it as a seaweed braid, it may be better to think of it as a \emph{transposition network}, which is a special case of a 
	\emph{sorting network}. (readers may refer to Wikipedia)

This is in fact described in chapter 10 of \cite{semilocal} by the same author.

You can visualize it as a wire diagram. We will use the following notation:
\begin{itemize}
	\item All permutation have length $n$.
	\item $I$ is the identity permutation $[1, 2, …, n]$, $R$ is the reversed permutation $[n, n-1, …, 2, 1]$.
	\item If $X$ is a permutation, we write $X₁, …, X_n$ for the elements.
\end{itemize}


We define:
\begin{definition}[Elementary sorter]
$p_i$ is a function that takes in a permutation $X$, swaps $X_i$ and $X_(i+1)$ if $X_i<X_(i+1)$, otherwise return $X$ unchanged.
\end{definition}

We call the functions $p_i$ above the \emph{elementary sorter}. (technically we should probably call it "elementary anti-sorter")

We write $X ≫ p_i$ to mean $p_i (X)$, or $p_i ≫ p_j$ to mean $p_j ∘ p_i$ (function composition) when convenient. This way, we can read the function applications "left to right".

\begin{definition}[Transposition network]
A \emph{transposition network} to be a sequence $p_i₁ ≫ p_i₂ ≫ ⋯ ≫ p_i_m$ for some nonnegative integer $m$.
\end{definition}


For example:
\begin{itemize}
	\item $[1, 2, 3] ≫ p₁ = [2, 1, 3]$.
	\item $R ≫ p_i =R$ for any $i$.
\end{itemize}

\section{The auxiliary problem}

Consider the following problem, which doesn't immediately seem to have anything to do:
\begin{quote}
	Let $A=[A₀, …, A₉]$ be a list of integers.

	You're given a list of operations $[q₁, …, q_m]$, where each operation can be one of the following:
	\begin{enumerate}
		\item $A₀ ← A₀+c$ where $c ∈ ℤ$,
		\item $A₀ ← min(A₀, b)$ where $b ∈ ℤ$,
		\item $A ← [A_π₀, …, A_π₉]$ where $π$ is a permutation of $[0, …, 9]$,
		\item $A₀ ← A₀ mod c$ where $c ∈ ℤ⁺$.
		\item $A ← A ≫ p_i$, where $p_i$ is an elementary sorter defined above.
	\end{enumerate}

	Now, there are $q$ queries, each query gives you an input array $A$ and two values $l$ and $r$, you need to compute $A ≫ q_l ≫ q_(l+1) ≫ ⋯ ≫ q_r$.

	Limits: $m ≤ 10^5$, $q ≤ 10^5$. All numbers appearing in the input is $≤ 10^9$.
\end{quote}
As is, the problem is pretty much unsolvable, but let us restrict our focus on a subset of the possible types of queries.

You may want to think about various cases first.

\begin{center}
\begin{tabular}{ccc}
	Allowed types of queries & Algorithm \\ \hline
	(1) only & fenwick tree/prefix sum array \\
	(2) only & RMQ/segment tree \\
	(3) only & segment tree \\
	(1) and (3) & segment tree \\
	(4) and (1) & (seems impossible...?)
\end{tabular}
\end{center}

We may want to think about what makes the various solutions above work.

When there's only type (3) query, the key observation is the composition of a sequence of such operations can be "compressed" into a single permutation $π=[π₀, …, π₉]$ of $[0, …, 9]$.

When there's only type (1) and (3) queries, we do the same, but this time each node of the segment tree need to store an action of the form $A₀ ← min(b, A₀+c)$.

If we generalize this, the main part is, you can in some sense take a look at the segment $q_l ≫ ⋯ ≫ q_r$ corresponds to an internal node of the segment tree, "precompute" it, such that after the precomputation you can quickly "evaluate" the action on any input array $A$.

(Optional: In fancy math terms, as a special case, you may want to say that the \emph{monoid} generated by all the operations is "small" in some sense, but this trick applies more generally. If you want to also handle \emph{operation update} query however, you do need the monoid to be "small" however.)

Looking again in the case where there's only (1) and (3) queries, while the queries themselves only has $A₀ ← A₀+c$ and $A₀ ← min(A₀, b)$ type, you naturally need to consider the operation $A₀ ← min(b, A₀+c)$ while implementing the segment tree solution.
(in math terms, the monoid generated by the type (1) and (3) queries contain these elements in addition.)

\section{Composing two seaweed braids}

So, the problem we need to ask now is the following: if there are type (5) queries in the problem above, can we solve it efficiently?

In other words, is the composition $p₁ ≫ ⋯ ≫ p_m$ something that is "quickly computable"?

The answer is yes.
\begin{theorem}
	There are at most $n!$ distinct transposition network, where two transposition networks are distinct if they have distinct output for some input.
\end{theorem}

This is in fact lemma 1 in \cite{fastdistance}.

In fact, we have a stronger theorem:
\begin{theorem}[Transposition network determined by action on $I$]\label{transposition-network-uniqueness}
	A transposition network $f$ is uniquely determined by its action on $I$.
\end{theorem}

In other words, $f$ is uniquely determined by the value of the permutation $I ≫ f$.

This is roughly theorem 3 (which shows the unit-Monge matrices are closed under $⊙$) in \cite{fastdistance}, or theorem 3.4 in \cite{semilocal}.

\subsection{Computing a composition}

Even if we don't look at the proof, if we know the theorem, we can think about:
\begin{itemize}
	\item To save memory, any transposition network can be represented by a permutation $P$, namely $f$ is represented by $I ≫ f$.

		In fact, this is precisely what \cite{tutorialrangelisqueries1} means by \emph{describing} the total operation with a single permutation.

	\item Write $P^σ$ to be the unique transposition network $f$ such that $I ≫ f = P$. Then, in order to compute the (representation) of the transposition network $P^σ ≫ Q^σ$, we can simply find any transposition network that gives $Q$ with $O(n²)$ elementary position sorter, then apply it on $P$ to get the result.
\end{itemize}

This gives an immediate $O(n²)$ algorithm to "multiply two seaweed braids".


\subsection{Proof (optional)}

I believe I have found a simpler proof than in the original paper.

For now, let us forget about the theorem above, and consider some simpler problem.
\begin{quote}
	Given a transposition network $f = p_i₁ ≫ p_i₂ ≫ ⋯ ≫ p_i_m$. If we have already computed the value of $I ≫ f$, can we compute $I ≫ (f ≫ p_j)$ and $I ≫ (p_j ≫ f)$ quickly?

	Assume $m$ is much larger than the size of the permutation $n$.
\end{quote}

Computing $I ≫ (f ≫ p_j)$ is easy, it's just equal to $(I ≫ f) ≫ p_j$. Computing $I ≫ (p_j ≫ f)$ is a bit more difficult, you can think about it.

If you trace the steps where the input $I$ flows through $f$, and the input $I ≫ p_j$ flows through $f$, you'll see that...
\begin{itemize}
	\item Any step in $f$ that does not compare the element with value $j$ and $j+1$, the behavior is the same either way.
	\item If value $j$ and $j+1$ are never compared, then the swaps are the same for both inputs.
	\item If they're ever compared, starting from the first moment they're compared, the values will be the same afterwards.
\end{itemize}

Thus the answer is, $I ≫ p_j ≫ f$ is equal to $I ≫ f$, then if the element with value $j$ is to the left of the element with value $j+1$ in the result, swap them, otherwise do nothing.

\begin{definition}[Elementary value sorter]
	$v_i$ is a function that takes in a permutation $X$, then if value $i$ appears before value $i+1$ in $X$, swap them, otherwise return $X$ unchanged.
\end{definition}

To avoid confusion, we will call the $p_j$ defined above as (elementary) \emph{position sorter}, to emphasize the fact that they look at the \emph{position} of the elements instead of the values.

With this new definition, we can write the above as: $I ≫ p_j ≫ f = I ≫ f ≫ v_j$ for any (position) sorting network $f$.

But, we have accidentally proved that:
\begin{claim}
	If $X$ is a permutation that is $I$ with two adjacent elements swapped, then $X ≫ f$ is uniquely determined by the value of $I ≫ f$.
\end{claim}
\begin{proof}
Write $X = I ≫ p_j$, then $X ≫ f = I ≫ p_j ≫ f = (I ≫ f) ≫ v_j$.
\end{proof}

Hopefully it's natural to see how to generalize the above to handle all cases.

\begin{claim}
	$v_j$ commutes with any position sorting network.
\end{claim}
You can prove this by (exhaustively) consider some cases -- it suffices to prove $v_j$ commutes with the elementary position sorter.

\begin{claim}
	Any permutation $X$ is equal to $I ≫ v_i₁ ≫ v_i₂ ≫ ⋯ ≫ v_i_m$ for some $m ≥ 0$.
\end{claim}

Now we can prove \cref{transposition-network-uniqueness}: for any permutation $X$, write $X = I ≫ v_i₁ ≫ ⋯ ≫ v_i_m$, then $X ≫ f = (I ≫ f) ≫ v_i₁ ≫ ⋯ ≫ v_i_m$ by commutativity, we're done.


\subsection{Faster algorithm}

It's possible to solve this in $O(n log n)$, using the so-called Steady Ant algorithm as mentioned in \cite{efficientstringcomparison}.

TODO How?

\section{Intuition behind the original paper's notation}

If you think about the seaweed braid as a transposition network, what does a braid actually \emph{mean}?

In the case the seaweed braid is \emph{reduced}, then each seaweed corresponds to the \emph{flow} of a value, assume the original input is $I$.

What does $p^R$ corresponds to, then? It's a braid, where in the braid that corresponds to $p^R ≫ p$, each pair of seaweed cross exactly once.

\section{Embedding in the multiplicative monoid of the min-plus matrix multiplication semiring}

This section is not necessary to understand the content, but it tries to give some intuition on what the mathematical notation of the original paper is about.

For now, we will write $p ⟨0:i, 0:j⟩$ to mean the number of seaweeds (in the reduced braid that corresponds to the transposition network $p$) that starts in position within $[0:i]$ and ends in position within $[0:j]$.

(the notation here is Python's |slice| notation, so a position $j$ is in $[0:i]$ if $0 ≤ j<i$.)

Consider the matrix $p^Σ$.
If you think about it, the $(i, j)$ entries in $p^Σ$ is precisely $p ⟨i:n, 0:j⟩$.

Which means the following, where $p$ and $q$ are any transposition network and $r = p ≫ q$:
\begin{theorem}
	For any $i$ and $j$, then $r ⟨0:i, j:n⟩ = min_(k=0)^n p ⟨0:i, k:n⟩+q ⟨0:k, j:n⟩$.
\end{theorem}
This is precisely the content of theorem 4 in \cite{fastdistance}.

While this looks symmetric, I think it doesn't give too much intuition. So, if you subtract $i$ from both sides and negate them, you get the following:
\begin{theorem}
	For any $i$ and $j$, then $r ⟨0:i, 0:j⟩ = max_(k=0)^n p ⟨0:i, 0:k⟩-q ⟨0:k, j:n⟩$.
\end{theorem}
I think this is much more intuitive: the number of seaweeds that starts from $0:i$ and ends in $0:j$ in the composition is the maximum of number of seaweeds that starts from $0:i$, touch the splitting point in $0:k$, then you need to subtract the number of seaweeds that "derails" from $0:k$ to $j:n$.

Unfortunately, I don't have a direct proof apart from showing that the relation is \emph{associative}, and holds when $q$ is an elementary position sorters, and use induction.

\section{Additional properties of the operation}\label{additionalproperties}

We have the following obvious properties, which shows how to "evaluate" a transposition network (given implicitly as a permutation) on some integer array.
\begin{enumerate}
	\item $(I ≫ f)^σ = f$. (by definition)
	\item Given $P$ and $Q$, the permutation that corresponds to the composition can be computed by $I ≫ P^σ ≫ Q^σ$.
	\item (evaluating $f(P)$ for permutation $P$) Given a permutation $P$ and transposition network $f$, we can compute $f(P)$ by composing $P^σ$ with $f$ -- namely, $I ≫ P^σ ≫ f$.
	\item (evaluating $f(A)$ for arbitrary array $A$) Given a permutation $P$, an array $A$ with the same element ordering as $P$ i.e. $P_i<P_j ⟹ A_i ≤ A_j$, then for any transposition network $f$, $f(A)_i = A_j$ where $j$ is such that $P_j = f(P)_i$.
	\item 
		\label{evalbinary}
		(evaluating $f$ on sorted binary array) For each $i$, let $A^((i))$ be the array where first $i$ elements is $0$ and last $n-i$ elements is $1$, then, given $I ≫ f$, we can implicitly compute all of $f(A^((0))), f(A^((1))), …, f(A^((n)))$ in $O(1)$ time. 
	\item ($f$ is order-preserving) If $A$ and $B$ are arrays, $A_i ≤ B_i$ for all $i$, then $f(A)_i ≤ f(B)_i$ for all $i$.
\end{enumerate}

\section{Relationship with the all-pair LCS problem}

Maybe a (slightly) clearer presentation than \cite{tutorialrangelisqueries1}.

We consider how we can solve the global LCS problem by passing a \emph{single} binary array into a transposition network. This is in fact similar to the explanation seen in \cite{efficientstringcomparison}.

Let $S$ be a string of length $n$, $T$ be a string of length $m$. Let $match(i, j)$ to be the longest common subsequence of $S[:i]$ and $T[:j]$ (0-indexed, Python |slice| notation, $0 ≤ i ≤ n$, $0 ≤ j ≤ m$).

We will use the convention that a coordinate $(i, j)$ corresponds to row $i$ and column $j$, as in matrix indexing.

(\cite{tutorialrangelisqueries1} uses "dist" for this function, but this is a bit confusing because "dist" usually mean shortest distance)

We have the obvious recurrence: For $i, j>0$, then
$
match(i, j) = cases(
match(i-1, j-1) &"if "S[i-1] = T[j-1],
max(match(i-1, j), match(i, j-1)) &"otherwise"
).
$

Our goal is to reduce the problem to a transposition problem \emph{on binary input}.

We observe that $match(i, j)$ is monotonically increasing with both parameters $i$ and $j$, and if $i$ or $j$ increase by $1$ then $match(i, j)$ changes by at most $1$ (lemma 1 and 2 in \cite{tutorialrangelisqueries1}).

So, a natural option is for us to take the consecutive difference in some direction.
Take $δ_v (i, j) = match(i, j)-match(i-1, j)$ and $δ_h (i, j) = match(i, j)-match(i, j-1)$, then all of their values are $0$ or $1$.

(remark: the subscript $h$ or $v$ here corresponds to whether the difference is taken \emph{horizontally} or \emph{vertically}, recall that first coordinate is for row and second coordinate is for column.)

That's \emph{roughly} what the $i_h$ and $i_v$ in \cite{tutorialrangelisqueries1} does, however, if we naively do that and all the input (i.e. the consecutive difference in the very first column and row) are all $0$, then the output of the transposition network would be 0.

The second natural option then, is to flip one of the two. Thus we define
$δ_h (i, j) = 1-(match(i, j)-match(i, j-1))$.

Now, we can simply exhaustively check all possibilities to get the equivalent of theorem 5 in \cite{tutorialrangelisqueries1}.

Finally, we have reduced the global LIS problem to a problem of evaluating a transposition network on binary input, applying the last property \cref{evalbinary} in \cref{additionalproperties}, we're done.

\section{Exercises}

The 2nd Universal Cup. Stage 5: Northern. Problem L, "LCSLCSLCS".  \url{https://contest.ucup.ac/contest/1388/problem/6557}

\section{Unwritten section}


A monoid is a structure...

We can see that, any collection of $S → S$ functions that is closed under composition will form a

So, essentially this shows that the distance multiplication monoid of unit-Monge matrices is isomorphic to the seaweed monoid. This is theorem 4 in \cite{fastdistance}.

There's some other relation:
\begin{itemize}
	\item The matrix $P_A$ is a permutation matrix, which is exactly equal to the permutation $P$. (TODO check!)
	\item The item $(i, j)$ ...
\end{itemize}

\begin{thebibliography}{9}

\bibitem{semilocal}
Semi-local string comparison: Algorithmic techniques and applications, arXiv:0707.3619v21.

\bibitem{fastdistance}
Fast Distance Multiplication of Unit-Monge Matrices, DOI 10.1007/s00453-013-9830-z.

\bibitem{stringcomparison}
String comparison by transposition networks, Peter Krusche and Alexander Tiskin, arXiv:0903.3579v1.

\bibitem{tutorialrangelisqueries1}
On Range LIS Queries, Part 1. ko\_osaga. \url{https://codeforces.com/blog/entry/111625}

\bibitem{efficientstringcomparison}
Efficient Parallel Algorithms for String Comparison, Nikita Mishin, Daniil Berezun, Alexander Tiskin,
\url{https://doi.org/10.1145/3472456.3472489}

\end{thebibliography}

\end{document}