2158.md (15611B)
1 Source: https://codeforces.com/blog/entry/148782 2 3 [2158A - Suspension](/contest/2158/problem/A "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") 4 5 **Hint 1** 6 7 Each red card immediately suspends a player. What is the best way to use $r$ red cards to maximize the number of distinct suspended players? 8 9 **Hint 2** 10 11 A player is suspended after receiving 2 yellow cards. With $y$ yellow cards, what is the maximum number of players you can suspend using only yellows? 12 13 **Hint 3** 14 15 If you add the maximum suspensions from red cards and yellow cards, can this total ever exceed $n$? What should happen with extra cards in that case? 16 17 **Tutorial** 18 19 Tutorial is loading... 20 21 **Solution** 22 23 ``` 24 #include<bits/stdc++.h> 25 using namespace std; 26 27 void solve(){ 28 int n,y,r; 29 cin >> n; 30 cin >> y >> r; 31 cout << min(n,r+y/2) << "\n"; 32 } 33 34 int main(){ 35 ios_base::sync_with_stdio(0); 36 cin.tie(0); 37 cout.tie(0); 38 int t; 39 cin >> t; 40 while(t--){ 41 solve(); 42 } 43 } 44 ``` 45 46 **Bonus** 47 48 How do you calculate the **minimum** number of players suspended from the game possible? 49 50 [2158B - Split](/contest/2158/problem/B "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") 51 52 **Hint 1** 53 54 Does the contribution of an element depend on its exact split $(u, v)$, or only on whether $u$ and $v$ are **odd** or **even**? 55 56 **Hint 2** 57 58 If every distinct element contributed its maximum possible amount, what would be the upper bound of the answer? 59 60 **Hint 3** 61 62 Elements with frequency of the form $4k+2$ can be split as $(2k+1,\,2k+1)$, creating $0$ size imbalance. Elements with frequency of the form $4k$ can be split as $(2k-1,\,2k+1)$, creating $2$ size imbalance. 63 64 **Hint 4** 65 66 The number of elements with odd total frequency is always even. How can these elements help correct any size imbalance? 67 68 **Hint 5** 69 70 In which situation does the size imbalance become impossible to fix, making the upper bound unreachable? 71 72 **Hint 6** 73 74 Consider the case when the number of distinct elements with frequency of the form $4k$ is **odd**. What happens if there exists **at least one** element with odd frequency? What happens if there are **no** elements with odd frequency? 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution** 81 82 ``` 83 #include<bits/stdc++.h> 84 using namespace std; 85 86 void solve(){ 87 int n; 88 cin >> n; 89 vector<int> a(2*n); 90 for(int i = 0;i < 2*n;i++){ 91 cin >> a[i]; 92 } 93 94 vector<int> cnt(2*n+1); 95 for(auto &x : a)cnt[x]++; 96 97 int x = 0,y = 0,z = 0; 98 for(int i = 1;i <= 2*n;i++){ 99 if(cnt[i] == 0)continue; 100 if(cnt[i]&1)x++; //odd elements 101 else if(cnt[i]%4)y++; //element of form 4*k + 2 102 else z++; //element of form 4*k 103 } 104 105 int ans = x+2*y+2*z; 106 if((z&1) && x == 0)ans -= 2; 107 cout << ans << "\n"; 108 } 109 110 int main(){ 111 ios_base::sync_with_stdio(0); 112 cin.tie(0); 113 cout.tie(0); 114 int t; 115 cin >> t; 116 while(t--){ 117 solve(); 118 } 119 } 120 ``` 121 122 [2158C - Annoying Game](/contest/2158/problem/C "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") 123 124 **Hint 1** 125 126 If Alice makes a move and Bob immediately performs the opposite move on the same index (and vice versa), what happens to the array? 127 128 **Hint 2** 129 130 How does the parity of $k$ affect who makes the last move and therefore who can enforce the final uncancelled change? 131 132 **Hint 3** 133 134 Using the cancellation idea, can the entire game be reduced to a simpler one with exactly $k \bmod 2$ effective moves? 135 136 **Hint 4** 137 138 If Alice changes $a_i$, only subarrays containing $i$ can improve. What are the maximum-sum subarrays that **end at $i$** and **start at $i$**, and how can combining them give the best subarray passing through $i$? 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Solution** 145 146 ``` 147 #include<bits/stdc++.h> 148 using namespace std; 149 150 void solve(){ 151 int n,k; 152 cin >> n >> k; 153 vector<int> a(n),b(n); 154 for(int i = 0;i < n;i++)cin >> a[i]; 155 for(int i = 0;i < n;i++)cin >> b[i]; 156 k &= 1; //It can be reduced as 0/1 move game 157 158 vector<long long> L(n); //maximum sum non empty subarray ending at each position 159 for(int i = 0;i < n;i++){ 160 L[i] = (i && L[i-1]>0 ? L[i-1] : 0ll) + a[i]; 161 } 162 163 vector<long long> R(n); //maximum sum non empty subarray starting at each position 164 for(int i = n-1;i >= 0;i--){ 165 R[i] = (i+1<n && R[i+1]>0 ? R[i+1] : 0ll) + a[i]; 166 } 167 168 if(k == 0){ 169 long long ans = *max_element(L.begin(),L.end()); 170 cout << ans << "\n"; 171 } 172 else{ 173 long long ans = LONG_MIN; 174 for(int i = 0;i < n;i++){ 175 ans = max(ans,L[i]+R[i]-a[i]+b[i]); 176 } 177 cout << ans << "\n"; 178 } 179 } 180 181 int main(){ 182 ios_base::sync_with_stdio(0); 183 cin.tie(0); 184 cout.tie(0); 185 int t; 186 cin >> t; 187 while(t--){ 188 solve(); 189 } 190 } 191 ``` 192 193 **Bonus** 194 195 How do you calculate the final score if goals of Alice and Bob were **swapped**? 196 197 [2158D - Palindrome Flipping](/contest/2158/problem/D "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") and [abc864197532](/profile/abc864197532 "International Grandmaster abc864197532") 198 199 **Hint 1** 200 201 Instead of directly transforming $s$ into $t$, is it enough to know how to transform any string into an intermediate string? 202 203 **Hint 2** 204 205 If you know how to turn any string into $0^n$ in at most $n$ operations, how can you use that to transform $s$ into $t$ in at most $2n$ operations? 206 207 **Hint 3** 208 209 If there is at least one position $p$ with $s_p = s_{p+1}$. Can you grow a block of equal bits starting from $[p, p+1]$? 210 211 **Hint 4** 212 213 How do you ensure such a position $p$ in strictly alternating string after exactly one operation? 214 215 **Hint 5** 216 217 When trying to grow the block to the right (or left), what happens if the next bit is equal to the block's boundary bit? 218 What if it is different? Can you use flipping a palindromic block (all equal bits) to force the boundary to match the next bit? 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution** 225 226 ``` 227 #include<bits/stdc++.h> 228 using namespace std; 229 230 vector<array<int,2>> reduce(string &s){ 231 int n = s.size(); 232 vector<array<int,2>> op; 233 234 int p = -1; // position p such that two consecutive characters are same 235 for(int i = 0;i < n-1;i++){ 236 if(s[i] == s[i+1])p = i; 237 } 238 if(p == -1){ // string is alternating 239 op.push_back({0,2}); // substring of first three character must be palindrome 240 s[0] ^= 1;s[1] ^= 1; 241 p = 2; 242 } 243 244 char value = s[p+1]; 245 int L = p,R = p+1; // We maintain [L,R] such that all position in it have the same value 246 247 while(R+1 < n){ 248 if(s[R+1] != value)op.push_back({L,R}); 249 R++;value = s[R]; 250 } 251 252 while(L){ 253 if(s[L-1] != value)op.push_back({L,R}); 254 L--;value = s[L]; 255 } 256 257 if(value == '1')op.push_back({0,n-1}); // We want to make all zeroes 258 259 return op; 260 } 261 262 void solve(){ 263 int n; 264 cin >> n; 265 string s,t; 266 cin >> s >> t; 267 268 auto operation_s = reduce(s); // operations to reduce s to all zeroes 269 auto operation_t = reduce(t); // operations to reduce t to all zeroes 270 271 reverse(operation_t.begin(),operation_t.end()); 272 273 int moves = operation_s.size() + operation_t.size(); 274 cout << moves << "\n"; 275 for(auto &[x,y] : operation_s)cout << x+1 << " " << y+1 << "\n"; 276 for(auto &[x,y] : operation_t)cout << x+1 << " " << y+1 << "\n"; 277 278 } 279 280 int main(){ 281 ios_base::sync_with_stdio(0); 282 cin.tie(0); 283 cout.tie(0); 284 int t; 285 cin >> t; 286 while(t--){ 287 solve(); 288 } 289 } 290 ``` 291 292 [2158E - Sink](/contest/2158/problem/E "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") 293 294 **Hint 1** 295 296 How would you solve the problem if every value in the grid was distinct? 297 298 **Hint 2** 299 300 When some cells have the same value, is it natural to treat a connected component of equal valued cells as a single group? 301 For such a group, how can you decide whether this entire group **needs** a hole? 302 303 **Hint 3** 304 305 After a single query (decreasing the value of one cell), can the beauty increase by more than 1? 306 How many groups from previous grid can stop needing a hole because they now have a strictly smaller neighbour? 307 308 **Hint 4** 309 310 How can you model the evolution of the grid as a graph, where edges reflect either adjacency in the grid or "time adjacency" between different versions of the same cell? 311 312 **Hint 5** 313 314 If a cell receives $k$ decreasing updates over all queries, can you model it as a chain of $k+1$ nodes (one per value over time)? 315 How does connecting each new node to the latest versions of its neighbours help you maintain connected components of equal values efficiently? 316 317 **Tutorial** 318 319 Tutorial is loading... 320 321 **Solution** 322 323 ``` 324 #include<bits/stdc++.h> 325 using namespace std; 326 327 const int N = 400005; 328 int parent[N],siz[N],important[N],val[N]; 329 330 void make_set(int v,int x) { 331 parent[v] = v;siz[v] = 1;important[v] = 1;val[v] = x; 332 } 333 334 int find_set(int v) { 335 if (v == parent[v])return v; 336 return parent[v] = find_set(parent[v]); 337 } 338 339 void union_sets(int a, int b) { 340 a = find_set(a); 341 b = find_set(b); 342 if (a != b) { 343 if (siz[a] < siz[b])swap(a, b); 344 parent[b] = a; 345 siz[a] += siz[b]; 346 important[a] = min(important[a],important[b]); 347 } 348 } 349 350 int n,m; 351 352 vector<array<int,2>> neighbours(int r,int c){ 353 vector<array<int,2>> v; 354 if(r)v.push_back({r-1,c}); 355 if(r+1 < n)v.push_back({r+1,c}); 356 if(c)v.push_back({r,c-1}); 357 if(c+1 < m)v.push_back({r,c+1}); 358 return v; 359 } 360 361 void solve() 362 { 363 cin >> n >> m; 364 vector<vector<int>> a(n,vector<int>(m)); // latest value of a given cell 365 vector<vector<int>> ls(n,vector<int>(m)); // latest node created for a given cell 366 for(int i = 0;i < n;i++){ 367 for(int j = 0;j < m;j++){ 368 cin >> a[i][j]; 369 ls[i][j] = m*i+j; 370 } 371 } 372 373 for(int i = 0;i < n;i++){ 374 for(int j = 0;j < m;j++){ 375 make_set(m*i+j,a[i][j]); 376 for(auto &[p,q] : neighbours(i,j)){ 377 if(a[p][q] < a[i][j])important[m*i+j] = 0; 378 } 379 } 380 } 381 382 for(int i = 0;i < n;i++){ 383 for(int j = 0;j < m;j++){ 384 for(auto &[p,q] : neighbours(i,j)){ 385 if(a[p][q] == a[i][j])union_sets(m*i+j,m*p+q); 386 } 387 } 388 } 389 390 int ans = 0; 391 for(int i = 0;i < n;i++){ 392 for(int j = 0;j < m;j++){ 393 if(parent[m*i+j] == m*i+j)ans+=important[m*i+j]; 394 } 395 } 396 397 cout << ans << "\n"; 398 399 int q; 400 cin >> q; 401 int nd = n*m; 402 403 for(int i = 0;i < q;i++){ 404 int r,c,x; 405 cin >> r >> c >> x; 406 r--;c--; 407 x = a[r][c] - x; 408 set<int> s; 409 410 int mn = INT_MAX; 411 for(auto &[p,q] : neighbours(r,c)){ 412 s.insert(find_set(ls[p][q])); 413 mn = min(mn,a[p][q]); 414 } 415 s.insert(find_set(ls[r][c])); 416 417 for(auto &y : s){ 418 ans -= important[y]; 419 } 420 421 for(auto &y : s){ 422 if(val[y] > x)important[y] = 0; 423 } 424 425 make_set(nd,x); 426 if(mn < x)important[nd] = 0; 427 else important[nd] = 1; 428 429 430 for(auto &y : s){ 431 if(val[y] == x){ 432 union_sets(y,nd); 433 } 434 } 435 436 a[r][c] = x; 437 ls[r][c] = nd++; 438 439 s.clear(); 440 for(auto &[p,q] : neighbours(r,c)){ 441 s.insert(find_set(ls[p][q])); 442 } 443 s.insert(find_set(ls[r][c])); 444 445 for(auto &y : s){ 446 ans += important[y]; 447 } 448 449 cout << ans << "\n"; 450 } 451 452 } 453 454 signed main(){ 455 ios_base::sync_with_stdio(0); 456 cin.tie(0); 457 cout.tie(0); 458 int t; 459 cin >> t; 460 while(t--) 461 solve(); 462 return 0; 463 } 464 ``` 465 466 [2158F2 - Distinct GCDs (Hard Version)](/contest/2158/problem/F2 "Codeforces Round 1067 (Div. 2)") Idea & Solution: [koderkushy](/profile/koderkushy "Candidate Master koderkushy") 467 468 **Tutorial** 469 470 Tutorial is loading... 471 472 **Solution (Python)** 473 474 ``` 475 from copy import deepcopy 476 477 def get_nums(k: int=10): 478 nums = [ 479 2**(i + j) * 3**i * 5**j * 7**(k-1-i) * 11**(k-1-j) 480 for i in range(k) for j in range(k) 481 ] 482 483 return nums 484 485 def eulerian_paths(max_k: int = 100): 486 paths = [[], [0, 0], [1,1,0,0]] 487 488 for k in range(3, max_k + 1): 489 path = deepcopy(paths[k - 2]) 490 x, y = k-2, k-1 491 492 if k % 2: 493 path.extend([x, x, y, y]) 494 for j in range(1, x, 2): 495 path.extend([j, x, j+1, y]) 496 path.append(0) 497 else: 498 path.extend([x, x, 1, y, y]) 499 for j in range(2, x, 2): 500 path.extend([j, x, j+1, y]) 501 path.append(0) 502 503 paths.append(path) 504 505 return paths 506 507 def path_len(k: int): 508 return 1 + (k*k+k)//2 - (0 if k%2 else k//2-1) 509 510 if __name__ == "__main__": 511 nums = get_nums(10) 512 paths = eulerian_paths(100) 513 514 for i in range(1, 101): 515 assert len(paths[i]) == path_len(i) 516 517 t = int(input()) 518 519 for _ in range(t): 520 n = int(input()) 521 522 l, r = 0, 100 523 while l < r-1: 524 m = r - (r-l)//2 525 if path_len(m) < n: 526 l = m 527 else: 528 r = m 529 530 path = paths[r] 531 assert len(path) >= n 532 533 a = [nums[i] for i in path[: n]] 534 print(*a) 535 ``` 536 537 **Solution (C++)** 538 539 ``` 540 #include "bits/stdc++.h" 541 using namespace std; 542 543 constexpr int64_t poww (int64_t a, int64_t p) { 544 assert(p >= 0); 545 int64_t res = 1; 546 while (p > 0) { 547 if (p & 1) res *= a; 548 a *= a, p >>= 1; 549 } 550 return res; 551 } 552 553 constexpr int32_t path_len(const int32_t n) { 554 return 1 + (n*n + n) / 2 - (n % 2 ? 0: n/2 - 1); 555 } 556 557 vector nums(0, 0ll); 558 vector walks(0, vector(0, 0)); 559 560 void load_nums(const size_t p=10) { 561 nums.resize(p * p); 562 563 for (int i = 0; i < p; ++i) 564 for (int j = 0; j < p; ++j) 565 nums[i * 10 + j] = poww(2,(i+j)) * poww(3,i) * poww(5,j) * poww(7,(9-i)) * poww(11,(9-j)); 566 } 567 568 void load_walks(const size_t max_k=100) { 569 walks.resize(max_k + 1); 570 walks[1] = vector({0, 0}); 571 walks[2] = vector({1, 1, 0, 0}); 572 573 for (int k = 3; k <= max_k; k++) { 574 auto& walk = walks[k]; 575 walk = walks[k - 2]; 576 const int x = k-2, y = k-1; 577 578 if (k % 2) { 579 walk.push_back(x); 580 walk.push_back(x); 581 walk.push_back(y); 582 walk.push_back(y); 583 for (int j = 1; j < x; j += 2) 584 walk.push_back(j), 585 walk.push_back(x), 586 walk.push_back(j+1), 587 walk.push_back(y); 588 walk.push_back(0); 589 } else { 590 walk.push_back(x); 591 walk.push_back(x); 592 walk.push_back(1); 593 walk.push_back(y); 594 walk.push_back(y); 595 for (int j = 2; j < x; j += 2) 596 walk.push_back(j), 597 walk.push_back(x), 598 walk.push_back(j+1), 599 walk.push_back(y); 600 walk.push_back(0); 601 } 602 } 603 } 604 605 void solve (const int kase) { 606 607 int n; cin >> n; 608 609 int l = 0, r = 100; 610 while (l < r - 1) { 611 int m = r - (r-l) / 2; 612 if (path_len(m) < n) 613 l = m; 614 else 615 r = m; 616 } 617 618 vector a(n, 0ll); 619 for (size_t i = 0; i < n; ++i) { 620 a[i] = nums[walks[r][i]]; 621 cout << a[i] << ' ' ; 622 } 623 624 vector gcds(n-1, 0ll); 625 for (size_t i = 1; i < n; ++i) { 626 gcds[i-1] = gcd(a[i], a[i - 1]); 627 } 628 629 assert(set(gcds.begin(), gcds.end()).size() == n-1); 630 631 cout << '\n'; 632 } 633 634 int main () { 635 ios_base::sync_with_stdio(0), cin.tie(0); 636 637 load_nums(); 638 load_walks(); 639 640 for (size_t i = 1 ; i < 101; ++i) 641 assert(walks[i].size() == path_len(i)); 642 643 int t; cin >> t, assert(t >= 0); 644 for (int i = 0; t--; ) 645 solve(++i); 646 647 } 648 ```