1682.md (34851B)
1 Source: https://codeforces.com/blog/entry/103097 2 3 I hope you all liked the round. Please share your feedback in the comments section. 4 5 # [1682A — Palindromic Indices](https://codeforces.com/contest/1682/problem/A) 6 7 **Hint** 8 9 Read the statement carefully!! The given string is a **palindrome**. 10 11 **Tutorial** 12 13 Let's remove some index $i$ from the first half of $s$ and check whether the resulting string is a palindrome or not, the other half has the same approach. The prefix of length $i-1$ already matches with the suffix of the same length because the initial string was a palindrome, so we just need to check if $t = s[i + 1 \ldots n - i + 1]$ is a palindrome. 14 15 For $t$ to be a palindrome, $s_{n - i + 1}$ should be equal to $s_{i + 1}$ which was initially equal to $s_{n - i}$, again which should be equal to $s_{i + 2}$ and this goes on. Here we can see that $s_i = s_{i + 1} \ldots = s_{n - i + 1}$. So the answer is simply equal to the number of contiguous same characters in the center of the string which can be calculated in $\mathcal{O(n)}$. 16 17 **Solution** 18 19 ``` 20 #include<bits/stdc++.h> 21 using namespace std ; 22 23 #define ll long long 24 #define pb push_back 25 #define all(v) v.begin(),v.end() 26 #define sz(a) (ll)a.size() 27 #define F first 28 #define S second 29 #define INF 2000000000000000000 30 #define popcount(x) __builtin_popcountll(x) 31 #define pll pair<ll,ll> 32 #define pii pair<int,int> 33 #define ld long double 34 35 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; } 36 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; } 37 38 #ifdef LOCAL 39 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 40 #else 41 #define debug(...) 2401 42 #endif 43 44 int _runtimeTerror_() 45 { 46 int n; 47 cin >> n; 48 string s; 49 cin >> s; 50 int cnt = 0; 51 for(int i=(n-1)/2;i>=0;--i) { 52 if(s[i] == s[(n - 1) / 2]) { 53 ++cnt; 54 } 55 else { 56 break; 57 } 58 } 59 cout << 2 * cnt - (n & 1) << "\n"; 60 return 0; 61 } 62 63 int main() 64 { 65 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 66 #ifdef runSieve 67 sieve(); 68 #endif 69 #ifdef NCR 70 initncr(); 71 #endif 72 int TESTS = 1; 73 cin >> TESTS; 74 while(TESTS--) { 75 _runtimeTerror_(); 76 } 77 return 0; 78 } 79 ``` 80 81 # [1682B — AND Sorting](https://codeforces.com/contest/1682/problem/B) 82 83 **Hints** 84 85 **Hint 1** 86 87 You must have to make at least one swap on the elements which are not at their correct positions initially. So $X$ must be a submask of all elements which are not at their correct positions. 88 89 **Hint 2** 90 91 What is the maximum possible value of $X$ from Hint $1$? It is the bitwise AND of all elements which are not at their correct positions. It turns out that this value is achievable too. 92 93 **Tutorial** 94 95 We always have to make at least one swap for the elements which are not at their correct positions. Hence an upper bound of answer would be the bitwise AND of those elements. Let the value be $X$. It turns out that the given permutation is $X$-sortable. 96 97 **Proof**: 98 99 First, notice that $X$ would always be present in $p$. Let $pos_x$ be the position of $X$ in $p$ initially. Let's say at some point we want to swap two values $p_i$ and $p_j$, then $p_i$ and $p_j$ would always be a supermask of $X$ i.e. $p_i$ & $X = X$ and $p_j$ & $X = X$. We can make the following moves to swap $p_i$ and $p_j$ without disturbing any other element. 100 101 * Swap values at indices $i$ and $pos_x$. 102 * Swap values at indices $i$ and $j$. 103 * Swap values at indices $j$ and $pos_x$. 104 105 It can be seen that in every swap the bitwise AND of two values which we are swapping is always $X$. Hence we can swap any two values which were not at their correct positions, therefore we can sort the permutation $p$. 106 107 Overall Complexity: $\mathcal{O(n)}$. 108 109 **Solution** 110 111 ``` 112 #include<bits/stdc++.h> 113 using namespace std ; 114 115 #define ll long long 116 #define pb push_back 117 #define all(v) v.begin(),v.end() 118 #define sz(a) (ll)a.size() 119 #define F first 120 #define S second 121 #define INF 2000000000000000000 122 #define popcount(x) __builtin_popcountll(x) 123 #define pll pair<ll,ll> 124 #define pii pair<int,int> 125 #define ld long double 126 127 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; } 128 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; } 129 130 #ifdef LOCAL 131 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 132 #else 133 #define debug(...) 2401 134 #endif 135 136 int _runtimeTerror_() 137 { 138 int n; 139 cin >> n; 140 int ans = (1 << 30) - 1; 141 for(int i=0;i<n;++i) { 142 int x; 143 cin >> x; 144 if(x != i) { 145 ans &= x; 146 } 147 } 148 cout << ans << "\n"; 149 return 0; 150 } 151 152 int main() 153 { 154 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 155 #ifdef runSieve 156 sieve(); 157 #endif 158 #ifdef NCR 159 initncr(); 160 #endif 161 int TESTS = 1; 162 cin >> TESTS; 163 while(TESTS--) { 164 _runtimeTerror_(); 165 } 166 return 0; 167 } 168 ``` 169 170 # [1682C — LIS or Reverse LIS?](https://codeforces.com/contest/1682/problem/C) 171 172 **Hint** 173 174 Let $\text{LDS}(a)$ be the longest strictly decreasing subsequence of $a$, then $\text{LIS}(a')$ = $\text{LDS}(a)$. 175 176 There can be at most one index common between $\text{LIS}(a)$ and $\text{LDS}(a)$. 177 178 **Tutorial** 179 180 Let's make a small observation: 181 182 * There can be at most one index common to both $\text{LIS}(a)$ and $\text{LDS}(a)$. 183 184 If some element $x$ occurs $\geq 2$ times, then one of its occurrences can be included in $\text{LIS}(a)$ and another one in $\text{LDS}(a)$, and all the remaining occurrences are of no use because none of them can contain 2 equal elements. 185 186 If some element $x$ is a singleton i.e. the frequency of $x$ in $a$ is $1$, then it can have $3$ positions 187 188 * In $\text{LIS}(a)$ only. 189 * In $\text{LDS}(a)$ only. 190 * The only common element of $\text{LIS}(a)$ and $\text{LDS}(a)$. 191 192 It can be seen that it is always optimal to choose some singleton as the only common element (if available) because those with frequency $\geq 2$ can easily contribute $1$ to both $\text{LIS}(a)$ and $\text{LDS}(a)$ easily. 193 194 Let $t$ be the number of elements having frequency $\geq 2$ and $s$ be the number of singletons in $a$. The singletons should be divided equally among $\text{LIS}(a)$ and $\text{LDS}(a)$ with one of them given to both, if available. 195 196 Hence, the answer is $t + \lceil \frac{s}{2} \rceil$. 197 198 The values $s$ and $t$ can be found using some data structure like $\text{std:map}$ in C++ in $\mathcal{O}(n\log(n))$. 199 200 **Solution** 201 202 ``` 203 #include<bits/stdc++.h> 204 using namespace std ; 205 206 #define ll long long 207 #define pb push_back 208 #define all(v) v.begin(),v.end() 209 #define sz(a) (ll)a.size() 210 #define F first 211 #define S second 212 #define INF 2000000000000000000 213 #define popcount(x) __builtin_popcountll(x) 214 #define pll pair<ll,ll> 215 #define pii pair<int,int> 216 #define ld long double 217 218 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; } 219 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; } 220 221 #ifdef LOCAL 222 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 223 #else 224 #define debug(...) 2401 225 #endif 226 227 int _runtimeTerror_() 228 { 229 int n; 230 cin >> n; 231 map<int, int> mp; 232 for(int i=1;i<=n;++i) { 233 int x; 234 cin >> x; 235 ++mp[x]; 236 } 237 int single = 0, doble = 0; 238 for(auto &[i, j]:mp) { 239 single += j == 1; 240 doble += j > 1; 241 } 242 cout << doble + (single + 1) / 2 << "\n"; 243 return 0; 244 } 245 246 int main() 247 { 248 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 249 #ifdef runSieve 250 sieve(); 251 #endif 252 #ifdef NCR 253 initncr(); 254 #endif 255 int TESTS = 1; 256 cin >> TESTS; 257 while(TESTS--) { 258 _runtimeTerror_(); 259 } 260 return 0; 261 } 262 ``` 263 264 # [1682D — Circular Spanning Tree](https://codeforces.com/contest/1682/problem/D) 265 266 **Hints** 267 268 **Hint 1** 269 270 What are the mandatory conditions on string $s$ for a tree to be possible? 271 272 **Hint 2** 273 274 If there are no odd degree vertices or the count of odd degree vertices is odd, then it is impossible to construct any tree. It turns out that these conditions are sufficient too. 275 276 **Tutorial** 277 278 Let's check some cases when it is not possible to construct the answer- 279 280 * When all vertices have an even degree, then there is no way to generate a tree because every tree contains at least $2$ leaves. 281 * When there are an odd number of vertices with odd degrees, then there is no tree possible because the sum of degrees must be even. 282 283 It turns out that it is always possible to construct a tree if none of the above is true. 284 285 The following construction works - 286 287 * Select some vertex $i$ such that the previous vertex of $i$ (assumed cyclically) has an odd degree i.e. $s_{i - 1} = 1$. Clearly, such a vertex always exists. 288 * Now left rotate $s$, $i - 1$ times such that the selected vertex is now at index $1$. Note that after the rotation $s_n$ will become $1$. Now we can see that $s[2\ldots n]$ can be divided into several segments such that each segment ends with some vertex having an odd degree. And each segment should contain exactly one vertex with an odd degree. So $s[2 \ldots n] = [0\ldots 1][0\ldots 1] \ldots [0\ldots 1]$ where $0$ may appear $0$ times. Connect vertex $1$ to the starting vertex of each segment and connect adjacent vertices inside each segment. It can be clearly seen that edges will never intersect internally. The only thing we need to verify is the degree constraints. 289 290 **Proof**: 291 292 * The degree condition is valid for each segment, as each vertex with an even degree is connected with $2$ other vertices and the last vertex with an odd degree will be connected to only one vertex i.e it's previous one or vertex $1$ if it was only on its segment. 293 * Let $cnt_1$ be the number of vertices with odd degree. If $s_1 = 1$, then there will be $cnt_1 - 1$ segments which is an odd number, hence vertex $1$ will be connected to odd number of vertices. If $s_1 = 0$, then there will be $cnt_1$ segments which is an even number, hence vertex $1$ will be connected to even number of vertices. 294 295 Note that we renumbered the vertices during rotation which should be handled in implementation. 296 297 The intuition for the above approach comes from the case when all $s_i$ are $1$ in which we create a star network. 298 299 Overall complexity: $\mathcal{O(n)}$. 300 301 **Solution** 302 303 ``` 304 #include<bits/stdc++.h> 305 using namespace std; 306 307 #define all(v) v.begin(),v.end() 308 #define endl "\n" 309 310 int solve(){ 311 int n; cin >> n; 312 string s; cin >> s; 313 auto cnt = count(all(s),'1'); 314 if(cnt == 0 or cnt & 1){ 315 cout << "NO" << endl; 316 return 0; 317 } 318 auto inc = [&](int j){ 319 return (j + 1)%n; 320 }; 321 cout << "YES" << endl; 322 for(int p = 1; p < n; p++){ 323 if(s[p - 1] == '1'){ 324 auto i = inc(p); 325 while(i != p){ 326 int j = i; 327 int prev = p; 328 while(j != p){ 329 cout << prev + 1 << " " << j + 1 << endl; 330 prev = j; 331 j = inc(j); 332 if(s[prev] == '1')break; 333 } 334 i = j; 335 } 336 return 0; 337 } 338 } 339 340 return 0; 341 } 342 signed main(){ 343 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 344 //freopen("input.txt", "r", stdin); 345 //freopen("output.txt", "w", stdout); 346 #ifdef SIEVE 347 sieve(); 348 #endif 349 #ifdef NCR 350 init(); 351 #endif 352 int t=1;cin>>t; 353 while(t--){ 354 solve(); 355 } 356 return 0; 357 } 358 ``` 359 360 # [1682E — Unordered Swaps](https://codeforces.com/contest/1682/problem/E) 361 362 **Tutorial** 363 364 One way of solving permutation problems is to look at permutation cycles. Let's decompose our permutation into cycles, then it's easy to see that each cycle can be solved independently because we have to sort the permutation in a minimum number of moves which isn't possible if two cycles are merged at any instant. 365 366 Let's look at one cycle only, whose vertices are numbered from $1$ to $n$ in the orientation of cycle i.e the cycle is $1 \rightarrow 2 \rightarrow \ldots \rightarrow n \rightarrow 1$. Also assume that we only have swaps $(x, y)$ that are relevant to this cycle. 367 368 It is known that we can sort a cycle of size $n$ in $n - 1$ moves and it is the minimum number of required moves. 369 370 **Claim 1:** The set of swaps if considered as edges $(x, y)$ form a tree on the $n$ vertices of the cycle. 371 372 **Proof** 373 374 Assume that the edges don't form a tree, then there exist at least two disjoint components let's say $S$ and $T$. Now we must be able to make swaps inside $S$ only, to sort elements in $S$ which needs that the set {$i, i \in S$} is same as set {$p_i, i \in S$} which is not possible by property of permutation cycles. Any cycle of permutation, say $C$, can't be split further into two sets $S$ and $T$ such that both of them can be sorted independently among themselves. 375 376 So we must use all the $n - 1$ edges of the tree in some order to get $n$ cycles each of size $1$. 377 378 Let's consider any element $u$ having adjacency list as $[x_1, x_2, ..., x_k]$ in the order they appear on the cycle if we start moving from $u$ in the orientation of cycle i.e $u \rightarrow u + 1 \rightarrow ... \rightarrow n \rightarrow 1 \rightarrow ... \rightarrow u$. 379 380 **Claim 2:** We can never make the swap $(u, x_j)$ before swap $(u, x_i)$ if $j \gt i$. 381 382 **Proof** 383 384 If we make the swap $(u, x_j)$ first, then $u$ and $x_i$ will go in different cycles for subsequent operations and we will never be able to use edge $(u, x_i)$ because it will merge the two different cycles which isn't possible because we are constrained to break a cycle into smaller cycles only. 385 386 And if are not able to use edge $(u, x_i)$ then we will never be able to sort the permutation because we had $n - 1$ edges all of which were to be used and we wasted $1$ of them. 387 388 Using above claim, for every element $u$ the order of edges is fixed i.e $x_1$, then $x_2$, ..., and finally $x_k$. 389 390 Let's build a directed graph on $n - 1$ vertices (representing the swaps) where for every element $u$ we add directed edges $(u,x_1) \rightarrow (u,x_2)$, ..., $(u,x_{k-1}) \rightarrow (u,x_k)$. 391 392 Since it is guaranteed that the answer will exist i.e a valid sequence of moves exist, hence the topological sorting of the above graph must exist, any of which represents a correct sequence of swaps. 393 394 Note that whenever we make a swap that is not violating claim $2$ for any element $u$, then there will be no cross edge in two smaller cycles that are going to be formed and those smaller cycles can be further solved independently. Also the order of edges i.e $[x_1, x_2, ..., x_k]$ is not going to change for any element which ensures that the directed graph we built remains correct even if we remove some appropriate edge. 395 396 Hence the answer is simply the topological sort of the graph we built. 397 398 Overall Complexity: $\mathcal{O(nlog(n))}$, $nlog(n)$ for sorting the edges according to cycle's orientation to get the order $[x_1, x_2, ..., x_k]$ for every vertex. 399 400 **Some other interesting things about this problem** 401 402 **Claim:** The given swaps considered as edges $(x, y)$ forms a non-intersecting tree on $n$ vertices on the circle i.e no two edges intersect internally. ~~Motivation for problem D~~ 403 404 **Proof** 405 406 Let's say edges $(a, b)$ and $(c, d)$ intersect internally in the circle. 407 408 WLOG, let's suppose we make swap $(a, b)$ before swap $(c, d)$, then $c$ and $d$ will go in different cycles as in Claim $2$ above. 409 410 What if you were given any tree on $n$ vertices and asked to solve the problem with "YES/NO"? 411 412 * If the given edges intersect internally in the circle then the answer is "NO" otherwise it's always possible to construct a valid sequence of swaps. This is what the validator of E and checker of D do, try this one, and feel free to discuss in the comments section. 413 414 **Validator** 415 416 Let's make every edge $(u, v)$ such that $u \lt v$, clearly the order of $u$, $v$ doesn't matter. 417 418 Consider each edge as a segment $[u, v]$, then the edges of the tree intersect internally if and only if any two segments say $[l_1, r_1]$ and $[l_2, r_2]$ satisfies any of the below conditions- 419 420 1. $l_1\lt l_2 \lt r_1 \lt r_2$ 421 2. $l_2 \lt l_1 \lt r_2 \lt r_1$ 422 423 In the original problem, it was mentioned that there is always a correct sequence of swaps so we claimed that topological sorting must exist and indeed any topological sorting suffices. What if we were given a non-intersecting spanning tree? Can we still claim that there exists a correct move at every step? 424 425 **Claim:** Yes, we can 426 427 **Proof** 428 429 We need to show that there there is always some edge that can be removed without breaking claim $2$ above which is the only required condition. 430 431 Cycles of length $\le 2$ are trivial. 432 433 Let's represent by $u_{next}$ the first element of the list $[x_1, x_2, ..., x_k]$ for $u$ i.e the closest vertex having an edge with $u$ in cycle's orientation. 434 435 Now, let's start an iteration, start moving from $1$ and jump to $v_{next}$ every time when you are at vertex $v$. Continue this process until you again reach $1$ or cross over $1$. 436 437 Let the sequence obtained be $s$ i.e $s_1 = 1, s_2, ..., s_k$ where on moving further from $s_k$ we cross/reach $1$. For simplicity assume $k \ge 3$, $k = 2$ is trivial. 438 439 It can be shown that $(s_{k-1}, s_k)$ is the required edge. 440 441 **Proof** 442 443 $s_{k_{next}}$ lies between $s_{k-1}$ and $s_k$. There are three cases other that this: 444 445 1. $s_{k_{next}}$ lies between $s_k$ and $1$, which is not possible because we would have moved further and $s_k$ would not be the last element of sequence $s$. 446 2. $s_{k_{next}}$ = $1$ which is not possible because it will create a cycle and we are given a tree. 447 3. $s_{k_{next}}$ lies between $s_j$ and $s_{j+1}$ for $j \le k-2$, this is also not possible because then the edges $(s_k, s_{k_{next}})$ and $(s_j, s_{j+1})$ will intersect and we are given a non-intersecting tree. 448 449 $s_{k}$ is first element of adjacency list of $s_{k-1}$ by the definition of $v_{next}$ and $s_{k-1}$ is the first element of adjacency list of $s_{k}$ by above 3 points. 450 451 Hence it is safe to make the swap $(s_{k-1}, s_{k})$. 452 453 So the topological sort still works. 454 455 This might not be the only proof, if you have some other proofs feel free to discuss them in the comments. 456 457 Hope you liked the details!! 458 459 **Generator** 460 461 Any ideas on how to write a generator for this problem? 462 463 **My Approach** 464 465 Randomly partition the permutation into cycles, so generating swaps for a particular cycle is the main issue. 466 467 Let's represent the cycle by an array $a$ of size $n$ with cycle as $a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_n \rightarrow a_1$ Now let's start making random swaps say $(a_i, a_j)$ to break the cycle, then this generates two smaller cycles - 468 469 1. $a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_i \rightarrow a_{j+1} \rightarrow ... \rightarrow a_n \rightarrow a_1$. 470 2. $a_{i+1} \rightarrow ... \rightarrow a_j \rightarrow a_{i+1}$. 471 472 This can be easily done using treaps :) and then we can use recursion to solve them independently. 473 474 **Review by Anton Sir** 475 476  477 478 It's very rare!! Atleast first time for us. 479 480 **Solution** 481 482 ``` 483 #include<bits/stdc++.h> 484 using namespace std ; 485 486 #define ll long long 487 #define pb push_back 488 #define all(v) v.begin(),v.end() 489 #define sz(a) (ll)a.size() 490 #define F first 491 #define S second 492 #define INF 2000000000000000000 493 #define popcount(x) __builtin_popcountll(x) 494 #define pll pair<ll,ll> 495 #define pii pair<int,int> 496 #define ld long double 497 498 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; } 499 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; } 500 501 #ifdef LOCAL 502 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 503 #else 504 #define debug(...) 2401 505 #endif 506 507 const int N = 2e5 + 5; 508 vector<int> t_sort; 509 int idx[N]; 510 int vs[N]; 511 vector<int> v[N]; 512 513 bool dfs_sort(int u) 514 { 515 vs[u]=2; 516 for(auto j:v[u]) 517 { 518 if(vs[j]==2) 519 return true; 520 if(vs[j]==0 && dfs_sort(j)) 521 return true; 522 } 523 vs[u]=1; 524 t_sort.push_back(u); 525 return false; 526 } 527 528 // Returns true if there is a topological sort else returns false 529 bool top_sort(int n) 530 { 531 t_sort.clear(); 532 for(int i=1;i<=n;++i) 533 vs[i]=0; 534 for(int i=1;i<=n;++i) 535 { 536 if(vs[i]==0) 537 { 538 if(dfs_sort(i)) 539 { 540 t_sort.clear(); 541 return false; 542 } 543 } 544 } 545 reverse(t_sort.begin(),t_sort.end()); 546 assert(t_sort.size()==n); 547 for(int i=0;i<n;++i) 548 idx[t_sort[i]]=i; 549 return true; 550 } 551 552 int _runtimeTerror_() 553 { 554 int n, k; 555 cin >> n >> k; 556 vector<int> p(n+1), a(k), b(k); 557 for(int i=1;i<=n;++i) { 558 cin >> p[i]; 559 } 560 561 vector<vector<pii>> g(n+1); 562 for(int i=0;i<k;++i) { 563 int x, y; 564 cin >> x >> y; 565 a[i] = x, b[i] = y; 566 g[x].push_back({y, i + 1}); 567 g[y].push_back({x, i + 1}); 568 } 569 vector<int> id(n+1); 570 vector<int> ans; 571 auto solve = [&](vector<int> &cyc) { 572 int n = sz(cyc); 573 if(n == 1) { 574 return; 575 } 576 for(int i=0;i<n;++i) { 577 id[cyc[i]] = i; 578 } 579 auto dist = [&](int x, int y) { 580 return (id[y] - id[x] + n) % n; 581 }; 582 vector<int> good; 583 for(int i:cyc) { 584 sort(all(g[i]), [&](pii &a, pii &b) { 585 return dist(i, a.F) < dist(i, b.F); 586 }); 587 for(int j=1;j<sz(g[i]);++j) { 588 v[g[i][j-1].S].push_back(g[i][j].S); 589 } 590 } 591 }; 592 vector<bool> vis(n+1); 593 for(int i=1;i<=n;++i) { 594 if(vis[i]) { 595 continue; 596 } 597 vector<int> cycle; 598 int cur = i; 599 while(!vis[cur]) { 600 cycle.push_back(cur); 601 vis[cur] = 1; 602 cur = p[cur]; 603 } 604 solve(cycle); 605 } 606 top_sort(k); 607 for(auto i:t_sort) { 608 cout << i << " "; 609 } 610 cout << "\n"; 611 return 0; 612 } 613 614 int main() 615 { 616 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 617 #ifdef runSieve 618 sieve(); 619 #endif 620 #ifdef NCR 621 initncr(); 622 #endif 623 int TESTS = 1; 624 //cin >> TESTS; 625 while(TESTS--) { 626 _runtimeTerror_(); 627 } 628 return 0; 629 } 630 ``` 631 632 # [1682F — MCMF?](https://codeforces.com/contest/1682/problem/F) 633 634 **Tutorial** 635 636 Let us suppose we need to calculate the answer for only one query, say complete array i.e $a[1:n]$. 637 638 The scary flow structure in the problem can be reduced as- 639 640 Let's replicate each vertex $i$, $|b_i|$ times. Then we can see that there will be an equal number of vertices on the left and right side. Now the problem reduces that we have to match these vertices with minimum cost such that the cost of matching $i$ and $j$ is $|a_i - a_j|$. 641 642 There are only 2 type of elements (left side and right side) and the following greedy algorithm to match the elements works. 643 644 Algorithm: Sort the type $1$ and $2$ elements independently and match them in the sorted order. 645 646 **Proof** 647 648 Assume that two elements from left $l_1 \le l_2$ are matched with two elements from right $r_1 \le r_2$ as $[l_1, r_2]$ and $[l_2, r_1]$, then it can be easily shown that matching $[l_1, r_1]$ and $[l_2, r_2]$ is always more optimal. The proof is left as an excercise to reader. 649 650 Since the array $a$ is given in sorted order, let's use it!! 651 652 Let's assume- 653 654 * Type $1$ elements are those having $b_i \lt 0$. 655 * Type $2$ elements are those having $b_i \gt 0$. 656 657 Now instead of replicating elements $|b_i|$ times and sorting them independently, let's iterate on array $a$ from left to right and add the contribution of each element independently. Say we are at index $i$, and prefix sum of $b_i$ so far is $psum_i$, then the following cases arise- 658 659 * $b_i \gt 0$, $psum_i \ge 0$ — There is no unmatched type $1$ element on the left, so we just add this element's contribution to the answer i.e $-b_i \cdot a_i$. 660 * $b_i \gt 0$, $psum_i \lt -b_i$ — There are more than $b_i$ unmatched type $1$ elements on the left, so we match $b_i$ of them to $a_i$, adding a contribution of $a_i \cdot b_i$ to the answer. 661 * $b_i \gt 0$, $psum_i \lt 0$ and $psum_i \gt -b_i$ — There are less than $b_i$ unmatched elements ($= |psum_i|$) on the left, so we match those with equal number of $a_i$ and remaining are propagated further, adding a contribution of $|psum_i| * a_i - (b_i - |psum_i|) * a_i$, where the positive term comes from those matching with previous unmatched elements and the negative term comes from those that are going to be left unmatched. 662 663 Similar cases are there for $b_i \lt 0$. 664 665 Ok so now we can easily solve the problem for one query in $O(n)$. 666 667 **Main idea**: 668 669 Let's simulate the above algorithm for every suffix and record the obtained answer in $ans_i$ for $i^{th}$ suffix. Note that the value $ans_i$ doesn't denote any answer for some suffix because the sum of $b_i$ over that suffix might or might not be zero. One important observation here is that- 670 671 * Let some subarray $a[l:r]$ for which sum of $b_i$ is $0$, then $ans_l - ans_{r+1}$ do have a good meaning, it's the answer for that query indeed. 672 673 **Proof** 674 675 Our answer for $a[l:r]$ would have been the result of simulation on the subarray, but how does simulation on $l^{th}$ suffix looks? 676 677 It greedily matches the subarray $a[l:r]$ first because the sum of $b_i$ is zero, so it will surely pair up all elements in that subarray. Then it moves further on $r+1$ and continuing the simulation after $r+1$ is equivalent to starting the simulation from $r+1$ itself because $psum$ so far (defined above) would be automatically 0. 678 679 Note that $ans_l$ doesn't have any physical meaning because it will add some junk value if elements after $r+1$ are not paired up equally but those junk values are exactly same in $ans_l$ and $ans_r$ which cancel out, giving the correct answer. 680 681 But still, we can't simulate for every suffix, right? It would go $O(n^2)$ again. 682 683 Let's iterate from left to right and for every $i$ try calculating it's contribution in $1^{st}$, $2^{nd}$, ..., $(i-1)^{th}$ suffixes which is easy because it depends only on $psum_i$, $b_i$ (which are constant for a given $i$) and $psum_l$ for contribution to $l^{th}$ suffix. This is pretty standard using $2$ fenwick trees. 684 685 **How to calculate $ans_i$?** 686 687 Let's solve $b_i \gt 0$ and $b_i \lt 0$ independently, say $b_i \gt 0$ for now. Other case is similar. 688 689 Let $psum_i = \sum_{j=1}^{i}b_j$. 690 691 Consider the contribution of index $i$ to $ans_l$ for $l \lt i$, from three cases described above the contribution is different for different $l$ with different $psum_l$. We can build a fenwick tree on compressed prefix sums. Case $1$ and $2$ above add a constant value to a range of prefix sums that can be maintained in one fenwick tree and Case $2$ gives some linear function of $psum$ to be added in a range that can be maintained in other fenwick tree. Add contribution of each $i$ from $1$ to $n$ first, and let's start calculating $ans_i$. 692 693 * For $i = 1$, $ans_1$ can be obtained by querying at $psum_1$ in both fenwicks. 694 * Then we remove the contribution of $i = 1$ from the two fenwick trees (simply the negative of which we added above), because $i = 1$ won't be contributing to any suffix other than $1^{st}$ one. 695 * Similarly we move from left to right and calculate $ans_i$ by querying at $psum_i$ and then remove the contribution of $i^{th}$ element. 696 697 **Solution** 698 699 ``` 700 #include<bits/stdc++.h> 701 using namespace std ; 702 703 #define ll long long 704 #define pb push_back 705 #define all(v) v.begin(),v.end() 706 #define sz(a) (ll)a.size() 707 #define F first 708 #define S second 709 #define INF 2000000000000000000 710 #define popcount(x) __builtin_popcountll(x) 711 #define pll pair<ll,ll> 712 #define pii pair<int,int> 713 #define ld long double 714 715 template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; } 716 template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; } 717 718 #ifdef LOCAL 719 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 720 #else 721 #define debug(...) 2401 722 #endif 723 724 725 const int MOD=1000000007; 726 struct Mint { 727 int val; 728 729 Mint(long long v = 0) { 730 if (v < 0) 731 v = v % MOD + MOD; 732 if (v >= MOD) 733 v %= MOD; 734 val = v; 735 } 736 737 static int mod_inv(int a, int m = MOD) { 738 int g = m, r = a, x = 0, y = 1; 739 while (r != 0) { 740 int q = g / r; 741 g %= r; swap(g, r); 742 x -= q * y; swap(x, y); 743 } 744 return x < 0 ? x + m : x; 745 } 746 explicit operator int() const { 747 return val; 748 } 749 Mint& operator+=(const Mint &other) { 750 val += other.val; 751 if (val >= MOD) val -= MOD; 752 return *this; 753 } 754 Mint& operator-=(const Mint &other) { 755 val -= other.val; 756 if (val < 0) val += MOD; 757 return *this; 758 } 759 static unsigned fast_mod(uint64_t x, unsigned m = MOD) { 760 #if !defined(_WIN32) || defined(_WIN64) 761 return x % m; 762 #endif 763 unsigned x_high = x >> 32, x_low = (unsigned) x; 764 unsigned quot, rem; 765 asm("divl %4\n" 766 : "=a" (quot), "=d" (rem) 767 : "d" (x_high), "a" (x_low), "r" (m)); 768 return rem; 769 } 770 Mint& operator*=(const Mint &other) { 771 val = fast_mod((uint64_t) val * other.val); 772 return *this; 773 } 774 Mint& operator/=(const Mint &other) { 775 return *this *= other.inv(); 776 } 777 friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; } 778 friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; } 779 friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; } 780 friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; } 781 Mint& operator++() { 782 val = val == MOD - 1 ? 0 : val + 1; 783 return *this; 784 } 785 Mint& operator--() { 786 val = val == 0 ? MOD - 1 : val - 1; 787 return *this; 788 } 789 Mint operator++(int32_t) { Mint before = *this; ++*this; return before; } 790 Mint operator--(int32_t) { Mint before = *this; --*this; return before; } 791 Mint operator-() const { 792 return val == 0 ? 0 : MOD - val; 793 } 794 bool operator==(const Mint &other) const { return val == other.val; } 795 bool operator!=(const Mint &other) const { return val != other.val; } 796 Mint inv() const { 797 return mod_inv(val); 798 } 799 Mint power(long long p) const { 800 assert(p >= 0); 801 Mint a = *this, result = 1; 802 while (p > 0) { 803 if (p & 1) 804 result *= a; 805 806 a *= a; 807 p >>= 1; 808 } 809 return result; 810 } 811 friend ostream& operator << (ostream &stream, const Mint &m) { 812 return stream << m.val; 813 } 814 friend istream& operator >> (istream &stream, Mint &m) { 815 return stream>>m.val; 816 } 817 }; 818 819 template<typename T=long long> 820 struct fenwick { 821 vector<T> bit; 822 int n; 823 fenwick(int x) { 824 n = x; 825 bit.resize(x + 1, T(0)); 826 } 827 void update(int j,T val) 828 { 829 for(;j<=n;j+=j&-j) 830 bit[j] += val; 831 } 832 T get(int r) 833 { 834 T u = 0; 835 for(;r;r-=r&-r) 836 u += bit[r]; 837 return u; 838 } 839 T query(int l,int r) 840 { 841 return get(r)-get(l-1); 842 } 843 // kth element 844 int getKth(T k) { 845 int ans = 0; 846 T cnt = 0; 847 for(int i=20;i>=0;--i) { 848 if(ans + (1 << i) <= n && cnt + bit[ans + (1 << i)] < k) { 849 ans += (1 << i); 850 cnt += bit[ans]; 851 } 852 } 853 if(ans == n) { 854 return -1; 855 } 856 return ans + 1; 857 } 858 void insert(int x) { 859 update(x, 1); 860 } 861 void erase(int x) { 862 update(x, -1); 863 } 864 }; 865 int _runtimeTerror_() 866 { 867 int n; 868 int Q; 869 cin >> n >> Q; 870 vector<array<int,2>> a(n); 871 for(int i=0;i<n;++i) { 872 cin >> a[i][0]; 873 } 874 for(int i=0;i<n;++i) { 875 cin >> a[i][1]; 876 } 877 vector<Mint> val(n, 0); 878 for(int i=n-1;i>=0;--i) { 879 if(i < n - 1) { 880 val[i] = val[i + 1]; 881 } 882 val[i] += a[i][0] * Mint(abs(a[i][1])); 883 } 884 auto solve = [&](vector<array<int,2>> &a) { 885 886 ll psum = 0; 887 vector<ll> psums; 888 psums.push_back(0); 889 for(int i=0;i<n;++i) { 890 psum += a[i][1]; 891 assert(a[i][1] != 0); 892 psums.push_back(psum); 893 } 894 sort(all(psums)); 895 psums.resize(unique(all(psums)) - psums.begin()); 896 psum = 0; 897 auto get_next = [&](ll x) { 898 return lower_bound(all(psums), x) - psums.begin() + 1; 899 }; 900 fenwick<Mint> f1(2*n), f2(2*n), f3(2*n); 901 for(int i=0;i<n;++i) { 902 if(a[i][1] > 0) { 903 f1.update(1, Mint(a[i][1]) * a[i][0]); 904 f1.update(get_next(psum), -Mint(a[i][1]) * a[i][0]); 905 906 f2.update(get_next(psum), a[i][0]); 907 f2.update(get_next(psum + a[i][1]), -a[i][0]); 908 909 f3.update(get_next(psum), Mint(a[i][0]) * Mint(psum + a[i][1])); 910 f3.update(get_next(psum + a[i][1]), -Mint(a[i][0]) * (psum + a[i][1])); 911 } 912 psum += a[i][1]; 913 } 914 psum = 0; 915 for(int i=0;i<n;++i) { 916 val[i] -= 2 * f1.get(get_next(psum)); 917 918 val[i] -= 2 * (f3.get(get_next(psum)) - psum * f2.get(get_next(psum))); 919 if(a[i][1] > 0) { 920 921 f1.update(1, -Mint(a[i][1]) * a[i][0]); 922 f1.update(get_next(psum), Mint(a[i][1]) * a[i][0]); 923 924 f2.update(get_next(psum), -a[i][0]); 925 f2.update(get_next(psum + a[i][1]), a[i][0]); 926 927 f3.update(get_next(psum), -Mint(a[i][0]) * Mint(psum + a[i][1])); 928 f3.update(get_next(psum + a[i][1]), Mint(a[i][0]) * (psum + a[i][1])); 929 } 930 psum += a[i][1]; 931 } 932 }; 933 solve(a); 934 for(int i=0;i<n;++i) { 935 a[i][1] = -a[i][1]; 936 } 937 solve(a); 938 val.push_back(0); 939 while(Q--) { 940 int l, r; 941 cin >> l >> r; 942 --l, --r; 943 cout << val[l] - val[r + 1] << "\n"; 944 } 945 return 0; 946 } 947 948 int main() 949 { 950 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 951 #ifdef runSieve 952 sieve(); 953 #endif 954 #ifdef NCR 955 initialize(); 956 #endif 957 int TESTS = 1; 958 //cin >> TESTS; 959 while(TESTS--) 960 _runtimeTerror_(); 961 return 0; 962 } 963 ```