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.