codeforces-scrape

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

1748.md (19103B)


      1 Source: https://codeforces.com/blog/entry/108319
      2 
      3 ## [A — The Ultimate Square](https://codeforces.com/contest/1748/problem/A)
      4 
      5 Author: [Gheal](/profile/Gheal "Master Gheal")
      6 
      7 **Hints**
      8 
      9 **Hint 1**
     10 
     11 If $n$ is odd, it is possible to create a square using all $n$ blocks.
     12 
     13 **Hint 2**
     14 
     15 If $n$ is even, it is possible to create a square using only the first $n-1$ blocks, since $n-1$ is odd. Can we use the last block to create a larger square?
     16 
     17 **Solution**
     18 
     19 If $n$ is odd, let $k=\frac{n+1}{2}$ be the width of the last block. It is possible to create a square of side length $k$ using every block as follows:
     20 
     21 * Line $1$ contains a $1 \times k$ block;
     22 * Line $2$ contains a $1 \times 1$ block and a $1 \times (k-1)$ block;
     23 * Line $3$ contains a $1 \times 2$ block and a $1 \times (k-2)$ block;
     24 * $\ldots$
     25 * Line $i$ contains a $1 \times (i-1)$ block and a $1 \times (k-i+1)$ block;
     26 * $\ldots$
     27 * Line $k$ contains a $1 \times (k-1)$ block and a $1 \times 1$ block.
     28 
     29 Since the area of this square is $k^2$, and the $n+1$-th block has a width of $k$ tiles, the total area of the first $n+1$ blocks is equal to $k^2+k \lt (k+1)^2$. Therefore, the answer for $n+1$ is also $k$.
     30 
     31 In conclusion, the answer for each testcase is $\lfloor \frac{n+1}{2} \rfloor$.
     32 
     33 Time complexity per testcase: $O(1)$.
     34 
     35 **Code (C++)**
     36 
     37 ```
     38 #include<bits/stdc++.h>
     39 
     40 using namespace std;
     41 
     42 typedef long long ll;
     43 void testcase(){
     44     ll n;
     45     cin>>n;
     46     cout<<(n+1)/2<<'\n';
     47 }
     48 int main()
     49 {
     50     ll t; cin>>t; while(t--)
     51        testcase();
     52     return 0;
     53 }
     54 ```
     55 
     56 **Rate Problem**
     57 
     58 Good problem
     59 
     60 Ok problem
     61 
     62 Bad problem
     63 
     64 Didn't solve it, idk
     65 
     66 ## [B — Balanced Substrings](https://codeforces.com/contest/1748/problem/B)
     67 
     68 Author: [Gheal](/profile/Gheal "Master Gheal")
     69 
     70 **Hints**
     71 
     72 **Hint 1**
     73 
     74 What is the maximum number of distinct characters in a diverse string?
     75 
     76 **Hint 2**
     77 
     78 What is the maximum frequency of a character in a diverse string?
     79 
     80 **Hint 3**
     81 
     82 What is the maximum possible length a diverse string?
     83 
     84 **Solution**
     85 
     86 In a diverse string, there are at most $10$ distinct characters: '0', '1', $\ldots$, '9'. Therefore, each of these characters can appear at most $10$ times in a diverse string.
     87 
     88 With all this in mind, the maximum possible length of a diverse string is $10^2=100$. To solve this problem, we only need to check whether each substring of length $l \le 100$ is diverse.
     89 
     90 Time complexity per testcase: $O(n \cdot 10^2)$
     91 
     92 **Code(C++)**
     93 
     94 ```
     95 #include<bits/stdc++.h>
     96 
     97 using namespace std;
     98 
     99 typedef long long ll;
    100 void tc(){
    101     ll n;
    102     string s;
    103     cin>>n>>s;
    104     ll ans=0;
    105 
    106     for(ll i=0;i<s.size();i++){
    107 
    108         int fr[10]{}, distinct=0, max_freq=0;
    109 
    110         for(ll j=i;j<s.size() && (++fr[s[j]-'0'])<=10;j++){
    111 
    112             max_freq=max(max_freq,fr[s[j]-'0']);
    113             if(fr[s[j]-'0']==1) distinct++;
    114 
    115             if(distinct>=max_freq) ans++;
    116         }
    117     }
    118     cout<<ans<<'\n';
    119 }
    120 int main()
    121 {
    122 
    123     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    124     ll t; cin>>t; while(t--) tc();
    125     return 0;
    126 }
    127 ```
    128 
    129 **Rate problem**
    130 
    131 Good problem
    132 
    133 Ok problem
    134 
    135 Bad problem
    136 
    137 Didn't solve it, idk
    138 
    139 ## [C — Zero Sum Prefixes](https://codeforces.com/contest/1748/problem/C)
    140 
    141 Idea: [Gheal](/profile/Gheal "Master Gheal"), Solution: [IgorI](/profile/IgorI "Grandmaster IgorI")
    142 
    143 **Hints**
    144 
    145 **Hint 1**
    146 
    147 What is the answer if $a_1=0$ and $a_i \neq 0$ for all $2 \le i \le n$?
    148 
    149 **Hint 2**
    150 
    151 What is the answer if $a_i=0$ and $a_j \neq 0$ for all $1 \le j \le n$, $j \neq i$?
    152 
    153 **Hint 3**
    154 
    155 What is the answer if there are only two indices $i$ and $j$ for which $a_i=a_j=0$?
    156 
    157 **Solution**
    158 
    159 Let's consider the prefix sum array $s=[a_1,a_1+a_2,\ldots,a_1+a_2+\ldots+a_n]$.
    160 
    161 For every index $i$ such that $a_i=0$, if we change the value of $a_i$ to $x$, then every element from the suffix $[s_i,s_{i+1},\ldots,s_n]$ will be increased by $x$. Therefore, if $a_{i_1}=a_{i_2}=\ldots=a_{i_k}=0$, we'll partition array $s$ into multiple subarrays:
    162 
    163 * $[s_1,s_2,\ldots,s_{i_1-1}]$;
    164 * $[s_{i_1},s_{i_1+1},\ldots,s_{i_2-1}]$;
    165 * $[s_{i_2},s_{i_2+1},\ldots,s_{i_3-1}]$;
    166 * $\ldots$
    167 * $[s_{i_k},s_{i_{k+1}},\ldots,s_n]$;
    168 
    169 Since none of the elements from the first subarray can be changed, it will contribute with the number of occurences of $0$ in $[s_1,s_2,\ldots,s_{i_1-1}]$ towards the final answer.
    170 
    171 For each of the other subarrays $[s_l,s_{l+1},\ldots,s_r]$, let $x$ be the most frequent element in the subarray, appearing $fr[x]$ times. Since $a_l=0$, we can change the value of $a_l$ to $-x$. In this case, every $x$ in this subarray will become equal to $0$, and our current subarray will contribute with $fr[x]$ towards the final answer.
    172 
    173 Time complexity per testcase: $O(NlogN)$
    174 
    175 **Code(C++)**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 
    180 using namespace std;
    181 typedef long long ll;
    182 const ll MAXN=2e5+5;
    183 
    184 ll a[MAXN];
    185 map<ll,ll> freq;
    186 
    187 void tc(){
    188     ll n;
    189     cin>>n;
    190     ll maxfr=0,current_sum=0,ans=0;
    191     bool found_wildcard=0;
    192     freq.clear();
    193     for(ll i=0;i<n;i++){
    194         cin>>a[i];
    195 
    196         if(a[i]==0){
    197 
    198             if(found_wildcard) ans+=maxfr;
    199             else ans+=freq[0];
    200 
    201             found_wildcard=1;
    202 
    203             maxfr=0,freq.clear();
    204         }
    205 
    206         current_sum+=a[i];
    207         maxfr=max(maxfr,++freq[current_sum]);
    208     }
    209     if(found_wildcard) ans+=maxfr;
    210     else ans+=freq[0];
    211 
    212     cout<<ans<<'\n';
    213 }
    214 
    215 int main()
    216 {
    217     ios_base::sync_with_stdio(false), cin.tie(0);
    218     ll t; cin>>t; while(t--)
    219         tc();
    220     return 0;
    221 }
    222 ```
    223 
    224 **Rate problem**
    225 
    226 Good problem
    227 
    228 Ok problem
    229 
    230 Bad problem
    231 
    232 Didn't solve it, idk
    233 
    234 ## [D — ConstructOR](https://codeforces.com/contest/1748/problem/D)
    235 
    236 Author: [Gheal](/profile/Gheal "Master Gheal")
    237 
    238 **Hints**
    239 
    240 **Hint 1**
    241 
    242 If at least one of $a$ and $b$ is odd, and $d$ is even, then there are no solutions.
    243 
    244 **Proof**
    245 
    246 Without loss of generality, we will only consider the case when $a$ is odd and $d$ is even. Since the last bit of $a$ is $1$, then the last bit of $a|x$ must also be $1$.
    247 
    248 Therefore, $a|x$ cannot be a multiple of $d$, as $a|x$ is odd, while $d$ is even.
    249 
    250 Note that there are more cases in which no solutions exist, however they are more generalised versions of this case.
    251 
    252 **Hint 2**
    253 
    254 If a triplet ($a,b,d$) has no solutions, then ($a\cdot 2,b\cdot 2,d\cdot 2$) has no solutions as well.
    255 
    256 Combined with the first hint, we can say that a triplet ($a,b,d$) has no solutions if $min(\text{lsb}(a),\text{lsb}(b)) \lt \text{lsb}(d)$. Here, $\text{lsb}(x)$ represents the [least significant bit](https://en.wikipedia.org/wiki/Bit_numbering#Bit_significance_and_indexing) of $x$.
    257 
    258 **Hint 3**
    259 
    260 Since both $a|x$ and $b|x$ must be divisible by $d$, it's better to choose an $x$ such that $a|x=b|x=x$.
    261 
    262 **Hint 4**
    263 
    264 If $d$ is odd, since $a,b \lt 2^{30}$, we can ensure that $a|x=b|x=x$ by setting the last $30$ bits of $c$ to $1$.
    265 
    266 If $d$ is even, then the last $\text{lsb}(d)$ bits of $x$ should be set to $0$, while the other bits from the last $30$ bits should be set to $1$. Here, $\text{lsb}(x)$ represents the [least significant bit](https://en.wikipedia.org/wiki/Bit_numbering#Bit_significance_and_indexing) of $x$.
    267 
    268 **Solution**
    269 
    270 Let $k=\text{lsb}(d)$, where $\text{lsb}(d)$ represents the [least significant bit](https://en.wikipedia.org/wiki/Bit_numbering#Bit_significance_and_indexing) of $d$.
    271 
    272 Since $a|x$ and $b|x$ are multiples of $d$, the last $k$ bits of $a$ and $b$ (and also $x$) must be equal to $0$.
    273 
    274 Otherwise, there are no solutions and we can print $-1$.
    275 
    276 To simplify the construction process, we will try to find some $x$ such that $a|x=b|x=x$. Since we already know that the last $k$ bits of $a$, $b$ and $x$ are $0$, we will consider that the other $30-k$ of the $30$ least significant bits of $x$ are equal to $1$:
    277 
    278 $x_{(2)}=p\text{ }1\text{ }1\text{ }1\text{ }\ldots\text{ }1\text{ }0\text{ }0\text{ }\ldots\text{ }0$
    279 
    280 This gives the following general formula for $x$:
    281 
    282 $x=2^k \cdot (p \cdot 2^{30-k} + (2^{30-k} -1))$
    283 
    284 Now, we'll try to find some $p$ for which $x$ is a multiple of $d=2^k \cdot d'$:
    285 
    286 $x=2^k \cdot (p \cdot 2^{30-k} + (2^{30-k} -1) \equiv 0 \mod 2^k \cdot d' \Leftrightarrow$ $\Leftrightarrow (p \cdot 2^{30-k} + (2^{30-k} -1) \equiv 0 \mod d' \Leftrightarrow$ $\Leftrightarrow (p+1) \cdot 2^{30-k} \equiv 1 \mod d' \Leftrightarrow$ $\Leftrightarrow p+1 \equiv 2^{k-30} \mod d' \Leftrightarrow$ $\Leftrightarrow p+1 \equiv (2^{-1})^{30-k} \mod d' \Leftrightarrow$ $\Leftrightarrow p+1 \equiv (\frac{d'+1}{2})^{30-k} \mod d' \Rightarrow$ $\Rightarrow p = ((\frac{d'+1}{2})^{30-k}+d'-1) \mod d'$
    287 
    288 Time complexity per testcase: $O(log d)$
    289 
    290 Note that if $a|b$ is already a multiple of $d$, we can consider $x=a|b$.
    291 
    292 **Code(C++)**
    293 
    294 ```
    295 #include <bits/stdc++.h>
    296 
    297 using namespace std;
    298 typedef long long ll;
    299 void tc(){
    300     ll a,b,d,k=0,inverse_of_2,total_inverse=1;
    301     cin>>a>>b>>d;
    302     a|=b;
    303     if(a%d==0){
    304         cout<<a<<'\n';
    305         return;
    306     }
    307     while(a%2==0 && d%2==0)
    308         a/=2,d/=2,k++;
    309     inverse_of_2=(d+1)/2;
    310     if(a%2==1 && d%2==0){
    311         cout<<"-1\n";
    312         return;
    313     }
    314 
    315     for(ll i=0;i<30-k;i++)
    316         total_inverse=total_inverse*inverse_of_2%d;
    317 
    318     cout<<((total_inverse<<(30-k))-1)*(1ll<<k)<<'\n';
    319 }
    320 int main()
    321 {
    322     ios_base::sync_with_stdio(false), cin.tie(0);
    323     ll t; cin>>t; while(t--)
    324         tc();
    325 }
    326 ```
    327 
    328 **Rate problem**
    329 
    330 Good problem
    331 
    332 Ok problem
    333 
    334 Bad problem
    335 
    336 Didn't solve it, idk
    337 
    338 ## [E — Yet Another Array Counting Problem](https://codeforces.com/contest/1748/problem/E)
    339 
    340 Author: [Gheal](/profile/Gheal "Master Gheal")
    341 
    342 **Hints**
    343 
    344 **Hint 1**
    345 
    346 Let $m$ be the position of the leftmost maximum on the segment $[1;n]$.
    347 
    348 1. If $l \le m \le r$, then the position of the leftmost maximum on the segment $[l;r]$ is equal to $m$.
    349 2. If $l \le r \lt m $, then the leftmost maximum on the segment $[l;r]$ is some element $a_p$, $p \lt m$.
    350 3. If $m \lt l \le r$, then the leftmost maximum on the segment $[l;r]$ is some element $a_{p_2}$, $p_2 \gt m$.
    351 
    352 **Hint 2**
    353 
    354 Let $m$ be the position of the leftmost maximum on the segment $[l;r]$.
    355 
    356 If $p$ is the position of the leftmost maximum on the segment $[l;m-1]$ and $p_2$ is the position of the leftmost maximum on the segment $[m+1;r]$, then $b_m \gt b_{p}$ and $b_m \ge b_{p_2}$.
    357 
    358 **Hint 3**
    359 
    360 Using the idea from the previous hint, we can recursively build a binary tree where the children of node $m$ are nodes $p$ and $p_2$.
    361 
    362 **Hint 4**
    363 
    364 Can this problem be boiled down to a tree dp? (Note that $n \cdot m \le 10^6$)
    365 
    366 **Solution**
    367 
    368 Let $f(i,j)$ be the position of the leftmost maximum in the interval $(i;j)$, $1 \le i \le j \le n$.
    369 
    370 Let's consider an interval $(l;r)$ such that $f(l,r)=m$. For the sake of simplicity, let's assume that $l \lt m \lt r$.
    371 
    372 Let $p=f(l,m-1)$ and $p_2=f(m+1,r)$. Since $a_m$ is the leftmost maximum in $(l;r)$, $p \lt m$ and $p_2 \gt m$, the following conditions must hold for array $b$:
    373 
    374 * $b_m \gt b_p$
    375 * $b_m \ge b_{p_2}$
    376 
    377 Let's consider a binary tree where the children of node $u=f(l,r)$ are nodes $p=f(l,u-1)$ and $p_2=f(u+1,r)$, for every $1 \le u \le n$.
    378 
    379 Note that if $u=l$, $f(l,l-1)$ is not defined, and, as such, node $u$ will have no left child. Similarly, if $u=r$, then node $u$ will have no right child.
    380 
    381 Let $dp[u][x]$ be equal to the number of ways to assign values to every element $b_v$ from the subtree rooted in $u$, if $b_u=x$.
    382 
    383 * If $u$ has a left child and $x=1$, then $dp[u][x]=0$;
    384 * Otherwise, if $u$ has two children, then $dp[u][x]=(\sum_{i=1}^{x-1}dp[p][i]) \cdot(\sum_{i=1}^{x}dp[p_2][i])$;
    385 * If $u$ only has a left child, then $dp[u][x]=\sum_{i=1}^{x-1}dp[p][i]$;
    386 * If $u$ only has a right child, then $dp[u][x]=\sum_{i=1}^{x}dp[p_2][i]$;
    387 * If $u$ has no children, then $dp[u][x]=1$.
    388 
    389 To optimise the transitions, we'll also need to compute $sum[u][x]=\sum_{i=1}^{x} dp[u][x]$ alongside our normal $dp$.
    390 
    391 Intended time complexity per testcase: $O(n \cdot m+n \cdot log(n))$
    392 
    393 **Additional implementation details**
    394 
    395 In order to construct the binary tree, we can use a recursive divide and conquer function $divide(l,r)$ to split our current interval $(l;r)$ into two new intervals $(l;m-1)$ and $(m+1;r)$.
    396 
    397 Additionally, we can also compute the values of $dp[m][x]$ and $sum[m][x]$ inside $divide(l,r)$ after calling $divide(l,m-1)$ and divide $(m+1,r)$.
    398 
    399 Range leftmost maximumum queries can be answered in $O(1)$ using a sparse table, see the model solution for more information.
    400 
    401 **Code(C++)**
    402 
    403 ```
    404 #include<bits/stdc++.h>
    405 
    406 using namespace std;
    407 
    408 typedef long long ll;
    409 const ll NMAX=2e5+5,LGMAX=18,MOD=1e9+7;
    410 int n,m;
    411 
    412 int leftmost_maximum[LGMAX][NMAX],msb[NMAX];
    413 int v[NMAX];
    414 
    415 vector<vector<ll>> dp,sum;
    416 
    417 int leftmost_maximum_query(int l, int r){
    418     int bit=msb[r-l+1];
    419     if(v[leftmost_maximum[bit][l]]>=v[leftmost_maximum[bit][r-(1<<bit)+1]]) return leftmost_maximum[bit][l];
    420     else return leftmost_maximum[bit][r-(1<<bit)+1];
    421 }
    422 int divide(int l, int r){
    423 
    424     if(l>r) return -1;
    425 
    426     int mid=leftmost_maximum_query(l,r);
    427 
    428     int p=divide(l,mid-1),p2=divide(mid+1,r);
    429 
    430     for(int i=1;i<=m;i++){
    431         if(p!=-1 && i==1) dp[mid][1]=0;
    432         else dp[mid][i]=(p>=0?sum[p][i-1]:1ll)*(p2>=0?sum[p2][i]:1ll)%MOD;
    433 
    434         sum[mid][i]=(sum[mid][i-1]+dp[mid][i])%MOD;
    435     }
    436     return mid;
    437 }
    438 void tc(){
    439 
    440     cin>>n>>m;
    441     dp.resize(n),sum.resize(n);
    442     for(int i=0;i<n;i++){
    443         cin>>v[i];
    444 
    445         leftmost_maximum[0][i]=i;
    446 
    447         dp[i].resize(m+1),sum[i].resize(m+1);
    448         for(int j=0;j<=m;j++) dp[i][j]=sum[i][j]=0;
    449     }
    450 
    451     for(int bit=1;bit<LGMAX;bit++){
    452         for(int i=0;i+(1<<bit)<=n;i++){
    453             if(v[leftmost_maximum[bit-1][i]]>=v[leftmost_maximum[bit-1][i+(1<<(bit-1))]])
    454                 leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i];
    455             else
    456                 leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i+(1<<(bit-1))];
    457         }
    458     }
    459 
    460     divide(0,n-1);
    461 
    462     cout<<sum[leftmost_maximum_query(0,n-1)][m]<<'\n';
    463 }
    464 int main()
    465 {
    466     for(int i=2;i<NMAX;i++)
    467         msb[i]=msb[i-1]+((i&(i-1))==0); /// msb = floor(log2)
    468 
    469     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    470     int t; cin>>t; while(t--)
    471         tc();
    472 
    473     return 0;
    474 }
    475 ```
    476 
    477 **Rate problem**
    478 
    479 Good problem
    480 
    481 Ok problem
    482 
    483 Bad problem
    484 
    485 Didn't solve it, idk
    486 
    487 ## [F — Circular Xor Reversal](https://codeforces.com/contest/1748/problem/F)
    488 
    489 Idea: [Gheal](/profile/Gheal "Master Gheal"), Solution: [IgorI](/profile/IgorI "Grandmaster IgorI")
    490 
    491 **Hints**
    492 
    493 **Hint 1**
    494 
    495 How can we perform $a_i=a_i \oplus a_j$ for any $0 \le i,j \lt n$, $i \neq j$?
    496 
    497 **Hint 2**
    498 
    499 We can swap the values of $a_i$ and $a_j$ by performing the following sequence of xor assignments:
    500 
    501 * $a_i=a_i \oplus a_j$;
    502 * $a_j=a_j \oplus a_i$;
    503 * $a_i=a_i \oplus a_j$;
    504 
    505 **Hint 3**
    506 
    507 Performing $a_i=a_i \oplus a_j$ on its own is pretty wasteful, as it requires $4 \cdot \text{dist}(i,j) - c$ operations, where $dist(i,j)=(j+n-i) \mod n$, and $c$ is a constant.
    508 
    509 If $j=i+3$, can we perform $a_i=a_i \oplus a_j$ and $a_{i+1}=a_{i+1} \oplus a_{j-1}$ simultaneously?
    510 
    511 **Hint 4**
    512 
    513 Building on the idea presented in hint $3$, can we perform the following $\frac{n}{2}$ xor assignments simultaneously if $n$ is even?
    514 
    515 * $a_0 = a_0 \oplus a_{n-1}$;
    516 * $a_1 = a_1 \oplus a_{n-2}$;
    517 * $a_2 = a_2 \oplus a_{n-3}$;
    518 * $\ldots$
    519 * $a_{\frac{n}{2}-1} = a_{\frac{n}{2}-1} \oplus a_{\frac{n}{2}}$
    520 
    521 The target number of operations for performing all $\frac{n}{2}$ assignments is $\frac{n^2}{2}$.
    522 
    523 **Hint 5**
    524 
    525 Using hints $2$ and $4$, we can already solve the problem if $n$ is even.
    526 
    527 If $m=dist(i,j) \gt 0$ and $b_k=a_{(i+k) \mod n}$, let $f(i,j)$ be a sequence of operations that performs:
    528 
    529 * $b_0 = b_0 \oplus b_{m}$;
    530 * $b_1 = b_1 \oplus b_{m-1}$;
    531 * $b_2 = b_2 \oplus b_{m-2}$;
    532 * $\ldots$
    533 * $b_{\lfloor\frac{m-2}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$
    534 
    535 We can reverse array $a$ by performing $f(0,n-1)$, $f(\frac{n}{2},\frac{n}{2}-1)$ and $f(0,n-1)$, in this order.
    536 
    537 Otherwise, if $n$ is odd, we can perform $f(0,n-1)$, $f(\frac{n+1}{2},\frac{n-3}{2})$ and $f(0,n-1)$, in this order.
    538 
    539 The total number of operations is $3\cdot \frac{n^2}{2} \le 3 \cdot \frac{400^2}{2} = 240\,000 \lt 250\,000$.
    540 
    541 **Solution**
    542 
    543 If $m=dist(i,j)=((j+n-i) \mod n)$, $m \gt 0$ and $b_k=a_{(i+k) \mod n}$, let $f(i,j)$ be a sequence of operations that performs:
    544 
    545 * $b_0 = b_0 \oplus b_{m-1}$;
    546 * $b_1 = b_1 \oplus b_{m-2}$;
    547 * $b_2 = b_2 \oplus b_{m-3}$;
    548 * $\ldots$
    549 * $b_{\lfloor\frac{m-1}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$
    550 
    551 If $n$ is even, we can reverse array $a$ by performing $f(0,n-1)$, $f(\frac{n}{2},\frac{n}{2}-1)$ and $f(0,n-1)$, in this order.
    552 
    553 Otherwise, if $n$ is odd, we can perform $f(0,n-1)$, $f(\frac{n+1}{2},\frac{n-3}{2})$ and $f(0,n-1)$, in this order.
    554 
    555 One possible way to construct $f(i,j)$ is as follows:
    556 
    557 * Perform an operation on every $i$ from $m-1$ to $0$:
    558 
    559 $\Rightarrow b=[(0..m),(1..m),(2..m)\ldots,(i..m),\ldots,b_{m}]$
    560 
    561 * Perform an operation on every $i$ from $1$ to $m-1$:
    562 
    563 $\Rightarrow b=[(0..m),b_1,b_2,\ldots,b_i,\ldots,b_{m}]$
    564 
    565 * Perform an operation on every $i$ from $m-2$ to $1$:
    566 
    567 $\Rightarrow b=[(0..m),(1..m-1),(2..m-1),\ldots,(i..m-1),\ldots,b_{m-1},b_{m}]$
    568 
    569 * Perform an operation on every $i$ from $2$ to $m-2$:
    570 
    571 $\Rightarrow b=[(0..m),(1..m-1),b_2,b_3,\ldots,b_i,\ldots,b_{m-1},b_{m}]$
    572 
    573 * $\ldots$
    574 
    575 $\Rightarrow b=[(0..m),(1..m-1),(2..m-2),\ldots, (i..m-i),(\lfloor\frac{m-1}{2}\rfloor..\lfloor\frac{m+2}{2}\rfloor),b_{\lfloor\frac{m+1}{2}\rfloor},\ldots,b_j,b_{m-1}]$
    576 
    577 * The last step is to perform an operation on every $i$ from $0$ to $\lfloor\frac{m-2}{2}\rfloor$:
    578 
    579 $\Rightarrow b=[a_0 \oplus a_{m},a_1 \oplus a_{m-1},\ldots,a_i \oplus a_{m-i},\ldots,b_{\lfloor\frac{m-1}{2}\rfloor} \oplus b_{\lfloor\frac{m+2}{2}\rfloor},b_{\lfloor\frac{m+1}{2}\rfloor},\ldots,b_j,\ldots,b_{m}]$
    580 
    581 Here, $(l..r)$ denotes $b_l \oplus b_{l+1} \oplus \ldots \oplus b_r$.
    582 
    583 The number of operations needed for $f(i,j)$ is equal to $m+(m-1)+\ldots+1+(\frac{m}{2})=\frac{m\cdot(m+1)}{2}+\frac{m}{2}=\frac{m^2+2\cdot m}{2}$, therefore the total number of operations needed to reverse the array is $\frac{3}{2} \cdot (m^2+2\cdot m)$. Since $m \le n-1$, $\frac{3}{2} \cdot (m^2+2\cdot m) \le \frac{3}{2} \cdot (399^2 + 2\cdot 399) \lt 250\,000$.
    584 
    585 Time complexity per testcase: $O(N^2)$
    586 
    587 **Code(C++)**
    588 
    589 ```
    590 #include <bits/stdc++.h>
    591 
    592 using namespace std;
    593 
    594 vector<int> ans;
    595 int n;
    596 void add_op(int pos){
    597     ans.push_back(pos%n);
    598 }
    599 void f(int l, int r){
    600 
    601     if(r<l) r+=n;
    602 
    603     int m=r-l,direction=0,start=l;
    604     r--;
    605     while(l<=r){
    606 
    607         if(direction==0){
    608             for(int i=r;i>=l;i--)
    609                 add_op(i);
    610             l++;
    611         }
    612         else{
    613             for(int i=l;i<=r;i++)
    614                 add_op(i);
    615             r--;
    616         }
    617 
    618         direction=1-direction;
    619     }
    620     for(int i=start;i<start+m/2;i++)
    621         add_op(i);
    622 }
    623 int main()
    624 {
    625     ios_base::sync_with_stdio(false), cin.tie(0);
    626     cin>>n;
    627 
    628     f(0,n-1);
    629 
    630     f((n+1)/2,(n-2)/2);
    631 
    632     f(0,n-1);
    633 
    634     cout<<ans.size()<<'\n';
    635 
    636     for(auto it : ans) cout<<it<<' ';
    637 }
    638 ```
    639 
    640 **Rate problem**
    641 
    642 Good problem
    643 
    644 Ok problem
    645 
    646 Bad problem
    647 
    648 Didn't solve it, idk
    649 
    650 If there is anything wrong or unclear in this editorial, feel free to ping me in the comments.