codeforces-scrape

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

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 ```