codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.