2179.md (19003B)
1 Source: https://codeforces.com/blog/entry/149406 2 3 # [2179A - Blackslex and Password](/contest/2179/problem/A "Codeforces Round 1071 (Div. 3)") 4 5 Author: [IceBorworntat](/profile/IceBorworntat "Candidate Master IceBorworntat") 6 7 **Hint 1** 8 9 Think about the indices that have the same remainder after division by $x$. 10 11 **Solution** 12 13 Consider the subsequence formed from the indices that have the same remainder after division by $x$. There are $x$ such subsequences. Each subsequence contains distinct characters, so the maximum length of such subsequences is $k$. As such, the minimum string length that cannot be constructed is $n = kx+1$. 14 15 Time complexity: $\mathcal{O}(1)$ 16 17 **Implementation (Python)** 18 19 ``` 20 t = int(input()) 21 for _ in range(t): 22 k, x = [int(i) for i in input().split()] 23 print(k*x+1) 24 ``` 25 26 # [2179B - Blackslex and Showering](/contest/2179/problem/B "Codeforces Round 1071 (Div. 3)") 27 28 Author: [spycoderyt](/profile/spycoderyt "Expert spycoderyt") 29 30 **Hint 1** 31 32 First observe that it is always helpful to remove a floor. Now the question becomes which floor to remove. 33 34 **Solution** 35 36 You can simply simulate the process of removing any possible floor. To do this efficiently, compute the current time taken and consider the change to the time taken if a floor is removed. If we remove floor $i$ where $i \neq 1$ and $i \neq n$, then the differences $|a[i] - a[i-1]|$ and $|a[i+1] - a[i]|$ are removed and the difference $|a[i-1] - a[i+1]|$ is added. If $i = 1$ or $i = n$, only the adjacent difference is removed. 37 38 Time complexity: $\mathcal{O}(n)$ 39 40 **Implementation (C++)** 41 42 ``` 43 #include <bits/stdc++.h> 44 45 using namespace std; 46 typedef long long ll; 47 48 void test_case_run() { 49 int n; 50 cin >> n; 51 52 ll a[n+1]; 53 for (int i = 1; i <= n; i++) cin >> a[i]; 54 55 ll sum = 0; 56 for (int i = 2; i <= n; i++) sum += abs(a[i]-a[i-1]); 57 58 ll ans = min(sum - abs(a[2]-a[1]), sum - abs(a[n]-a[n-1])); 59 for (int i = 2; i < n; i++) { 60 ans = min(ans, sum - abs(a[i+1]-a[i]) - abs(a[i]-a[i-1]) + abs(a[i+1]-a[i-1])); 61 } 62 63 cout << ans << "\n"; 64 } 65 66 int main() { 67 ios_base::sync_with_stdio(false); 68 cin.tie(NULL); 69 70 int t; 71 cin >> t; 72 while (t--) test_case_run(); 73 74 return 0; 75 } 76 ``` 77 78 # [2179C - Blackslex and Number Theory](/contest/2179/problem/C "Codeforces Round 1071 (Div. 3)") 79 80 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut") 81 82 **Hint 1** 83 84 Making everying zeros works often. 85 86 **Hint 2** 87 88 Sometimes, it's better to make all numbers something else that's not zero. 89 90 **Hint 3** 91 92 Following Hint 2, if we don't make everything zero, then what's our target number? 93 94 **Solution** 95 96 Sort the array from small to large. 97 98 We can mod every number in the array by itself, and this would require $k = a_1$. 99 100 For a larger value of $k$, we cannot modify the value of $a_1$, so every number must be made into $a_1$. We can mod $a_i$ with $a_i - a_1$, using $k = a_2 - a_1$. 101 102 The answer is thus $\max(a_1, a_2 - a_1)$. 103 104 Time complexity: $\mathcal{O}(n)$ or $\mathcal{O}(n \log n)$ depending on implementation. 105 106 **Implementation (Python)** 107 108 ``` 109 for test_case in range(int(input())): 110 n = int(input()) 111 a = sorted([int(_) for _ in input().split()]) 112 print(max(a[0], a[1]-a[0])) 113 ``` 114 115 # [2179D - Blackslex and Penguin Civilization](/contest/2179/problem/D "Codeforces Round 1071 (Div. 3)") 116 117 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut") 118 119 **Hint 1** 120 121 Ignore the lexicographically minimum condition first. Can you find any permutation that maximizes $S(p)$? Can you explain why the permutation maximizes $S(p)$? 122 123 **Hint 2** 124 125 There's an easy permutation that maximizes $S(p)$. 126 127 **The permutation** 128 129 $p_i = 2^n-i-1$ 130 131 **Hint 3** 132 133 There are at most $2^{n-i}$ prefixes of the permutation that has the popcount of the bitwise AND be at least $i$. 134 135 **Why?** 136 137 For a popcount of a prefix to exceed $i$, you'll need to fix $i$ bits to be all ones, so there are only $n-i$ bits left to do other things to. 138 139 **Solution** 140 141 Read all hints. Now, look at this sentence in Hint 3. 142 143 "For a popcount of a prefix to exceed $i$, you'll need to fix $i$ bits to be all ones." 144 145 We will fix the $i$ lowest-value bits, and iterate the other bits lexicographically minimally. 146 147 Here's an example for $n=3$: 148 149 **1 1 1** = 7 150 151 0 **1 1** = 3 152 153 0 0 **1** = 1 154 155 1 0 **1** = 5 156 157 0 0 0 = 0 158 159 0 1 0 = 2 160 161 1 0 0 = 4 162 163 1 1 0 = 6 164 165 For a clean implementation, note that iterating the unfixed bits is basically iterating even numbers. 166 167 Time complexity: $\mathcal{O}(2^n)$. 168 169 **Implementation (Python)** 170 171 ``` 172 t = int(input()) 173 for _ in range(t): 174 n = int(input()) 175 print(2**n - 1, end = ' ') 176 for i in range(1, n+1): 177 for j in range(0, 2**i, 2): 178 print(j*2**(n-i) + 2**(n-i) - 1, end = ' ') 179 print() 180 ``` 181 182 # [2179E - Blackslex and Girls](/contest/2179/problem/E "Codeforces Round 1071 (Div. 3)") 183 184 Author: [spycoderyt](/profile/spycoderyt "Expert spycoderyt") 185 186 **Hint 1** 187 188 Denote the party that is supposed to win a district as the 'designated winner.' A minimum population $p_i$ for each district and a strict majority condition creates a lower bound on the number of votes from the designated winner. What is this lower bound? 189 190 **Hint 2** 191 192 The lower bound is $\lfloor \frac{p_i}{2} \rfloor + 1$. 193 194 **Hint 3** 195 196 What happens if at least one pair of districts has a different designated winner? 197 198 **Hint 4** 199 200 What happens if that is not true; i.e all districts have the same designated winner? 201 202 **Solution** 203 204 Consider the process of constructing a solution, even though we will not explicitly construct it in the code. First note that if $x+y \lt \sum p_i$, then it is impossible. 205 206 Then if $x+y \geq \sum p_i$, we start off by filling each district with the lower bound number $\lfloor \frac{p_i}{2} \rfloor + 1$ of votes from the designated winner. If we run out of votes from either party then the answer is no. After that we have two cases: 207 208 Case 1: if there is at least one pair of districts with different designated winners, we can arbitrarily fill (with any color) each district up to its minimum capacity $p_i$, and then allocate the rest of the votes to a district where that vote's party is supposed to win in. Therefore we only need to check if the lower bound on designated winner votes can be achieved. 209 210 Case 2: if all districts have the same designated winner, sometimes there are too many votes from the 'losing' party for a solution to exist. The minimum votes the winning party must have over the losing party is $n$, because we need a strict majority in every district, which corresponds to a vote difference of at least 1 in each district. WLOG let $x$ be the votes from the winning party and $y$ be the votes from the losing party, and we simply check if $x \geq y + n$. 211 212 Time complexity: $\mathcal{O}(n)$ 213 214 **Implementation (C++)** 215 216 ``` 217 #include <bits/stdc++.h> 218 219 using namespace std; 220 typedef long long ll; 221 222 void test_case_run() { 223 int n; 224 ll x, y; 225 cin >> n >> x >> y; 226 227 string s; 228 cin >> s; 229 s = '.'+s; 230 231 ll p[n+1]; 232 for (int i = 1; i <= n; i++) cin >> p[i]; 233 234 if (accumulate(p+1, p+n+1, 0LL) > x+y) { 235 cout << "NO\n"; 236 return; 237 } 238 239 if (s == "." + string(n, '0') || s == "." + string(n, '1')) { 240 if (s == "." + string(n, '1')) { 241 swap(x, y); 242 } 243 244 ll x_need = 0; 245 for (int i = 1; i <= n; i++) { 246 x_need += p[i]/2 + 1; 247 } 248 249 if (x < x_need || x < y+n) { 250 cout << "NO\n"; 251 } else { 252 cout << "YES\n"; 253 } 254 255 return; 256 } 257 258 ll x_need = 0, y_need = 0; 259 for (int i = 1; i <= n; i++) { 260 if (s[i] == '0') { 261 x_need += p[i]/2 + 1; 262 } else { 263 y_need += p[i]/2 + 1; 264 } 265 } 266 if (x >= x_need && y >= y_need) cout << "YES\n"; 267 else cout << "NO\n"; 268 } 269 270 int main() { 271 ios_base::sync_with_stdio(false); 272 cin.tie(NULL); 273 274 int t; 275 cin >> t; 276 while (t--) test_case_run(); 277 278 return 0; 279 } 280 ``` 281 282 # [2179F - Blackslex and Another RGB Walking](/contest/2179/problem/F "Codeforces Round 1071 (Div. 3)") 283 284 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut") 285 286 **Hint 1** 287 288 Solve for a line graph. 289 290 **Hint 2** 291 292 Solve for a tree. 293 294 **Hint 3** 295 296 Does the exact same thing work? Why? 297 298 **Solution** 299 300 In the first run, use breadth-first search to find the distance of each vertex from vertex $1$. Color a vertex red if the distance is dividsible by $3$, green if the remainder of the division by $3$ is $1$, and blue if the remainder of the division by $3$ is $2$. 301 302 Note that if two vertices are connected by an edge, then their distances differ by no more than $1$. In fact, the distances differ by exactly $1$ for a bipartite graph. 303 304 **Why?** 305 306 Consider two adjacent vertices has the same distance. Connect the shortest paths from the two vertices to vertex $1$ with the edge connecting the two vertices. We can see that an odd cycle would form. 307 308 In the second run, move anywhere if every neighbor have the same color. Otherwise, note that 309 310 * If the neighbors are red and green, then B is at a blue vertex, and should move to any green vertex. 311 * If the neighbors are green and blue, then B is at a red vertex, and should move to any blue vertex. 312 * If the neighbors are blue and red, then B is at a green vertex, and should move to any red vertex. 313 314 Time complexity: $\mathcal{O}(n+m)$ 315 316 **Implementation (C++)** 317 318 ``` 319 #include <bits/stdc++.h> 320 321 using namespace std; 322 const int INF = 1e9; 323 324 void test_first() { 325 int n, m; 326 cin >> n >> m; 327 328 vector<vector<int>> edge(n+1); 329 for (int i = 1; i <= m; i++) { 330 int a, b; 331 cin >> a >> b; 332 edge[a].push_back(b); 333 edge[b].push_back(a); 334 } 335 336 vector<int> dist(n+1, INF); 337 dist[1] = 0; 338 339 queue<int> bfs; 340 bfs.push(1); 341 while (!bfs.empty()) { 342 int a = bfs.front(); 343 bfs.pop(); 344 345 for (int b : edge[a]) { 346 if (dist[b] > dist[a] + 1) { 347 dist[b] = dist[a] + 1; 348 bfs.push(b); 349 } 350 } 351 } 352 353 for (int i = 1; i <= n; i++) cout << "rgb"[dist[i]%3]; 354 cout << "\n"; 355 } 356 357 void test_second() { 358 int dv; 359 string color; 360 cin >> dv >> color; 361 362 bool fr = false, fg = false, fb = false; 363 for (char c : color) { 364 if (c == 'r') fr = true; 365 if (c == 'g') fg = true; 366 if (c == 'b') fb = true; 367 } 368 369 if ((int)fr + (int)fg + (int)fb == 1) { 370 cout << 1 << "\n"; 371 return; 372 } 373 374 char target; 375 if (fr && fg) target = 'g'; 376 if (fg && fb) target = 'b'; 377 if (fb && fr) target = 'r'; 378 379 for (int i = 0; i < dv; i++) { 380 if (color[i] == target) { 381 cout << i+1 << "\n"; 382 return; 383 } 384 } 385 } 386 387 int main() { 388 ios_base::sync_with_stdio(false); 389 cin.tie(NULL); 390 391 string player; 392 int t; 393 cin >> player >> t; 394 395 if (player == "first") while (t--) test_first(); 396 else while (t--) { 397 int q; 398 cin >> q; 399 while (q--) test_second(); 400 } 401 402 return 0; 403 } 404 ``` 405 406 # [2179G - Blackslex and Penguin Migration](/contest/2179/problem/G "Codeforces Round 1071 (Div. 3)") 407 408 Author: [omsincoconut](/profile/omsincoconut "Master omsincoconut") 409 410 **Hint 1** 411 412 Think about corners. 413 414 **Hint 2** 415 416 Think about non-opposite corners. 417 418 **Hint 3** 419 420 Think about cells furthest from another cell. 421 422 **Solution** 423 424 The idea is that distance from two non-opposite corners uniquely determine the position. 425 426 **Why?** 427 428 Note that the answer can be rotated or flipped and still be correct. Let us assume the two corners are at position $(1, 1)$ and position $(1, n)$. Let the distance from the two corners be $d_1$ and $d_2$. Assume that the cell is on $(x, y)$. Then, we can write 429 430 $|1-x| + |1-y| = x+y-2 = d_1$ $|1-x| + |n-y| = x-y+n-1 = d_2$ 431 432 We can solve the system of equations to have 433 434 $x = \frac{d_1+d_2-n+3}{2}$ $y = \frac{d_1-d_2+n+1}{2}$ 435 436 Start from an arbitrary cell, and query the distance from that cell to every other cell, using $n^2$ queries. Any cell furthest is a corner. 437 438 Next, from that corner, query to every other cell, using $n^2$ queries. We now get the distances from one corner. 439 440 Now, notice that the non-opposite corners would have a distance of $n-1$ from the corner we have right now. There will be $n$ candidate corners. Choose one arbitrary candidate and query the distance from this candidate to all other candidates, using $n$ queries. Any furthest cell is a desired non-opposite corner. 441 442 Lastly, query from the new-found corner, using $n^2$ queries. We now have sufficient information to answer. 443 444 Query count: $3n^2 + n - \mathcal{O}(1)$. This analysis did not account for small constant optimizations like not querying the same pair twice and not querying the distance to self. 445 446 Time complexity: $\mathcal{O}(n^2)$ 447 448 **Implementation (C++)** 449 450 ``` 451 #include <bits/stdc++.h> 452 453 using namespace std; 454 455 int query(int i, int j) { 456 cout << "? " << i << " " << j << endl; 457 int ret; 458 cin >> ret; 459 return ret; 460 } 461 462 void test_case_run() { 463 int n; 464 cin >> n; 465 466 // Find the first corner 467 int dist1[n*n+1]; 468 for (int i = 1; i <= n*n; i++) dist1[i] = query(1, i); 469 470 int corner1 = 1; 471 for (int i = 1; i <= n*n; i++) if (dist1[i] > dist1[corner1]) corner1 = i; 472 473 // Query distance from first corner 474 int dist_corner1[n*n+1]; 475 for (int i = 1; i <= n*n; i++) { 476 dist_corner1[i] = query(corner1, i); 477 } 478 479 // Find second corner 480 vector<int> corner2_candidates; 481 for (int i = 1; i <= n*n; i++) { 482 if (dist_corner1[i] == n-1) corner2_candidates.push_back(i); 483 } 484 485 int dist_findcorner2[corner2_candidates.size()]; 486 for (int i = 0; i < corner2_candidates.size(); i++) { 487 dist_findcorner2[i] = query(corner2_candidates[0], corner2_candidates[i]); 488 } 489 490 int corner2_index = 0; 491 for (int i = 0; i < corner2_candidates.size(); i++) { 492 if (dist_findcorner2[i] > dist_findcorner2[corner2_index]) corner2_index = i; 493 } 494 495 int corner2 = corner2_candidates[corner2_index]; 496 497 // Query distance from second corner 498 int dist_corner2[n*n+1]; 499 for (int i = 1; i <= n*n; i++) { 500 dist_corner2[i] = query(corner2, i); 501 } 502 503 // Find position 504 /* 505 d1 = |x-1|+|y-1| = x+y-2 506 d2 = |x-1|+|y-n| = x-y+n-1 507 508 d1 + d2 = 2x+n-3 => x = (d1+d2-n+3)/2 509 d1 - d2 = 2y-n-1 => y = (d1-d2+n+1)/2 510 */ 511 int ans[n+1][n+1]; 512 for (int i = 1; i <= n*n; i++) { 513 int d1 = dist_corner1[i], d2 = dist_corner2[i]; 514 int x = (d1+d2-n+3)/2; 515 int y = (d1-d2+n+1)/2; 516 ans[x][y] = i; 517 } 518 519 cout << "!" << endl; 520 for (int i = 1; i <= n; i++) { 521 for (int j = 1; j <= n; j++) cout << ans[i][j] << " "; 522 cout << endl; 523 } 524 }; 525 526 int main() { 527 ios_base::sync_with_stdio(false); 528 cin.tie(NULL); 529 530 int t; 531 cin >> t; 532 while (t--) test_case_run(); 533 534 return 0; 535 } 536 ``` 537 538 **Challenge** 539 540 This problem is solvable in $3n^2$ queries. Try it. 541 542 # [2179H - Blackslex and Plants](/contest/2179/problem/H "Codeforces Round 1071 (Div. 3)") 543 544 Author: [NortGlG](/profile/NortGlG "Candidate Master NortGlG") 545 546 **Hint 1** 547 548 Solve the easier version of this problem first: 549 550 * Let $f(x)$ be the value of the least significant bit of $x$. 551 552 **Hint 1.1** 553 554 Find the conditions needed to be satisfied to make the value of $f(x)$ become $2^y$ for any non-negative integer $y$. 555 556 **Hint 1.2** 557 558 $f(x) = 2^y$ if and only if $y$ is the largest non-negative integer that makes $2^y$ divide $x$. 559 560 What other things can we imply from that observation ? 561 562 **Hint 1.3** 563 564 If $2^y$ divides $x$, then $2^0, 2^1, 2^2, \ldots, 2^{y-1}$ will divide $x$ too. Use this fact to solve this version of the problem. 565 566 **Solution** 567 568 For any non-negative integer $y$, this equation is always true: 569 570 $2^{y+1} - 1 = 2^0 + 2^1 + 2^2 + \ldots + 2^y$ 571 572 From this equation, the value of $f(x) - 1$ can be represented as the sum of $2^{a-1}$ for each positive integer $a$ that $2^a$ divides $x$, that is: 573 574 $f(x) - 1 = 2^0 + 2^1 + 2^2 + \ldots + 2^{a-1}$ 575 576 Which can be rearranged as: 577 578 $f(x) = 2^0 + 2^1 + 2^2 + \ldots + 2^{a-1} + 1$ 579 580 You can see that every term of this sum can be calculated independently because the term $2^b$ exists because $2^{b+1}$ divides $x$. 581 582 For each watering operation on range $[l,r]$, you need to perform this action: 583 584 * For $a = 1, 2, 3, \ldots, \log n$; increase the water amount by $2^{a-1}$ in every position $i$ where $2^a$ divides $(i - l + 1)$, and also increase the water amount in every position in range $[l, r]$ by $1$, too. 585 586 These operations can be handled using prefix sum arrays separately in each $a$. 587 588 Time complexity: $\mathcal{O}((n + q)\log n)$. 589 590 **Solution** 591 592 Read **Hint 1** first. 593 594 You can extend the idea from the easier version to solve the actual task. 595 596 Since the value of the least significant bit can be represented using the sum of $2^0, 2^1, 2^2, \ldots$, the only thing left to consider is the coefficient of those values in each position. 597 598 For watering operations that cover the range $[l, r]$, you can perform the following update to the coefficient array: 599 600 * For all $l \leq i \leq r$, add $i$ to the $i$-th position. 601 * For all $l \leq i \leq r$, subtract $l-1$ from the $i$-th position. 602 603 Which is basically the same as increasing the coefficients value in each $l \leq i \leq r$ by $i - l + 1$. 604 605 These operations can be implemented using prefix sum arrays separately in each $a$, too. 606 607 Time complexity: $\mathcal{O}((n+q)\log n)$. 608 609 **Implementation (C++)** 610 611 ``` 612 #include<bits/stdc++.h> 613 using namespace std; 614 using ll = long long; 615 const int N = 200200; 616 int qs1[20][N]; 617 ll qs2[20][N]; 618 ll ans[N]; 619 void solve() { 620 int n, q; 621 cin >> n >> q; 622 int sz = 31 - __builtin_clz(n); 623 for (int i = 1;i <= n;i++) ans[i] = 0; 624 for (int j = 0;j <= sz;j++) { 625 for (int i = 0;i <= n;i++) qs1[j][i] = 0, qs2[j][i] = 0; 626 } 627 while (q--) { 628 int l, r; 629 cin >> l >> r; 630 int sz = 31 - __builtin_clz(r - l + 1); 631 for (int j = 0;j <= sz;j++) { 632 int k = (r - l + 1) >> j; 633 qs1[j][l + (1 << j) - 1]++; 634 qs2[j][l + (1 << j) - 1] += l - 1; 635 qs1[j][min(n + 1, l + ((k + 1) << j) - 1)]--; 636 qs2[j][min(n + 1, l + ((k + 1) << j) - 1)] -= l - 1; 637 } 638 } 639 for (int i = 0;i <= sz;i++) { 640 for (int j = 1;j <= n;j++) { 641 if (j >= (1 << i)) { 642 qs1[i][j] += qs1[i][j - (1 << i)]; 643 qs2[i][j] += qs2[i][j - (1 << i)]; 644 } 645 ans[j] += 1ll * qs1[i][j] * j * (1 << max(0, i - 1)); 646 ans[j] -= 1ll * qs2[i][j] * (1 << max(0, i - 1)); 647 } 648 } 649 for (int i = 1;i <= n;i++) { 650 cout << ans[i] << ' '; 651 } 652 cout << '\n'; 653 } 654 655 int main() { 656 cin.tie(nullptr)->sync_with_stdio(false); 657 int q; 658 cin >> q; 659 while (q--) { 660 solve(); 661 } 662 return 0; 663 } 664 ```