## 1896A - Jagged Swaps

Writer: maomao90

**Hint 1**

Look at the samples.

**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. 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.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <ll> vi;
int main() {
int t;
cin >> t;
while (t --> 0) {
int n;
cin >> n;
vi arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (arr[0] == 1) {
cout << "YES";
} else {
cout << "NO";
}
cout << '\n';
}
}
```

## 1896B - AB Flipping

Writer: maomao90

**Hint 1**

What happens when $$$s$$$ starts with some $$$\texttt{B}$$$ and ends with some $$$\texttt{A}$$$?

**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 be done are from $$$x$$$ to $$$y - 1$$$. 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.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
char s[200005];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc, n; cin >> tc;
while (tc--) {
cin >> n; s[n + 1] = 'C';
for (int i = 1; i <= n; ++i) cin >> s[i];
int pt1 = 1, pt2 = 1, ans = 0;
while (s[pt1] == 'B') ++pt1, ++pt2;
while (pt1 <= n) {
int cntA = 0, cntB = 0;
while (s[pt2] == 'A') ++pt2, ++cntA;
while (s[pt2] == 'B') ++pt2, ++cntB;
if (s[pt2 - 1] == 'B') ans += pt2 - pt1 - 1;
if (cntB) pt1 = pt2 - 1;
else break;
}
cout << ans << '\n';
}
}
```

## 1896C - Matching Arrays

Writer: maomao90

**Hint 1**

Consider a greedy algorithm.

**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.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
const int INF = 1000000005;
const int MAXN = 200005;
int t;
int n, x;
int a[MAXN], b[MAXN], aid[MAXN];
int ans[MAXN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> t;
while (t--) {
cin >> n >> x;
REP (i, 0, n) {
cin >> a[i];
}
REP (i, 0, n) {
cin >> b[i];
}
iota(aid, aid + n, 0);
sort(aid, aid + n, [&] (int l, int r) {
return a[l] < a[r];
});
sort(b, b + n);
REP (i, 0, x) {
ans[aid[n - x + i]] = b[i];
}
REP (i, x, n) {
ans[aid[i - x]] = b[i];
}
REP (i, 0, n) {
x -= a[i] > ans[i];
}
if (x == 0) {
cout << "YES\n";
REP (i, 0, n) {
cout << ans[i] << ' ';
}
cout << '\n';
} else {
cout << "NO\n";
}
}
return 0;
}
```

## 1896D - Ones and Twos

Writer: lanhf

**Hint 1**

Consider some small examples and write down every possible value of subarray sums. Can you see some patterns?

**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 to check if there exists a subarray whose sum equals $$$v$$$, we can find the 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 a different parity with $$$v$$$. So we will compare $$$\max(s[x+1, n],s[1,y-1])$$$ with $$$v$$$ to get the answer.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector<int> a(n);
set<int> pos;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] == 1) pos.insert(i);
}
while (q--) {
int cmd; cin >> cmd;
if (cmd == 1) {
int v; cin >> v;
int num = pos.size();
if ((v - num) & 1) {
if (num == 0) cout << "NO";
else {
int s1 = 2 * *pos.rbegin() - (num - 1);
int s2 = 2 * (n - *pos.begin() - 1) - (num - 1);
if (v <= max(s1, s2)) cout << "YES";
else cout << "NO";
}
} else {
if (v <= 2 * n - num) cout << "YES";
else cout << "NO";
}
cout << '\n';
} else {
int i; cin >> i; i--;
pos.erase(i);
cin >> a[i];
if (a[i] == 1) pos.insert(i);
}
}
}
}
```

## 1896E - Permutation Sorting

Writer: maomao90

**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$$$?

