\section{Increasing Cost Vectors}
\subsection{General Observations}

We say that a swap of a number $m$ with a number $m'$ is called a \emph{step}.
During this step, $m$ does one \emph{semistep} and $m'$ does another one.
Our approach is to examine the trajectories of individual numbers and the semisteps
that they make in a particular strategy.
Formally, by a \emph{trajectory} of a number $m$ in a strategy $\St$ we mean
the sequence of positions occupied by $m$ during $\St$. The sequence of $m$'s left/right
semisteps is called the \emph{tour} of $m$.
Note that two distinct trajectories of $m$ may define the same tour, because $m$
does not change position in every step.

Regardless of the strategy, each number $m$ has a unique hypothetic \emph{ideal
trajectory} that goes from the original position $m$ straight to the final position
$n-m+1$. It is easy to observe that in any reversing strategy, each number's
trajectory includes the ideal one (perhaps interleaved with other positions), and the same is true for tours.

Let $s$ be a semistep of a number $m$ from position $p$ to $p'$ in a strategy $\St$.
If a semistep from $p$ to $p'$ belongs to $m$'s ideal tour and if $s$ is the first
semistep of $m$ from $p$ to $p'$ in $\St$, we call $s$ a \emph{necessary semistep} in $\St$.
Otherwise, we call it an \emph{unnecessary semistep} in $\St$.

\begin{lemma}\label{steps}
Any optimal reversing strategy performs $n^2 - n$ semisteps, out of which
$\lfloor n^2 / 2 \rfloor$ are necessary and $\lceil n^2 / 2 - n\rceil$
are unnecessary semisteps.
\end{lemma}
\begin{proof}
It follows from Corollary~\ref{col:shortest} that there are $n \choose 2$ steps,
hence $n^2 - n$ semisteps.

The number of necessary semisteps done by a number $m$ is
the distance between the initial position $m$ and the final position $n - m + 1$.
By summing this over all numbers, we get
$$\sum_{m=1}^{\lfloor{\frac n 2}\rfloor} (n - 2m + 1) + \sum_{m=\lfloor{\frac n 2}\rfloor+1}^n (2m - n - 1).$$
If $n$ is odd, this yields $n^2/2 - 1/2$, and for $n$ even, the result is $n^2/2$, as desired.
The remaining semisteps are the unnecessary semisteps, so their number is simply the difference of $n$ and $\lfloor n^2 / 2 \rfloor$.
\end{proof}

\subsection{Increasing and Non-decreasing Weights}
\def\ssta{$s_{\hbox{\scriptsize{start}}}$}
\def\send{$s_{\hbox{\scriptsize{end}}}$}
\def\De{\mathcal{D}}

There is a simple strategy which we call the Bubble strategy, $\St_B$:
\begin{algorithmic}
 \FOR{$j= 1$ to $n-1$}
 \FOR{$i = 1$ to $n-j$}
\item    swap the number at $i$-th position with number at $(i+1)$-th position
 \ENDFOR \ENDFOR 
\end{algorithmic}

\begin{proposition}\label{prop:bubble-cost}
The cost $\c_\w(\St_B)$ is $\sum_{j=1}^{n-1} (n-j) \w_j$.
\end{proposition}
\begin{proof}
The cost of $j$-th cycle is $\sum_{i=1}^{n-j} \w_i $. The total cost over all cycles is
$$ \sum_{j=1}^{n-1} \sum_{i=1}^{n-j} \w_i = \sum_{j=1}^{n-1} (n-j) \w_j.$$
\end{proof}

\begin{theorem}\label{thm:optimal}
Let $\w$ be a non-decreasing cost vector. Then the Bubble strategy is optimal, and the
cost of any optimal strategy is $\sum_{j=1}^{n-1} (n-j) \w_j$.
\end{theorem}

Before we prove the theorem, we need several definitions and lemmas.
Assume that a number $m$ left a position $i$ during step \ssta,
and then $m$ first returned to $i$ during step \send.
We call the pair $(\hbox{\ssta},\hbox{\send})$ a \emph{zigzag}, a the sequence of
semisteps starting by \ssta{} and ending with \send{} is called a \emph{detour of $m$}.
Note that $m$ goes either to the right during \ssta{} and to the left during
\send, or vice versa.  We call these cases a \emph{right zigzag} and
\emph{right detour}, or a \emph{left zigzag} and \emph{left detour}, respectively.

