codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1896.md (36509B)


      1 Source: https://codeforces.com/blog/entry/122172
      2 
      3 ## [1896A - Пиковые обмены](/contest/1896/problem/A)
      4 
      5 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90")
      6 
      7 **Hint 1**
      8 
      9 Look at the samples.
     10 
     11 **Solution**
     12 
     13 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.
     14 
     15 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} \lt a_i$ and $a_i \gt 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.
     16 
     17 **Implementation**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 using namespace std;
     22 typedef long long ll;
     23 typedef vector <ll> vi;
     24 int main() {
     25     int t;
     26     cin >> t;
     27     while (t --> 0) {
     28         int n;
     29         cin >> n;
     30         vi arr(n);
     31         for (int i = 0; i < n; i++) {
     32             cin >> arr[i];
     33         }
     34         if (arr[0] == 1) {
     35             cout << "YES";
     36         } else {
     37             cout << "NO";
     38         }
     39         cout << '\n';
     40     }
     41 }
     42 ```
     43 
     44 ## [1896B - AB-обмен](/contest/1896/problem/B)
     45 
     46 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90")
     47 
     48 **Hint 1**
     49 
     50 What happens when $s$ starts with some $\texttt{B}$ and ends with some $\texttt{A}$?
     51 
     52 **Solution**
     53 
     54 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 \gt 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$.
     55 
     56 Now, we are left with the case where $x \lt 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$.
     57 
     58 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 \lt b_1 \lt b_2 \lt \ldots \lt 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:
     59 
     60 $b_1 - 1, b_1 - 2, \ldots, b_0 + 1, b_0,$
     61 
     62 $b_2 - 1, b_2 - 2, \ldots, b_1 + 1, b_1,$
     63 
     64 $b_3 - 1, b_3 - 2, \ldots, b_2 + 1, b_2,$
     65 
     66 $\vdots$
     67 
     68 $b_k - 1, b_k - 2, \ldots, b_{k - 1} + 1, b_k$
     69 
     70 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.
     71 
     72 **Implementation**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 using namespace std;
     77  
     78 char s[200005];
     79  
     80 signed main() {
     81 	ios_base::sync_with_stdio(0);
     82 	cin.tie(0); cout.tie(0);
     83 	int tc, n; cin >> tc;
     84 	while (tc--) {
     85 		cin >> n; s[n + 1] = 'C';
     86 		for (int i = 1; i <= n; ++i) cin >> s[i];
     87 		int pt1 = 1, pt2 = 1, ans = 0;
     88 		while (s[pt1] == 'B') ++pt1, ++pt2;
     89 		while (pt1 <= n) {
     90 			int cntA = 0, cntB = 0;
     91 			while (s[pt2] == 'A') ++pt2, ++cntA;
     92 			while (s[pt2] == 'B') ++pt2, ++cntB;
     93 			if (s[pt2 - 1] == 'B') ans += pt2 - pt1 - 1;
     94 			if (cntB) pt1 = pt2 - 1;
     95 			else break;
     96 		}
     97 		cout << ans << '\n';
     98 	}
     99 }
    100 ```
    101 
    102 ## [1896C - Сопоставление массивов](/contest/1896/problem/C)
    103 
    104 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90")
    105 
    106 **Hint 1**
    107 
    108 Consider a greedy algorithm.
    109 
    110 **Solution**
    111 
    112 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$.
    113 
    114 **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$.
    115 
    116 *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 \gt b_{p_i}$ in increasing order. In other words, $1 \le q_1 \lt q_2 \lt \ldots \lt q_x \le n$ and $a_{q_i} \gt b_{p_{q_i}}$. Let $i$ be the largest index where $q_i \neq n - i + 1$ ($q_i \lt n - i + 1$ also holds due to strict inequality above). We know that $a_{q_i} \gt b_{p_{q_i}}$ and $a_{n - i + 1} \le b_{p_{n - i + 1}}$. Since $a$ is sorted and $q_i \lt n - i + 1$, we have $a_{q_i} \le a_{n - i + 1}$, and hence, $a_{n - i + 1} \gt 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$.
    117 
    118 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 \gt b_{p_i}$. Let $i$ be the largest index between $1$ and $n - x$ where $p_i \neq i + x$ ($p_i \lt i + x$ due to maximality). Then, let $j$ be the index where $p_j = i + x$. Consider two cases:
    119 
    120 * $j \le n - x$. Since $i$ is the largest index where $p_i \neq i + x$, this means that $j \lt 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$.
    121 * $j \gt n - x$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j \gt b_{p_j} = b_{i + x} \gt 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$.
    122 
    123 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 \gt i - n + x$ by minimality). Then, let $j$ be the index where $p_j = i - n + x$. Note that $j \gt 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 \lt j$ and hence $a_i \le a_j$. We have $a_i \gt b_{p_i} \ge b_{i - n + x} = b_{p_j}$ and $a_j \ge a_i \gt 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.
    124 
    125 **Implementation**
    126 
    127 ```
    128 #include <bits/stdc++.h> 
    129 using namespace std;
    130  
    131 #define REP(i, s, e) for (int i = (s); i < (e); i++)
    132 #define RREP(i, s, e) for (int i = (s); i >= (e); i--)
    133  
    134 const int INF = 1000000005;
    135 const int MAXN = 200005;
    136  
    137 int t;
    138 int n, x;
    139 int a[MAXN], b[MAXN], aid[MAXN];
    140 int ans[MAXN];
    141  
    142 int main() {
    143     ios::sync_with_stdio(0), cin.tie(0);
    144     cin >> t;
    145     while (t--) {
    146         cin >> n >> x;
    147         REP (i, 0, n) {
    148             cin >> a[i];
    149         }
    150         REP (i, 0, n) {
    151             cin >> b[i];
    152         }
    153         iota(aid, aid + n, 0);
    154         sort(aid, aid + n, [&] (int l, int r) {
    155                 return a[l] < a[r];
    156                 });
    157         sort(b, b + n);
    158         REP (i, 0, x) {
    159             ans[aid[n - x + i]] = b[i];
    160         }
    161         REP (i, x, n) {
    162             ans[aid[i - x]] = b[i];
    163         }
    164         REP (i, 0, n) {
    165             x -= a[i] > ans[i];
    166         }
    167         if (x == 0) {
    168             cout << "YES\n";
    169             REP (i, 0, n) {
    170                 cout << ans[i] << ' ';
    171             }
    172             cout << '\n';
    173         } else {
    174             cout << "NO\n";
    175         }
    176     }
    177     return 0;
    178 }
    179 ```
    180 
    181 ## [1896D - Единицы и двойки](/contest/1896/problem/D)
    182 
    183 Writer: [lanhf](/profile/lanhf "Мастер lanhf")
    184 
    185 **Hint 1**
    186 
    187 Consider some small examples and write down every possible value of subarray sums. Can you see some patterns?
    188 
    189 **Solution**
    190 
    191 Denote $s[l,r]$ as the sum of subarray from $l$ to $r$.
    192 
    193 **Claim**: If there is any subarray with sum $v\ge 2$, we can find a subarray with sum $v-2$.
    194 
    195 *Proof*: Suppose $s[l,r]=v$, consider 3 cases:
    196 
    197 * $a[l]=2$, we have $s[l+1,r]=v-2$.
    198 * $a[r]=2$, we have $s[l,r-1]=v-2$.
    199 * $a[l]=a[r]=1$, we have $s[l+1,r-1]=v-2$.
    200 
    201 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$.
    202 
    203 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.
    204 
    205 **Implementation**
    206 
    207 ```
    208 #include <bits/stdc++.h>
    209 
    210 using namespace std;
    211 
    212 int main() {
    213     cin.tie(0)->sync_with_stdio(0);
    214     int t; cin >> t;
    215     while (t--) {
    216         int n, q; cin >> n >> q;
    217         vector<int> a(n);
    218         set<int> pos;
    219         for (int i = 0; i < n; i++) {
    220             cin >> a[i];
    221             if (a[i] == 1) pos.insert(i);
    222         }
    223         while (q--) {
    224             int cmd; cin >> cmd;
    225             if (cmd == 1) {
    226                 int v; cin >> v;
    227                 int num = pos.size();
    228                 if ((v - num) & 1) {
    229                     if (num == 0) cout << "NO";
    230                     else {
    231                         int s1 = 2 * *pos.rbegin() - (num - 1);
    232                         int s2 = 2 * (n - *pos.begin() - 1) - (num - 1);
    233                         if (v <= max(s1, s2)) cout << "YES";
    234                         else cout << "NO";
    235                     }
    236                 } else {
    237                     if (v <= 2 * n - num) cout << "YES";
    238                     else cout << "NO";
    239                 }
    240                 cout << '\n';
    241             } else {
    242                 int i; cin >> i; i--;
    243                 pos.erase(i);
    244                 cin >> a[i];
    245                 if (a[i] == 1) pos.insert(i);
    246             }
    247         }
    248     }
    249 }
    250 ```
    251 
    252 ## [1896E - Сортировка перестановки](/contest/1896/problem/E)
    253 
    254 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90")
    255 
    256 **Hint 1**
    257 
    258 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$?
    259 
    260 **Solution**
    261 
    262 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 \lt j \lt i + h_i$ and $i \lt a_j \lt i + h_i$ (or $i \lt a_j + n \lt i + h_i$ to handle cyclic case when $i + h_i \gt 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.
    263 
    264 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.
    265 
    266 **Implementation**
    267 
    268 ```
    269 #include <bits/stdc++.h> 
    270 using namespace std;
    271  
    272 #define REP(i, s, e) for (int i = (s); i < (e); i++)
    273 #define RREP(i, s, e) for (int i = (s); i >= (e); i--)
    274 #define ALL(_a) _a.begin(), _a.end()
    275 #define SZ(_a) (int) _a.size()
    276  
    277 const int INF = 1000000005;
    278 const int MAXN = 1000005;
    279  
    280 int t;
    281 int n;
    282 int p[MAXN];
    283 int ans[MAXN];
    284  
    285 int fw[MAXN * 2];
    286 void incre(int i, int x) {
    287     for (; i <= 2 * n; i += i & -i) {
    288         fw[i] += x;
    289     }
    290 }
    291 int qsm(int i) {
    292     int res = 0;
    293     for (; i > 0; i -= i & -i) {
    294         res += fw[i];
    295     }
    296     return res;
    297 }
    298 inline int qsm(int s, int e) {
    299     return qsm(e) - qsm(s - 1);
    300 }
    301  
    302 int main() {
    303 #ifndef DEBUG
    304     ios::sync_with_stdio(0), cin.tie(0);
    305 #endif
    306     cin >> t;
    307     while (t--) {
    308         cin >> n;
    309         REP (i, 1, n + 1) {
    310             cin >> p[i];
    311         }
    312         REP (i, 0, 2 * n + 5) {
    313             fw[i] = 0;
    314         }
    315         vector<pair<int, int>> rgs;
    316         REP (i, 1, n + 1) {
    317             if (i <= p[i]) {
    318                 rgs.push_back({i, p[i]});
    319                 rgs.push_back({i + n, p[i] + n});
    320             } else {
    321                 rgs.push_back({i, p[i] + n});
    322             }
    323         }
    324         sort(ALL(rgs), greater<pair<int, int>>());
    325         for (auto [l, r] : rgs) {
    326             if (l <= n) {
    327                 ans[p[l]] = r - l - qsm(l, r);
    328             }
    329             incre(r, 1);
    330         }
    331         REP (i, 1, n + 1) {
    332             cout << ans[i] << ' ';
    333         }
    334         cout << '\n';
    335     }
    336     return 0;
    337 }
    338 ```
    339 
    340 ## [1896F - Инвертирование скобок](/contest/1896/problem/F)
    341 
    342 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90")
    343 
    344 **Hint 1**
    345 
    346 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.
    347 
    348 **Proof**
    349 
    350 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.
    351 
    352 **Hint 2**
    353 
    354 Every operation will always toggle $s_1$ and $s_n$. Furthermore, every operation will always toggle an even number of positions.
    355 
    356 **Proof**
    357 
    358 If $s$ is toggled at an open bracket, $s$ will be toggled at its matching close bracket as well.
    359 
    360 **Hint 3**
    361 
    362 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.
    363 
    364 **Hint 4**
    365 
    366 If it is possible to change all elements of $s$ to $\texttt{0}$, at most $3$ operations are needed.
    367 
    368 **Solution 1**
    369 
    370 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}$.
    371 
    372 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.
    373 
    374 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.
    375 
    376 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}$.
    377 
    378 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}$.
    379 
    380 **Solution 2**
    381 
    382 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.
    383 
    384 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$.
    385 
    386 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.
    387 
    388 Now, we will demonstrate a greedy algorithm.
    389 
    390 $(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)$
    391 
    392 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.
    393 
    394 **Solution 3**
    395 
    396 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.
    397 
    398 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.
    399 
    400 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.
    401 
    402 **Implementation**
    403 
    404 ```
    405 #include <bits/stdc++.h>
    406 using namespace std;
    407 
    408 void solve(int n, string s) {
    409 	vector<int> a;
    410 	for (char &i : s) {
    411 		a.push_back(i & 1);
    412 	}
    413 	
    414 	if (a.front() != a.back()) {
    415 		cout << -1 << endl;
    416 		return ;
    417 	}
    418 	
    419 	if (count(a.begin(), a.end(), 1) % 2) {
    420 		cout << -1 << endl;
    421 		return ;
    422 	}
    423 	
    424 	bool flipped = false;
    425 	if (a.front() == 1 && a.back() == 1) {
    426 		for (int &i : a) i ^= 1;
    427 		flipped = true;
    428 	}
    429 	
    430 	string l(2 * n, '-'), r(2 * n, '-');
    431 	int cnt = 0;
    432 	for (int i = 0; i < 2 * n; i++) {
    433 		if (a[i]) {
    434 			l[i] = (cnt) ? '(' : ')';
    435 			r[i] = (cnt ^ 1) ? '(' : ')';
    436 			cnt ^= 1;
    437 		}
    438 	}
    439 	
    440 	int tot = count(a.begin(), a.end(), 0) / 2;
    441 	cnt = 0;
    442 	for (int i = 0; i < 2 * n; i++) {
    443 		if (!a[i]) {
    444 			if (cnt < tot) l[i] = '(', r[i] = '(';
    445 			else l[i] = ')', r[i] = ')';
    446 			cnt++;
    447 		}
    448 	}
    449 	
    450 	if (flipped) {
    451 		cout << 3 << endl;
    452 		cout << l << endl;
    453 		cout << r << endl;
    454 		for (int i = 0; i < n; i++) cout << "()";
    455 		cout << endl;
    456 	} else {
    457 		cout << 2 << endl;
    458 		cout << l << endl;
    459 		cout << r << endl;
    460 	}
    461 }
    462 
    463 int main() {	
    464 	int t;
    465 	cin >> t;
    466 	while (t--) {
    467 		int n;
    468 		cin >> n;
    469 		string s;
    470 		cin >> s;
    471 		solve(n, s);
    472 	}
    473 	
    474 	return 0;
    475 }
    476 ```
    477 
    478 ## [1896G - Гонка пепе](/contest/1896/problem/G)
    479 
    480 Writer: [thenymphsofdelphi](/profile/thenymphsofdelphi "Международный гроссмейстер thenymphsofdelphi")
    481 
    482 **Hint 1**
    483 
    484 Find the fastest pepe in $n + 1$ queries.
    485 
    486 **Hint**
    487 
    488 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.
    489 
    490 **Hint 2**
    491 
    492 After knowing the fastest pepe, find the second fastest pepe in $n + 1$ queries.
    493 
    494 **Hint**
    495 
    496 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.
    497 
    498 **Hint 3**
    499 
    500 Note that the above process for Hint 2 uses a lot of repeated queries. Can we optimize it to $2$ queries?
    501 
    502 **Hint**
    503 
    504 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.
    505 
    506 **Hint 4**
    507 
    508 Solve the problem using $2n^2 - n + 1$ queries.
    509 
    510 **Hint**
    511 
    512 Our algorithm has three phases:
    513 
    514 * 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$.
    515 * Phase 2: Until there are $2n - 1$ pepes, repeat these two steps:
    516   + 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$.
    517   + Steal non-head pepes from other groups so that $|G_i| = n$, then use $1$ query to recalculate its head.
    518 * 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.
    519 
    520 Total number of queries is $n + 2(n^2 - 2n + 1) + 2(n - 1) + 1 = 2n^2 - n + 1$.
    521 
    522 **Solution 1**
    523 
    524 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.
    525 
    526 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.
    527 
    528 Total number of queries is $n + 2(n^2 - 2n + 1) + (n - 1) = 2n^2 - 2n + 1$.
    529 
    530 **Solution 2**
    531 
    532 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$.
    533 
    534 We modify the algorithm in hint 4 to maintain an invariant: $|G_i| - |G_j| \le 1$ $\forall \, 1 \le i \lt j \le n$. In other words, we want to make the sizes of these groups as balanced as possible.
    535 
    536 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.
    537 
    538 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.
    539 
    540 Total number of queries is $n + 2(n^2 - 2n) + (n + 1) = 2n^2 - 2n + 1$.
    541 
    542 **Implementation (Solution 1)**
    543 
    544 ```
    545 #include <bits/stdc++.h>
    546 
    547 using namespace std;
    548 
    549 const int N = 30;
    550 
    551 vector<int> buc[N];
    552 int buc_id[N * N], buc_max[N];
    553 int n;
    554 
    555 int ask(vector<int> que) {
    556   cout << "?";
    557   for (int i : que) cout << ' ' << i + 1;
    558   cout << endl;
    559   int res; cin >> res;
    560   return res - 1;
    561 }
    562 
    563 int ask_all() {
    564   vector<int> que;
    565   for (int i = 0; i < n; i++)
    566     if (buc[i].size())
    567       que.push_back(buc_max[i]);
    568   for (int i = 0; i < n; i++)
    569     for (int j : buc[i])
    570       if (int(que.size()) < n && j != buc_max[i])
    571         que.push_back(j);
    572   return ask(que);
    573 }
    574 
    575 void answer(vector<int> ans) {
    576   cout << "!";
    577   for (int i : ans) cout << ' ' << i + 1;
    578   cout << endl;
    579 }
    580 
    581 void add(int id, int pepe) {
    582   buc[id].push_back(pepe);
    583   buc_id[pepe] = id;
    584 }
    585 
    586 void remove(int id, int pepe) {
    587   buc[id].erase(find(buc[id].begin(), buc[id].end(), pepe));
    588 }
    589 
    590 void send(int id, vector<int> &que) {
    591   for (int pepe : buc[id])
    592     if (int(que.size()) < n && pepe != buc_max[id])
    593       que.push_back(pepe);
    594 }
    595 
    596 void check_balance() {
    597   size_t min_size = n, max_size = 0;
    598   for (int id = 0; id < n; id++) {
    599     min_size = min(min_size, buc[id].size());
    600     max_size = max(max_size, buc[id].size());
    601   }
    602   assert(max_size - min_size <= 1);
    603 }
    604 
    605 int main() {
    606   cout << endl;
    607   int t; cin >> t;
    608   while (t--) {
    609     cin >> n;
    610     for (int id = 0; id < n; id++)
    611       buc[id].clear();
    612       
    613     for (int pepe = 0; pepe < n * n; pepe++) {
    614       buc_id[pepe] = pepe / n;
    615       buc[pepe / n].push_back(pepe);
    616     }
    617     
    618     for (int id = 0; id < n; id++)
    619       buc_max[id] = ask(buc[id]);
    620       
    621     vector<int> ans;
    622     
    623     /// balancing phase
    624     for (int step = 0; step < n * n - 2 * n; step++) {
    625       ans.push_back(ask_all());
    626       int last_id = buc_id[ans.back()];
    627       remove(last_id, ans.back());
    628       
    629       vector<int> que;
    630               
    631       for (int pepe : buc[last_id])
    632         que.push_back(pepe);
    633         
    634       /// find bucket with largest size != last_id
    635       int max_id = (last_id == 0);
    636       for (int id = 0; id < n; id++)
    637         if (id != last_id && buc[id].size() > buc[max_id].size())
    638           max_id = id;
    639           
    640       
    641       send(max_id, que);
    642       
    643       for (int id = 0; id < n; id++)
    644         if (id != max_id && id != last_id)
    645           send(id, que);
    646       
    647       buc_max[last_id] = ask(que);
    648       int move_id = buc_id[buc_max[last_id]];
    649       if (move_id != last_id) {
    650         remove(move_id, buc_max[last_id]);
    651         add(move_id, buc[last_id].back());
    652         remove(last_id, buc[last_id].back());
    653         add(last_id, buc_max[last_id]);
    654       }        
    655       
    656       if (buc[last_id].size() == buc[max_id].size() - 2) {
    657         if (move_id == max_id) {
    658           add(last_id, buc[move_id].back());
    659           remove(move_id, buc[move_id].back());
    660         } else {
    661           for (int pepe : buc[max_id])
    662             if (pepe != buc_max[max_id]) {
    663               add(last_id, pepe);
    664               remove(max_id, pepe);
    665               break;
    666             }
    667         }
    668       }
    669       
    670       check_balance();
    671     }
    672   
    673     
    674     for (int step = 0; step < n + 1; step++) {
    675       ans.push_back(ask_all());
    676       int last_id = buc_id[ans.back()];
    677       remove(last_id, ans.back());
    678       if (buc[last_id].size())
    679         buc_max[last_id] = buc[last_id][0];
    680     }
    681     
    682     answer(ans);
    683   }
    684 }
    685 ```
    686 
    687 **Implementation (Solution 2)**
    688 
    689 ```
    690 #include <bits/stdc++.h>
    691 using namespace std;
    692 
    693 #define int long long
    694 #define ll long long
    695 #define ii pair<ll,ll>
    696 #define iii pair<ii,ll>
    697 #define fi first
    698 #define se second
    699 #define debug(x) cout << #x << ": " << x << endl
    700 
    701 #define pub push_back
    702 #define pob pop_back
    703 #define puf push_front
    704 #define pof pop_front
    705 #define lb lower_bound
    706 #define ub upper_bound
    707 
    708 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
    709 #define all(x) (x).begin(),(x).end()
    710 #define sz(x) (int)(x).size()
    711 
    712 mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
    713 
    714 int n;
    715 vector<int> v[25];
    716 
    717 int ask(vector<int> v){
    718 	cout<<"? "; for (auto it:v) cout<<it<<" "; cout<<endl;
    719 	int res; cin>>res;
    720 	return res;
    721 }
    722 
    723 vector<int> fix(vector<int> v){
    724 	int t=ask(v);
    725 	rep(x,0,n) if (v[x]==t) swap(v[0],v[x]);
    726 	return v;
    727 }
    728 
    729 signed main(){
    730 	ios::sync_with_stdio(0);
    731 	cin.tie(0);
    732 	cout.tie(0);
    733 	cin.exceptions(ios::badbit | ios::failbit);
    734 	
    735 	int TC;
    736 	cin>>TC;
    737 	while (TC--){
    738 		cin>>n;
    739 		rep(x,0,n){
    740 			v[x].clear();
    741 			rep(y,1,n+1) v[x].pub(x*n+y);
    742 		}
    743 		
    744 		rep(x,0,n) v[x]=fix(v[x]);
    745 		
    746 		vector<int> ans;
    747 		rep(x,0,n*n-2*n+1){
    748 			vector<int> t;
    749 			rep(x,0,n) t.pub(v[x][0]);
    750 			int best=ask(t);
    751 			
    752 			int idx=-1;
    753 			rep(x,0,n) if (t[x]==best) idx=x;
    754 			
    755 			ans.pub(best);
    756 			v[idx].erase(v[idx].begin());
    757 			
    758 			rep(x,0,n) if (x!=idx){
    759 				while (sz(v[x])>1 && sz(v[idx])<n){
    760 					v[idx].pub(v[x].back());
    761 					v[x].pob();
    762 				}
    763 			}
    764 			v[idx]=fix(v[idx]);
    765 		}
    766 		
    767 		vector<int> a,b;
    768 		rep(x,0,n){
    769 			rep(y,0,sz(v[x])){
    770 				if (y==0) a.pub(v[x][y]);
    771 				else b.pub(v[x][y]);
    772 			}
    773 		}
    774 		set<int> bad=set<int>(all(b));
    775 		
    776 		rep(x,0,n-1){
    777 			a=fix(a);
    778 			ans.pub(a[0]);
    779 			a.erase(a.begin());
    780 			a.pub(b.back()); b.pob();
    781 		}
    782 		
    783 		for (auto it:a) if (!bad.count(it)) ans.pub(it);
    784 		
    785 		cout<<"! "; for (auto it:ans) cout<<it<<" "; cout<<endl;
    786 	}
    787 	
    788 }
    789 ```
    790 
    791 ## [1896H2 - Цикличный Хэмминг (сложная версия)](/contest/1896/problem/H2)
    792 
    793 Writer: [xuanquang1999](/profile/xuanquang1999 "Гроссмейстер xuanquang1999")
    794 
    795 **Hint 1**
    796 
    797 For any $c$ which is a cyclic shift of $t$, what will happen if $h(s,c) \gt 2^k$?
    798 
    799 **Hint 2**
    800 
    801 Try finding some useful relationship between $1$-s of $s$ and $1$-s of $c$.
    802 
    803 **Hint**
    804 
    805 There are exactly $n/2$ positions $i$ such that $s[i]=c[i]=1$.
    806 
    807 **Hint 3**
    808 
    809 Think about polynomial multiplication.
    810 
    811 **Hint 1**
    812 
    813 Consider $S\cdot T$, where $S=\sum s[i]x^i$ and $T=\sum t[2n-i-1]x^i$ (reversed coefficients).
    814 
    815 **Hint 2**
    816 
    817 What are some properties that the coefficients of $S\cdot T$ tell us?
    818 
    819 **Hint**
    820 
    821 Denote $A=S\cdot T$, we have $A[x^i]+A[x^{i+2n}]=n/2$.
    822 
    823 **Hint 3**
    824 
    825 Try factoring $S\cdot T$ into some irreducible polynomials.
    826 
    827 **Hint 4**
    828 
    829 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?
    830 
    831 **Solution**
    832 
    833 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).
    834 
    835 **Claim 1.** For all $0\le i \lt 2n$, we have $A[x^i]+A[x^{i+2n}]=n/2$, where $A[x^k]$ denote the coefficient of $x^k$ in $A$.
    836 
    837 **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$.
    838 
    839 **Proof**
    840 
    841 $ \begin{align} &(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)(n/2+C(x-1))\\ =\ &C(x^{2n}-1)+n/2\cdot (x^0+x^1+x^2+\ldots+x^{2n-1}) \end{align} $
    842 
    843 It is easy to see that this satisfies claim 1.
    844 
    845 **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.
    846 
    847 **Proof**
    848 
    849 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.
    850 
    851 Recall $n=2^k$, define $f_s(mask)$ ($0\le mask \lt 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.
    852 
    853 The answer to the problem is $\displaystyle\sum_{mask} f_s(mask)\cdot \mu(f^{\prime}_t(mask))$ where $\mu$ denote [Mobius transform](https://codeforces.com/blog/entry/72488). The reason we need Mobius transform is that $mask_s$ does not represent all divisors, just a subset of it.
    854 
    855 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.
    856 
    857 **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).
    858 
    859 **Hint**
    860 
    861 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.
    862 
    863 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:
    864 
    865 * $dp_s[i][mask][num_1+num_2]\text{ += }dp_s[2i][mask][num_1]\cdot dp_s[2i+1][mask][num_2]$
    866 * $dp_s[i][mask+2^l][2\cdot num]\text{ += }dp_s[2i][mask][num]\cdot dp_s[2i+1][mask][num]$
    867 
    868 The above dp took $\mathcal{O}(n^3)$, which is sufficient to solve the easy version.
    869 
    870 To solve the hard version, we will optimize the above transitions:
    871 
    872 * 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.
    873 * 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.
    874 
    875 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.