**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 a binary indexed tree in $$$O(\log n)$$$ time per query/update. Hence, the problem can be solved in $$$O(n\log n)$$$ time.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
const int INF = 1000000005;
const int MAXN = 1000005;
int t;
int n;
int p[MAXN];
int ans[MAXN];
int fw[MAXN * 2];
void incre(int i, int x) {
for (; i <= 2 * n; i += i & -i) {
fw[i] += x;
}
}
int qsm(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
res += fw[i];
}
return res;
}
inline int qsm(int s, int e) {
return qsm(e) - qsm(s - 1);
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> t;
while (t--) {
cin >> n;
REP (i, 1, n + 1) {
cin >> p[i];
}
REP (i, 0, 2 * n + 5) {
fw[i] = 0;
}
vector<pair<int, int>> rgs;
REP (i, 1, n + 1) {
if (i <= p[i]) {
rgs.push_back({i, p[i]});
rgs.push_back({i + n, p[i] + n});
} else {
rgs.push_back({i, p[i] + n});
}
}
sort(ALL(rgs), greater<pair<int, int>>());
for (auto [l, r] : rgs) {
if (l <= n) {
ans[p[l]] = r - l - qsm(l, r);
}
incre(r, 1);
}
REP (i, 1, n + 1) {
cout << ans[i] << ' ';
}
cout << '\n';
}
return 0;
}
```

## 1896F - Bracket Xoring

Writer: maomao90

**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.

**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.

**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.

**Hint 4**

If it is possible to change all elements of $$$s$$$ to $$$\texttt{0}$$$, at most $$$3$$$ operations are needed.

**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 and 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 stay the same. Now, $$$s_1 = s_n = \texttt{0}$$$, so if we can 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}$$$.

To reduce the number of operations from $$$2n$$$ to $$$2$$$, notice that a lot of the operations can be parallelized 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}$$$.

**Solution 2**

We will demonstrate a way to use $$$2$$$ bracket sequence to 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 brackets 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 the same. Suppose the balance 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.

**Solution 3**

Similar to solution 2, we will demonstrate a way to use $$$2$$$ bracket sequence to 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.

**Implementation**

```
#include <bits/stdc++.h>
using namespace std;
void solve(int n, string s) {
vector<int> a;
for (char &i : s) {
a.push_back(i & 1);
}
if (a.front() != a.back()) {
cout << -1 << endl;
return ;
}
if (count(a.begin(), a.end(), 1) % 2) {
cout << -1 << endl;
return ;
}
bool flipped = false;
if (a.front() == 1 && a.back() == 1) {
for (int &i : a) i ^= 1;
flipped = true;
}
string l(2 * n, '-'), r(2 * n, '-');
int cnt = 0;
for (int i = 0; i < 2 * n; i++) {
if (a[i]) {
l[i] = (cnt) ? '(' : ')';
r[i] = (cnt ^ 1) ? '(' : ')';
cnt ^= 1;
}
}
int tot = count(a.begin(), a.end(), 0) / 2;
cnt = 0;
for (int i = 0; i < 2 * n; i++) {
if (!a[i]) {
if (cnt < tot) l[i] = '(', r[i] = '(';
else l[i] = ')', r[i] = ')';
cnt++;
}
}
if (flipped) {
cout << 3 << endl;
cout << l << endl;
cout << r << endl;
for (int i = 0; i < n; i++) cout << "()";
cout << endl;
} else {
cout << 2 << endl;
cout << l << endl;
cout << r << endl;
}
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
solve(n, s);
}
return 0;
}
```

## 1896G - Pepe Racing

Writer: thenymphsofdelphi

**Hint 1**

Find the fastest pepe in $$$n + 1$$$ queries.

**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.

**Hint 2**

After knowing the fastest pepe, find the second fastest pepe in $$$n + 1$$$ queries.

**Hint**

Just remove the fastest pepe and repeat the process from hint 1. One of the groups will have size $$$n - 1$$$, but we can "steal" one non-head pepe from another already-queried group.

**Hint 3**

Note that the above process for Hint 2 uses a lot of repeated queries. Can we optimize it to $$$2$$$ queries?

**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.

**Hint 4**

Solve the problem using $$$2n^2 - n + 1$$$ queries.

**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$$$.

**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$$$.

**Solution 2**

We will try to decrease the number 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 the head of $$$G_i$$$, which in turn 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$$$.

**Implementation (Solution 1)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
vector<int> buc[N];
int buc_id[N * N], buc_max[N];
int n;
int ask(vector<int> que) {
cout << "?";
for (int i : que) cout << ' ' << i + 1;
cout << endl;
int res; cin >> res;
return res - 1;
}
int ask_all() {
vector<int> que;
for (int i = 0; i < n; i++)
if (buc[i].size())
que.push_back(buc_max[i]);
for (int i = 0; i < n; i++)
for (int j : buc[i])
if (int(que.size()) < n && j != buc_max[i])
que.push_back(j);
return ask(que);
}
void answer(vector<int> ans) {
cout << "!";
for (int i : ans) cout << ' ' << i + 1;
cout << endl;
}
void add(int id, int pepe) {
buc[id].push_back(pepe);
buc_id[pepe] = id;
}
void remove(int id, int pepe) {
buc[id].erase(find(buc[id].begin(), buc[id].end(), pepe));
}
void send(int id, vector<int> &que) {
for (int pepe : buc[id])
if (int(que.size()) < n && pepe != buc_max[id])
que.push_back(pepe);
}
void check_balance() {
size_t min_size = n, max_size = 0;
for (int id = 0; id < n; id++) {
min_size = min(min_size, buc[id].size());
max_size = max(max_size, buc[id].size());
}
assert(max_size - min_size <= 1);
}
int main() {
cout << endl;
int t; cin >> t;
while (t--) {
cin >> n;
for (int id = 0; id < n; id++)
buc[id].clear();
for (int pepe = 0; pepe < n * n; pepe++) {
buc_id[pepe] = pepe / n;
buc[pepe / n].push_back(pepe);
}
for (int id = 0; id < n; id++)
buc_max[id] = ask(buc[id]);
vector<int> ans;
/// balancing phase
for (int step = 0; step < n * n - 2 * n; step++) {
ans.push_back(ask_all());
int last_id = buc_id[ans.back()];
remove(last_id, ans.back());
vector<int> que;
for (int pepe : buc[last_id])
que.push_back(pepe);
/// find bucket with largest size != last_id
int max_id = (last_id == 0);
for (int id = 0; id < n; id++)
if (id != last_id && buc[id].size() > buc[max_id].size())
max_id = id;
send(max_id, que);
for (int id = 0; id < n; id++)
if (id != max_id && id != last_id)
send(id, que);
buc_max[last_id] = ask(que);
int move_id = buc_id[buc_max[last_id]];
if (move_id != last_id) {
remove(move_id, buc_max[last_id]);
add(move_id, buc[last_id].back());
remove(last_id, buc[last_id].back());
add(last_id, buc_max[last_id]);
}
if (buc[last_id].size() == buc[max_id].size() - 2) {
if (move_id == max_id) {
add(last_id, buc[move_id].back());
remove(move_id, buc[move_id].back());
} else {
for (int pepe : buc[max_id])
if (pepe != buc_max[max_id]) {
add(last_id, pepe);
remove(max_id, pepe);
break;
}
}
}
check_balance();
}
for (int step = 0; step < n + 1; step++) {
ans.push_back(ask_all());
int last_id = buc_id[ans.back()];
remove(last_id, ans.back());
if (buc[last_id].size())
buc_max[last_id] = buc[last_id][0];
}
answer(ans);
}
}
```