Since weights of transpositions only increase rightwards, one may observe that right detours
are undesirable. Indeed, we have the following proposition.  

\begin{proposition}\label{thm:no-detours}
In an optimal reversing strategy for an increasing cost vector $\w$, no number makes any right detour.
If $\w$ is non-decreasing, then there exists an optimal strategy without any right detours.
\end{proposition}
\begin{proof}
Let $\w$ be a non-decreasing cost vector and let $\St$ be a reversing
strategy optimal for $\w$. We modify $\St$ so that all right detours are destroyed
without increasing the total cost.

Let $\De$ be a right detour of a number $m$ starting with step \ssta{} and ending with \send.
Let $a_1$, \dots, $a_j$ be all the numbers that are positioned to the left of $m$ before \ssta.
We say that $\De$ is \emph{extreme} if none of the numbers $a_1$, \dots, $a_j$ does a right
detour between \ssta{} and \send. Observe that for any right detour, there is at least one extreme right detour
to the left of it; hence, we can without loss of generality assume that $\De$ is extreme.
Further, we assume that $\De$ is minimal in inclusion, i.e., only the \ssta{} and \send{} steps change the
position of $m$.

Let $b$ and $c$ be the numbers swapped with $m$ during \ssta{} and \send, respectively.
Then $c\in\{a_1,\dots,a_j\}$, otherwise $c$ would be swapped with $m$ more than once.
Clearly, $b \not\in\{a_1,\dots,a_j\}$. Let the permutation before \ssta{} be
$$a_1, a_2, \dots, a_l, c, a_{l+2}, \dots, a_{j-1}, a_j, m, b, \dots$$

From \ssta{} to \send, the number $c$ moves $j-l$ positions to the right. By the extremality
of $\De$, the number $c$ does not do any semistep to the left (otherwise, there is a right detour).
Hence between \ssta{} and \send, the number $c$ does exactly $j-l$ semisteps, all of them to the right.
By a slight abuse of notation, we denote them $s_1$, \dots, $s_{j-l}$.

\begin{lemma}\label{lemma:order}
During the steps $s_1$, \dots, $s_{j-l}$, the number $c$ was
swapped with $a_{l+2}$, $a_{l+3}$, \dots, $a_{j-1}$, $a_j$, $b$, in this order.
\end{lemma}
\begin{proof}
Throughout this proof we consider only swaps that are done from \ssta{} to \send{}.
Suppose that, in the step $s_{j-l}$, the number $c$ was swapped with a number $x$.

Since $c$ never goes left and $m$ never goes right after \ssta{},
no number can get between $m$ and $c$ except for $a_{l+2}$, \dots, $a_j$, $b$.
Hence, if $x$ is not $b$, then $x\in \{a_{l+2},\dots,a_j\}$, and it must have
moved to the right so as to get to its position before $s_{j-l}$.
But during $s_{j-l}$, the number $x$ goes left, so the tour of $x$ contains
a right detour. A contradiction with the extremality of $\De$.
So $c$ was swapped with $b$ during $s_{j-l}$.

The rest of the claim follows by induction using the same arguments
for the numbers $a_j$ down to $a_{l+2}$.
\end{proof}

We continue the detour-destroying proof by reordering the strategy steps to create a new strategy $\St'$.
It follows from Lemma~\ref{lemma:order} that none of $a_{l+2}$, \dots, $a_j$, $b$ was
swapped with anything before its swap with $c$. Also, neither $m$ nor $b$ is involved in any of
$s_1$, \dots, $s_{j-l-1}$. Hence we can move these steps back in time and do them before the beginning
of the detour $\De$.

Then, instead of \ssta{}, we swap $c$ and $m$, because they are now neighbors.
We perform all the steps that remain before \send{} with the role of $c$ and $m$ exchanged.
After that, instead of \send{} we do nothing, because $c$ and $m$ have already been swapped.
Now the permutation is the same as it was after \send{}, and the rest of the
strategy is the same as in $\St$.

So the new strategy $\St'$ is the following:
\begin{enumerate}
\item all steps of $\St$ before \ssta{},
\item $s_1$, \dots, $s_{j-l-1}$,
\item swap the pair $(c, m)$,
\item all the remaining steps of $\St$ from \ssta{} to the one before \send{} (with the role of $m$ and $c$ exchanged),
\item all steps of $\St$ after \send{}.
\end{enumerate}

