1896A - Пиковые обмены

Observe that since we are only allowed to choose $$$i \ge 2$$$ to swap $$$a_i$$$ and $$$a_{i+1}$$$, it means that $$$a_1$$$ cannot be modified by the operation. Hence, $$$a_1 = 1$$$ must hold. In fact, we can prove that as long as $$$a_1 = 1$$$, we will be able to sort the array.

Consider the largest element of the array. Let its index be $$$i$$$. Our objective is to move $$$a_i$$$ to the end of the array. If $$$i = n$$$, it means that the largest element is already at the end. Otherwise, since $$$a_i$$$ is the largest element, this means that $$$a_{i-1} < a_i$$$ and $$$a_i > a_{i+1}$$$. Hence, we can do an operation on index $$$i$$$ and move the largest element one step closer to the end. We repeatedly do the operation until we finally move the largest element to the end of the array. Then, we can pretend that the largest element does not exist and do the same algorithm for the prefix of size $$$n - 1$$$. Hence, we will able to sort the array by doing this repeatedly.

1896B - AB-обмен

If the string consists of only $$$\texttt{A}$$$ or only $$$\texttt{B}$$$, no operations can be done and hence the answer is $$$0$$$. Otherwise, let $$$x$$$ be the smallest index where $$$s_x = \texttt{A}$$$ and $$$y$$$ be the largest index where $$$x_y = \texttt{B}$$$. If $$$x > y$$$, this means that the string is of the form $$$s=\texttt{B}\ldots\texttt{BA}\ldots\texttt{A}$$$. Since all the $$$\texttt{B}$$$ are before the $$$\texttt{A}$$$, no operation can be done and hence the answer is also $$$0$$$.

Now, we are left with the case where $$$x < y$$$. Note that $$$s[1,x-1] = \texttt{B}\ldots\texttt{B}$$$ and $$$s[y+1,n] = \texttt{A}\ldots\texttt{A}$$$ by definition. Since the operation moves $$$\texttt{A}$$$ to the right and $$$\texttt{B}$$$ to the left, this means that $$$s[1,x - 1]$$$ will always consist of all $$$\texttt{B}$$$ and $$$s[y + 1, n]$$$ will always consist of all $$$\texttt{A}$$$. Hence, no operation can be done from index $$$1$$$ to $$$x - 1$$$ as well as from index $$$y$$$ to $$$n - 1$$$.

The remaining indices where an operation could possibly be done are from $$$x$$$ to $$$y - 1$$$. In fact, it can be proven that all $$$y - x$$$ operations can be done if their order is chosen optimally. Let array $$$b$$$ store the indices of $$$s$$$ between $$$x$$$ and $$$y$$$ that contain $$$\texttt{B}$$$ in increasing order. In other words, $$$x < b_1 < b_2 < \ldots < b_k = y$$$ and $$$b_i = \texttt{B}$$$, where $$$k$$$ is the number of occurences of $$$\texttt{B}$$$ between $$$x$$$ and $$$y$$$. For convenience, we let $$$b_0 = x$$$. Then, we do the operations in the following order:

$$$b_1 - 1, b_1 - 2, \ldots, b_0 + 1, b_0,$$$

$$$b_2 - 1, b_2 - 2, \ldots, b_1 + 1, b_1,$$$

$$$b_3 - 1, b_3 - 2, \ldots, b_2 + 1, b_2,$$$

$$$\vdots$$$

$$$b_k - 1, b_k - 2, \ldots, b_{k - 1} + 1, b_k$$$

It can be seen that the above ordering does operation on all indices between $$$x$$$ and $$$y - 1$$$. To see why all of the operations are valid, we look at each row separately. Each row starts with $$$b_i - 1$$$, which is valid as $$$s_{b_i} = \texttt{B}$$$ and $$$s_{b_i - 1} = \texttt{A}$$$ (assuming that it is not the last operation of the row). Then, the following operations in the same row move $$$\texttt{B}$$$ to the left until position $$$b_{i - 1}$$$. To see why the last operation of the row is valid as well, even though $$$s_{b_{i - 1}}$$$ might be equal to $$$\texttt{B}$$$ initially by definition, either $$$i = 1$$$ which means that $$$s_{b_0} = s_x = \texttt{A}$$$, or an operation was done on index $$$b_{i - 1} - 1$$$ in the previous row which moved $$$\texttt{A}$$$ to index $$$b_{i - 1}$$$. Hence, all operations are valid.