## [problem:1896A]↵
↵
<spoiler summary="Hint 1">↵
Look at the samples.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
## [problem:1896B]↵
↵
<spoiler summary="Hint 1">↵
What happens when $s$ starts with some $\texttt{B}$ and ends with some $\texttt{A}$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
## [problem:1896C]↵
↵
<spoiler summary="Hint 1">↵
Consider a greedy algorithm.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For simplicity, assume that both arrays $a$ and $b$ are sorted in increasing order. The final answer can be obtained by permuting the answer array using the same permutation to permute sorted array $a$ to the original array $a$.↵
↵
**Claim**:↵
If the rearrangement $b_{x + 1}, b_{x + 2}, \ldots, b_n, b_1, b_2, \ldots, b_x$ does not have beauty $x$, it is not possible to rearrange $b$ to make the beauty equals to $x$.↵
↵
*Proof*: Suppose there exists an alternative rearrangement different from above represented by permutation $p$ where $b_{p_1}, b_{p_2}, \ldots, b_{p_n}$ results in a beauty of $x$. Let array $q$ represent the $x$ indices where $a_i > b_{p_i}$ in increasing order. In other words, $1 \le q_1 < q_2 < \ldots < q_x \le n$ and $a_{q_i} > b_{p_{q_i}}$. Let $i$ be the largest index where $q_i \neq n - i + 1$ ($q_i < n - i + 1$ also holds due to strict inequality above). We know that $a_{q_i} > b_{p_{q_i}}$ and $a_{n - i + 1} \le b_{p_{n - i + 1}}$. Since $a$ is sorted and $q_i < n - i + 1$, we have $a_{q_i} \le a_{n - i + 1}$, and hence, $a_{n - i + 1} > b_{p_{q_i}}$ and $a_{q_i} \le b_{p_{n - i + 1}}$. This means that we can swap $p_{q_i}$ with $p_{n - i + 1}$ without changing the beauty of the array, while allowing $q_i = n - i + 1$. Hence, by doing the swapping repeatedly, we will get $q_i = n - i + 1$ for all $i$ between 1 and $x$.↵
↵
An alternative interpretation to the result above is that we managed to obtain a solution where for all $i$ between $1$ and $n - x$, we have $a_i \le b_{p_i}$. On the other hand, for all $i$ between $n - x + 1$ and $n$, we have $a_i > b_{p_i}$. Let $i$ be the largest index between $1$ and $n - x$ where $p_i \neq i + x$ ($p_i < i + x$ due to maximality). Then, let $j$ be the index where $p_j = i + x$. Consider two cases:↵
↵
- $j \le n - x$. Since $i$ is the largest index where $p_i \neq i + x$, this means that $j < i$ and hence $a_j \le a_i$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j \le a_i \le b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$.↵
- $j > n - x$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j > b_{p_j} = b_{i + x} > b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$.↵
↵
By repeating the above repeatedly, we can obtain a solution where $p_i = i + x$ for all $i$ between $1$ and $n - x$. Let $i$ be the smallest index between $n - x + 1$ and $n$ where $p_i \neq i - n + x$ ($p_i > i - n + x$ by minimality). Then, let $j$ be the index where $p_j = i - n + x$. Note that $j > n - x$ as well since $p_i = i + x$ for all $i$ between $1$ and $n - x$. Since $i$ is the smallest index where $p_i \neq i - n + x$, this means that $i < j$ and hence $a_i \le a_j$. We have $a_i > b_{p_i} \ge b_{i - n + x} = b_{p_j}$ and $a_j \ge a_i > b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i - n + x$. By doing this repeatedly, we can obtain a solution where $p_i = i - n + x$ for all $i$ between $n - x + 1$ and $n$. Now, $p = [x + 1, x + 1, \ldots, n, 1, 2, \ldots, x]$, which matches the rearrangement in our claim.↵
</spoiler>↵
↵
# [problem:1896D]↵
↵
<spoiler summary="Hint 1">↵
Consider some small examples and write down every possible values of subarray sums. Can you see some patterns ?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Denote $s[l,r]$ as the sum of subarray from $l$ to $r$.↵
↵
↵
**Claim**: If there is any subarray with sum $v\ge 2$, we can find a subarray with sum $v-2$.↵
*Proof*: Suppose $s[l,r]=v$, consider 3 cases:↵
- $a[l]=2$, we have $s[l+1,r]=v-2$.↵
- $a[r]=2$, we have $s[l,r-1]=v-2$.↵
- $a[l]=a[r]=1$, we have $s[l+1,r-1]=v-2$.↵
↵
So in order to check if there exists a subarray whose sum equals to $v$, we can find maximum subarray sum having the same parity with $v$ and compare it with $v$.↵
↵
The case where $(s[1,n]-v)\%2=0$ is obvious, suppose the opposite happens. If array $a$ is full of $2$-s, the answer is $\texttt{NO}$. Otherwise, let $x$ and $y$ be the positions of the first $1$ and last $1$ in $a$. Any subarray with $l\le x\le y\le r$ will have different parity with $v$. So we will compare $\max(s[l+1, n],s[1,r-1])$ with $v$ to get the answer.↵
</spoiler>↵
↵
# [problem:1896E]↵
↵
<spoiler summary="Hint 1">↵
For each index $i$ from $1$ to $n$, let $h_i$ denote the number of cyclic shifts needed to move $a_i$ to its correct spot. In other words, $h_i$ is the minimum value such that $(i + h_i - 1)\ \%\ n + 1 = a_i$. How can we get the answer from $h_i$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For convenience, we will assume that the array is cyclic, so $a_j = a_{(j - 1)\ \%\ n + 1}$. The answer for each index $i$ from $1$ to $n$ is $h_i$ (defined in hint 1) minus the number of indices $j$ where $i < j < i + h_i$ and $i < a_j < i + h_i$ (or $i < a_j + n < i + h_i$ to handle cyclic case when $i + h_i > n$). This is because the value that we are calculating is equal to the number of positions that $a_i$ will skip during the rotation as the index is already good.↵
↵
To calculate the above value, it is convenient to define an array $b$ of size $2n$ where $b_i = a_i$ for all $i$ between $1$ to $n$, and $b_i = a_{i - n} + n$ for all $i$ between $n + 1$ to $2n$ to handle cyclicity. We will loop from $i = 2n$ to $i = 1$, and do a point increment to position $a_i$ if $a_i \ge i$, otherwise, do a point increment to position $a_i + n$. Then, to get the answer for index $i$, we do a range sum query from $i + 1$ to $i + h_i - 1$. Point increment and range sum query can be done using binary indexed tree in $O(\log n)$ time per query/update. Hence, the problem can be solved in $O(n\log n)$ time.↵
</spoiler>↵
↵
# [problem:1896F]↵
↵
<spoiler summary="Hint 1">↵
The operation is equivalent to toggling $s$ at every odd $i$ where $b_i$ is an open bracket and every even $i$ where $b_i$ is a closed bracket.↵
*Proof*: Suppose there are $x$ open brackets and $y$ close brackets between positions $1$ and $i$. Note that $x \ge y$ by definition of balanced bracket sequences.↵
- Case 1: $b_i$ is an open bracket. Position $i$ will be toggled exactly $x - y$ times as $y$ of the open brackets will be matched before position $i$, and the remaining $x - y$ open brackets will only be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is odd, and hence, $x - y + 2y = x + y = i$ must be odd as well.↵
- Case 2: $b_i$ is a close bracket. Position $i$ will be toggled exactly $x - y + 1$ times as $y - 1$ of the open brackets will be matched before $i$, $1$ of the open bracket will be matched with position $i$, and the remaining $x - y$ open brackets will be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is even, and hence, $x - y + 2y = x + y = i$ must be even as well.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Every operation will always toggle $s_1$ and $s_n$. Furthermore, every operation will always toggle an even number of positions.↵
*Proof*: If $s$ is toggled at an open bracket, $s$ will be toggled at its matching close bracket as well.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $s_1 \neq s_n$ or there is an odd number of $\texttt{1}$s in $s$, it is not possible to change all elements of $s$ to $\texttt{0}$. Otherwise, it is always possible.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If it is possible to change all elements of $s$ to $\texttt{0}$, at most $3$ operations are needed.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
From hint 3, we know the cases where it is impossible to change all elements of $s$ to $\texttt{0}$. We will now only consider the case where it is possible to change all elements of $s$ to $\texttt{0}$.↵
↵
Using hint 1, we can easily check whether it is possible to change all elements of $s$ to $\texttt{0}$ using only one operation by first constructing the bracket sequence then checking whether the resultant bracket sequence is balanced. From now on, we will assume that it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation.↵
↵
Suppose $s_1 = s_n = \texttt{1}$. We know from hint 2 that each operation will always toggle $s_1$ and $s_n$, so since it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation, we will need three operations. If we let the first operation be $b=\texttt{(()()}\ldots\texttt{()())}$, $s_1$ and $s_n$ will be toggled while the remaining elements stays the same. Now, $s_1 = s_n = \texttt{0}$, so if we are able to solve this case using only two operations, it means that we can solve the $s_1 = s_n = \texttt{1}$ case using only three operations.↵
↵
To solve the final case where $s_1 = s_n = \texttt{0}$, we will look at a special balanced bracket sequences $b = \texttt{(()()}\ldots\texttt{()())}$. Notice that if we do an operation using this bracket sequence, only $s_1$ and $s_n$ will be toggled. Suppose there exist an index $i$ between $2$ and $2n - 2$ where we want to toggle both $s_i$ and $s_{i + 1}$. We can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, then swap $b_i$ and $b_{i + 1}$. This will always result in a balanced bracket sequence that will toggle $s_1$, $s_n$, as well as the desired $s_i$ and $s_{i + 1}$. This will allow us to change all elements of $s$ to $\texttt{0}$ in $2n$ moves as we can scan from $i = 2$ to $i = 2n - 2$ and do an operation toggling $s_i$ and $s_{i+1}$ if $s_i = \texttt{1}$. Since there is an even number of $\texttt{1}$s in $s$ from hint 3, toggling adjacent positions will always change all elements of $s$ to $\texttt{0}$.↵
↵
In order to reduce the number of operations from $2n$ to $2$, notice that a lot of the operations can be parallelised into a single operation. Let $A_0$ represent the set of even indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. Similarly, let $A_1$ represent the set of odd indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. In a single operation, we can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, and swap $b_i$ and $b_{i + 1}$ for all $i$ that is in the set $A_0$. Since $A_0$ only contains even indices, the swaps are non-intersecting and hence, the resultant bracket sequence will still be balanced and $s_1$, $s_n$, as well as $s_i$ and $s_{i + 1}$ will be toggled for all the desired even indices $i$. We can use the same strategy with $A_1$, starting with the same special balanced bracket sequence and then swapping $b_i$ and $b_{i + 1}$ for all $i$ that is in set $A_1$. Hence, after using these two operations, all elements of $s$ will change to $\texttt{0}$.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
We will demonstrate a way to use $2$ bracket sequence solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s.↵
↵
Defined the balance of an (incomplete) bracket sequence as the number of open brakcets minus the number of closed brakcets. For example, `((()` has balance $2$, `(()()((` has balance $3$ and `()` has balance $0$.↵
↵
Using hint $1$ we can see that the resulting binary string will contain `0` at position $i$ iff the character at position $i$ in both bracket sequences is same. Suppose the balances of your current bracket sequences is $(a,b)$. You can change it $(a\pm 1, b\pm 1)$. If both $\pm$ have the same parity, then the resulting binary string will contain $\texttt{0}$ at that position.↵
↵
Now, we will demonstrate a greedy algorithm.↵
↵
$(0,0) \to (1,1) \to (0,2),(2,2) \to (1,3),(1,1) \to (0,2),(2,2) \to \ldots \to (1,1) \to (0,0)$↵
↵
One can show by a simple parity argument that the second last balance must necessarily be $(1,1)$ since the number of $\texttt{1}$s in the string is even.↵
</spoiler>↵
↵
<spoiler summary="Solution 3">↵
Similar to solution 2, we will demonstrate a way to use $2$ bracket sequence solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s.↵
↵
Using the same greedy argument in solution 2 (or by guessing), we know that we can always use two bracket sequences where the number of open brackets minus the number of close brackets is always between $0$ and $3$ for all prefixes of the bracket sequence. For convenience, we will define "balance" as the number of open brackets minus the number of close brackets. ↵
↵
Hence, we can do dynamic programming using the states $dp[i][balance1][balance2]$ which returns whether it is possible to create two bracket sequences $b1$ and $b2$ of length $i$ such that the balance of $b1$ and $b2$ are $balance1$ and $balance2$ respectively and $s[1, i]$ becomes all $\mathtt{0}$. The transition can be done by making sure that the balances stay between $0$ and $3$ and that $b1_i \neq b2_i$ if $s_i=\mathtt{1}$ and vice versa.↵
</spoiler>↵
↵
# [problem:1896G]↵
↵
<spoiler summary="Hint 1">↵
Find the fastest pepe in $n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call him the *head* of $G_i$. Finally, use $1$ query to find the fastest pepe of all the heads.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
After knowing the fastest pepe, find the second fastest pepe in $n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Just remove the fastest pepe and repeat the process from hint 1. One of the group will has size $n - 1$, but we can "steal" one non-head pepe from another already-queried group.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Note that the above process for Hint 2 use a lot of repeated queries. Can we optimize it to $2$ queries?↵
↵
<spoiler summary="Hint">↵
Assume that the fastest pepe is the head of $G_i$. After removing him, we can recalculate the head of $G_i$ using $1$ query similar to hint 2. Then, use the second query on all the heads, similar to the last query of hint 1.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Solve the problem using $2n^2 - n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Our algorithm has three phases:↵
↵
- Phase 1: Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call this guy the *head* of $G_i$.↵
- Phase 2: Until there are $2n - 1$ pepes, repeat these two steps:↵
- Use $1$ query to find the fastest pepe of the heads of all groups, then remove him. Assume that this pepe is the head of $G_i$.↵
- Steal non-head pepes from other groups so that $|G_i| = n$, then use $1$ query to recalculate its head.↵
- Phase 3: Until there are $n - 1$ pepes, repeatedly find the fastest pepe using $2$ queries (or $1$ if there are only $n$ pepes left), then remove him.↵
↵
Total number of queries is $n + 2(n^2 - 2n + 1) + 2(n - 1) + 1 = 2n^2 - n + 1$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
Call a pepe *slow* if it does not belong in the fastest $n^2 - n + 1$ pepes. Note that there are $n - 1$ slow pepes, and we do not care for their relative speed. After each query, we know that the fastest pepe cannot be slow.↵
↵
We use the algorithm in hint 4 until there are $2n - 1$ pepes left. Since the head of $n$ groups cannot be slow, we are left with exactly $(2n - 1) - n = n - 1$ candidates for slow pepes. Once we determine the $n - 1$ slow pepes, we only need to find the ranking of the other $n$ pepes, which can be done using $n - 1$ queries.↵
↵
Total number of queries is $n + 2(n^2 - 2n + 1) + (n - 1) = 2n^2 - 2n + 1$.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
We will try to decrease the amount of queries based on the fact that we can omit one query for recalculation when the size of a group decreases from $2$ to $1$.↵
↵
We modify the algorithm in hint 4 to maintain an invariant: $|G_i| - |G_j| \le 1$ $\forall \, 1 \le i < j \le n$. In other words, we want to make the sizes of these groups as balanced as possible.↵
↵
To maintain this, whenever we have $|G_j| - |G_i| = 2$ after removing some pepe, we can transfer any non-head pepe from $G_j$ to $G_i$ to balance these groups out. Next, to recalculate the head of $G_i$, we will "borrow" instead of "steal" from other groups. If the fastest pepe is borrowed from $G_j$, then we transfer a random non-head pepe in $G_i$ back to $G_j$. This works since the head of $G_j$ is faster than head of $G_i$, which in turns is faster than the random pepe.↵
↵
Finally, when there are $2n$ pepes left, all groups have the size of $2$, and we only need to use $1$ query for each pepe from later on.↵
↵
Total number of queries is $n + 2(n^2 - 2n) + (n + 1) = 2n^2 - 2n + 1$.↵
</spoiler>↵
↵
# [problem:1896H2]↵
*Coming soon*↵
↵
↵
<spoiler summary="Hint 1">↵
Look at the samples.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
## [problem:1896B]↵
↵
<spoiler summary="Hint 1">↵
What happens when $s$ starts with some $\texttt{B}$ and ends with some $\texttt{A}$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
## [problem:1896C]↵
↵
<spoiler summary="Hint 1">↵
Consider a greedy algorithm.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For simplicity, assume that both arrays $a$ and $b$ are sorted in increasing order. The final answer can be obtained by permuting the answer array using the same permutation to permute sorted array $a$ to the original array $a$.↵
↵
**Claim**:
↵
*Proof*: Suppose there exists an alternative rearrangement different from above represented by permutation $p$ where $b_{p_1}, b_{p_2}, \ldots, b_{p_n}$ results in a beauty of $x$. Let array $q$ represent the $x$ indices where $a_i > b_{p_i}$ in increasing order. In other words, $1 \le q_1 < q_2 < \ldots < q_x \le n$ and $a_{q_i} > b_{p_{q_i}}$. Let $i$ be the largest index where $q_i \neq n - i + 1$ ($q_i < n - i + 1$ also holds due to strict inequality above). We know that $a_{q_i} > b_{p_{q_i}}$ and $a_{n - i + 1} \le b_{p_{n - i + 1}}$. Since $a$ is sorted and $q_i < n - i + 1$, we have $a_{q_i} \le a_{n - i + 1}$, and hence, $a_{n - i + 1} > b_{p_{q_i}}$ and $a_{q_i} \le b_{p_{n - i + 1}}$. This means that we can swap $p_{q_i}$ with $p_{n - i + 1}$ without changing the beauty of the array, while allowing $q_i = n - i + 1$. Hence, by doing the swapping repeatedly, we will get $q_i = n - i + 1$ for all $i$ between 1 and $x$.↵
↵
An alternative interpretation to the result above is that we managed to obtain a solution where for all $i$ between $1$ and $n - x$, we have $a_i \le b_{p_i}$. On the other hand, for all $i$ between $n - x + 1$ and $n$, we have $a_i > b_{p_i}$. Let $i$ be the largest index between $1$ and $n - x$ where $p_i \neq i + x$ ($p_i < i + x$ due to maximality). Then, let $j$ be the index where $p_j = i + x$. Consider two cases:↵
↵
- $j \le n - x$. Since $i$ is the largest index where $p_i \neq i + x$, this means that $j < i$ and hence $a_j \le a_i$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j \le a_i \le b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$.↵
- $j > n - x$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j > b_{p_j} = b_{i + x} > b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$.↵
↵
By repeating the above repeatedly, we can obtain a solution where $p_i = i + x$ for all $i$ between $1$ and $n - x$. Let $i$ be the smallest index between $n - x + 1$ and $n$ where $p_i \neq i - n + x$ ($p_i > i - n + x$ by minimality). Then, let $j$ be the index where $p_j = i - n + x$. Note that $j > n - x$ as well since $p_i = i + x$ for all $i$ between $1$ and $n - x$. Since $i$ is the smallest index where $p_i \neq i - n + x$, this means that $i < j$ and hence $a_i \le a_j$. We have $a_i > b_{p_i} \ge b_{i - n + x} = b_{p_j}$ and $a_j \ge a_i > b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i - n + x$. By doing this repeatedly, we can obtain a solution where $p_i = i - n + x$ for all $i$ between $n - x + 1$ and $n$. Now, $p = [x + 1, x + 1, \ldots, n, 1, 2, \ldots, x]$, which matches the rearrangement in our claim.↵
</spoiler>↵
↵
# [problem:1896D]↵
↵
<spoiler summary="Hint 1">↵
Consider some small examples and write down every possible values of subarray sums. Can you see some patterns ?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Denote $s[l,r]$ as the sum of subarray from $l$ to $r$.↵
↵
↵
**Claim**: If there is any subarray with sum $v\ge 2$, we can find a subarray with sum $v-2$.↵
*Proof*: Suppose $s[l,r]=v$, consider 3 cases:↵
- $a[l]=2$, we have $s[l+1,r]=v-2$.↵
- $a[r]=2$, we have $s[l,r-1]=v-2$.↵
- $a[l]=a[r]=1$, we have $s[l+1,r-1]=v-2$.↵
↵
So in order to check if there exists a subarray whose sum equals to $v$, we can find maximum subarray sum having the same parity with $v$ and compare it with $v$.↵
↵
The case where $(s[1,n]-v)\%2=0$ is obvious, suppose the opposite happens. If array $a$ is full of $2$-s, the answer is $\texttt{NO}$. Otherwise, let $x$ and $y$ be the positions of the first $1$ and last $1$ in $a$. Any subarray with $l\le x\le y\le r$ will have different parity with $v$. So we will compare $\max(s[l+1, n],s[1,r-1])$ with $v$ to get the answer.↵
</spoiler>↵
↵
# [problem:1896E]↵
↵
<spoiler summary="Hint 1">↵
For each index $i$ from $1$ to $n$, let $h_i$ denote the number of cyclic shifts needed to move $a_i$ to its correct spot. In other words, $h_i$ is the minimum value such that $(i + h_i - 1)\ \%\ n + 1 = a_i$. How can we get the answer from $h_i$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
For convenience, we will assume that the array is cyclic, so $a_j = a_{(j - 1)\ \%\ n + 1}$. The answer for each index $i$ from $1$ to $n$ is $h_i$ (defined in hint 1) minus the number of indices $j$ where $i < j < i + h_i$ and $i < a_j < i + h_i$ (or $i < a_j + n < i + h_i$ to handle cyclic case when $i + h_i > n$). This is because the value that we are calculating is equal to the number of positions that $a_i$ will skip during the rotation as the index is already good.↵
↵
To calculate the above value, it is convenient to define an array $b$ of size $2n$ where $b_i = a_i$ for all $i$ between $1$ to $n$, and $b_i = a_{i - n} + n$ for all $i$ between $n + 1$ to $2n$ to handle cyclicity. We will loop from $i = 2n$ to $i = 1$, and do a point increment to position $a_i$ if $a_i \ge i$, otherwise, do a point increment to position $a_i + n$. Then, to get the answer for index $i$, we do a range sum query from $i + 1$ to $i + h_i - 1$. Point increment and range sum query can be done using binary indexed tree in $O(\log n)$ time per query/update. Hence, the problem can be solved in $O(n\log n)$ time.↵
</spoiler>↵
↵
# [problem:1896F]↵
↵
<spoiler summary="Hint 1">↵
The operation is equivalent to toggling $s$ at every odd $i$ where $b_i$ is an open bracket and every even $i$ where $b_i$ is a closed bracket.↵
*Proof*: Suppose there are $x$ open brackets and $y$ close brackets between positions $1$ and $i$. Note that $x \ge y$ by definition of balanced bracket sequences.↵
- Case 1: $b_i$ is an open bracket. Position $i$ will be toggled exactly $x - y$ times as $y$ of the open brackets will be matched before position $i$, and the remaining $x - y$ open brackets will only be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is odd, and hence, $x - y + 2y = x + y = i$ must be odd as well.↵
- Case 2: $b_i$ is a close bracket. Position $i$ will be toggled exactly $x - y + 1$ times as $y - 1$ of the open brackets will be matched before $i$, $1$ of the open bracket will be matched with position $i$, and the remaining $x - y$ open brackets will be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is even, and hence, $x - y + 2y = x + y = i$ must be even as well.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Every operation will always toggle $s_1$ and $s_n$. Furthermore, every operation will always toggle an even number of positions.↵
*Proof*: If $s$ is toggled at an open bracket, $s$ will be toggled at its matching close bracket as well.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $s_1 \neq s_n$ or there is an odd number of $\texttt{1}$s in $s$, it is not possible to change all elements of $s$ to $\texttt{0}$. Otherwise, it is always possible.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If it is possible to change all elements of $s$ to $\texttt{0}$, at most $3$ operations are needed.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
From hint 3, we know the cases where it is impossible to change all elements of $s$ to $\texttt{0}$. We will now only consider the case where it is possible to change all elements of $s$ to $\texttt{0}$.↵
↵
Using hint 1, we can easily check whether it is possible to change all elements of $s$ to $\texttt{0}$ using only one operation by first constructing the bracket sequence then checking whether the resultant bracket sequence is balanced. From now on, we will assume that it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation.↵
↵
Suppose $s_1 = s_n = \texttt{1}$. We know from hint 2 that each operation will always toggle $s_1$ and $s_n$, so since it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation, we will need three operations. If we let the first operation be $b=\texttt{(()()}\ldots\texttt{()())}$, $s_1$ and $s_n$ will be toggled while the remaining elements stays the same. Now, $s_1 = s_n = \texttt{0}$, so if we are able to solve this case using only two operations, it means that we can solve the $s_1 = s_n = \texttt{1}$ case using only three operations.↵
↵
To solve the final case where $s_1 = s_n = \texttt{0}$, we will look at a special balanced bracket sequences $b = \texttt{(()()}\ldots\texttt{()())}$. Notice that if we do an operation using this bracket sequence, only $s_1$ and $s_n$ will be toggled. Suppose there exist an index $i$ between $2$ and $2n - 2$ where we want to toggle both $s_i$ and $s_{i + 1}$. We can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, then swap $b_i$ and $b_{i + 1}$. This will always result in a balanced bracket sequence that will toggle $s_1$, $s_n$, as well as the desired $s_i$ and $s_{i + 1}$. This will allow us to change all elements of $s$ to $\texttt{0}$ in $2n$ moves as we can scan from $i = 2$ to $i = 2n - 2$ and do an operation toggling $s_i$ and $s_{i+1}$ if $s_i = \texttt{1}$. Since there is an even number of $\texttt{1}$s in $s$ from hint 3, toggling adjacent positions will always change all elements of $s$ to $\texttt{0}$.↵
↵
In order to reduce the number of operations from $2n$ to $2$, notice that a lot of the operations can be parallelised into a single operation. Let $A_0$ represent the set of even indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. Similarly, let $A_1$ represent the set of odd indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. In a single operation, we can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, and swap $b_i$ and $b_{i + 1}$ for all $i$ that is in the set $A_0$. Since $A_0$ only contains even indices, the swaps are non-intersecting and hence, the resultant bracket sequence will still be balanced and $s_1$, $s_n$, as well as $s_i$ and $s_{i + 1}$ will be toggled for all the desired even indices $i$. We can use the same strategy with $A_1$, starting with the same special balanced bracket sequence and then swapping $b_i$ and $b_{i + 1}$ for all $i$ that is in set $A_1$. Hence, after using these two operations, all elements of $s$ will change to $\texttt{0}$.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
We will demonstrate a way to use $2$ bracket sequence solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s.↵
↵
Defined the balance of an (incomplete) bracket sequence as the number of open brakcets minus the number of closed brakcets. For example, `((()` has balance $2$, `(()()((` has balance $3$ and `()` has balance $0$.↵
↵
Using hint $1$ we can see that the resulting binary string will contain `0` at position $i$ iff the character at position $i$ in both bracket sequences is same. Suppose the balances of your current bracket sequences is $(a,b)$. You can change it $(a\pm 1, b\pm 1)$. If both $\pm$ have the same parity, then the resulting binary string will contain $\texttt{0}$ at that position.↵
↵
Now, we will demonstrate a greedy algorithm.↵
↵
$(0,0) \to (1,1) \to (0,2),(2,2) \to (1,3),(1,1) \to (0,2),(2,2) \to \ldots \to (1,1) \to (0,0)$↵
↵
One can show by a simple parity argument that the second last balance must necessarily be $(1,1)$ since the number of $\texttt{1}$s in the string is even.↵
</spoiler>↵
↵
<spoiler summary="Solution 3">↵
Similar to solution 2, we will demonstrate a way to use $2$ bracket sequence solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s.↵
↵
Using the same greedy argument in solution 2 (or by guessing), we know that we can always use two bracket sequences where the number of open brackets minus the number of close brackets is always between $0$ and $3$ for all prefixes of the bracket sequence. For convenience, we will define "balance" as the number of open brackets minus the number of close brackets. ↵
↵
Hence, we can do dynamic programming using the states $dp[i][balance1][balance2]$ which returns whether it is possible to create two bracket sequences $b1$ and $b2$ of length $i$ such that the balance of $b1$ and $b2$ are $balance1$ and $balance2$ respectively and $s[1, i]$ becomes all $\mathtt{0}$. The transition can be done by making sure that the balances stay between $0$ and $3$ and that $b1_i \neq b2_i$ if $s_i=\mathtt{1}$ and vice versa.↵
</spoiler>↵
↵
# [problem:1896G]↵
↵
<spoiler summary="Hint 1">↵
Find the fastest pepe in $n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call him the *head* of $G_i$. Finally, use $1$ query to find the fastest pepe of all the heads.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
After knowing the fastest pepe, find the second fastest pepe in $n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Just remove the fastest pepe and repeat the process from hint 1. One of the group will has size $n - 1$, but we can "steal" one non-head pepe from another already-queried group.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Note that the above process for Hint 2 use a lot of repeated queries. Can we optimize it to $2$ queries?↵
↵
<spoiler summary="Hint">↵
Assume that the fastest pepe is the head of $G_i$. After removing him, we can recalculate the head of $G_i$ using $1$ query similar to hint 2. Then, use the second query on all the heads, similar to the last query of hint 1.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Solve the problem using $2n^2 - n + 1$ queries.↵
↵
<spoiler summary="Hint">↵
Our algorithm has three phases:↵
↵
- Phase 1: Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call this guy the *head* of $G_i$.↵
- Phase 2: Until there are $2n - 1$ pepes, repeat these two steps:↵
- Use $1$ query to find the fastest pepe of the heads of all groups, then remove him. Assume that this pepe is the head of $G_i$.↵
- Steal non-head pepes from other groups so that $|G_i| = n$, then use $1$ query to recalculate its head.↵
- Phase 3: Until there are $n - 1$ pepes, repeatedly find the fastest pepe using $2$ queries (or $1$ if there are only $n$ pepes left), then remove him.↵
↵
Total number of queries is $n + 2(n^2 - 2n + 1) + 2(n - 1) + 1 = 2n^2 - n + 1$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
Call a pepe *slow* if it does not belong in the fastest $n^2 - n + 1$ pepes. Note that there are $n - 1$ slow pepes, and we do not care for their relative speed. After each query, we know that the fastest pepe cannot be slow.↵
↵
We use the algorithm in hint 4 until there are $2n - 1$ pepes left. Since the head of $n$ groups cannot be slow, we are left with exactly $(2n - 1) - n = n - 1$ candidates for slow pepes. Once we determine the $n - 1$ slow pepes, we only need to find the ranking of the other $n$ pepes, which can be done using $n - 1$ queries.↵
↵
Total number of queries is $n + 2(n^2 - 2n + 1) + (n - 1) = 2n^2 - 2n + 1$.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
We will try to decrease the amount of queries based on the fact that we can omit one query for recalculation when the size of a group decreases from $2$ to $1$.↵
↵
We modify the algorithm in hint 4 to maintain an invariant: $|G_i| - |G_j| \le 1$ $\forall \, 1 \le i < j \le n$. In other words, we want to make the sizes of these groups as balanced as possible.↵
↵
To maintain this, whenever we have $|G_j| - |G_i| = 2$ after removing some pepe, we can transfer any non-head pepe from $G_j$ to $G_i$ to balance these groups out. Next, to recalculate the head of $G_i$, we will "borrow" instead of "steal" from other groups. If the fastest pepe is borrowed from $G_j$, then we transfer a random non-head pepe in $G_i$ back to $G_j$. This works since the head of $G_j$ is faster than head of $G_i$, which in turns is faster than the random pepe.↵
↵
Finally, when there are $2n$ pepes left, all groups have the size of $2$, and we only need to use $1$ query for each pepe from later on.↵
↵
Total number of queries is $n + 2(n^2 - 2n) + (n + 1) = 2n^2 - 2n + 1$.↵
</spoiler>↵
↵
# [problem:1896H2]↵
*Coming soon*↵
↵
