1747.md (19304B)
1 Source: https://codeforces.com/blog/entry/108782 2 3 I hope you all liked the round. Please share your feedback in the comments section. 4 5 # [1747A — Two Groups](https://codeforces.com/contest/1747/problem/A) 6 7 **Hint** 8 9 How about putting all positive numbers in one group and negative in second group 10 11 **Tutorial** 12 13 Let $S$ denotes sum of element of array $a$. 14 15 **Claim**: Answer is $|S|$. 16 17 **Proof**: Let sum of all positive elements is $S_{pos}$ and sum of all negative elements $S_{neg}$. Put all positive numbers in first group and negative numbers in second group. We get $||S_{pos}| - |S_{neg}|| = |S|$. 18 19 Let's prove that we can not do better than that. Let $S_1$ denotes sum of elements of first group and $S_2$ denotes sum of elements of second group. We have $|S_1| - |S_2| \leq |S_1 + S_2| = |S|$. Hence $|S|$ is the upperbound for the answer. 20 21 **Solution** 22 23 ``` 24 // Jai Shree Ram 25 #include<bits/stdc++.h> 26 using namespace std; 27 28 #define rep(i,a,n) for(int i=a;i<n;i++) 29 #define ll long long 30 #define int long long 31 #define pb push_back 32 #define all(v) v.begin(),v.end() 33 #define endl "\n" 34 #define x first 35 #define y second 36 #define gcd(a,b) __gcd(a,b) 37 #define mem1(a) memset(a,-1,sizeof(a)) 38 #define mem0(a) memset(a,0,sizeof(a)) 39 #define sz(a) (int)a.size() 40 #define pii pair<int,int> 41 #define hell 1000000007 42 #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 43 44 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;} 45 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;} 46 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;} 47 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;} 48 49 int solve(){ 50 int n; cin >> n; 51 int s = 0; 52 for(int i = 0; i < n; i++){ 53 int x; cin >> x; 54 s += x; 55 } 56 cout << abs(s) << endl; 57 return 0; 58 } 59 signed main(){ 60 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 61 //freopen("input.txt", "r", stdin); 62 //freopen("output.txt", "w", stdout); 63 #ifdef SIEVE 64 sieve(); 65 #endif 66 #ifdef NCR 67 init(); 68 #endif 69 int t=1;cin>>t; 70 while(t--){ 71 solve(); 72 } 73 return 0; 74 } 75 ``` 76 77 # [1747B — BAN BAN](https://codeforces.com/contest/1747/problem/B) 78 79 **Hint 1** 80 81 Instead of subsequences solve for substrings. That is there should not be any substring $\texttt{BAN}$ after performing operations. 82 83 **Hint 2** 84 85 In one operation you can destroy atmost $2$ substrings. Find minimum operations to destroy $n$ substrings. 86 87 **Answer** 88 89 $\left \lceil\frac{n}{2}\right \rceil $ 90 91 **Hint 3** 92 93 Congrats, you have solved for subsequences also! 94 95 **Tutorial** 96 97 No subsequences of string $\texttt{BAN}$ would also mean no substrings of $\texttt{BAN}$ in original string. Let minimum number of operations to have no substrings of $\texttt{BAN}$ be $x$, it would be also be the lower bound for having no subsequences of string $\texttt{BAN}$. 98 99 **Claim**: $x = \left \lceil\frac{n}{2}\right \rceil$. 100 101 **Proof**: Swap $i$-th $\texttt{B}$ from start with $i$-th $\texttt{N}$ from end for $1 \leq i \leq \left \lceil\frac{n}{2}\right \rceil$. We can see that, no substrings of $\texttt{BAN}$ exists after performing $ \left \lceil\frac{n}{2}\right \rceil$ operations. Since we can only destroy atmost $2$ substrings in one operations, $\left \lceil\frac{n}{2}\right \rceil$ is minimum possible. 102 103 Now if you see clearly, after performing above operations, there does not exist any subsequence of string $\texttt{BAN}$ in original string. Hence $\left \lceil\frac{n}{2}\right \rceil$ is also the answer for the original problem. 104 105 **Solution** 106 107 ``` 108 // Jai Shree Ram 109 110 #include<bits/stdc++.h> 111 using namespace std; 112 113 #define rep(i,a,n) for(int i=a;i<n;i++) 114 #define ll long long 115 #define int long long 116 #define pb push_back 117 #define all(v) v.begin(),v.end() 118 #define endl "\n" 119 #define x first 120 #define y second 121 #define gcd(a,b) __gcd(a,b) 122 #define mem1(a) memset(a,-1,sizeof(a)) 123 #define mem0(a) memset(a,0,sizeof(a)) 124 #define sz(a) (int)a.size() 125 #define pii pair<int,int> 126 #define hell 1000000007 127 #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 128 129 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;} 130 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;} 131 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;} 132 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;} 133 134 int solve(){ 135 int n; cin >> n; 136 cout << n/2 + n % 2 << endl; 137 int l = 1, r = 3*n; 138 while(l < r){ 139 cout << l << " " << r << endl; 140 l += 3; 141 r -= 3; 142 } 143 return 0; 144 } 145 signed main(){ 146 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 147 //freopen("input.txt", "r", stdin); 148 //freopen("output.txt", "w", stdout); 149 #ifdef SIEVE 150 sieve(); 151 #endif 152 #ifdef NCR 153 init(); 154 #endif 155 int t=1;cin>>t; 156 while(t--){ 157 solve(); 158 } 159 return 0; 160 } 161 ``` 162 163 # [1747C — Swap Game](https://codeforces.com/contest/1747/problem/c) 164 165 **Hint 1** 166 167 Divide problem into two different cases. When $a_1 \gt \min(a)$ and when $a_1 = \min(a)$. 168 169 **Hint 2** 170 171 You do not need more hints to solve the problem. 172 173 **Tutorial** 174 175 **Case 1**: $a_1 \gt \min(a)$ 176 177 $\texttt{Alice}$ can force the $\texttt{Bob}$ to always decrease the minimum element by always choosing minimum element of $a$ in her turn. Where as $\texttt{Bob}$ can not do much, all other elements he would swap with would be greater than or equal to $\min(a)$. Even if there exists multiple minimums in $a$, In first move $\texttt{Alice}$ would decrease from $a_1$, hence in this case $\texttt{Alice}$ would always win. 178 179 **Case 2**: $a_1 = \min(a)$ 180 181 In this case optimal startegy for $\texttt{Bob}$ would be to always chhose minimum element of the array, which is $a_1$. $\texttt{Alice}$ would always be swapping the element greater than $a_1$ in her turn, hence in the case $\texttt{Bob}$ would always win 182 183 **Solution** 184 185 ``` 186 // Jai Shree Ram 187 188 #include<bits/stdc++.h> 189 using namespace std; 190 191 #define rep(i,a,n) for(int i=a;i<n;i++) 192 #define ll long long 193 #define int long long 194 #define pb push_back 195 #define all(v) v.begin(),v.end() 196 #define endl "\n" 197 #define x first 198 #define y second 199 #define gcd(a,b) __gcd(a,b) 200 #define mem1(a) memset(a,-1,sizeof(a)) 201 #define mem0(a) memset(a,0,sizeof(a)) 202 #define sz(a) (int)a.size() 203 #define pii pair<int,int> 204 #define hell 1000000007 205 #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 206 207 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;} 208 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;} 209 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;} 210 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;} 211 212 int solve(){ 213 int n; cin >> n; 214 vector<int> a(n); 215 for(auto &i:a)cin >> i; 216 sort(a.begin() + 1,a.end()); 217 cout << (a[0] > a[1] ? "Alice" : "Bob") << endl; 218 return 0; 219 } 220 signed main(){ 221 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 222 //freopen("input.txt", "r", stdin); 223 //freopen("output.txt", "w", stdout); 224 #ifdef SIEVE 225 sieve(); 226 #endif 227 #ifdef NCR 228 init(); 229 #endif 230 int t=1;cin>>t; 231 while(t--){ 232 solve(); 233 } 234 return 0; 235 } 236 ``` 237 238 # [1747D — Yet another Problem](https://codeforces.com/contest/1747/problem/D) 239 240 **Hint 1** 241 242 Forget queries, they are just here to make problem look complicated. Solve for $q = 1$. 243 244 **Hint 2** 245 246 XOR of array does not change after operations. Hence if initially XOR is not equal to $0$, answer is $-1$. Is this condition sufficient? 247 248 **Answer** 249 250 No, We need one more condition 251 252 **Hint 3** 253 254 There must exist some prefix of odd size, such that xor of elements of that prefix is $0$. 255 256 **Tutorial** 257 258 First forget queries, solve for single array $a$. 259 260 Let's make some observations. 261 262 1. Xor of array does not change after each operation 263 2. Look at the set of prefix XORs while doing operations. Its size always decreases or remains same after each operation. Infact we can further reduce it to parities. Let $S_{0}$, $S_{1}$ be sets of prefix XOR's of parities $0$ and $1$ respectively. After each operation new sets $S'_{0}$, $S'_{1}$ will be subsets of $S_{0}$ and $S_1$ respectively. 264 265 So necessary conditions for answer to exist is that xor of array should be $0$ and $S_{1}$ should contains $0$. 266 267 Now comes to minimum operations. 268 269 **Claim:** If above conditions are satisfied, its always possible to make all elements $0$ in less than or equal to $2$ operations 270 271 **Proof:** Let length of array be $n$. 272 273 **Case 1:** $n$ is odd 274 275 Just apply the operation on whole array. 276 277 **Case 2:** $n$ is even 278 279 There will exists some odd size prefix $j$ such that xor of its elements is $0$. Apply operation on $[1,j]$ and $[j + 1,n]$. It can happen that $j = 1$ or $j = n - 1$, in that case we only need one operation, because other remaining element would already be equal to $0$. 280 281 To solve for queries, you just need to check for odd prefix, which can be done using some data structure like $\texttt{std::map}$ or $\texttt{std::set}$ in C++. Do not forget to check the case when all elements are already $0$. 282 283 **Solution** 284 285 ``` 286 #include<bits/stdc++.h> 287 using namespace std ; 288 289 #define ll long long 290 #define pb push_back 291 #define all(v) v.begin(),v.end() 292 #define sz(a) (ll)a.size() 293 #define F first 294 #define S second 295 #define INF 2000000000000000000 296 #define popcount(x) __builtin_popcountll(x) 297 #define pll pair<ll,ll> 298 #define pii pair<int,int> 299 #define ld long double 300 301 template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; } 302 template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; } 303 304 #ifdef LOCAL 305 #define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__) 306 #else 307 #define debug(...) 3000 308 #endif 309 310 int _runtimeTerror_() 311 { 312 int n, Q; 313 cin >> n >> Q; 314 map<int, int> odd, even; 315 vector<int> last_nz(n + 1, 0), last(n + 1, -1), pxor(n + 1, 0); 316 vector<int> a(n + 1); 317 even[0] = 0; 318 int cur = 0; 319 for(int i=1;i<=n;++i) { 320 cin >> a[i]; 321 cur ^= a[i]; 322 pxor[i] = cur; 323 if(a[i] == 0) { 324 last_nz[i] = last_nz[i - 1]; 325 } 326 else { 327 last_nz[i] = i; 328 } 329 if(i & 1) { 330 if(even.count(cur)) { 331 last[i] = even[cur]; 332 } 333 odd[cur] = i; 334 } 335 else { 336 if(odd.count(cur)) { 337 last[i] = odd[cur]; 338 } 339 even[cur] = i; 340 } 341 } 342 while(Q--) { 343 int l, r; 344 cin >> l >> r; 345 if(pxor[l - 1] != pxor[r]) { 346 cout << "-1\n"; 347 } 348 else if(last_nz[r] < l) { 349 cout << "0\n"; 350 } 351 else if(r % 2 == l % 2) { 352 cout << "1\n"; 353 } 354 else if(a[l] == 0 or a[r] == 0) { 355 cout << "1\n"; 356 } 357 else if(last[r] >= l) { 358 cout << "2\n"; 359 } 360 else { 361 cout << "-1\n"; 362 } 363 } 364 return 0; 365 } 366 367 int main() 368 { 369 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 370 #ifdef runSieve 371 sieve(); 372 #endif 373 #ifdef NCR 374 initncr(); 375 #endif 376 int TESTS = 1; 377 //cin >> TESTS; 378 while(TESTS--) { 379 _runtimeTerror_(); 380 } 381 return 0; 382 } 383 ``` 384 385 # [1747E — List Generation](https://codeforces.com/contest/1747/problem/E) 386 387 **Hint 1** 388 389 Change your point of view from array to grid. Think of pair of arrays as paths in grid of size $(n + 1) \times (m + 1)$. 390 391 **Hint 2** 392 393 First try counting number of good pair of arrays. 394 395 **answer** 396 397 Number of good pairs of arrays comes out to be $\sum\limits_{k = 0}{k = \min(n,m} \binom{n}{k} \cdot \binom{m}{k} \cdot 2^{n + m - k - 1}$ 398 399 **Tutorial** 400 401 Given problem is equivalent to: 402 403 You are currently at cell $(0,0)$. From any cell $(x,y)$ you can jump to cell $(x',y')$ such that $x \leq x' \leq n$ , $y \leq y' \leq m$ and $(x,y) \neq (x',y')$. Find sum of number of visited cells over all paths starting from $(0,0)$ and ending at $(n,m)$. Denote the required value by $f(n,m)$. 404 405 Directly thinking in $2$ dimensions is difficult, lets first solve for case when $n = 0$ or $m = 0$. WLOG, assuming $m = 0$. We can solve this case using some binomials. 406 407 $f(n,0) = 2^{n - 1} \cdot \frac{n + 3}{2}$, $n \gt 0$. 408 409 Now, we can divide all possible paths from $(0,0)$ to $(n,m)$ into several classes of one dimensional paths. 410 411 These classes are defined by what I call *breakpoints*. When we passes the breakpoint we turns right. Hence we can group paths by fixing the number of breakpoints. 412 413 WLOG, Assuming $n \geq m$. For $k$ breakpoints there are $\binom{n}{k} \cdot \binom{m}{k}$ ways to select for $0 \leq k \leq m $. For a path with $k$ breakpoints, $n + m - k$ points are *optional*, that is there will exist $2^{n + m - k}$ paths with $k$ breakpoints. It is not difficult to see that sum of number of visited cells over paths with $k$ breakpoints turned out to be $f(n + m - k,0) + 2^{n + m - k - 1}\cdot k$. Hence we can write $f(n,m) = \sum\limits_{k = 0}^{m} \binom{n}{k} \cdot \binom{m}{k} \cdot (f(n + m - k,0) + 2^{n + m - k - 1}\cdot k)$ 414 415 Time complexity of the solution would be $\mathcal{O}(\min(n,m))$ 416 417 **Solution** 418 419 ``` 420 // Jai Shree Ram 421 422 #include<bits/stdc++.h> 423 using namespace std; 424 425 #define rep(i,a,n) for(int i=a;i<n;i++) 426 #define ll long long 427 #define int long long 428 #define pb push_back 429 #define all(v) v.begin(),v.end() 430 #define endl "\n" 431 #define x first 432 #define y second 433 #define gcd(a,b) __gcd(a,b) 434 #define mem1(a) memset(a,-1,sizeof(a)) 435 #define mem0(a) memset(a,0,sizeof(a)) 436 #define sz(a) (int)a.size() 437 #define pii pair<int,int> 438 #define hell 1000000007 439 #define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 440 441 template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;} 442 template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;} 443 template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;} 444 template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;} 445 446 const int MOD = hell; 447 448 struct mod_int { 449 int val; 450 451 mod_int(long long v = 0) { 452 if (v < 0) 453 v = v % MOD + MOD; 454 455 if (v >= MOD) 456 v %= MOD; 457 458 val = v; 459 } 460 461 static int mod_inv(int a, int m = MOD) { 462 int g = m, r = a, x = 0, y = 1; 463 464 while (r != 0) { 465 int q = g / r; 466 g %= r; swap(g, r); 467 x -= q * y; swap(x, y); 468 } 469 470 return x < 0 ? x + m : x; 471 } 472 473 explicit operator int() const { 474 return val; 475 } 476 477 mod_int& operator+=(const mod_int &other) { 478 val += other.val; 479 if (val >= MOD) val -= MOD; 480 return *this; 481 } 482 483 mod_int& operator-=(const mod_int &other) { 484 val -= other.val; 485 if (val < 0) val += MOD; 486 return *this; 487 } 488 489 static unsigned fast_mod(uint64_t x, unsigned m = MOD) { 490 #if !defined(_WIN32) || defined(_WIN64) 491 return x % m; 492 #endif 493 unsigned x_high = x >> 32, x_low = (unsigned) x; 494 unsigned quot, rem; 495 asm("divl %4\n" 496 : "=a" (quot), "=d" (rem) 497 : "d" (x_high), "a" (x_low), "r" (m)); 498 return rem; 499 } 500 501 mod_int& operator*=(const mod_int &other) { 502 val = fast_mod((uint64_t) val * other.val); 503 return *this; 504 } 505 506 mod_int& operator/=(const mod_int &other) { 507 return *this *= other.inv(); 508 } 509 510 friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; } 511 friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; } 512 friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; } 513 friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; } 514 515 mod_int& operator++() { 516 val = val == MOD - 1 ? 0 : val + 1; 517 return *this; 518 } 519 520 mod_int& operator--() { 521 val = val == 0 ? MOD - 1 : val - 1; 522 return *this; 523 } 524 525 mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; } 526 mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; } 527 528 mod_int operator-() const { 529 return val == 0 ? 0 : MOD - val; 530 } 531 532 bool operator==(const mod_int &other) const { return val == other.val; } 533 bool operator!=(const mod_int &other) const { return val != other.val; } 534 535 mod_int inv() const { 536 return mod_inv(val); 537 } 538 539 mod_int pow(long long p) const { 540 assert(p >= 0); 541 mod_int a = *this, result = 1; 542 543 while (p > 0) { 544 if (p & 1) 545 result *= a; 546 547 a *= a; 548 p >>= 1; 549 } 550 551 return result; 552 } 553 554 friend ostream& operator<<(ostream &stream, const mod_int &m) { 555 return stream << m.val; 556 } 557 friend istream& operator >> (istream &stream, mod_int &m) { 558 return stream>>m.val; 559 } 560 }; 561 #define NCR 562 const int N = 5e6 + 5; 563 mod_int fact[N],inv[N],invv[N]; 564 void init(int n=N){ 565 fact[0]=inv[0]=inv[1]=1; 566 invv[0] = invv[1] = 1; 567 rep(i,1,N)fact[i]=i*fact[i-1]; 568 rep(i,2,N){ 569 invv[i] = (MOD - MOD/i)*invv[MOD % i]; 570 inv[i] = invv[i]*inv[i - 1]; 571 } 572 } 573 mod_int C(int n,int r){ 574 if(r>n || r<0)return 0; 575 return fact[n]*inv[n-r]*inv[r]; 576 } 577 578 int solve(){ 579 int n,m; cin >> n >> m; 580 if(m > n)swap(n,m); 581 auto brute = [&](){ 582 vector<vector<mod_int>>dp(n + 1,vector<mod_int>(m + 1)); 583 vector<vector<mod_int>>exp(n + 1,vector<mod_int>(m + 1)); 584 dp[0][0] = 1; 585 exp[0][0] = 0; 586 for(int i = 0; i <= n; i++){ 587 for(int j = 0; j <= m; j++){ 588 if(i + j == 0)continue; 589 for(int x = 0; x <= i; x++){ 590 for(int y = 0; y <= j; y++){ 591 if(x + y == i + j)continue; 592 dp[i][j] += dp[x][y]; 593 exp[i][j] += (exp[x][y] + dp[x][y]); 594 } 595 } 596 } 597 } 598 return exp[n][m] + dp[n][m]; 599 }; 600 auto correct = [&](){ 601 mod_int in = mod_int(2).inv(); 602 auto d = [&](int x){ 603 mod_int val = x + 1; 604 return val * in; 605 }; 606 mod_int ans = 0; 607 mod_int pw = mod_int(2).pow(n + m); 608 for(int i = 0; i <= m; i++){ 609 pw *= in; 610 ans += C(n,i)*C(m,i)*pw*(i + d(n + m - i) + 1); 611 } 612 return ans; 613 }; 614 cout << correct() << endl; 615 616 return 0; 617 } 618 signed main(){ 619 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 620 //freopen("input.txt", "r", stdin); 621 //freopen("output.txt", "w", stdout); 622 #ifdef SIEVE 623 sieve(); 624 #endif 625 #ifdef NCR 626 init(); 627 #endif 628 int t=1;cin>>t; 629 while(t--){ 630 solve(); 631 } 632 return 0; 633 } 634 ```