By the arguments above, $\St'$ is a correct reversing strategy.
Now we compare the costs of $\St$ and $\St'$.
We have removed \send{} and introduced a new swap $(c,m)$. The remaining swaps were reordered, but
their positions were preserved, and costs as well.
Say that the swap \send{} occured at position $i$, and its cost is $w_i$.
Then the swap $(c,m)$ ocurred at position $i-1$, so it costs $w_{i-1}$.
Hence the total cost was not increased, and if $w_{i-1} < w_i$, it was even decreased.

Our aim is to show that $\St'$ is better, meaning that it contains ``less'' right detours.
Indeed, we prove that $\St'$ contains less right zigzags.

By doing the above modification to $\St$, the trajectories of numbers were changed.
But it is straightforward to verify that the tours of all numbers except for $b$ and $m$
are preserved, hence the number of their zigzags remains the same.

{\bf XXX} The tours of $m$ and $b$

Clearly, if the strategy $\St$ contains any right detours, there is at least one
right zigzag. Hence, if the cost vector $\w$ is increasing, we perform the above modification
and get a contradiction with the optimality of $\St$.

If $\w$ is non-decreasing, then applying the above modification to an optimal strategy $\St$
preserves the cost while decreasing the number of right zigzags by one.
By applying it repeatedly, we obtain an optimal strategy without any right detours.
\end{proof}

The following lemma is an immediate corollary of Proposition~\ref{thm:no-detours}.

\begin{lemma}\label{r-l}
Let $m$ be a number. In a trajectory of $m$ without right detours,
all left semisteps precede all right ones.
Furthermore, in the trajectory of $m$, there is at most one left
detour and that is situated to the left of the leftmost position
of the ideal trajectory of $m$.
\end{lemma}

\begin{lemma}\label{lemma:trajectories}
Let $\w$ be a non-decreasing cost vector. In an optimal strategy for $\w$, every number
first goes leftwards to the first position, and then rightwards to its final one.
\end{lemma}
\begin{proof}
We count the lengths of longest possible detours of each number.
By Corollary~\ref{r-l}, the detour of a number $j$ must be positioned to the left
of $j$'s ideal trajectory, i.e., it must be within the $\mathop{\min}{(j-1, n-j)}$ leftmost
positions. And since all the left steps precede all right ones, $j$ can go only once
in each direction, and the length of $j$'s detour is at most twice the number of these positions.

Assume that $n$ is even, and let $n=2k$. By summing up the maximal detour lengths, we get
$$\sum_{j=1}^{k} 2(j-1) + \sum_{j=k+1}^{2k} 2(2k-j) = 2k(k-1) =  n^2/2 - n.$$

If $n = 2k+1$, then the sum of maximal detour lengths is
$$\sum_{j=1}^{k} 2(j-1) + \sum_{j=k+1}^{2k+1} 2(2k + 1 -j),$$
which is
$$k^2 - k + k^2 + k = 2k^2 = \frac {n^2} 2 - n + \frac 1 2.$$

Since in both cases we are summing integers, the resulting expressions are also integral
and equal to $\lceil n^2 / 2 - n\rceil$. But by Lemma~\ref{steps}, that is the number of
unnecessary semisteps present in any optimal algorithm. Hence, the detour of every number must
be the unique longest possible one. {\bf XXX proc}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:optimal}]
We compare the trajectories of numbers in Bubble to the trajectories
described by Lemma~\ref{lemma:trajectories}.

It is then easy to see that, in the Bubble strategy, a number $m$ first
goes one step left per each of the first $m-1$ cycles,
then it reaches the first position and in the $m$-th cycle, it is bubbled to its final position, $n-m+1$.
After that, no step involves that position, so $m$ does not move.
Hence, the trajectory of $m$ is the same as the one described by Lemma~\ref{lemma:trajectories}.

We have shown that the number trajectories of Bubble and any optimal strategy are identical.
Therefore, the costs of all semisteps in any optimal strategy sum up to the same
cost as for Bubble. Hence Bubble is optimal, and the cost of Bubble is $\sum_{j=1}^{n-1} (n-j) \w_j$
by Proposition~\ref{prop:bubble-cost}.
\end{proof}