1672.md (52076B)
1 Source: https://codeforces.com/blog/entry/102172 2 3 Hope that everyone enjoyed the round. Feel free to ask questions in the comments if you do not understand any part of the editorial 4 5 [1672A - Log Chopping](/contest/1672/problem/A "Codeforces Global Round 20") 6 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 7 8 **Hints** 9 10 **Hint 1** 11 12 No matter what move each player does, the result of the game will **always** be the same. 13 14 **Hint 2** 15 16 Count the number of moves. 17 18 **Tutorial** 19 20 Let us consider the ending state of the game. It turns out that at the ending state, we will only have logs of $1$ meter. Otherwise, players can make a move. 21 22 Now, at the ending state of the game, we will have $\sum\limits_{k=1}^n a_k$ logs. And each move we increase the number of logs by exactly $1$. Since we started with $n$ logs, there has been exactly $(\sum\limits_{k=1}^n a_k) - n$ turns. 23 24 Alternatively, a log of length $a_k$ will be cut $a_k-1$ times, so there will be $\sum\limits_{k=1}^n (a_k-1)$ turns. 25 26 If there were an odd number of turns $\texttt{errorgorn}$ wins, otherwise $\texttt{maomao90}$ wins. 27 28 **Solution** 29 30 ``` 31 // Super Idol的笑容 32 // 都没你的甜 33 // 八月正午的阳光 34 // 都没你耀眼 35 // 热爱105°C的你 36 // 滴滴清纯的蒸馏水 37 38 #include <bits/stdc++.h> 39 #include <ext/pb_ds/assoc_container.hpp> 40 #include <ext/pb_ds/tree_policy.hpp> 41 #include <ext/rope> 42 using namespace std; 43 using namespace __gnu_pbds; 44 using namespace __gnu_cxx; 45 46 #define int long long 47 #define ll long long 48 #define ii pair<ll,ll> 49 #define iii pair<ii,ll> 50 #define fi first 51 #define se second 52 #define endl '\n' 53 #define debug(x) cout << #x << ": " << x << endl 54 55 #define pub push_back 56 #define pob pop_back 57 #define puf push_front 58 #define pof pop_front 59 #define lb lower_bound 60 #define ub upper_bound 61 62 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 63 #define all(x) (x).begin(),(x).end() 64 #define sz(x) (int)(x).size() 65 66 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 67 //change less to less_equal for non distinct pbds, but erase will bug 68 69 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 70 71 int n; 72 int arr[105]; 73 74 signed main(){ 75 ios::sync_with_stdio(0); 76 cin.tie(0); 77 cout.tie(0); 78 cin.exceptions(ios::badbit | ios::failbit); 79 80 int TC; 81 cin>>TC; 82 while (TC--){ 83 cin>>n; 84 rep(x,0,n) cin>>arr[x]; 85 86 int tot=0; 87 rep(x,0,n) tot+=arr[x]-1; 88 89 if (tot%2==0) cout<<"maomao90"<<endl; 90 else cout<<"errorgorn"<<endl; 91 } 92 } 93 ``` 94 95 [1672B - I love AAAB](/contest/1672/problem/B "Codeforces Global Round 20") 96 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 97 98 **Hints** 99 100 **Hint 1** 101 102 Pretend that we can only insert $\texttt{AB}$. 103 104 **Hint 2** 105 106 What if we replaced $\texttt{A}$ and $\texttt{B}$ with $\texttt{(}$ and $\texttt{)}$? 107 108 **Tutorial** 109 110 Claim: The string is obtainable if it ends in $\texttt{B}$ and every prefix of the string has at least as many $\texttt{A}$ as $\texttt{B}$. 111 112 An alternative way to think about the second condition is to assign $\texttt{A}$ to have a value of $1$ and $\texttt{B}$ to have a value of $-1$. Then, we are just saying that each prefix must have a non-negative sum. This is pretty similar to bracket sequences. 113 114 Now, both conditions are clearly necessary, let us show that they are sufficient too. 115 116 We will explicitly construct the string (in the reverse direction). While there are more than $1$ occurrences of $\texttt{B}$ in the string, remove the first occurrence of $\texttt{AB}$. After doing this process, you will eventually end up with the string $\texttt{AAA...AAB}$. 117 118 **Solution** 119 120 ``` 121 // Super Idol的笑容 122 // 都没你的甜 123 // 八月正午的阳光 124 // 都没你耀眼 125 // 热爱105°C的你 126 // 滴滴清纯的蒸馏水 127 128 #include <bits/stdc++.h> 129 #include <ext/pb_ds/assoc_container.hpp> 130 #include <ext/pb_ds/tree_policy.hpp> 131 #include <ext/rope> 132 using namespace std; 133 using namespace __gnu_pbds; 134 using namespace __gnu_cxx; 135 136 #define int long long 137 #define ll long long 138 #define ii pair<ll,ll> 139 #define iii pair<ii,ll> 140 #define fi first 141 #define se second 142 #define endl '\n' 143 #define debug(x) cout << #x << ": " << x << endl 144 145 #define pub push_back 146 #define pob pop_back 147 #define puf push_front 148 #define pof pop_front 149 #define lb lower_bound 150 #define ub upper_bound 151 152 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 153 #define all(x) (x).begin(),(x).end() 154 #define sz(x) (int)(x).size() 155 156 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 157 //change less to less_equal for non distinct pbds, but erase will bug 158 159 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 160 161 signed main(){ 162 ios::sync_with_stdio(0); 163 cin.tie(0); 164 cout.tie(0); 165 cin.exceptions(ios::badbit | ios::failbit); 166 167 int TC; 168 cin>>TC; 169 while (TC--){ 170 string s; 171 cin>>s; 172 173 bool ok=(s.back()=='B'); 174 175 int sum=0; 176 for (auto it:s){ 177 if (it=='A') sum++; 178 else sum--; 179 if (sum<0) ok=false; 180 } 181 182 if (ok) cout<<"YES"<<endl; 183 else cout<<"NO"<<endl; 184 } 185 } 186 ``` 187 188 [1672C - Unequal Array](/contest/1672/problem/C "Codeforces Global Round 20") 189 Author: [maomao90](/profile/maomao90 "Master maomao90") 190 191 **Hints** 192 193 **Hint 1** 194 195 If the array is $a=[1,1,\ldots,1]$. We will need $0$ moves if $n \leq 2$ and will need $\max(n-3,1)$ moves. 196 197 **Hint 2** 198 199 The only way to reduce the number of $i$ such that $a_i = a_{i+1}$ is when $a_i = a_{i+1}$ and $a_{i+2} = a_{i+3}$, and you apply the operation on $a_{i+1}$ and $a_{i+2}$. 200 201 **Tutorial** 202 203 Suppose $l$ is the smallest index where $a_l = a_{l+1}$ and r is the largest index where $a_r = a_{r+1}$. If $l=r$ or $l$ and $r$ does not exist, the condition is already satisfied and we can do 0 operations. Otherwise, the answer is $\max(1, r - l - 1)$. The proof is as follows: 204 205 1. Suppose $l+1=r$, then, there are 3 elements that are adjacent to each other. Hence, we can just do one operation with $i=l$ and $x=\infty$ to make the equality of the array 1. 206 2. Suppose otherwise, then the array will look something like $[..., X, X, ..., Y, Y, ...]$, with $r - l - 2$ elements between the second $X$ and the first $Y$. Then, we can do operations on $i={l+1, l+2, \ldots, r-2, r-1}$ to make the equality of the array 1. 207 208 To see why we need at least $r - l - 1$ operations, observe that each operation will cause $r - l$ to decrease by at most 1. This is because if we do not do an operation on $i \in \{l-1,l+1,r-1,r+1\}$, then both $a_l = a_{l+1}$ and $a_r = a_{r+1}$ will still hold. We see that $r-l$ only decreases when do we an operation on $i \in {l+1,r-1}$ and it is not too hard to show that it only decreases by $1$ in those cases while $r-l \gt 2$ 209 210 Hence, we keep doing the operation until $r - l = 2$, which will only require 1 operation to change both pairs and make the equality 1. 211 212 **Solution** 213 214 ``` 215 #include <bits/stdc++.h> 216 using namespace std; 217 218 template <class T> 219 inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} 220 template <class T> 221 inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} 222 #define REP(i, s, e) for (int i = s; i < e; i++) 223 #define RREP(i, s, e) for (int i = s; i >= e; i--) 224 typedef long long ll; 225 typedef long double ld; 226 #define MP make_pair 227 #define FI first 228 #define SE second 229 typedef pair<int, int> ii; 230 typedef pair<ll, ll> pll; 231 #define MT make_tuple 232 typedef tuple<int, int, int> iii; 233 #define ALL(_a) _a.begin(), _a.end() 234 #define pb push_back 235 typedef vector<int> vi; 236 typedef vector<ll> vll; 237 typedef vector<ii> vii; 238 239 #ifndef DEBUG 240 #define cerr if (0) cerr 241 #endif 242 243 #define INF 1000000005 244 #define LINF 1000000000000000005ll 245 #define MAXN 200005 246 247 int t; 248 int n; 249 int a[MAXN]; 250 251 int main() { 252 #ifndef DEBUG 253 ios::sync_with_stdio(0), cin.tie(0); 254 #endif 255 cin >> t; 256 while (t--) { 257 cin >> n; 258 REP (i, 0, n) { 259 cin >> a[i]; 260 } 261 int mn = -1, mx = -1; 262 REP (i, 1, n) { 263 if (a[i] == a[i - 1]) { 264 if (mn == -1) { 265 mn = i; 266 } 267 mx = i; 268 } 269 } 270 if (mn == mx) { 271 cout << 0 << '\n'; 272 } else { 273 cout << max(1, mx - mn - 1) << '\n'; 274 } 275 } 276 return 0; 277 } 278 ``` 279 280 [1672D - Cyclic Rotation](/contest/1672/problem/D "Codeforces Global Round 20") 281 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 282 283 **Hints** 284 285 **Hint 1** 286 287 The operation of cyclic shift is equivalent to deleting $a_i$ and duplicating $a_j$ where $a_i = a_j$. 288 289 **Hint 2** 290 291 Reverse the process. 292 293 **Tutorial 1** 294 295 We will solve the problem by reversing the steps and transform array $b$ to array $a$. 296 297 We can do the following operation on $b$: 298 299 * pick index $i \lt j$ such that $b_j=b_{j+1}$ and remove $b_{j+1}$ and insert it after position $i$. 300 301 Now, for every consecutive block of identical elements in $b$, we can remove all but one element from it and move it left. 302 303 If we process from right to left, we can imagine as taking consecutive elemnets in $b$ out and placing in a reserve, and using them to match some elements in $a$ towards the left. 304 305 Using this idea, we can use the following greedy two-pointer algorithm: 306 307 Let $i$ and $j$ represent the size of $a$ and $b$ respectively (and hence $a_i$ and $b_j$ will refer to the last elements of $a$ and $b$ respectively). We also have an initially empty multiset $S$, which represents the reserve. We will perform the following operations in this order: 308 309 1. While $b_{j-1}=b_j$, add $b_j$ to the multiset $S$ and decrement $j$ 310 2. If $a_i = b_j$, then decrement both $i$ and $j$ 311 3. Otherwise, we delete an occurance of $a_i$ in $S$ and decrement $i$. If we cannot find $a_i$ in $S$, it is impossible to transform $b$ to $a$. 312 313 **Tutorial 2** 314 315 Let us define an array $c$ where all elements of $c$ is $1$. We can rephrase the problem in the following way: 316 317 * Choose $i \lt j$ such that $a_i = a_j$ and $c_i \gt 0$. Then update $c_i \gets c_i-1$ and $c_j \gets c_j+1$. 318 319 The final array $b$ is obtained by the following: Let $b$ be initially empty, then iterate $i$ from $1$ to $n$ and add $c_i$ copies of $a_i$ to $b$. 320 321 As such, we can consider mapping elements of $b$ into elements of $a$. More specifically, consider a mapping $f$ where $f$ is non-decreasing, $b_i=a_{f_i}$ and we increment $c_{f_i}$ by $1$ for all $i$. All that remains is to determine if we can make such a mapping such that $c$ is valid. 322 323 Notice that if all elements of $a$ are identical, the necessary and sufficient condition for a valid array $c$ is that $c_1+c_2+\ldots+c_i \leq i$ for all $i$. 324 325 This motivates us to construct an array $pa$ where $pa_i$ is the number of indices $j \leq i$ such that $a_i=a_j$. Analogously, construct $pb$. 326 327 Then the necessary and sufficient conditions for a mapping $f$ is that $f$ is non-decreasing, $b_i=a_{f_i}$ and $pb_i \leq pa_{f_i}$. A greedy algorithm to construct $f$, if it exists, is trivial by minimizing $f_i$ for each $i$. 328 329 **Solution 1** 330 331 ``` 332 #include <bits/stdc++.h> 333 using namespace std; 334 335 template <class T> 336 inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} 337 template <class T> 338 inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} 339 #define REP(i, s, e) for (int i = s; i < e; i++) 340 #define RREP(i, s, e) for (int i = s; i >= e; i--) 341 typedef long long ll; 342 typedef long double ld; 343 #define MP make_pair 344 #define FI first 345 #define SE second 346 typedef pair<int, int> ii; 347 typedef pair<ll, ll> pll; 348 #define MT make_tuple 349 typedef tuple<int, int, int> iii; 350 #define ALL(_a) _a.begin(), _a.end() 351 #define pb push_back 352 typedef vector<int> vi; 353 typedef vector<ll> vll; 354 typedef vector<ii> vii; 355 356 #ifndef DEBUG 357 #define cerr if (0) cerr 358 #endif 359 360 #define INF 1000000005 361 #define LINF 1000000000000000005ll 362 #define MAXN 200005 363 364 int t; 365 int n; 366 int a[MAXN], b[MAXN]; 367 int cnt[MAXN]; 368 369 int main() { 370 #ifndef DEBUG 371 ios::sync_with_stdio(0), cin.tie(0); 372 #endif 373 cin >> t; 374 while (t--) { 375 cin >> n; 376 REP (i, 1, n + 1) { 377 cnt[i] = 0; 378 } 379 REP (i, 0, n) { 380 cin >> a[i]; 381 } 382 REP (i, 0, n) { 383 cin >> b[i]; 384 } 385 int i = 0, j = 0; 386 bool pos = 1; 387 while (j < n) { 388 if (i < n && j < n && a[i] == b[j]) { 389 i++; j++; 390 continue; 391 } 392 if (cnt[b[j]] > 0 && b[j] == b[j - 1]) { 393 cnt[b[j++]]--; 394 } else if (i < n) { 395 cnt[a[i++]]++; 396 } else { 397 pos = 0; 398 break; 399 } 400 } 401 if (pos) { 402 assert(i == n); 403 REP (i, 1, n + 1) { 404 assert(cnt[i] == 0); 405 } 406 cout << "YES\n"; 407 } else { 408 cout << "NO\n"; 409 } 410 } 411 return 0; 412 } 413 ``` 414 415 **Solution 2** 416 417 ``` 418 // Super Idol的笑容 419 // 都没你的甜 420 // 八月正午的阳光 421 // 都没你耀眼 422 // 热爱105°C的你 423 // 滴滴清纯的蒸馏水 424 425 #include <bits/stdc++.h> 426 #include <ext/pb_ds/assoc_container.hpp> 427 #include <ext/pb_ds/tree_policy.hpp> 428 #include <ext/rope> 429 using namespace std; 430 using namespace __gnu_pbds; 431 using namespace __gnu_cxx; 432 433 #define int long long 434 #define ll long long 435 #define ii pair<ll,ll> 436 #define iii pair<ii,ll> 437 #define fi first 438 #define se second 439 #define endl '\n' 440 #define debug(x) cout << #x << ": " << x << endl 441 442 #define pub push_back 443 #define pob pop_back 444 #define puf push_front 445 #define pof pop_front 446 #define lb lower_bound 447 #define ub upper_bound 448 449 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 450 #define all(x) (x).begin(),(x).end() 451 #define sz(x) (int)(x).size() 452 453 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 454 //change less to less_equal for non distinct pbds, but erase will bug 455 456 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 457 458 int n; 459 int arr[200005]; 460 int brr[200005]; 461 int crr[200005]; 462 int num[200005]; 463 464 signed main(){ 465 ios::sync_with_stdio(0); 466 cin.tie(0); 467 cout.tie(0); 468 cin.exceptions(ios::badbit | ios::failbit); 469 470 int TC; 471 cin>>TC; 472 while (TC--){ 473 cin>>n; 474 rep(x,1,n+1) cin>>arr[x]; 475 rep(x,1,n+1) cin>>brr[x]; 476 477 rep(x,1,n+1) num[x]=0; 478 rep(x,1,n+1){ 479 num[arr[x]]++; 480 crr[x]=num[arr[x]]; 481 } 482 483 rep(x,1,n+1) num[x]=0; 484 int idx=1; 485 rep(x,1,n+1){ 486 num[brr[x]]++; 487 while (idx<=n && (arr[idx]!=brr[x] || crr[idx]<num[brr[x]])) idx++; 488 } 489 490 if (idx>n) cout<<"NO"<<endl; 491 else cout<<"YES"<<endl; 492 } 493 } 494 ``` 495 496 [1672E - notepad.exe](/contest/1672/problem/E "Codeforces Global Round 20") 497 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn"), [oolimry](/profile/oolimry "Master oolimry") 498 499 **Hints** 500 501 **Hint 1** 502 503 Find the sum of lengths of words. 504 505 **Hint 2** 506 507 Given a height, how many "good" widths are there. 508 509 **Tutorial** 510 511 The first idea that we have is that we want to be able to find the minimum possible width of the text editor for a specific height. We can do this in $n\log (n \cdot 2000)$ queries using binary search for each height. This is clearly not good enough, so let us come up with more observations. 512 513 First, we can binary search for the minimum possible width for height $1$. This value is $(\sum_{i=1}^n l_i)+n-1$ which we will denote with $S$. 514 515 Let us consider what we might want to query for height $h$. Suppose that the words are arranged very nicely such that there are no trailing spaces in each line. Then, the total number of characters will be $S - h +1$. This means that the minimum possible area for height $h$ will be $S-h+1$. We also know that if the area is more than $S$, it will not be useful as the area for $h=1$ is already $S$. 516 517 Now, we know that the range of possible areas that we are interested in is $[S - h +1, S]$. There is a total of $h$ possible areas that it can take, and an area is only possible if $h \cdot w = a$, or in other words, the area is divisible by $h$. Among the $h$ consecutive possible values, exactly one of them will be divisible by $h$, hence we can just query that one value of $w$ which can very nicely be found as $\lfloor \frac{S}{h} \rfloor$. 518 519 The total number of queries used is $n + \log(n \cdot 2000)$ where $n$ comes from the single query for each height and the $\log(n \cdot 2000)$ comes from the binary search at the start. 520 521 **Solution** 522 523 ``` 524 // Super Idol的笑容 525 // 都没你的甜 526 // 八月正午的阳光 527 // 都没你耀眼 528 // 热爱105°C的你 529 // 滴滴清纯的蒸馏水 530 531 #include <bits/stdc++.h> 532 #include <ext/pb_ds/assoc_container.hpp> 533 #include <ext/pb_ds/tree_policy.hpp> 534 #include <ext/rope> 535 using namespace std; 536 using namespace __gnu_pbds; 537 using namespace __gnu_cxx; 538 539 #define int long long 540 #define ll long long 541 #define ii pair<ll,ll> 542 #define iii pair<ii,ll> 543 #define fi first 544 #define se second 545 #define debug(x) cout << #x << ": " << x << endl 546 547 #define pub push_back 548 #define pob pop_back 549 #define puf push_front 550 #define pof pop_front 551 #define lb lower_bound 552 #define ub upper_bound 553 554 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 555 #define all(x) (x).begin(),(x).end() 556 #define sz(x) (int)(x).size() 557 558 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 559 //change less to less_equal for non distinct pbds, but erase will bug 560 561 int n; 562 563 int ask(int i){ 564 if (i==0) return 0; 565 cout<<"? "<<i<<endl; 566 int temp; 567 cin>>temp; 568 569 if (temp==-1){ 570 exit(0); 571 } 572 573 return temp; 574 } 575 576 signed main(){ 577 ios::sync_with_stdio(0); 578 cin.tie(0); 579 cout.tie(0); 580 cin.exceptions(ios::badbit | ios::failbit); 581 582 cin>>n; 583 584 int lo=-2,hi=5e6,mi; 585 while (hi-lo>1){ 586 mi=hi+lo>>1; 587 588 if (ask(mi)==1) hi=mi; 589 else lo=mi; 590 } 591 592 int ans=1e9; 593 rep(x,1,n+1){ 594 int temp=ask(hi/x); 595 if (temp) ans=min(ans,temp*(hi/x)); 596 } 597 598 cout<<"! "<<ans<<endl; 599 } 600 ``` 601 602 [1672F1 - Array Shuffling](/contest/1672/problem/F1 "Codeforces Global Round 20") and [1672F2 - Checker for Array Shuffling](/contest/1672/problem/F2 "Codeforces Global Round 20") 603 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 604 605 **Hints** 606 607 **Hint 1** 608 609 The number of occurances of the most frequent element is important. 610 611 **Hint 2** 612 613 Let $X$ be the number of occurances of the most common element. The maximal sadness is $N-X$. 614 615 **Hint 3** 616 617 For every minimal sequence of swaps, we have duality of maximal number of cycles when considering the graph with edges $a_i \to b_i$. 618 619 **Tutorial** 620 621 Let $N$ be the length of $A$ and $B$. 622 623 We want to prove that an optimal swapping from $B \to A$ is equivalent to sorting via some cycles. Suppose our swap order is $\{(l_1,r_1),(l_2,r_2),\ldots,(l_K,r_K)\}$. Let's consider a graph $G$ with edges being the swaps. Suppose the number of connected components in $G$ is $CC$, then there is a way to perform the transformation $B \to A$ using $CC$ cycles since we can view the labels of each connected component of $G$ as a permutation of the original vertices. One cycle of length $X$ uses $X-1$ swaps, so we use $N-CC$ swaps in total. Since $CC \geq N-K$, we can always change the swap order to swapping cycles while not performing a bigger number of moves. Now we have changed the problem to maximizing the number of cycles we use. 624 625 Let $cnt_x$ be the number of occurrences of $x$ in $A$. WLOG $cnt_1 \geq cnt_2 \geq \ldots$. 626 627 Let $s_A(B)$ denote the **sadness** of $B$ when the original array is $A$. 628 629 Claim: $\max(s_A) \leq N-cnt_1$ 630 631 Proof: By pigeonhole principle, we know there exist a cycle with $2$ occurrences of the element $1$. 632 633 Consider a cycle that swaps $i_1 \to i_2 \to \ldots \to i_K \to i_1$ where $A_{i_1}=A_{i_z}=1$. Then we can increase the number of connected components while maintaining $B$ by splitting into $2$ cycles $i_1 \to i_2 \to \ldots \to i_{z-1} \to i_1$ and $i_z \to i_2 \to \ldots \to i_N \to i_z$. 634 635 Therefore, in an optimal solution, there should not be a cycle that passes through the same value twice. $\blacksquare$ 636 637 Therefore, we can assume that all occurrences of $1$ belong to different cycles. Therefore, $\#cyc \geq cnt_1$ swaps are used. The number of swaps used is $N-\#cyc \leq N-cnt_1$. 638 639 Therefore, $N-cnt_1$ is a upper bound of $s$. 640 641 Claim: $s_A(B) \lt N-cnt_1$ $\Leftrightarrow$ there exists a cycle $i_1 \to i_2 \to \ldots \to i_K \to i_1$ such that all $i_x \neq 1$. 642 643 Proof: $(\Rightarrow)$ There exists a cycle decomposition of the graph that uses at least $cnt_1+1$ cycles. Since a single element of $1$ can only go to a single cycle, there exists a cycle without $1$. 644 645 $(\Leftarrow)$ Let's remove this cycle to form an arrays $A'$ and $B'$. Then $s_{A'}(B') \leq N-K-cnt_1$. Now, we only needed $K-1$ swaps to remove the cycle, so it much be that $s_A(B) \leq (N-K-cnt_1)+(K-1)=N-cnt_1-1$. $\blacksquare$ 646 647 ### Constructing maximal $B$ 648 649 To construction a permutation such that $s(B)=N-cnt_1$, let's construct a graph $G_{cnt}$ based on the number of occurrences of each element in $A$. We draw $cnt_{i+1}$ edges from $(i) \to (i+1)$ and $cnt_{i}-cnt_{i+1}$ edges from $(i) \to (1)$. It is obviously impossible to find a cycle that does not contain $1$. Since all edges will be of the form $(i) \to (i+1)$. 650 651 Another way to construct this permutation is to assume that $A$ is sorted. Then we perform $cnt_1$ cyclic shifts on $A$ to obtain $B$. 652 653 ### Checking if $B$ is maximal 654 655 Given the graph representation, finding such a cycle $i_1 \to i_2 \to \ldots \to i_K \to i_1$ such that all $i_x \neq 1$ is easy. Let's remove $1$ from the graph then check if the graph is a DAG. 656 657 **Solution for F1** 658 659 ``` 660 // Super Idol的笑容 661 // 都没你的甜 662 // 八月正午的阳光 663 // 都没你耀眼 664 // 热爱105°C的你 665 // 滴滴清纯的蒸馏水 666 667 #include <bits/stdc++.h> 668 #include <ext/pb_ds/assoc_container.hpp> 669 #include <ext/pb_ds/tree_policy.hpp> 670 #include <ext/rope> 671 using namespace std; 672 using namespace __gnu_pbds; 673 using namespace __gnu_cxx; 674 675 #define int long long 676 #define ll long long 677 #define ii pair<ll,ll> 678 #define iii pair<ii,ll> 679 #define fi first 680 #define se second 681 #define endl '\n' 682 #define debug(x) cout << #x << ": " << x << endl 683 684 #define pub push_back 685 #define pob pop_back 686 #define puf push_front 687 #define pof pop_front 688 #define lb lower_bound 689 #define ub upper_bound 690 691 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 692 #define all(x) (x).begin(),(x).end() 693 #define sz(x) (int)(x).size() 694 695 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 696 //change less to less_equal for non distinct pbds, but erase will bug 697 698 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 699 700 int n; 701 int arr[200005]; 702 int brr[200005]; 703 int cnt[200005]; 704 vector<int> al[200005]; 705 706 signed main(){ 707 ios::sync_with_stdio(0); 708 cin.tie(0); 709 cout.tie(0); 710 cin.exceptions(ios::badbit | ios::failbit); 711 712 int TC; 713 cin>>TC; 714 while (TC--){ 715 cin>>n; 716 rep(x,0,n) cin>>arr[x]; 717 rep(x,1,n+1) al[x].clear(); 718 rep(x,1,n+1) cnt[x]=0; 719 720 rep(x,0,n) cnt[arr[x]]++; 721 722 int mx=0; 723 rep(x,1,n+1) mx=max(mx,cnt[x]); 724 725 rep(x,0,n) brr[x]=arr[x]; 726 sort(brr,brr+n); 727 728 rep(x,0,n) al[brr[x]].pub(brr[(x+mx)%n]); 729 730 rep(x,0,n){ 731 cout<<al[arr[x]].back()<<" \n"[x==n-1]; 732 al[arr[x]].pob(); 733 } 734 } 735 736 } 737 ``` 738 739 **Solution for F2** 740 741 ``` 742 // Super Idol的笑容 743 // 都没你的甜 744 // 八月正午的阳光 745 // 都没你耀眼 746 // 热爱105°C的你 747 // 滴滴清纯的蒸馏水 748 749 #include <bits/stdc++.h> 750 #include <ext/pb_ds/assoc_container.hpp> 751 #include <ext/pb_ds/tree_policy.hpp> 752 #include <ext/rope> 753 using namespace std; 754 using namespace __gnu_pbds; 755 using namespace __gnu_cxx; 756 757 #define int long long 758 #define ll long long 759 #define ii pair<ll,ll> 760 #define iii pair<ii,ll> 761 #define fi first 762 #define se second 763 #define endl '\n' 764 #define debug(x) cout << #x << ": " << x << endl 765 766 #define pub push_back 767 #define pob pop_back 768 #define puf push_front 769 #define pof pop_front 770 #define lb lower_bound 771 #define ub upper_bound 772 773 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 774 #define all(x) (x).begin(),(x).end() 775 #define sz(x) (int)(x).size() 776 777 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 778 //change less to less_equal for non distinct pbds, but erase will bug 779 780 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 781 782 int n; 783 int arr[200005]; 784 int brr[200005]; 785 786 vector<int> al[200005]; 787 bool onstk[200005]; 788 bool vis[200005]; 789 790 bool cyc; 791 void dfs(int i){ 792 onstk[i]=vis[i]=true; 793 794 for (auto it:al[i]){ 795 if (onstk[it]) cyc=true; 796 if (!vis[it]) dfs(it); 797 } 798 799 onstk[i]=false; 800 } 801 802 signed main(){ 803 ios::sync_with_stdio(0); 804 cin.tie(0); 805 cout.tie(0); 806 cin.exceptions(ios::badbit | ios::failbit); 807 808 int TC; 809 cin>>TC; 810 while (TC--){ 811 cin>>n; 812 813 rep(x,1,n+1) al[x].clear(); 814 rep(x,1,n+1) vis[x]=onstk[x]=false; 815 816 rep(x,1,n+1) cin>>arr[x]; 817 rep(x,1,n+1) cin>>brr[x]; 818 819 rep(x,1,n+1) al[arr[x]].pub(brr[x]); 820 821 int mx=1; 822 rep(x,1,n+1) if (sz(al[x])>sz(al[mx])) mx=x; 823 824 vis[mx]=true; 825 cyc=false; 826 rep(x,1,n+1) if (!vis[x]) dfs(x); 827 828 if (cyc) cout<<"WA"<<endl; 829 else cout<<"AC"<<endl; 830 } 831 } 832 ``` 833 834 [1672G - Cross Xor](/contest/1672/problem/G "Codeforces Global Round 20") 835 Author: [maomao90](/profile/maomao90 "Master maomao90"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 836 837 **Hints** 838 839 **Hint 1** 840 841 We need to consider $4$ cases based on the parity of $r$ and $c$. 842 843 **Hint 2** 844 845 Let $R_i$ and $C_j$ denote $\bigotimes\limits_{j=1}^c a_{i,j}$ and $\bigotimes\limits_{i=1}^r a_{i,j}$ respectively, or the xor-sum of the $i$-th row and the xor-sum of the $j$-th column respectively. For some cases, $R$ and $C$ will be constant sequences no matter what sequence of operations we perform. 846 847 **Hint 3** 848 849 The obvious necessary conditions for $R$ and $C$ are actually sufficient. 850 851 **Hint 4** 852 853 When at least one of $r$ or $c$ is even, counting the valid grids is easy. When both $r$ and $c$ is odd, consider drawing the bipartite graph where edges are cells with $\texttt{?}$. 854 855 **Tutorial** 856 857 ### Determining which Grids are Obtainable 858 859 Let $R_i$ and $C_j$ denote $\bigotimes\limits_{j=1}^c a_{i,j}$ and $\bigotimes\limits_{i=1}^r a_{i,j}$ respectively, or the xor-sum of the $i$-th row and the xor-sum of the $j$-th column respectively. 860 861 We will split the problem into 3 cases. 862 863 #### Case 1: $r$ is even and $c$ is even 864 865 Choose some $(x,y)$ and do an operation on all $(i,j)$ where $i=x$ or $j=y$. The effect of this series of operations is toggling $(x,y)$. 866 867 All possible grids are reachable. Counting them is easy. 868 869 #### Case 2: $r$ is even and $c$ is odd 870 871 If $r$ is odd and $c$ is even, we can treat it as the same case by swapping a few variables. 872 873 Notice that every operation toggles all elements in $R$. It is neccasary that $R$ all values in R are the same, let us prove that this is sufficient as well. 874 875 Now suppose $R$ is all 0. If $R$ is all $1$. We can perform the operation on $(1,1)$ and now $R$ is all $0$. 876 877 If we pick $1 \leq x \leq r$ and $1 \leq y \lt c$ and perform operations on all $(i,j)$ where $i \neq x$ and $j=y$ or $j=c$, then it is equivalent to toggling $(x,y)$ and $(x,c)$. 878 879 We can perform the following new operation: 880 881 * pick $1 \leq x \leq r$ and $1 \leq y \lt c$ 882 * toggle $(x,y)$,$(x,c)$ 883 884 Since $R$ is all 0, each row has an even number of $1$. If we apply the new operation on all $(x,y)$ where $a_{x,y} = 1$ and $y \lt c$, then $(x,c)$ will be $0$ in the end. Hence, the whole grid will be $0$. 885 886 #### Case 3: $r$ is odd and $c$ is odd 887 888 Notice that every operation toggles all elements in $R$ and $C$. It is neccasary that both $R$ are $C$ all having the same values, let us prove that this is sufficient as well. 889 890 Suppose $R$ is all $0$ and $C$ is all $0$. If $R$ and $C$ are all $1$, we apply the operation on $(1,1)$ to make $R$ and $C$ both all $0$ 891 892 Notice that if we pick $1 \leq x_1 \lt x_2 \leq r$ and $1 \leq y_1 \lt y_2 \leq c$. Let $S=\{(x_1,y_1), (x_1,y_2), (x_2,y_1),(x_2,y_2)\}$. When we perform operations on all cells in $S$, it is equivalent to toggling all cells in $S$. 893 894 We can perform the following new operation: 895 896 * pick $1 \leq x \lt r$ and $1 \leq y \lt c$ 897 * toggle $(x,y)$,$(x,c)$,$(r,y)$,$(r,c)$ 898 899 Since $R$ and $C$ is all 0, each row and column has an even number of 1. If we apply the new operation on all $(x,y)$ where $a_{x,y} = 1$ and $x \lt r$ and $y \lt c$ , then $(x,c)$ will be $0$ for $0 \lt x \lt r$ and $(r,y)$ will be $0$ for $0 \lt y \lt c$ in the end. And hence, $a_{r,c} = 0$ too since $R$ and $C$ is all 0. Hence, the whole grid will be $0$. 900 901 ### Alternate Justification 902 903 Thanks to [dario2994](/profile/dario2994 "International Grandmaster dario2994") for writing this. 904 905 Let $V = Z_2^{nm}$. $V$ is endowed with the natural scalar product, which induces the concept of orthogonality. 906 907 Let $M$ be the subspace generated by the moves. Let $M^{\perp}$ be the space orthogonal to $M$. It is a basic result in linear algebra that $(M^{\perp})^{\perp} = M$. 908 909 One can see that $\{(x1, y1), (x1, y2), (x2, y1), (x2, y2)\}$ belongs to $M$ (it is a combination of 4 moves). Thus one deduces that if $u \in M^{\perp}$ then $u_{x,y} = a_x \oplus b_y$ for two vectors $a\in Z_2^r, b \in Z_2^c$. Given $a, b$; the scalar product between $u$ and the move centered at $(x, y)$ is: $xor(a) \oplus xor(b) \oplus (c+1)a_x \oplus (r+1)b_y$. Assume that $u$ is in $M^{\perp}$: 910 911 * If $r, c$ are both even, then $a_x$ and $b_y$ must be constant and equal each other. Thus $M^{\perp}$ is only the $0$ vector. 912 * If $r$ is even and $c$ is odd, then $b_y$ is constant. Hence $M^{\perp}$ is generated by any two rows. 913 * If $r$ is odd and $c$ is even, analogous. 914 * If $r$ and $c$ are both odd, then the only condition is $xor(a) \oplus xor(b) = 0$. This is necessary and sufficient for the orthogonality. And it implies that $M^{\perp}$ is generated by any two rows and any two columns. 915 916 Since we determined $M^{\perp}$, we have determined also $M$. 917 918 ### Counting 919 920 Case 1 and 2 are the easy cases while counting case 3 is more involved. 921 922 #### Case 1: $r$ is even and $c$ is even 923 924 All grids are obtainable. Let $\#?$ denote the number of $\texttt{?}$s in the grid. Then the answer is $2^{\#?}$ since all grid are obtainable. 925 926 #### Case 2: $r$ is even and $c$ is odd 927 928 If $r$ is odd and $c$ is even, we can treat it as the same case by swapping a few variables. 929 930 Let us fix whether we want $R=[0,0,\ldots,0]$ or $R=[1,1,\ldots,1]$. We will count the number of valid grids for each case. 931 932 Let $\#?_i$ denote the number of $\texttt{?}$s in the $i$-th row. If $\#?_i \gt 0$, then then number of ways to set the $i$-th row is $2^{\#?_i-1}$. Otherwise, the number of ways is either $0$ to $1$ depending on the initial value of $R_i$. 933 934 #### Case 3: $r$ is odd and $c$ is odd 935 936 Let us define a bipartite graph with vertices $r+c$ vertices, labelled $V_{R,i}$ for $1 \leq i \leq r$ and $V_{C,j}$ for $1 \leq j \leq c$. If $a_{i,j}=\texttt{?}$, then we will add an (undirected) edge $V_{R,i} \leftrightarrow V_{C,j}$. Now we assume that each $\texttt{?}$ is set to $\texttt{0}$ at first. We will choose a subset of them to turn into $\texttt{1}$. When we do this on $a_{i,j}$, the value of $R_i$ and $C_j$ will toggle. In terms of the graph, this corresponds to assigning $0$ or $1$ to each edge. When we assign $1$ to the edge connecting $V_{R,i}$ and $V_{C,j}$, then $R_i$ and $C_j$ will toggle. We can consider $R_i$ and $C_j$ to be the weight of the vertices $V_{R,i}$ and $V_{C,j}$ respecitvely. 937 938 Consider a connected component of this bipartite graph. Choose an arbitrary spanning tree of this connected component. By assinging the weights of the edges in the spanning tree, we can arbitrarily set the weights of all but one vertex. We cannot arbitarily set the weight of all vertices as the xor-sum of the weight of vertices is an invariant. 939 940 Let us show that we can arbitarily choose the weights of all but one vertex on this connected component using the spanning tree. Let us arbitrarily root the tree. Choose some arbitrary leaf of the tree, if the weight of the leaf is correct, assign the edge connected to that vertex weight $0$. Otherwise, assign it weight $1$. Then remove the leaf and its corresponding edge. Actually, this shows that there is a one-to-one correspondents between the possible weights of the edges and the possible weights of the vertices. 941 942 For the edges not in the spanning tree we have chosen, we can arbitarily set their weights while we are still able to choose the weights of all but one vertex on this connected component by properly assigning weights of the edges in the spanning tree. 943 944 Suppose we want this constant value of $R$ and $C$ to be $v$, where $v$ is either $0$ or $1$. 945 946 Suppose that the connected component has size $n$, has $m$ edges and the xor of all the initial vertex weights is $x$. 947 948 If $n$ is even: 949 950 * If $x=0$, then there are $2^{m-n+1}$ ways to assign weights to edges. 951 * If $x=1$, then there are $0$ ways to assign weights to edges. 952 953 If $n$ is odd: 954 955 * If $x=v$, then there are $2^{m-n+1}$ ways to assign weights to edges. 956 * If $x\neq v$, then there are $0$ ways to assign weights to edges. 957 958 **Solution** 959 960 ``` 961 // Super Idol的笑容 962 // 都没你的甜 963 // 八月正午的阳光 964 // 都没你耀眼 965 // 热爱105°C的你 966 // 滴滴清纯的蒸馏水 967 968 #include <bits/stdc++.h> 969 #include <ext/pb_ds/assoc_container.hpp> 970 #include <ext/pb_ds/tree_policy.hpp> 971 #include <ext/rope> 972 using namespace std; 973 using namespace __gnu_pbds; 974 using namespace __gnu_cxx; 975 976 #define int long long 977 #define ll long long 978 #define ii pair<ll,ll> 979 #define iii pair<ii,ll> 980 #define fi first 981 #define se second 982 #define endl '\n' 983 #define debug(x) cout << #x << ": " << x << endl 984 985 #define pub push_back 986 #define pob pop_back 987 #define puf push_front 988 #define pof pop_front 989 #define lb lower_bound 990 #define ub upper_bound 991 992 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 993 #define all(x) (x).begin(),(x).end() 994 #define sz(x) (int)(x).size() 995 996 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 997 //change less to less_equal for non distinct pbds, but erase will bug 998 999 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1000 1001 const int MOD=998244353; 1002 1003 ll qexp(ll b,ll p,int m){ 1004 ll res=1; 1005 while (p){ 1006 if (p&1) res=(res*b)%m; 1007 b=(b*b)%m; 1008 p>>=1; 1009 } 1010 return res; 1011 } 1012 1013 int n,m; 1014 char grid[2005][2005]; 1015 1016 int w[4005]; 1017 vector<int> al[4005]; 1018 1019 bool vis[4005]; 1020 int ss,par,edges; 1021 1022 void dfs(int i){ 1023 if (vis[i]) return; 1024 vis[i]=true; 1025 1026 ss++; 1027 par^=w[i]; 1028 edges+=sz(al[i]); 1029 1030 for (auto it:al[i]) dfs(it); 1031 } 1032 1033 signed main(){ 1034 ios::sync_with_stdio(0); 1035 cin.tie(0); 1036 cout.tie(0); 1037 cin.exceptions(ios::badbit | ios::failbit); 1038 1039 cin>>n>>m; 1040 rep(x,0,n) cin>>grid[x]; 1041 1042 if (n%2>m%2){ 1043 swap(n,m); 1044 rep(x,0,2005) rep(y,0,2005) if (x<y) swap(grid[x][y],grid[y][x]); 1045 } 1046 1047 // rep(x,0,n){ 1048 // rep(y,0,m) cout<<grid[x][y]<<" "; cout<<endl; 1049 // } 1050 1051 if (n%2==0 && m%2==0){ 1052 int cnt=0; 1053 rep(x,0,n) rep(y,0,m) if (grid[x][y]=='?') cnt++; 1054 cout<<qexp(2,cnt,MOD)<<endl; 1055 } 1056 else if (n%2==0 && m%2==1){ 1057 int cnt0=1,cnt1=1; 1058 1059 rep(x,0,n){ 1060 int val=0; 1061 int cnt=0; 1062 rep(y,0,m){ 1063 if (grid[x][y]=='?') cnt++; 1064 else val^=grid[x][y]-'0'; 1065 } 1066 if (cnt==0){ 1067 if (val==0) cnt1=0; 1068 else cnt0=0; 1069 } 1070 else{ 1071 cnt0=(cnt0*qexp(2,cnt-1,MOD))%MOD; 1072 cnt1=(cnt1*qexp(2,cnt-1,MOD))%MOD; 1073 } 1074 } 1075 1076 cout<<(cnt1+cnt0)%MOD<<endl; 1077 } 1078 else{ 1079 rep(x,0,n) rep(y,0,m){ 1080 if (grid[x][y]!='?'){ 1081 w[x]^=grid[x][y]-'0'; 1082 w[y+n]^=grid[x][y]-'0'; 1083 } 1084 else{ 1085 al[x].pub(y+n); 1086 al[y+n].pub(x); 1087 } 1088 } 1089 1090 int cnt0=1,cnt1=1; 1091 1092 rep(x,0,n+m) if (!vis[x]){ 1093 ss=0,par=0,edges=0; 1094 dfs(x); 1095 edges/=2; 1096 edges-=ss-1; //extra edge 1097 1098 int mul=qexp(2,edges,MOD); 1099 1100 if (ss%2==0){ 1101 if (par) mul=0; 1102 cnt0=(cnt0*mul)%MOD; 1103 cnt1=(cnt1*mul)%MOD; 1104 } 1105 else{ 1106 if (par==0){ 1107 cnt0=(cnt0*mul)%MOD; 1108 cnt1=0; 1109 } 1110 else{ 1111 cnt0=0; 1112 cnt1=(cnt1*mul)%MOD; 1113 } 1114 } 1115 } 1116 1117 cout<<(cnt0+cnt1)%MOD<<endl; 1118 } 1119 } 1120 ``` 1121 1122 [1672H - Zigu Zagu](/contest/1672/problem/H "Codeforces Global Round 20") 1123 Author: [maomao90](/profile/maomao90 "Master maomao90"), [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 1124 1125 **Hints** 1126 1127 **Hint 1** 1128 1129 We will always remove a maximal segment, or in other words we will select $l$ and $r$ such that $A_{l-1} = A_l$ and $A_r = A_{r+1}$. 1130 1131 **Hint 2** 1132 1133 Try to find an invariant. 1134 1135 **Tutorial** 1136 1137 We can first split string $A$ into the minimum number of sections of $\texttt{010101}\ldots$ and $\texttt{101010}\ldots$. Let the number of sections be $K$. Since we can simply delete each section individually, the worst answer that we can get is $K$. Also, there is no reason to only delete part of a segment, so from here on we only assume that we delete maximal segments. 1138 1139 Now, we can decompose $A$ based on its $K$ sections and write it as a string $D$. The rules for the decomposition is as follows: 1140 1141 * $10\ldots01 \to x$ 1142 * $01\ldots10 \to x'$ 1143 * $10\ldots10 \to y$ 1144 * $01\ldots01 \to y'$ 1145 1146 For example, the string $A=[0101][1][1010]$ becomes $D=y'xy$. Now, let us look at what our operation does on $D$. 1147 1148 When we remove a section of even length ($y$ or $y'$) **that is not on the endpoint of the string**, the left and right sections will get combined. This is because the two ends of an even section are opposite, allowing the left and right sections to merge. Otherwise, it results in no merging. 1149 1150 When some sections get combined, the length of string $D$ gets reduced by $2$, while the length of $D$ gets reduced by $1$ otherwise. Clearly, we want to maximize deleting the number of sections of even length that are not on the endpoints of the string. We will call such a move a **power** move. 1151 1152 Let us classify strings that have no power moves. They actually come in $8$ types: 1153 1154 * $x x \ldots x$ 1155 * $y' x x \ldots x$ 1156 * $x x \ldots x y$ 1157 * $y' x x \ldots x y$ 1158 * $x' x' \ldots x'$ 1159 * $y x' x' \ldots x'$ 1160 * $x' x' \ldots x' y'$ 1161 * $y x' x' \ldots x' y'$ 1162 1163 We can prove that for any string not of this form, there will be always be character $y$ or $y'$ that is not on the ends of the string. Suppose that the string contains both $x$ and $x'$, then $xyx'$ or $x'y'x$ must be a substring. Also, the number of $y$ or $y'$s on each side cannot be more than $1$. Note that strings such that $y$ or $yy'$ may fall under multiple types. 1164 1165 Furthermore, for string of these types, the number of moves we have to make is equal to the length of the string. 1166 1167 Let us define the balance of $x$ as the number of $x$ minus the number of $x'$. We will define the balance of $y$ similarly. When we perform a power move, notice that the balance of the string is unchanged. Indeed, each power move either removes a pair of $x$ and $x'$ or $y$ and $y'$ from the string. 1168 1169 With this, we can easily find which type of ending string we will end up with based on the perviously mentioned invariants, except for the cases of differentiating between the string $x x \ldots x$ and $y' x x \ldots x y$ (and the case for $x'$). 1170 1171 To differentiate between these $2$ cases, we can note that the first character of our string does not change when we perform power moves. And indeed, $x$ and $y'$ have different starting characters. 1172 1173 Note that we have to be careful when the balance of $x$ and the balance of $y$ is $0$ in the initial string as for strings such as $yy'$, the final string is not $\varnothing$ but $yy'$. With this, we can answer queries in $O(1)$ since we can query the balance of $x$, the balance of $y$ and the total length of the decomposed string in $O(1)$. 1174 1175 Furthermore, there is a implementation trick here. Notice that if $a_{l-1}\neq a_l$, then then answer for $s[l-1,r]$ will be equal to the answer for $s[l,r]$. So in implementation, it is easier to "extend" $l$ and $r$ to find the balance of $x$ and $y$. 1176 1177 **Solution** 1178 1179 ``` 1180 #include <bits/stdc++.h> 1181 using namespace std; 1182 1183 int n,q; 1184 string s; 1185 int l[200005]; 1186 int r[200005]; 1187 int psum[200005]; 1188 int balance[200005]; 1189 1190 signed main(){ 1191 ios::sync_with_stdio(0); 1192 cin.tie(0); 1193 cout.tie(0); 1194 cin.exceptions(ios::badbit | ios::failbit); 1195 1196 cin>>n>>q; 1197 cin>>s; 1198 1199 s=s[0]+s+s[n-1]; 1200 1201 for (int x=1;x<=n;x++){ 1202 if (s[x-1]==s[x]) l[x]=x; 1203 else l[x]=l[x-1]; 1204 } 1205 1206 for (int x=n;x>=1;x--){ 1207 if (s[x]==s[x+1]){ 1208 r[x]=x; 1209 psum[x]=1; 1210 if ((x-l[x])%2==0){ 1211 balance[x]=(s[x]=='1'?1:-1); 1212 } 1213 } 1214 else r[x]=r[x+1]; 1215 } 1216 1217 for (int x=1;x<=n;x++){ 1218 psum[x]+=psum[x-1]; 1219 balance[x]+=balance[x-1]; 1220 } 1221 1222 int a,b; 1223 while (q--){ 1224 cin>>a>>b; 1225 a=l[a],b=r[b]; 1226 1227 int bl=balance[b]-balance[a-1]; 1228 int sum=psum[b]-psum[a-1]; 1229 1230 int ans=(sum+abs(bl))/2; 1231 1232 if ((sum+abs(bl))%2==1) ans++; 1233 else if (abs(bl)==0) ans++; 1234 else if (bl>0 ^ s[a]=='1') ans++; 1235 1236 cout<<ans<<"\n"; 1237 } 1238 } 1239 ``` 1240 1241 [1672I - PermutationForces](/contest/1672/problem/I "Codeforces Global Round 20") 1242 Author: [errorgorn](/profile/errorgorn "International Grandmaster errorgorn") 1243 1244 **Hints** 1245 1246 **Hint 1** 1247 1248 When removing an element, consider how the costs of other elements change? 1249 1250 **Hint 2** 1251 1252 When removing an element, consider the elements whose cost increase. What are their properties? 1253 1254 **Hint 3** 1255 1256 Is there a greedy algorithm? 1257 1258 **Hint 4** 1259 1260 Yes there is. How to make it run fast? 1261 1262 **Hint 5** 1263 1264 Use monotonicity to reduce one dimension 1265 1266 **Tutorial** 1267 1268 Let us rephrase the problem. Let $x$ and $y$ be arrays where $x_i=p_i$ and $y_i=i$ initially. For brevity, let $c_i = |x_i - y_i|$. 1269 1270 We want to check if we can do the following operation $n$ times on the array: 1271 1272 * Choose an index $i$ such that and $c_i \leq s$. 1273 * For all $j$ where $x_i \lt x_j$, update $x_j \gets x_j-1$. 1274 * For all $j$ where $y_i \lt y_j$, update $y_j \gets y_j-1$. 1275 * Set $x_i \gets \infty$ and $y_i \gets -\infty$ 1276 1277 Let us fix $s$ and solve the problem of checking whether a value of $s$ allows us to transform the permutation into the empty permutation. 1278 1279 ### Lemma 1 1280 1281 Let $(x,y,c)$ be the arrays before some arbitrary operation and $(x',y',c')$ be the arrays after that operation. If we only perform moves with $c_i \leq s$, then $c_j \leq s$ implies that $c'_j \leq s$ i.e. if something was removable before, it will be removable later if we only use valid moves. 1282 1283 Proof: Note that $x'_j = x_j$ or $x'_j=x_j-1$. The case for $y$ is same. 1284 1285 We can see that $c'_j \leq c_j+1$. So the only case where $c'_j \gt s$ is when $c_j=s$. 1286 1287 Case $1$: $x_j \leq y_j$ 1288 1289 Then it must be that $x'_j=x_j$ and $y'_j=y_j-1$. By the definition of our operation, we have the following inequality: $x_i \lt x_j \leq y_j \lt y_i$. 1290 1291 This implies that $c_i \gt s$, which is a contradiction. 1292 1293 Case $2$: $x_j \geq y_j$ 1294 1295 By similar analysis we see that $c_i \gt s$. $\blacksquare$ 1296 1297 Suppose that we only remove points with $c_i \leq s$ for some fixed $s$. This greedy algorithm works here - at each step, choose any point $c_i \leq s$ with and remove it. - if no such point exists, the $s$ does not work 1298 1299 Proof: 1300 1301 Given any permutation, let any point with $c_a \leq s$ be $a$. Consider any optimal sequence of moves $[b_1,b_2,\ldots,b_w,a,\ldots]$. We can transform to another optimal solution it by moving $a$ to the front. 1302 1303 Let the element before $a$ to be $b_w$. We will swap $a$ and $b_w$. $a$ is already removable at the start so it will be removable after removing $b_1,b_2,\ldots,b_{w-1}$ by lemma $1$. After removing everything before $b_1,b_2,\ldots,b_{w-1}$, $b_w$ is removable, so it will be removable after removing $a$ by lemma $1$. Hence we can move $a$ to the front of the sequence of moves by repeatedly swaping elemenets. 1304 1305 By exchange arguement, the greedy solution of removing any point with $c_a \leq s$ is an optimal solution. 1306 1307 ### Time Complexity Speedups 1308 1309 By extension, the following greedy algorithm works: 1310 1311 Set $s \gets 0$. 1312 1313 * At each step, choose index $i$ with minimal $c_i$ 1314 * Update $s \gets \max(s,c_i)$ 1315 * Remove point $i$ 1316 1317 Let's start with $s=0$ and remove things while we can. If we are at a state that we are stuck, incremenet $s$. When we increment $s$, the moves that we haved done before will still be a valid choice with this new value of $s$. We simply increment $s$ until we can remove the entire permutation which is 1318 1319 Now the only difficult part about this is maintaining the array $c_i$ (the cost) for the points we have not removed. 1320 1321 Let's define a point as **good** as follows: 1322 1323 If $y \lt x$, the point is good if there exist no other point $(x',y')$ such that $y \lt y' \leq x' \lt x$. 1324 1325 Otherwise, the point is good if there exist no other point $(x',y')$ such that $x \lt x' \leq y' \lt y$. 1326 1327 We maintain only the good elements, because only good elements are candidates for the minimum $c_i$. Suppose element is not good and minimal, then the point that causes it to be not good has a strictly smaller cost, an obvious contradiction. 1328 1329 Now we will use data structures to maintain $c_i$ of good points. We will split the good points into the **left good** and **right good** points which are those of $x_i \leq y_i$ and $y_i \leq x_i$ respectively. Notice that if $x_i = y_i$, then it is both left good and right good. 1330 1331 We will focus on the left good points. Suppose $i$ and $j$ are both left good with $x_i \lt x_j$, then $y_i \lt y_j$. Suppose otherwise, then we have $x_i \lt x_j \leq y_j \lt y_i$, making $i$ not good. As such $x$ and $y$ of the left good points are monotone. 1332 1333 To find this monotone chain of left good points, we can maintain a max segment tree which stores max $y$ for all alive $x$. Using binary search on segment tree to find the unique point with $x' \gt x$ such that $y'$ is minimized. Where $(x,y)$ is a point on the chain, and $(x',y')$ is the next point. We can repeatedly do this to find the entire chain of left good elements 1334 1335 We can store a segment tree where $i$ is the key and $c_i$ is the value. If an element is left good, it will always be left good until it is removed. 1336 1337 The following two operations are simply range updates on the segment tree since $y_i$ is monotone. - For all $j$ such that $x_j \gt x_i$, set $x_j \leftarrow x_j-1$. - For all $j$ such that $y_j \lt y_i$, set $y_j \leftarrow y_j-1$. 1338 1339 Now, when we remove some left good point, some other points will become left good, and we will need to add them. We do this by starting from the previous element of the left good chain, and then keep repeating the same algo using descend on the segment tree. 1340 1341 When we add a new left good point, we need to know the cost at the current point in time. If we consider a point which is initially $(x,y)$, and all other previously removed $(x',y')$, $x$ decreases by 1 per $x' \lt x$ and $y$ decreases by 1 per $y' \lt y$. Hence, we can maintain a fenwick tree of the removed point's $x$ and $y$, and using that we can determine the $x$ and $y$ at the time when we add it to the left good chain (and hence to the segment tree). 1342 1343 Time Complexity: $O(n \log n)$ 1344 1345 #### Quad Trees 1346 1347 Thanks to [dario2994](/profile/dario2994 "International Grandmaster dario2994") for pointing this out. 1348 1349 Surprisingly quad trees are provably $O(n \sqrt n)$ here. Take the $k$-th layer of the quad tree. The $n \cdot n$ grid will be split into $4^k$ squares in the $k$-th layer. Since we are doing half plane covers, our query range will only touch $2^k$ squares. At the same time, the width of those $2^k$ squares is $\frac{n}{2^k}$. Since each column only has a single element, our query range will also by bounded by $\frac{n}{2^k}$. The time complexity for a single update is given by $\sum\limits_{k=1}^{\log n} \min(2^k,\frac{n}{2^k}) = O(\sqrt n)$. 1350 1351 **Solution** 1352 1353 ``` 1354 // Super Idol的笑容 1355 // 都没你的甜 1356 // 八月正午的阳光 1357 // 都没你耀眼 1358 // 热爱105°C的你 1359 // 滴滴清纯的蒸馏水 1360 1361 #include <bits/stdc++.h> 1362 #include <ext/pb_ds/assoc_container.hpp> 1363 #include <ext/pb_ds/tree_policy.hpp> 1364 #include <ext/rope> 1365 using namespace std; 1366 using namespace __gnu_pbds; 1367 using namespace __gnu_cxx; 1368 1369 #define ii pair<int,int> 1370 #define fi first 1371 #define se second 1372 #define debug(x) cout << #x << ": " << x << endl 1373 1374 #define pub push_back 1375 #define pob pop_back 1376 #define puf push_front 1377 #define pof pop_front 1378 #define lb lower_bound 1379 #define ub upper_bound 1380 1381 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 1382 #define all(x) (x).begin(),(x).end() 1383 #define sz(x) (int)(x).size() 1384 1385 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 1386 //change less to less_equal for non distinct pbds, but erase will bug 1387 1388 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1389 1390 struct FEN{ 1391 int fen[500005]; 1392 1393 FEN(){ 1394 memset(fen,0,sizeof(fen)); 1395 } 1396 1397 void upd(int i,int j){ 1398 while (i<500005){ 1399 fen[i]+=j; 1400 i+=i&-i; 1401 } 1402 } 1403 1404 int query(int i){ 1405 int res=0; 1406 while (i){ 1407 res+=fen[i]; 1408 i-=i&-i; 1409 } 1410 return res; 1411 } 1412 } fval,fidx; 1413 1414 struct dat{ 1415 struct node{ 1416 int s,e,m; 1417 ii val; 1418 int lazy=0; 1419 node *l,*r; 1420 1421 node (int _s,int _e){ 1422 s=_s,e=_e,m=s+e>>1; 1423 val={1e9,s}; 1424 1425 if (s!=e){ 1426 l=new node(s,m); 1427 r=new node(m+1,e); 1428 } 1429 } 1430 1431 void propo(){ 1432 if (lazy){ 1433 val.fi+=lazy; 1434 if (s!=e){ 1435 l->lazy+=lazy; 1436 r->lazy+=lazy; 1437 } 1438 lazy=0; 1439 } 1440 } 1441 1442 void update(int i,int j,int k){ 1443 if (s==i && e==j) lazy+=k; 1444 else{ 1445 if (j<=m) l->update(i,j,k); 1446 else if (m<i) r->update(i,j,k); 1447 else l->update(i,m,k),r->update(m+1,j,k); 1448 1449 l->propo(),r->propo(); 1450 val=min(l->val,r->val); 1451 } 1452 } 1453 1454 void set(int i,int k){ 1455 propo(); 1456 if (s==e) val.fi=k; 1457 else{ 1458 if (i<=m) l->set(i,k); 1459 else r->set(i,k); 1460 1461 l->propo(),r->propo(); 1462 val=min(l->val,r->val); 1463 } 1464 } 1465 } *root=new node(0,500005); 1466 1467 struct node2{ 1468 int s,e,m; 1469 int val=-1e9; 1470 node2 *l,*r; 1471 1472 node2 (int _s,int _e){ 1473 s=_s,e=_e,m=s+e>>1; 1474 1475 if (s!=e){ 1476 l=new node2(s,m); 1477 r=new node2(m+1,e); 1478 } 1479 } 1480 1481 void update(int i,int k){ 1482 if (s==e) val=k; 1483 else{ 1484 if (i<=m) l->update(i,k); 1485 else r->update(i,k); 1486 val=max(l->val,r->val); 1487 } 1488 } 1489 1490 ii query(int i,int key){ //find key<=val where i<=s 1491 if (e<i || val<key) return {-1,-1}; 1492 if (s==e) return {s,val}; 1493 else{ 1494 auto temp=l->query(i,key); 1495 if (temp!=ii(-1,-1)) return temp; 1496 else return r->query(i,key); 1497 } 1498 } 1499 } *root2=new node2(0,500005); 1500 1501 set<ii> s={ {500005,500005} }; 1502 1503 //root stores the values of each pair 1504 //root2 stores the left endpoint of each pair to add non-overlapping ranges 1505 //s stores the pairs are still alive so its easy to do searches 1506 1507 dat *d; //we also store the other guy 1508 bool orien; //false for i->arr[i] 1509 1510 int pp[500005]; 1511 1512 void push(int i,int j){ 1513 pp[j]=i; 1514 root2->update(j,i); 1515 } 1516 1517 void add(int i,int j){ 1518 root2->update(j,-1e9); 1519 s.insert({i,j}); 1520 1521 int val; 1522 if (!orien) val=fval.query(j)-fidx.query(i); 1523 else val=fidx.query(j)-fval.query(i); 1524 1525 root->set(j,val); 1526 } 1527 1528 void del(int j){ 1529 ii curr={-1,-1}; 1530 int lim=500005; 1531 1532 if (j!=-1){ 1533 int i=pp[j]; 1534 1535 auto it=d->s.ub({j,1e9}); 1536 d->root->update(i,(*it).se-1,-1); 1537 1538 if (!orien) fidx.upd(i,-1),fval.upd(j,-1); 1539 else fval.upd(i,-1),fidx.upd(j,-1); 1540 1541 it=s.find({i,j}); 1542 if (it!=s.begin()) curr=*prev(it); 1543 lim=(*next(it)).se; 1544 s.erase(it); 1545 root->set(j,1e9); 1546 root2->update(j,-1e9); 1547 } 1548 1549 while (true){ 1550 auto temp=root2->query(curr.se,curr.fi); 1551 swap(temp.fi,temp.se); 1552 if (temp==ii(-1,-1) || lim<=temp.se) break; 1553 1554 add(temp.fi,temp.se); 1555 curr=temp; 1556 } 1557 } 1558 } *l=new dat(),*r=new dat(); 1559 1560 int n; 1561 1562 int main(){ 1563 ios::sync_with_stdio(0); 1564 cin.tie(0); 1565 cout.tie(0); 1566 cin.exceptions(ios::badbit | ios::failbit); 1567 1568 //cyclic mapping to each other 1569 l->d=r; 1570 r->d=l; 1571 1572 r->orien=true; 1573 1574 cin>>n; 1575 rep(x,1,n+1){ 1576 int y; 1577 cin>>y; 1578 1579 if (x<=y) l->push(x,y); 1580 else r->push(y,x); 1581 } 1582 1583 rep(x,1,n+1) fidx.upd(x,1),fval.upd(x,1); 1584 l->del(-1); 1585 r->del(-1); 1586 1587 int ans=0; 1588 1589 rep(x,0,n){ 1590 if (l->root->val.fi<=r->root->val.fi){ 1591 ans=max(ans,l->root->val.fi); 1592 l->del(l->root->val.se); 1593 } 1594 else{ 1595 ans=max(ans,r->root->val.fi); 1596 r->del(r->root->val.se); 1597 } 1598 } 1599 1600 cout<<ans<<endl; 1601 } 1602 ```