2140.md (15515B)
1 Source: https://codeforces.com/blog/entry/146218 2 3 [2140A - Shift Sort](/contest/2140/problem/A "Codeforces Round 1049 (Div. 2)") 4 5 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 using ll = long long; 17 18 int main(){ 19 20 int tt; 21 cin >> tt; 22 23 while(tt--){ 24 25 int n; 26 string s; 27 cin >> n >> s; 28 29 int ans = 0; 30 31 string p = s; 32 sort(p.begin(), p.end()); 33 34 for(int i = 0; i < n; i++) if(s[i] != p[i]) ans++; 35 36 cout << ans / 2 << '\n'; 37 38 } 39 return 0; 40 } 41 ``` 42 43 [2140B - Another Divisibility Problem](/contest/2140/problem/B "Codeforces Round 1049 (Div. 2)") 44 45 Idea: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever") 46 47 **Solution** 48 49 Tutorial is loading... 50 51 **Code** 52 53 ``` 54 #include<bits/stdc++.h> 55 using namespace std; 56 57 int main(){ 58 int t; 59 cin >> t; 60 while(t--){ 61 int x; 62 cin >> x; 63 cout << 2*x<< '\n'; 64 } 65 return 0; 66 } 67 ``` 68 69 [2140C - Ultimate Value](/contest/2140/problem/C "Codeforces Round 1049 (Div. 2)") 70 71 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever") 72 73 **Solution** 74 75 Tutorial is loading... 76 77 **Code** 78 79 ``` 80 #include <bits/stdc++.h> 81 using namespace std; 82 using ll = long long; 83 84 int main(){ 85 86 int tt; 87 cin >> tt; 88 89 while(tt--){ 90 91 int n; 92 cin >> n; 93 94 vector<long long> a(n); 95 for(int i = 0; i < n; i++){ 96 cin >> a[i]; 97 } 98 99 ll ans = 0; 100 for(int i = 0; i < n; i++){ 101 if(i % 2) ans -= a[i]; 102 else ans += a[i]; 103 } 104 105 ll init = ans; 106 107 for(int i = 0; i < n; i++) ans = max(ans, init + i - (i % 2)); 108 109 ll min_even = LLONG_MAX / 2, min_odd = LLONG_MAX / 2; 110 for(int i = 0; i < n; i++){ 111 if(i % 2){ 112 ans = max(init + i + a[i] + a[i] - min_even, ans); 113 min_odd = min(min_odd, i - a[i] - a[i]); 114 } 115 else{ 116 ans = max(init + i - a[i] - a[i] - min_odd, ans); 117 min_even = min(min_even, i + a[i] + a[i]); 118 } 119 } 120 121 cout << ans << '\n'; 122 123 } 124 125 return 0; 126 } 127 ``` 128 129 [2140D - A Cruel Segment's Thesis](/contest/2140/problem/D "Codeforces Round 1049 (Div. 2)") 130 131 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [shorya1835](/profile/shorya1835 "Master shorya1835") 132 133 **Solution** 134 135 Tutorial is loading... 136 137 **Code** 138 139 ``` 140 #include<bits/stdc++.h> 141 using namespace std; 142 143 typedef long long ll; 144 typedef vector<int> vi; 145 typedef vector<ll> vl; 146 typedef set<int> si; 147 typedef pair<int, int> pi; 148 typedef pair<ll, ll> pl; 149 150 #define fo(i, a, b) for (ll i = a; i < b; i++) 151 #define F first 152 #define S second 153 #define pb push_back 154 #define mp make_pair 155 156 int main() { 157 cin.tie(0)->sync_with_stdio(0); 158 cin.exceptions(cin.failbit); 159 ll T, n; 160 cin >> T; 161 while (T--) { 162 cin >> n; 163 vector<pl> a(n); 164 fo(i, 0, n)cin >> a[i].first >> a[i].second; 165 ll ans = 0; 166 fo(i, 0, n)ans += a[i].second - a[i].first + 1; 167 ans += n / 2; 168 vector<pair<ll, pl>> b(n); 169 fo(i, 0, n) { 170 b[i].second = a[i]; 171 b[i].first = a[i].first + a[i].second; 172 } 173 sort(b.begin(), b.end()); 174 if (n % 2 == 0) { 175 fo(i, 0, n) { 176 ans += a[i].second; 177 } 178 fo(i, 0, n / 2) { 179 ans -= b[i].first; 180 } 181 cout << ans - n - n / 2 << "\n"; 182 } 183 else { 184 ll k = 0, w = 0; 185 fo(i, 0, n) { 186 w += a[i].second; 187 } 188 fo(i, 0, n / 2+1) { 189 w-= b[i].first; 190 } 191 fo(i, 0, n / 2 + 1) { 192 k = max(k, w + b[i].S.F); 193 } 194 w += b[n / 2].first; 195 fo(i, n / 2 + 1, n) { 196 k = max(k, w - b[i].S.S); 197 } 198 cout << ans + k - n - n / 2 << "\n"; 199 } 200 } 201 } 202 ``` 203 204 [2140E1 - Prime Gaming (Easy Version)](/contest/2140/problem/E1 "Codeforces Round 1049 (Div. 2)") 205 206 Idea: [Divine_Spark](/profile/Divine_Spark "Master Divine_Spark") Preparation: [shorya1835](/profile/shorya1835 "Master shorya1835") 207 208 **Solution** 209 210 Tutorial is loading... 211 212 **Code** 213 214 ``` 215 #include <bits/stdc++.h> 216 using namespace std; 217 218 typedef long long ll; 219 int removebit(int n, int bit) 220 { 221 int msk = (1 << 22); 222 int filtermask = msk - (1 << bit); 223 return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1)); 224 } 225 const ll MOD = 1e9+7; 226 class mint 227 { 228 public: 229 ll val; 230 static ll mod_exp(ll a, ll b) 231 { 232 ll res = 1; 233 a = a % MOD; 234 while (b > 0) 235 { 236 if (b % 2 == 1) 237 res = (res * a) % MOD; 238 b /= 2; 239 a = (a * a) % MOD; 240 } 241 return res; 242 } 243 static ll gcdExtended(ll a, ll b, ll *x, ll *y) 244 { 245 if (a == 0) 246 { 247 *x = 0, *y = 1; 248 return b; 249 } 250 ll x1, y1; 251 ll gcd = gcdExtended(b % a, a, &x1, &y1); 252 *x = y1 - (b / a) * x1; 253 *y = x1; 254 return gcd; 255 } 256 static ll modInverse(ll a) 257 { 258 ll x, y; 259 ll g = gcdExtended(a, MOD, &x, &y); 260 g++; 261 ll res = (x % MOD); 262 if (res < 0) 263 res += MOD; 264 return res; 265 } 266 mint() { val = 0; } 267 mint(ll x) 268 { 269 val = x % MOD; 270 if (val < 0) 271 val += MOD; 272 } 273 mint &operator+=(const mint &other) 274 { 275 val += other.val; 276 if (val >= MOD) 277 val -= MOD; 278 return (*this); 279 } 280 mint &operator-=(const mint &other) 281 { 282 val -= other.val; 283 if (val < 0) 284 val += MOD; 285 return (*this); 286 } 287 mint &operator*=(const mint &other) 288 { 289 val = (val * other.val) % MOD; 290 return (*this); 291 } 292 mint &operator/=(const mint &other) 293 { 294 val = (val * modInverse(other.val)) % MOD; 295 return (*this); 296 } 297 mint &operator=(const mint &other) 298 { 299 val = other.val; 300 return (*this); 301 } 302 mint operator+(const mint &other) const { return mint(*this) += other; } 303 mint operator-(const mint &other) const { return mint(*this) -= other; } 304 mint operator*(const mint &other) const { return mint(*this) *= other; } 305 mint operator/(const mint &other) const { return mint(*this) /= other; } 306 bool operator==(const mint &other) const { return val == other.val; } 307 308 mint operator++() 309 { 310 ++val; 311 if (val == MOD) 312 val = 0; 313 return (*this); 314 } 315 mint operator++(int) 316 { 317 val++; 318 if (val == MOD) 319 val = 0; 320 return mint(val - 1); 321 } 322 mint operator--() 323 { 324 --val; 325 if (val == -1) 326 val = MOD - 1; 327 return (*this); 328 } 329 mint operator--(int) 330 { 331 val--; 332 if (val == -1) 333 val = MOD - 1; 334 return mint(val + 1); 335 } 336 337 // ^ has very low precedence, careful!! 338 339 template <typename T> 340 mint &operator^=(const T &other) 341 { 342 val = mod_exp(val, other); 343 return (*this); 344 } 345 template <typename T> 346 mint operator^(const T &other) const { return mint(*this) ^= other; } 347 348 mint &operator^=(const mint &other) 349 { 350 val = mod_exp(val, other.val); 351 return (*this); 352 } 353 mint operator^(const mint &other) const { return mint(*this) ^= other; } 354 355 template <typename T> 356 explicit operator T() { return (T)val; } 357 template <typename T> 358 friend mint operator+(T other, const mint &M) { return mint(other) + M; } 359 template <typename T> 360 friend mint operator-(T other, const mint &M) { return mint(other) - M; } 361 template <typename T> 362 friend mint operator*(T other, const mint &M) { return mint(other) * M; } 363 template <typename T> 364 friend mint operator/(T other, const mint &M) { return mint(other) / M; } 365 template <typename T> 366 friend mint operator^(T other, const mint &M) { return mint(other) ^ M; } 367 368 friend std::ostream &operator<<(std::ostream &output, const mint &M) { return output << M.val; } 369 friend std::istream &operator>>(std::istream &input, mint &M) 370 { 371 input >> M.val; 372 M.val %= MOD; 373 return input; 374 } 375 }; 376 377 const int maxn = 20; 378 const int maxm = 30; 379 380 ll modpow(ll a , ll b ) { 381 ll res = 1 ; 382 a %= MOD; 383 while( b > 0 ) { 384 if( b&1 ) res = ( res*a ) % MOD; 385 a = ( a*a ) % MOD; 386 b >>= 1 ; 387 } 388 return res ; 389 } 390 391 int main() 392 { int t; 393 cin >> t; 394 while(t--){ 395 bool pl = 1; 396 int n, m; 397 cin >> n >> m; 398 int k,x; 399 cin >> k; 400 vector<int> good; 401 for(int i=0;i<k;i++){ 402 cin >> x; 403 good.push_back(x); 404 } 405 if(m==1){ 406 cout << 1<< "\n"; 407 continue; 408 } 409 vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1)); 410 int cntt = 0; 411 for (int i = 1; i <= n; i++) 412 { 413 414 dp[0][i].resize(1 << i); 415 dp[1][i].resize(1 << i); 416 if (i == 1) 417 { 418 for (int j = 0; j <= 1; j++) 419 { 420 for (int k = 0; k <= 1; k++) 421 { 422 dp[j][i][k] = k; 423 } 424 } 425 } 426 else 427 { 428 for (int msk = 0; msk < (1 << i); msk++) 429 { 430 bool ans0 = 1; 431 bool ans1 = 0; 432 for (auto x :good) 433 { 434 if (x <= i) 435 { 436 cntt++; 437 int finmsk = removebit(msk, x - 1); 438 ans0 &= dp[1][i - 1][finmsk]; 439 ans1 |= dp[0][i - 1][finmsk]; 440 } 441 else 442 { 443 break; 444 } 445 } 446 dp[0][i][msk] = ans0; 447 dp[1][i][msk] = ans1; 448 } 449 } 450 } 451 mint finans = 0; 452 for (int r = 0; r < (1<<n); r++) 453 { 454 finans += 1+dp[pl][n][r]; 455 456 } 457 cout << finans << endl; 458 } 459 } 460 ``` 461 462 [2140E2 - Prime Gaming (Hard Version)](/contest/2140/problem/E2 "Codeforces Round 1049 (Div. 2)") 463 464 Idea: [Divine_Spark](/profile/Divine_Spark "Master Divine_Spark") Preparation:[wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever"), [shorya1835](/profile/shorya1835 "Master shorya1835") 465 466 **Solution** 467 468 Tutorial is loading... 469 470 **Code** 471 472 ``` 473 #include <bits/stdc++.h> 474 using namespace std; 475 typedef long long ll; 476 const ll MOD = 1000000007; 477 int removebit(int n, int bit) 478 { 479 int msk = (1 << 22); 480 int filtermask = msk - (1 << bit); 481 return ((n >> 1) & filtermask) | (n & ((1 << bit) - 1)); 482 } 483 484 const int maxn = 20; 485 const int maxm = 30; 486 487 ll binpow(ll a,ll b,ll m = MOD){ 488 ll res = 1; 489 while (b){ 490 if (b&1) res = (res*a)%m; 491 a = (a*a)%m; 492 b>>=1; 493 } 494 return res; 495 } 496 int main() 497 { int t; 498 cin >> t; 499 while(t--){ 500 bool pl = 1; 501 int n, m; 502 cin >> n >> m; 503 int k,x; 504 cin >> k; 505 vector<int> good; 506 for(int i=0;i<k;i++){ 507 cin >> x; 508 good.push_back(x); 509 } 510 vector<vector<vector<bool>>> dp(2, vector<vector<bool>>(n + 1)); 511 vector<vector<vector<int>>> cnt(2, (n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)))); 512 int cntt = 0; 513 for (int i = 1; i <= n; i++) 514 { 515 516 dp[0][i].resize(1 << i); 517 dp[1][i].resize(1 << i); 518 if (i == 1) 519 { 520 for (int j = 0; j <= 1; j++) 521 { 522 for (int k = 0; k <= 1; k++) 523 { 524 dp[j][i][k] = k; 525 } 526 cnt[j][1][1]++; 527 } 528 } 529 else 530 { 531 for (int msk = 0; msk < (1 << i); msk++) 532 { 533 bool ans0 = 1; 534 bool ans1 = 0; 535 for (auto x :good) 536 { 537 if (x <= i) 538 { 539 cntt++; 540 int finmsk = removebit(msk, x - 1); 541 ans0 &= dp[1][i - 1][finmsk]; 542 ans1 |= dp[0][i - 1][finmsk]; 543 } 544 else 545 { 546 break; 547 } 548 } 549 dp[0][i][msk] = ans0; 550 dp[1][i][msk] = ans1; 551 cnt[0][i][__popcount(msk)] += ans0; 552 cnt[1][i][__popcount(msk)] += ans1; 553 } 554 } 555 } 556 ll finans = 0; 557 for (int r = 1; r <= n; r++) 558 { 559 for(int k=1;k<=m;k++){ 560 finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD; 561 } 562 } 563 cout << finans%MOD << endl; 564 } 565 } 566 ``` 567 568 **Bonus** 569 570 Solve the problem when piles must have distinct stones, $m \le 10^9$ and there is no constraint on sum of $m$. 571 572 [2140F - Sum Minimisation](/contest/2140/problem/F "Codeforces Round 1049 (Div. 2)") 573 574 Idea: [shorya1835](/profile/shorya1835 "Master shorya1835") Preparation: [wakanda-forever](/profile/wakanda-forever "Expert wakanda-forever"), [shorya1835](/profile/shorya1835 "Master shorya1835") 575 576 **Solution** 577 578 Tutorial is loading... 579 580 **Code** 581 582 ``` 583 #include<bits/stdc++.h> 584 using namespace std; 585 typedef long long ll; 586 typedef vector<int> vi; 587 typedef vector<ll> vl; 588 typedef set<int> si; 589 typedef pair<ll, ll> pl; 590 #define fo(i, a, b) for (ll i = a; i < b; i++) 591 #define pb push_back 592 593 ll gcd(ll a,ll b){ 594 if(a==0)return b; 595 else return gcd(b%a,a); 596 } 597 vl a; 598 ll lc, s, n; 599 bool good(){ 600 bool v=1; 601 if(n>23){ 602 fo(i,0,n){ 603 if(a[i]!=a[0]){ 604 v=0; 605 break; 606 } 607 } 608 } 609 else{ 610 fo(i,2,n){ 611 fo(j,0,n){ 612 if((a[j]%i)!=(a[0]%i)){ 613 v=0; 614 break; 615 } 616 } 617 } 618 } 619 v&=(s%n==0); 620 return v; 621 } 622 int main() { 623 cin.tie(0)->sync_with_stdio(0); 624 cin.exceptions(cin.failbit); 625 ll T; 626 cin >> T; 627 while (T--) { 628 cin >> n; 629 a.clear(); 630 a.resize(n); 631 s=0; 632 fo(i,0,n){ 633 cin >> a[i]; 634 s+=a[i]; 635 } 636 sort(a.begin(),a.end()); 637 lc=1; 638 if(n>23){ 639 lc=1e10; 640 } 641 else{ 642 fo(i,2,n+1){ 643 lc=(lc*i)/gcd(lc,i); 644 } 645 } 646 if(good()){ 647 cout << s<< "\n"; 648 continue; 649 } 650 a[0]--; 651 s--; 652 if(good()){ 653 cout << s<< "\n"; 654 continue; 655 } 656 cout << -1 << "\n"; 657 658 } 659 } 660 ``` 661 662 Thanks to [satyam343](/profile/satyam343 "Master satyam343") for his help throughout the round.