\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{CodeForces 1698F}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 110}
\maketitle
\section*{Problem}
There is a sequence $a = (a_1, \dots, a_n)$ of $n$ real numbers.
You may perform the following operation on it:
choose two integers $1 \le \ell \le r \le n$ where $a_l = a_r$,
and reverse the subsequence from the $\ell$\ts{th} to the $r$\ts{th} element,
i.e.\ change $(a_\ell, a_{\ell + 1}, \ldots, a_{r - 1}, a_r)$
to $(a_r, a_{r-1}, \ldots, a_{l+1}, a_\ell)$.
Given another sequence $b = (b_1, \dots, b_n)$,
determine in $O(n \log n)$ time
whether there exists finite sequence of moves changing $a$ into $b$.
\section*{Video}
\href{https://www.youtube.com/watch?v=h3CEfCfK924&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/h3CEfCfK924}}
\section*{External Link}
\url{https://codeforces.com/problemset/problem/1698/F}
\newpage
\section*{Solution}
We give two invariants:
\begin{itemize}
\ii The leftmost and rightmost elements obviously never change.
\ii Construct an undirected graph $G$ on the set of real numbers
by creating one edge $\{a_i, a_{i+1}\}$ for each $i=1,\dots,n-1$,
self-loops and multiple edges allowed (hence exactly $n-1$ edges).
Then $G$ never changes.
\end{itemize}
\begin{claim*}
If these invariants are the same between $a$ and $b$,
then it's possible to take $a$ to $b$.
\end{claim*}
\begin{proof}
By induction on $n$.
Let $a_1 = b_1 = x$ and $b_2 = y$.
We know $x$ is next to $y$ somewhere,
so perform a move to make the second element of $a$ equal to $y$.
Then continue the induction.
\end{proof}
\end{document}