**Implementation (Solution 2)**

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
vector<int> v[25];
int ask(vector<int> v){
cout<<"? "; for (auto it:v) cout<<it<<" "; cout<<endl;
int res; cin>>res;
return res;
}
vector<int> fix(vector<int> v){
int t=ask(v);
rep(x,0,n) if (v[x]==t) swap(v[0],v[x]);
return v;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n;
rep(x,0,n){
v[x].clear();
rep(y,1,n+1) v[x].pub(x*n+y);
}
rep(x,0,n) v[x]=fix(v[x]);
vector<int> ans;
rep(x,0,n*n-2*n+1){
vector<int> t;
rep(x,0,n) t.pub(v[x][0]);
int best=ask(t);
int idx=-1;
rep(x,0,n) if (t[x]==best) idx=x;
ans.pub(best);
v[idx].erase(v[idx].begin());
rep(x,0,n) if (x!=idx){
while (sz(v[x])>1 && sz(v[idx])<n){
v[idx].pub(v[x].back());
v[x].pob();
}
}
v[idx]=fix(v[idx]);
}
vector<int> a,b;
rep(x,0,n){
rep(y,0,sz(v[x])){
if (y==0) a.pub(v[x][y]);
else b.pub(v[x][y]);
}
}
set<int> bad=set<int>(all(b));
rep(x,0,n-1){
a=fix(a);
ans.pub(a[0]);
a.erase(a.begin());
a.pub(b.back()); b.pob();
}
for (auto it:a) if (!bad.count(it)) ans.pub(it);
cout<<"! "; for (auto it:ans) cout<<it<<" "; cout<<endl;
}
}
```

## 1896H2 - Cyclic Hamming (Hard Version)

Writer: xuanquang1999

**Hint 1**

For any $$$c$$$ which is a cyclic shift of $$$t$$$, what will happen if $$$h(s,c)>2^k$$$?

**Hint 2**

Try finding some useful relationship between $$$1$$$-s of $$$s$$$ and $$$1$$$-s of $$$c$$$.

**Hint**

There are exactly $$$n/2$$$ positions $$$i$$$ such that $$$s[i]=c[i]=1$$$.

**Hint 3**

Think about polynomial multiplication.

**Hint 1**

Consider $$$S\cdot T$$$, where $$$S=\sum s[i]x^i$$$ and $$$T=\sum t[2n-i-1]x^i$$$ (reversed coefficients).

**Hint 2**

What are some properties that the coefficients of $$$S\cdot T$$$ tell us?

**Hint**

Denote $$$A=S\cdot T$$$, we have $$$A[x^i]+A[x^{i+2n}]=n/2$$$.

**Hint 3**

Try factoring $$$S\cdot T$$$ into some irreducible polynomials.

**Hint 4**

Sort $$$0,1,\ldots,2n-1$$$ based on their bit-reversal values and build a binary tree on top of it. What condition should be satisfied on each level of the tree?

**Solution**

Consider the polynomial product $$$A=S\cdot T$$$, where $$$S=\sum s[i]x^i$$$ and $$$T=\sum t[2n-i-1]x^i$$$ (reversed coefficients).

**Claim 1.** For all $$$0\le i<2n$$$, we have $$$A[x^i]+A[x^{i+2n}]=n/2$$$, where $$$A[x^k]$$$ denote the coefficient of $$$x^k$$$ in $$$A$$$.

**Claim 2.** We can express $$$A=(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)(n/2+C(x-1))$$$ where $$$C$$$ is some polynomial with degree not greater than $$$2n-2$$$.

**Proof**

It is easy to see that this satisfies claim 1.

**Claim 3.** Since $$$x^{2^p}+1$$$ is cyclotomic polynomial and hence irreducible for all $$$p$$$, each factor in $$$x+1,x^2+1,\ldots,x^n+1$$$ must divide at least one of $$$S$$$ and $$$T$$$. And under the constraints that each of $$$s$$$ and $$$t$$$ must have exactly $$$n$$$ $$$1$$$-s, this condition is also sufficient.

**Proof**

Let $$$A=(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)\cdot D$$$. We have $$$A(1)=n^2$$$, hence $$$D(1)=n/2$$$, which means that $$$D$$$ has the form of $$$n/2+C(x-1)$$$. Therefore $$$A$$$ satisfies claim 2.

Recall $$$n=2^k$$$, define $$$f_s(mask)$$$ ($$$0\le mask<2n$$$) as the number of string $$$s$$$ such that for each $$$p$$$ where $$$p$$$-th bit of $$$mask$$$ is on, $$$S$$$ is divisible by $$$x^{p}+1$$$. Define $$$f_t$$$ similarly for $$$T$$$. Define $$$f^{\prime}_t$$$ such that $$$f^{\prime}_t(mask)=f_t(mask\oplus (2n-1))$$$ where $$$\oplus$$$ denotes bitwise XOR.

The answer to the problem is $$$\displaystyle\sum_{mask} f_s(mask)\cdot \mu(f^{\prime}_t(mask))$$$ where $$$\mu$$$ denote Mobius transform. The reason we need Mobius transform is that $$$mask_s$$$ does not represent all divisors, just a subset of it.

Let rearrange elements of $$$s$$$ into a new array $$$s^{\prime}$$$ so that $$$s^{\prime}[\text{reverse_bit}(i)]=s[i]$$$ (for example, with $$$n=8$$$, the new order will be $$$[0,8,4,12,2,6,10,14,1,9,5,13,3,11,7,15]$$$). Construct a perfect binary tree based on the array $$$s^{\prime}$$$. This binary will have $$$k+2$$$ levels from $$$0$$$ to $$$k+1$$$, starting at the root.

**Claim 4.** $$$S$$$ is divisible by $$$x^{2^p}+1$$$ if only if for every tree node at $$$p$$$-th level, the number of $$$1$$$-s of $$$s^{\prime}$$$ under both children are equal (the proof is left as an exercise for readers).

**Hint**

Group the positions by the remainder when divided by $$$2^p$$$, find the necessary condition for each group, and consider its position on the tree.

Consider the following dynamic programming: $$$dp_s[i][mask][num]$$$, where the levels in $$$mask$$$ satisfy claim 4 and $$$num$$$ is the number of $$$1$$$-s under $$$i$$$-th node on the tree. Denote $$$l$$$ as level of $$$i$$$-th node, transitions are:

- $$$dp_s[i][mask][num_1+num_2]\text{ += }dp_s[2i][mask][num_1]\cdot dp_s[2i+1][mask][num_2]$$$
- $$$dp_s[i][mask+2^l][2\cdot num]\text{ += }dp_s[2i][mask][num]\cdot dp_s[2i+1][mask][num]$$$

The above dp took $$$\mathcal{O}(n^3)$$$, which is sufficient to solve the easy version.

To solve the hard version, we will optimize the above transitions:

- The first transition is actually the convolution of $$$dp_s[2i][mask]$$$ and $$$dp_s[2i+1][mask]$$$, we can use FFT to optimize it.
- In the second transition, because $$$num$$$ is multiplied by $$$2$$$ every time, we can omit it and just make the transition to $$$dp_s[i][mask+2^l][num]$$$, reduce the length of $$$dp_s[i][mask+2^l]$$$ by two.

By careful analysis, we can show that the time complexity is now $$$\mathcal{O}(3^k\cdot k)$$$ (recall $$$n=2^k$$$) with a fair constant factor, which solved the hard version.

Auto comment: topic has been updated by lanhf (previous revision, new revision, compare).Thanks everyone for participating in our round! Do you have any suggestions for us?

I loved today's contest! Good job guys!

Maybe code examples for solutions?

We will update soon.

Pay the promised prize from previous round :) pretty please!

But that's not the problemsetters' job, is it? And even if it was, the previous CodeTON round was set by different people...

Hmm maybe you are right. But the problemsetters (maomao90) posted on the announcement that there would be prizes, so hopefully they can pass the message along.

sample of problem B is too weak

Thank you for your effort. It's been a great contest, and I liked the problems.

The hints are good, but I think some of them can be improved to give a real insight on how one could solve the problem:

1896A:

Hint 1Look at the first element.

1896C:

Hint 1Try to sort the arrays.

Hint 2When the answer is "YES", how to rearrange the array b greedily? let's call this array c.

Hint 3Can you use the array c to check if the answer is "YES" or "NO" in the first place?

Fast tutorial!

random greedy on F (make element i 0 if you can make it 0 without violating balanced string condition)

This takes k = 10 even on random tests of n = 2e5

You are welcome to hack :)

https://mirror.codeforces.com/contest/1896/submission/234298869

thanks, there we go :)

Nice problems. Thanks for the round.

D can also be done using bitsets by storing prefix sums

Yes, it can. I solved with

`bitset`

during the contest. Here is my explanation of details and link to submission.Oh! why does it works? I have thought about this...but is this algorithm's time complexity right? I thought it would goes to O(N*N/w) if the query's s was close to the pref[n].. //Oh my god! I have try your solution.. Incredible improvement "#pragma GCC optimize("Ofast")

## pragma GCC target("avx2")"

Will the implementations be append?

Good contest, Fast editorial, generous prizes!

Hello! I have a question at problem E: For the example: 6 3 2 7 4 1 5 for number 6 h[i] = 5 and the number of positions j where 1 < j < 6 and 1 < a[j] < 6 is 3 (for a[j] = 3, 2 and 4), so the answer for 6 will be 5 — 3 = 2. However, the correct answer for 6 is equal to 4, because it only jumps over number 3..Can you tell me where I'm wrong, please?

Actually, you have to subtract the number of skipped indexes not the total elements < 6 and its position > 6's position

OR you can make like that , let OP( x ) is number of operations needed to make x at i = x

OP( 6 ) = 6-1 = 5

OP( 3 ) = 3-2 = 1 , OP( 2 ) = 2+7-3 = 6 , OP( 4 ) = 4+7-5=6

for all j : where 1 < j < 6 and 1 < a[j] < 6

---[ Detailed Steps ]----

0 | 6 3 2 7 4 1 5 [ 6 need 5 op ]

1 | 5 6 3 2 7 4 1 [ 6 need 4 op ]

2 | 1 5 3 6 2 7 4 [ 6 need 3 — 1 op ] [ 6 skipped 3 position ]

3 | 1 4 3 5 6 2 7 [ 6 need 1 op ]

4 | 1 2 3 4 5 6 7 [ 6 is Good ]

I tried to do D with another approach but getting a wrong answer.

Approach->

Lets reconstruct the array by merging same consecutive elements to a single element. like for array 1,1,2,2,1,1,2 modified new array will be 1,2,1,2.

Let m be the size of the modified array

3.Now if m is even you can form every sum ranging from 1 to total_sum of array(proof is simple)

4.but in case m is odd we can separately check for for the first m-1 groups or last m-1 groups

5.how i checked for the last m-1 groups is if sum of last m-1 groups is >=s then ans is yes otherwise check parity of element in first group and the diff between s and sum of last m-1 groups should be same for yes(coz then you can add elements from 1st group..basically extend your subarray).

6.same goes for checking of first m-1 groups

7.also we have to maintain length of prefix starting with 1,2 and length of suffix starting with 1,2 (can be done either by segment tree or simple multiset which have index of 1 and 2 in the array)

I am getting wrong answer for this approach can anyone explain why??

234328583

Take a look at Ticket 17159 from

CF Stressfor a counter example.thanks and now going to die after this silly mistake...

234400632

very nice problems and clear editorial,the best round.

CodeTON Round 7 A is the same as CodeTON Round 3 A from a year ago, just worded in a different way

Here is a solution for E using persistent segment tree..Stuck in memory for a hole day..234365527

Can someone explain why we are taking max here in the editorial of problem D ** So we will compare max(s[l+1,n],s[1,r−1]) with v to get the answer.**

It is actuallly max(s[x+1,n],s[1,y−1]). We check this when parity of sum of entire array and v is different. Lets say sum of all elements is even and v is odd. In this case we need to find a subarray with maximum odd sum. To change the parity of subarray sum , we need to remove a '1' from the subarray. Removing 2 wont change the parity. So either we take a subarray after the first occurence of 1 in the array, or before the last occurence of 1 in the array. We actually take the maximum of both cases. This is what max(s[x+1,n],s[1,y−1]) means.

What is difficulty rating for E

I solved A with hardcore brute force. I submitted again in the contest but my first solution would have passed. 234320361

I wrote this code using wavelet tree for the problem E which gave MLE. Shouldn't the memory complexity of this program be O(N log MAXV) where N = 1e6 and MAXV = 1e6.

I used a similar code with merge sort tree which got accepted while the memory complexity of merge sort tree is similar to wavelet tree for this problem.

Was it due to the fact that wavelet tree has a bit higher constant factor. However even when I reduced the MAXV and N to 1e4 it still gave MLE which it shouldn't even with higher constant factor.

Can someone explain the case with wavelet tree.

G is really fun but only for the thought process not implementation ToT

In Problem D solution,

`max(s[l+1,n], s[1,r-1])`

should be`max(s[x+1,n], s[1, y-1])`

?Thanks, fixed.

I was able to pass Merge Sort Tree on problem E only after rewriting all vectors to arrays, in order to optimize memory usage. But even then, my solution consumed 245 MB out of 256 MB. During the contest, figuring out this trickery took me half an hour. Is there any reason to make such memory constraints that solution which requires $$$O(n\log n)$$$ memory barely passes?

Sorry for necroposting, I was going to post it before, but I forgor

I am surprised that the authors didn't mention (or did I miss it?) the following trick in F (which probably doesn't simplify the solution, but maybe makes the thought process easier). After each operation, let's also flip every second bit: that is, 2-nd, 4-th, 6-th, and so on. Now every operation flips the bits that correspond to

`(`

instead of that obscure statement.Looking at the first (or last) bit of the input, we know the parity of the total number of operations, and if it is odd, then we can say that this transformation should be applied to the input string once, and then we can think in terms of flipping open parentheses.

C's editorial is too tough to understand

Edit

Can someone explain this (C) : Let $$$i$$$ be the largest index between $$$1$$$ and $$$n-x$$$ where $$$p_i\neq i+x$$$ ($$$p_i<i+x$$$ due to maximality). Why does $$$p_i$$$ has to be less than $$$i+x$$$ ??

I dont know about editorial but heres how i solved

first I sort the array , how suppose that rearrangement is possible . so to get x beauty our best chance to bet on last x element (coz they are max in a) and smallest x element from b. after that we want that for n-x element we dont get any beauty . so for max of first n-x elemet we our best chance is max of n-xth element of b .(if(a>b) cout<<no<< else we make pair of these two .) similar for n-x-1 indice and so on. heres link of my solution

problem c

B could be done using DP.

in B

my approach was

1 find first A from start, first B from end

2 count the number of A's till B encountered. add no of A's -1 to totalA count restart count of A count total no od B's that is cntB

3 print totalA + cntB

can anyobody find the flaws in my logic

I created a small webpage to help visualize Problem B: https://swseverance.github.io/cp-visualization/1896B