2096.md (27473B)
1 Source: https://codeforces.com/blog/entry/142070 2 3 [Sorry about problem H.](https://codeforces.com/blog/entry/142069) 4 5 Thank you for understanding, and we hope you enjoyed the rest of the problems :D 6 7 --- 8 9 ### [2096A - Wonderful Sticks](/contest/2096/problem/A) 10 11 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 12 13 **Step 1** 14 15 Create your own test cases and solve them! What can you observe? 16 17 **Step 2** 18 19 What is the length of the $n$-th stick? 20 21 **Answer** 22 23 * If $s_{n - 1} = \texttt{ \lt }$, then $a_n = 1$, because the $n$-th stick must be shorter than all the other sticks. 24 * If $s_{n - 1} = \texttt{ \gt }$, then $a_n = n$, because the $n$-th stick must be longer than all the other sticks. 25 26 **Step 3** 27 28 Can we do something similar for the remaining sticks? 29 30 **Answer** 31 32 Yes! Remove the $n$-th stick, and then solve for the remaining $n - 1$ sticks. 33 34 We can make similar observations about the $(n - 1)$-th stick. 35 36 Then, remove the $(n - 1)$-th stick, and solve for the remaining $n - 2$ sticks, and so on. 37 38 **Step 4** 39 40 So the algorithm is as follows: 41 42 1. Initialize an array $b = [1, 2, \ldots, n]$. This represents the lengths of the remaining sticks. 43 2. For each $i$ from $n - 1$ to $1$: 44 * If $s_i = \texttt{ \lt }$, then set $a_{i + 1} = \min(b)$. 45 * If $s_i = \texttt{ \gt }$, then set $a_{i + 1} = \max(b)$. 46 * Now remove $a_{i + 1}$ from $b$, and continue. 47 3. In the end, we have $1$ remaining element in $b$. This is the value of $a_1$. 48 49 The time complexity of this solution is $O(n^2)$. 50 51 **Step 5 (Optional)** 52 53 We can notice that at any point, $b$ has the form $[l, l + 1, \ldots, r]$. 54 55 So we can represent $b$ using two integers $l$ and $r$: 56 57 * When we remove $\min(b)$, we increase $l$ by $1$. 58 * When we remove $\max(b)$, we decrease $r$ by $1$. 59 60 Now the time complexity of our solution is $O(n)$. 61 62 **Implementation** 63 64 ``` 65 #include <bits/stdc++.h> 66 using namespace std; 67 68 void test() { 69 int n; 70 cin >> n; 71 string s; 72 cin >> s; 73 74 int l = 1; 75 int r = n; 76 vector<int> a(n); 77 for (int i = n - 2; i >= 0; i--) { 78 if (s[i] == '<') { 79 a[i + 1] = l; 80 l++; 81 } 82 if (s[i] == '>') { 83 a[i + 1] = r; 84 r--; 85 } 86 } 87 a[0] = l; 88 89 for (int i = 0; i < n; i++) { 90 cout << a[i] << " "; 91 } 92 cout << '\n'; 93 } 94 95 int main() { 96 ios_base::sync_with_stdio(false); 97 cin.tie(nullptr); 98 99 int t; 100 cin >> t; 101 for (int i = 0; i < t; i++) { 102 test(); 103 } 104 105 return 0; 106 } 107 ``` 108 109 --- 110 111 ### [2096B - Wonderful Gloves](/contest/2096/problem/B) 112 113 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 114 115 **Step 1** 116 117 Let's look at the third test case in the example. We have $k = 2$, and the answer is $x = 303$. If we take out $302$ gloves, then it's possible that we only have matching pairs of $1$ color. 118 119 How can we generalize this fact for any $k$ and $x$? 120 121 **Answer** 122 123 If we take out $(x - 1)$ gloves or fewer, then it's possible that we only have at most $(k - 1)$ matching pairs of different colors. 124 125 **Step 2** 126 127 So we can solve the problem as follows: 128 129 * Let $y$ be the maximum number of gloves we can take out so that there are at most $(k - 1)$ matching pairs of different colors. Then the answer to the problem is $x = y + 1$. 130 131 Set $m = k - 1$. Now we need to find the maximum number of gloves so that there are at most $m$ matching pairs of different colors. 132 133 **Step 3** 134 135 Try solving it for $m = 0$ first. 136 137 **Step 4** 138 139 When $m = 0$, we want to find the maximum number of gloves so that there are no matching pairs. 140 141 Therefore, for each color $i$, we can either take all the left gloves, or all the right gloves. So we should choose the type with more gloves. 142 143 Formally, let $a_i = \max(l_i, r_i)$. Then the maximum number of gloves we can take is $y = a_1 + a_2 + \ldots + a_n$. 144 145 **Step 5** 146 147 Now, using the solution for $m = 0$, solve it for $m = 1$. Then solve it for $m = 2$, and so on. 148 149 **Step 6** 150 151 When $m = 0$, we take $a_i$ gloves of color $i$. So we're left with $b_i = \min(l_i, r_i)$ gloves of color $i$ that we haven't taken. 152 153 To get from $m = 0$ to $m = 1$, we can additionally form matching pairs of $1$ color. Therefore, we can choose a color $i$, and take the remaining $b_i$ gloves. So we should choose the color $i$ with the maximum value of $b_i$. 154 155 In other words, for $m = 1$, the maximum number of gloves we can take is $y = a_1 + a_2 + \ldots + a_n + \max(b_1, b_2, \ldots, b_n)$. 156 157 To get from $m = 0$ to $m = 2$, we can additionally form matching pairs of $2$ different colors. Therefore, we can choose two different colors $i$ and $j$, and take the remaining $b_i + b_j$ gloves. So we should choose the two colors $i$ and $j$ with the maximum value of $b_i + b_j$. 158 159 We can generalize this idea for any $m$. 160 161 **Step 7** 162 163 So the algorithm is as follows: 164 165 1. Set $m = k - 1$. 166 2. For each $i$ from $1$ to $n$, let $a_i = \max(l_i, r_i)$ and $b_i = \min(l_i, r_i)$. 167 3. Set $y = a_1 + a_2 + \ldots + a_n$. 168 4. Sort the values of $b$ in descending order. 169 5. Add the $m$ largest values of $b$ to $y$. 170 6. The answer is $x = y + 1$. 171 172 The time complexity of this solution is $O(n \log n)$. 173 174 **Implementation** 175 176 ``` 177 #include <bits/stdc++.h> 178 using namespace std; 179 180 void test() { 181 int n, k; 182 cin >> n >> k; 183 int m = k - 1; 184 185 vector<int> l(n); 186 for (int i = 0; i < n; i++) { 187 cin >> l[i]; 188 } 189 vector<int> r(n); 190 for (int i = 0; i < n; i++) { 191 cin >> r[i]; 192 } 193 194 vector<int> a(n), b(n); 195 long long y = 0; 196 for (int i = 0; i < n; i++) { 197 a[i] = max(l[i], r[i]); 198 b[i] = min(l[i], r[i]); 199 y += a[i]; 200 } 201 202 sort(b.begin(), b.end(), greater<>()); 203 for (int i = 0; i < m; i++) { 204 y += b[i]; 205 } 206 207 long long x = y + 1; 208 cout << x << '\n'; 209 } 210 211 int main() { 212 ios_base::sync_with_stdio(false); 213 cin.tie(nullptr); 214 215 int t; 216 cin >> t; 217 for (int i = 0; i < t; i++) { 218 test(); 219 } 220 221 return 0; 222 } 223 ``` 224 225 --- 226 227 ### [2096C - Wonderful City](/contest/2096/problem/C) 228 229 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 230 231 **Step 1** 232 233 We are given an $n \times n$ matrix of positive integers. There are two types of operations we can perform: 234 235 * When we hire worker $i$ from company A, let's call it *row operation* $i$. 236 * When we hire worker $j$ from company B, let's call it *column operation* $j$. 237 238 Each row and column operation can be performed at most once. 239 240 After performing the operations, the matrix must satisfy the following: 241 242 * **Horizontal Condition:** No two horizontally adjacent elements are the same. 243 * **Vertical Condition:** No two vertically adjacent elements are the same. 244 245 Suppose the matrix does not satisfy the Horizontal Condition, so there is a position $(i, j)$ such that $h_{i,j} = h_{i, j + 1}$. 246 247 What operations can we perform to fix this? Don't worry about other positions for now. We just want $h_{i,j} \neq h_{i, j + 1}$. 248 249 **Step 2** 250 251 We can either: 252 253 * Only perform column operation $j$, and increase $h_{i, j}$ by $1$; 254 * Or only perform column operation $(j + 1)$, and increase $h_{i, j + 1}$ by $1$. 255 256 Notice that when we perform row operation $i$, we increase both $h_{i, j}$ and $h_{i, j + 1}$ by $1$. Therefore, the difference between the two elements does not change. 257 258 Formally, when we perform row operation $i$, the value $d = h_{i, j} - h_{i, j + 1}$ does not change. 259 260 **Step 3** 261 262 From our previous observations, we see that: 263 264 * Only column operations affect the Horizontal Condition. 265 * Only row operations affect the Vertical Condition. 266 267 So we can solve for the Horizontal Condition and the Vertical Condition independently. 268 269 **Step 4** 270 271 Using DP, we will calculate: 272 273 * The minimum total cost of the row operations required to satisfy the Vertical Condition. 274 * The minimum total cost of the column operations required to satisfy the Horizontal Condition. 275 276 To get the answer, we add the two costs. 277 278 **Step 5** 279 280 Let $dp(i, x)$ be the minimum total cost of the row operations required so that: 281 282 * The first $i$ rows of the matrix satisfy the Vertical Condition. 283 * If $x = 0$, then we do not perform row operation $i$. 284 * If $x = 1$, then we perform row operation $i$. 285 286 If it is impossible, then $dp(i, x) = \infty$. 287 288 Our base cases are $dp(1, 0) = 0$ and $dp(1, 1) = a_1$. 289 290 For $i \gt 1$, initialize $dp(i, x)$ to $\infty$. Our $dp(i, x)$ will depend on some $dp(i - 1, y)$. 291 292 Now we need to check if row $(i - 1)$ and row $i$ satisfy the Vertical Condition: 293 294 * The elements in row $i - 1$ are: $(h_{i - 1, 1} + y), (h_{i - 1, 2} + y), \ldots, (h_{i - 1, n} + y)$. 295 * The elements in row $i$ are: $(h_{i, 1} + x), (h_{i, 2} + x), \ldots, (h_{i, n} + x)$. 296 297 If no two vertically adjacent elements are the same, then: 298 299 * For $x = 0$, set $dp(i, x) = \min(dp(i, x), dp(i - 1, y))$. 300 * For $x = 1$, set $dp(i, x) = \min(dp(i, x), dp(i - 1, y) + a_i)$. 301 302 The minimum total cost required so that the entire matrix satisfies the Vertical Condition is $\min(dp(n, 0), dp(n, 1))$. 303 304 Similarly, we can solve for the Horizontal Condition. 305 306 The time complexity of this solution is $O(n^2)$. 307 308 **Step 6 (Optional)** 309 310 To avoid repetition, we can solve for the Horizontal Condition by transposing the matrix and treating it as the Vertical Condition instead. 311 312 **Implementation** 313 314 ``` 315 #include <bits/stdc++.h> 316 using namespace std; 317 318 const long long INF = 1e18; 319 320 long long solveHor(int n, vector<vector<int>>& h, vector<int>& a) { 321 vector<vector<long long>> dp(n, vector<long long>(2, INF)); 322 dp[0][0] = 0; 323 dp[0][1] = a[0]; 324 325 for (int i = 1; i < n; i++) { 326 for (int x = 0; x < 2; x++) { 327 for (int y = 0; y < 2; y++) { 328 bool ok = true; 329 for (int j = 0; j < n; j++) { 330 ok &= (h[i - 1][j] + y != h[i][j] + x); 331 } 332 if (ok) { 333 if (x == 0) { 334 dp[i][x] = min(dp[i][x], dp[i - 1][y]); 335 } 336 if (x == 1) { 337 dp[i][x] = min(dp[i][x], dp[i - 1][y] + a[i]); 338 } 339 } 340 } 341 } 342 } 343 344 return min(dp[n - 1][0], dp[n - 1][1]); 345 } 346 347 void transpose(int n, vector<vector<int>>& h) { 348 for (int i = 0; i < n; i++) { 349 for (int j = i + 1; j < n; j++) { 350 swap(h[i][j], h[j][i]); 351 } 352 } 353 } 354 355 void test() { 356 int n; 357 cin >> n; 358 359 vector<vector<int>> h(n, vector<int>(n)); 360 for (int i = 0; i < n; i++) { 361 for (int j = 0; j < n; j++) { 362 cin >> h[i][j]; 363 } 364 } 365 366 vector<int> a(n); 367 for (int i = 0; i < n; i++) { 368 cin >> a[i]; 369 } 370 371 vector<int> b(n); 372 for (int i = 0; i < n; i++) { 373 cin >> b[i]; 374 } 375 376 long long horCost = solveHor(n, h, a); 377 transpose(n, h); 378 long long verCost = solveHor(n, h, b); 379 long long totalCost = horCost + verCost; 380 381 if (totalCost >= INF) { 382 cout << -1 << '\n'; 383 } 384 else { 385 cout << totalCost << '\n'; 386 } 387 } 388 389 int main() { 390 ios_base::sync_with_stdio(false); 391 cin.tie(nullptr); 392 393 int t; 394 cin >> t; 395 for (int i = 0; i < t; i++) { 396 test(); 397 } 398 399 return 0; 400 } 401 ``` 402 403 --- 404 405 ### [2096D - Wonderful Lightbulbs](/contest/2096/problem/D) 406 407 Idea: [thenymphsofdelphi](/profile/thenymphsofdelphi "International Grandmaster thenymphsofdelphi") 408 409 **Step 1** 410 411 What can we say about the number of lightbulbs that are turned on for any valid configuration in the input? 412 413 **Step 2** 414 415 Can the number of lightbulbs that are turned on be even? 416 417 **Answer** 418 419 The number of lightbulbs that are turned on is always odd. 420 421 This is because we start with exactly one lightbulb turned on. Every operation changes the state of $4$ lightbulbs, which is an even number. So no matter what operations we perform, we will always have an odd number of lightbulbs turned on. 422 423 **Step 3** 424 425 Let's use the idea of parity to come up with stricter conditions. 426 427 **Step 4** 428 429 Consider the lightbulbs on the vertical line $x = c$. What can we say about the number of lightbulbs that are turned on? 430 431 **Answer** 432 433 Suppose the treasure is buried at position $(s, t)$. 434 435 * If $c = s$, then the line $x = c$ has an odd number of lightbulbs turned on. 436 * If $c \neq s$, then the line $x = c$ has an even number of lightbulbs turned on. 437 438 This is because every operation $(u, v)$ changes the state of $4$ lightbulbs: $(u, v)$, $(u, v + 1)$, $(u + 1, v - 1)$, $(u + 1, v)$. 439 440 * $2$ of them are on the vertical line $x = u$. 441 * $2$ of them are on the vertical line $x = u + 1$. 442 443 **Step 5** 444 445 From our previous observations, we can uniquely determine the value of $s$. Can we do the same for the value of $t$? 446 447 **Step 6** 448 449 Consider the lightbulbs on the diagonal line $x + y = c$. What can we say about the number of lightbulbs that are turned on? 450 451 **Answer** 452 453 Suppose the treasure is buried at position $(s, t)$. 454 455 * If $c = s + t$, then the line $x + y = c$ has an odd number of lightbulbs turned on. 456 * If $c \neq s + t$, then the line $x + y = c$ has an even number of lightbulbs turned on. 457 458 This is because every operation $(u, v)$ changes the state of $4$ lightbulbs: $(u, v)$, $(u, v + 1)$, $(u + 1, v - 1)$, $(u + 1, v)$. 459 460 * $2$ of them are on the diagonal line $x + y = u + v$. 461 * $2$ of them are on the diagonal line $x + y = u + v + 1$. 462 463 **Step 7** 464 465 So, to summarize, we find two lines: 466 467 * The vertical line that has an odd number of lightbulbs turned on 468 * The diagonal line that has an odd number of lightbulbs turned on 469 470 The intersection of these two lines is the position of the treasure. 471 472 **Implementation** 473 474 ``` 475 #include <bits/stdc++.h> 476 using namespace std; 477 478 void test() { 479 int n; 480 cin >> n; 481 482 map<int, int> cntVer, cntDiag; 483 for (int i = 0; i < n; i++) { 484 int x, y; 485 cin >> x >> y; 486 cntVer[x]++; 487 cntDiag[x + y]++; 488 } 489 490 int s; 491 for (auto [c, cnt]: cntVer) { 492 if (cnt % 2 == 1) { 493 s = c; 494 break; 495 } 496 } 497 498 int t; 499 for (auto [c, cnt]: cntDiag) { 500 if (cnt % 2 == 1) { 501 t = c - s; 502 break; 503 } 504 } 505 506 cout << s << " " << t << '\n'; 507 } 508 509 int main() { 510 ios_base::sync_with_stdio(false); 511 cin.tie(nullptr); 512 513 int t; 514 cin >> t; 515 for (int i = 0; i < t; i++) { 516 test(); 517 } 518 519 return 0; 520 } 521 ``` 522 523 --- 524 525 ### [2096E - Wonderful Teddy Bears](/contest/2096/problem/E) 526 527 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 528 529 **Step 1** 530 531 First, we'll treat all the black teddy bears as $0$ and all the pink teddy bears as $1$. 532 533 So we are given a binary array of length $n$. In one operation, we can choose three consecutive elements and sort them in ascending order. Now we need to find the minimum number of operations required to sort the array. 534 535 There are four possible types of operations, depending on the values of the elements: 536 537 * Operation A: $(0, 1, 0) \rightarrow (0, 0, 1)$ 538 * Operation B: $(1, 0, 0) \rightarrow (0, 0, 1)$ 539 * Operation C: $(1, 0, 1) \rightarrow (0, 1, 1)$ 540 * Operation D: $(1, 1, 0) \rightarrow (0, 1, 1)$ 541 542 **Step 2** 543 544 Let's think of a greedy solution first. Which operations are better than others? 545 546 **Step 3** 547 548 We can evaluate an operation by how much it reduces the number of inversions in the array: 549 550 * Operation A reduces the number of inversions by $1$. 551 * Operation B reduces the number of inversions by $2$. 552 * Operation C reduces the number of inversions by $1$. 553 * Operation D reduces the number of inversions by $2$. 554 555 Therefore, ideally, we'd only perform operations B and D. 556 557 Let $x$ be the number of inversions in the original array. Then the answer is at least $\left\lceil \frac{x}{2} \right\rceil$. 558 559 **Step 4** 560 561 Suppose we keep performing operations B and D until we can no longer do so. What will the array look like? 562 563 **Answer** 564 565 The array will have the form $[0, 0, \ldots, 0, 0, 1, 0, 1, 0, \ldots 1, 0, 1, 0, 1, 1, \ldots, 1, 1]$. 566 567 In other words, the array will consist of: 568 569 1. A (possibly empty) sequence of consecutive $0$'s; 570 2. A (possibly empty) sequence of alternating $1$'s and $0$'s; 571 3. And a (possibly empty) sequence of consecutive $1$'s. 572 573 **Step 5** 574 575 Since the array has a sequence of alternating $1$'s and $0$'s, we should think about parity. 576 577 **Step 6** 578 579 Let $a$ be the number of $0$'s in the entire array, and $b$ be the number of $0$'s in the even positions. 580 581 When the array is sorted, all the $0$'s will be at the beginning of the array. So in the end, $b = \left\lfloor \frac{a}{2} \right\rfloor$. 582 583 Consider how each type of operation changes the value of $b$: 584 585 * Operation A either increases or decreases the value of $b$ by $1$. 586 * Operation B does not change the value of $b$. 587 * Operation C either increases or decreases the value of $b$ by $1$. 588 * Operation D does not change the value of $b$. 589 590 Therefore, we can only use operations A and C to change the value of $b$. 591 592 **Step 7** 593 594 Let $d = \lvert \, \left\lfloor \frac{a}{2} \right\rfloor - b \, \rvert$. Then we need at least $d$ operations of type A or type C. 595 596 After these $d$ operations, the array will have $(x - d)$ inversions. We can show that $(x - d)$ must be even. 597 598 Then, we perform $\frac{x - d}{2}$ operations of type B or type D to reduce the number of inversions to $0$. 599 600 So the answer to the problem is: $d + \frac{x - d}{2} = \frac{x + d}{2}$. 601 602 **Implementation** 603 604 ``` 605 #include <bits/stdc++.h> 606 using namespace std; 607 608 void test() { 609 int n; 610 cin >> n; 611 612 string s; 613 cin >> s; 614 615 long long x = 0; 616 int a = 0; 617 int b = 0; 618 for (int i = n - 1; i >= 0; i--) { 619 if (s[i] == 'B') { 620 a++; 621 if ((i + 1) % 2 == 0) { 622 b++; 623 } 624 } 625 if (s[i] == 'P') { 626 x += a; 627 } 628 } 629 630 int d = abs(a / 2 - b); 631 cout << (x + d) / 2 << '\n'; 632 } 633 634 int main() { 635 ios_base::sync_with_stdio(false); 636 cin.tie(nullptr); 637 638 int t; 639 cin >> t; 640 for (int i = 0; i < t; i++) { 641 test(); 642 } 643 644 return 0; 645 } 646 ``` 647 648 --- 649 650 ### [2096F - Wonderful Impostors](/contest/2096/problem/F) 651 652 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 653 654 **Step 1** 655 656 Let's call a set of statements *satisfiable* if it's possible that all of them are true. 657 658 How do we check if a set of statements is satisfiable? 659 660 **Answer** 661 662 For each statement of the form $0\,a_l\,a_r$, assign all viewers from $a_l$ to $a_r$ as crewmates. Then, assign the rest of the viewers as impostors. Now check if all statements of the form $1\,b_l\,b_r$ are true. 663 664 **Step 2** 665 666 When a segment of statements $[s_l, s_r]$ is satisfiable, what can we say about other segments of statements? 667 668 **Answer** 669 670 If $[s_l, s_r]$ is satisfiable, then $[s_l + 1, s_r]$ and $[s_l, s_r - 1]$ are also satisfiable. 671 672 **Step 3** 673 674 We'll use the two pointers method. For each $s_r$, let $low(s_r)$ be the smallest $s_l$ such that $[s_l, s_r]$ is satisfiable. To answer a question $s_l\,s_r$, we just check that $s_l \geq low(s_r)$. 675 676 When we increment $s_r$, we will add statement $(s_r + 1)$. So we must increment $s_l$ and remove statements from the beginning of the segment until $[s_l, s_r + 1]$ is satisfiable. 677 678 Now we need to efficiently check if we can add a new statement to our current set of statements. 679 680 **Step 4** 681 682 Let's rephrase how to determine if a set of statements is satisfiable. 683 684 * For statements of the form $0\,a_l\,a_r$, we'll call $[a_l, a_r]$ a *$0$-segment*. 685 * Similarly, for statements of the form $1\,b_l\,b_r$, we'll call $[b_l, b_r]$ a *$1$-segment*. 686 * When $0$-segments overlap and form a larger segment, we'll call it a *$0$-component*. 687 688 Then, a set of statements is satisfiable if there does not exist a $1$-segment that is fully covered by a $0$-component. 689 690 **Step 5** 691 692 When we add a $1$-segment $[b_l, b_r]$, we need to check if it will be fully covered by a $0$-component. 693 694 For each $i$ from $1$ to $n$, let $count(i)$ be the number of $0$-segments that contain viewer $i$. 695 696 Then, we can add $[b_l, b_r]$ if $\min(count(b_l), count(b_l + 1), \ldots, count(b_r)) = 0$. 697 698 The values of $count(i)$ can be maintained using a segment tree. 699 700 **Step 6** 701 702 When we add a $0$-segment $[a_l, a_r]$, it might merge several $0$-components. So first we need to find the $0$-component $[c_l, c_r]$ that contains $[a_l, a_r]$: 703 704 * $c_l$ is the smallest value such that $\min(count(c_l), count(c_l + 1), \ldots, count(a_l)) \gt 0$. 705 * $c_r$ is the largest value such that $\min(count(a_r), count(a_r + 1), \ldots, count(c_r)) \gt 0$. 706 707 Both of these values can be found by performing a walk on the segment tree. 708 709 Now we need to check if there's a $1$-segment that's fully covered by $[c_l, c_r]$. 710 711 **Step 7** 712 713 Sort all the $1$-segments in the input by ascending value of $b_r$. 714 715 Then, for all segments that satisfy $b_r \leq c_r$, find the one with largest value of $b_l$. If $b_l \geq c_l$, then $[b_l, b_r]$ is fully covered by $[c_l, c_r]$. 716 717 We can maintain another segment tree with prefix-max queries. 718 719 --- 720 721 ### [2096G - Wonderful Guessing Game](/contest/2096/problem/G) 722 723 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 724 725 **Step 1** 726 727 First, try solving it if Alice doesn't ignore any queries. 728 729 **Step 2** 730 731 We can represent the queries using a table. Let's look at the second test case in the example: 732 733 | $1$ | $2$ | $3$ | $4$ | $5$ | 734 | --- | --- | --- | --- | --- | 735 | $\texttt{R}$ | $\texttt{L}$ | $\texttt{L}$ | $\texttt{R}$ | $\texttt{N}$ | 736 | $\texttt{R}$ | $\texttt{N}$ | $\texttt{R}$ | $\texttt{L}$ | $\texttt{L}$ | 737 | $\texttt{L}$ | $\texttt{N}$ | $\texttt{R}$ | $\texttt{R}$ | $\texttt{L}$ | 738 739 Each row is a query. Column $x$ contains Alice's responses if her number was $x$. 740 741 **Step 3** 742 743 Let's treat $\texttt{L}$ as $-1$, $\texttt{R}$ as $1$, and $\texttt{N}$ as $0$. 744 745 | $1$ | $2$ | $3$ | $4$ | $5$ | 746 | --- | --- | --- | --- | --- | 747 | $1$ | $-1$ | $-1$ | $1$ | $0$ | 748 | $1$ | $0$ | $1$ | $-1$ | $-1$ | 749 | $-1$ | $0$ | $1$ | $1$ | $-1$ | 750 751 Then, our strategy works if each row has a sum of $0$ and all $n$ columns are distinct. 752 753 Since there are only $3$ possible values, we need at least $q = \left\lceil \log_3(n) \right\rceil$ queries. In fact, this lower bound can be achieved. 754 755 **Step 4** 756 757 We generate all $3^{q}$ possible columns: $[x_1, x_2, \ldots, x_q]$, where $x_i \in$ $\text{\{}$$-1, 0, 1$$\text{\}}$. 758 759 Now we need to choose $n$ of them so that they sum to $0$. 760 761 To do this, we can choose one pair of columns at a time: 762 763 * First, we choose $[x_1, x_2, \ldots, x_q]$; 764 * Then, we choose $[-x_1, -x_2, \ldots, -x_q]$. 765 766 We see that each pair of columns sums to $0$. 767 768 If $n$ is odd, we can include $[0, 0, \ldots, 0]$. 769 770 **Step 5** 771 772 Now let's try to solve the original problem. For our strategy to work, it must satisfy the following: 773 774 * Each row has a sum of $0$. 775 * No two columns are the same. 776 * No two columns differ by exactly $1$ element. 777 778 To achieve this, we only need $1$ additional query. 779 780 **Step 6** 781 782 Here's another way to think about it: 783 784 * For each column, no matter which element is ignored, we should be able to uniquely determine the missing value. 785 786 **Step 7** 787 788 We use the same solution as before, but with $1$ more element: 789 790 * For each column $[x_1, x_2, \ldots, x_q]$, add an element $x_{q + 1}$ such that $(x_1 + x_2 + \ldots + x_{q + 1})\mod 3 = 0$. 791 792 Because the sum of each column is $0$ modulo $3$, we can uniquely recover any missing element. 793 794 --- 795 796 ### [2096H - Wonderful XOR Problem](/contest/2096/problem/H) 797 798 Idea: [SanguineChameleon](/profile/SanguineChameleon "Grandmaster SanguineChameleon") 799 800 **Step 0** 801 802 Is this FFT? 803 804 **Step 1.1** 805 806 Let's consider the XOR convolution. Given two polynomials $A(x)$ and $B(x)$ with degree at most $(2^{m} - 1)$, the XOR convolution $C(x) = A(x) \star B(x)$ is defined as follows: 807 808 $\displaystyle [x^k]C(x) = \sum_{0 \leq i \lt 2^m \\ 0 \leq j \lt 2^m \\ i \oplus j = k} [x^i]A(x) \cdot [x^j]B(x)$ 809 810 **Step 1.2** 811 812 To efficiently compute the XOR convolution, we can use FWHT. 813 814 First, let $s(k, i) = (-1)^{\text{popcount}(k\,\&\,i)}$. 815 816 Then, $F(A(x))$ is defined as follows: 817 818 $\displaystyle [x^k]F(A(x)) = \sum_{0 \leq i \lt 2^m} [x^i]A(x) \cdot s(k, i)$ 819 820 Given $A^{\,\prime}(x) = F(A(x))$, we can uniquely determine $A(x) = F^{-1}(A^{\,\prime}(x))$ using the inverse of FWHT. 821 822 To compute $F(A(x))$ and $F^{-1}(A^{\,\prime}(x))$, we can use SOS DP. 823 824 **Step 1.3** 825 826 Define the dot product $D(x) = A(x) \cdot B(x)$ as follows: $\displaystyle [x^k]D(x) = [x^k]A(x) \cdot [x^k]B(x)$ 827 828 We can show that $F(A(x) \star B(x)) = F(A(x)) \cdot F(B(x))$ for any two polynomials $A(x)$ and $B(x)$. 829 830 **Step 2.1** 831 832 Let's solve the problem. For each interval $[l_i, r_i]$, let $A_i(x) = x^{l_i} + x^{l_i + 1} + \ldots + x^{r_i}$. 833 834 We want to find $A_1(x) \star A_2(x) \star \ldots \star A_n(x)$. To do this, we'll compute $F^{-1}(F(A_1(x)) \cdot F(A_2(x)) \cdot \ldots \cdot F(A_n(x)))$. 835 836 **Step 2.2** 837 838 We can note that $\displaystyle [x^k]F(A_i(x)) = \sum_{l_i \leq j \leq r_i} s(k, j)$ 839 840 Let $f(k, r) = \displaystyle \sum_{0 \leq j \leq r} s(k, j)$. Then $\displaystyle [x^k]F(A_i(x)) = f(k, r_i) - f(k, l_i - 1)$. 841 842 Now we need to find a way to compute $f(k, r)$ efficiently. 843 844 **Step 2.3** 845 846 Let $p$ be the ($0$-indexed) position of the least significant bit of $k$. 847 848 Let $c = \left\lfloor \frac{r}{2^{p + 1}} \right\rfloor$. Then $f(k, r) = \displaystyle f(k, c \cdot 2^{p+1} - 1) + \sum_{c \cdot 2^{p + 1} \leq j \leq r} s(k, j)$ 849 850 Due to cancellation of terms, we have $f(k, c \cdot 2^{p+1} - 1) = 0$. 851 852 We can also see that $s(k, j) = s(2^p, j) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, \left\lfloor \frac{j}{2^{p + 1}} \right\rfloor\right) = s(2^p, j) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, c\right)$ 853 854 Therefore, $\displaystyle f(k, r) = \left(\sum_{c \cdot 2^{p + 1} \leq j \leq r} s(2^p, j)\right) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, c\right)$. 855 856 **Step 2.4** 857 858 Returning to $F(A_i(x))$, we get: 859 860 $\displaystyle [x^k]F(A_i(x)) = a_i \cdot s(k^{\,\prime}, c_i) + b_i \cdot s(k^{\,\prime}, d_i)$ 861 862 where: 863 864 * $a_i$ and $b_i$ are constants independent of $k$. 865 * $k^{\,\prime} = \left\lfloor \frac{k}{2^{p + 1}} \right\rfloor$, $c_i = \left\lfloor \frac{r_i}{2^{p + 1}} \right\rfloor$, and $d_i = \left\lfloor \frac{l_i - 1}{2^{p + 1}} \right\rfloor$. 866 867 But wait! This is just $[x^{k^{\,\prime}}]F(a_i \cdot x^{c_i} + b_i \cdot x^{d_i})$. So we'll let $B_i(x) = a_i \cdot x^{c_i} + b_i \cdot x^{d_i}$. 868 869 Therefore, 870 871 $[x^k](F(A_1(x)) \cdot F(A_2(x)) \cdot \ldots \cdot F(A_n(x))) = [x^{k^{\,\prime}}]F(B_1(x) \star B_2(x) \star \ldots \star B_n(x))$ 872 873 Now we need to find a way to compute $F(B_1(x) \star B_2(x) \star \ldots \star B_n(x))$ efficiently. 874 875 **Step 3.1** 876 877 First, we can normalize each polynomial: $a \cdot x^c + b \cdot x^d = (a + b \cdot x^{c\,\oplus\,d}) \star x^c$ 878 879 Now all polynomials have the form $a_i + b_i \cdot x^{c_i}$. 880 881 **Step 3.2** 882 883 Next, we can convolve polynomials with matching powers of $x$: 884 885 $(a_1 + b_1 \cdot x^c) \star (a_2 + b_2 \cdot x^c) = (a_1 a_2 + b_1 b_2) + (a_1 b_2 + b_1 a_2) \cdot x^c $ 886 887 Now the expression is of the form: 888 889 $F((a_0 + b_0 \cdot x^0) \star (a_1 + b_1 \cdot x^1) \star \ldots \star (a_{2^m - 1} + b_{2^m - 1} \cdot x^{2^m - 1})) = F(B_0) \cdot F(B_1) \cdot \ldots \cdot F(B_{2^m - 1})$ 890 891 **Step 3.3** 892 893 Finally, we have: 894 895 $\displaystyle [x^k] (F(B_0) \cdot F(B_1) \cdot \ldots \cdot F(B_{2^m - 1})) = \prod_{i = 0}^{2^m - 1} (a_i + b_i \cdot s(k, i))$ 896 897 This can be computed using SOS DP.