codeforces-scrape

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

2217.md (39094B)


      1 Source: https://codeforces.com/blog/entry/152772
      2 
      3 # [2217A - The Equalizer](/contest/2217/problem/A "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
      4 
      5 **Idea:** [shakr](/profile/shakr "Expert shakr")   
      6  **Problem Setting:** [AS23](/profile/AS23 "Expert AS23"), [shakr](/profile/shakr "Expert shakr")
      7 
      8 **Hint 1**
      9 
     10 What if Shaunak never uses the special move?
     11 
     12 **Hint 2**
     13 
     14 If Shaunak uses the special move, is using it on the first turn any different from using it later?
     15 
     16 **Hint 3**
     17 
     18 The above two cases are independent, and give you two conditions for Shaunak to win. What are they?
     19 
     20 **Solution**
     21 
     22 In a game without special moves, every turn reduces the total sum of the array, $\sum a_i$, by exactly $1$. Thus, the game lasts exactly $\sum a_i$ turns. The first player (Shaunak) wins if $\sum a_i$ is odd, and the second player (Yash) wins if $\sum a_i$ is even.
     23 
     24 * **If $\sum a_i$ is odd:** Shaunak plays normally and wins. He doesn't need the special move.
     25 * **If $\sum a_i$ is even:** Shaunak is guaranteed to lose normally, so he must use his special move. Using it on his first turn sets the new array sum to $n \cdot k$. Now, Yash is forced to play first in a standard game. Following the parity logic, Yash loses (and Shaunak wins) if $n \cdot k$ is even.
     26 
     27 Therefore, Shaunak wins if $\sum a_i$ is odd or if $n \cdot k$ is even. Otherwise, Yash wins.
     28 
     29 **C++ Code**
     30 
     31 ```
     32 #include <iostream>
     33  
     34 int main()
     35 {
     36     int t = 1;
     37     std::cin >> t;
     38  
     39     while (t--) {
     40         int n, k;
     41         std::cin >> n >> k;
     42         bool ans = ((n * k) % 2 == 0); // Either n*k is even
     43  
     44         int tot = 0; 
     45         while (n--) {
     46             int x;
     47             std::cin >> x; 
     48             tot += x;
     49         } 
     50         ans |= tot & 1; // Or sum(a) is odd
     51         
     52         std::cout << (ans ? "YES" : "NO") << std::endl;
     53     }
     54  
     55     return 0;
     56 }
     57 ```
     58 
     59 **Python Code**
     60 
     61 ```
     62 t = int(input())
     63  
     64 for _ in range(t):
     65     n, k = map(int, input().split())
     66     arr = list(map(int, input().split()))
     67     
     68     tot = sum(arr)
     69     ans = (tot % 2 == 1) or ((n * k) % 2 == 0)
     70     
     71     print("YES" if ans else "NO")
     72 ```
     73 
     74 # [2217B - Flip the Bit (Easy Version)](/contest/2217/problem/B "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
     75 
     76 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Candidate Master SilverTongue1729")   
     77  **Problem Setting:** [penguinnoob](/profile/penguinnoob "Expert penguinnoob"), [sumit_kk10](/profile/sumit_kk10 "Expert sumit_kk10"), [Prakul_Agrawal](/profile/Prakul_Agrawal "Expert Prakul_Agrawal")
     78 
     79 **Hint 1**
     80 
     81 Think of the array in terms of segments instead of individual elements. What really matters is where the value changes. Define a **boundary** as a position where adjacent elements differ. How does a flip operation affect boundaries?
     82 
     83 **Hint 2**
     84 
     85 A valid operation must include the special index. So one endpoint of the flip lies to the left of it, and the other to the right (or at it). What does this imply about which boundaries you can remove together?
     86 
     87 **Hint 3**
     88 
     89 You can pair boundaries from the left and right. What happens to the remaining ones after pairing?
     90 
     91 **Solution**
     92 
     93 Let $V$ be the target value (the value at the special index $p_1$). Construct a binary array $b$ of size $n+2$ (0-indexed) where $b_i = 1$ if $a_i = V$, and $0$ otherwise. Pad the array with $b_0 = 1$ and $b_{n+1} = 1$.
     94 
     95 Define a boundary as an index $j$ where $b_j \neq b_{j+1}$. Our goal is to eliminate all boundaries.
     96 
     97 * Flipping a range $[l, r]$ toggles the boundaries at $l-1$ and $r$.
     98 * The pivot constraint $l \le p_1 \le r$ means one toggled boundary must be $ \lt p_1$ and the other $\ge p_1$.
     99 
    100 This naturally divides the boundaries into two independent regions:
    101 
    102 1. Region 1: Boundaries in $[0, p_1 - 1]$. Let the count be $x_1$.
    103 2. Region 2: Boundaries in $[p_1, n]$. Let the count be $x_2$.
    104 
    105 Each valid operation removes at most one boundary from Region 1 and one from Region 2. We can pair boundaries across regions at a cost of 1 operation per pair. Once the smaller region is exhausted, the remaining boundaries in the larger region must be eliminated individually.
    106 
    107 Thus, the minimum operations required are:
    108 
    109 $ \max(x_1, x_2) $
    110 
    111 **Time Complexity:** $O(n)$
    112 
    113 **C++ Code**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 using namespace std;
    118  
    119 void solve() {
    120     int n, k;
    121     cin >> n >> k;
    122     vector<int> arr(n+2);
    123     for (int i = 1; i <= n; i++) {
    124         cin >> arr[i];
    125     }
    126     int pivot;
    127     cin >> pivot;
    128  
    129     arr[0] = arr[n+1] = arr[pivot];
    130  
    131     int countL = 0, countR = 0;
    132     for (int i = 0; i < pivot; i++) {
    133         if (arr[i] != arr[i+1]) {
    134             countL++;
    135         }
    136     }
    137     for (int i = pivot; i < n+1; i++) {
    138         if (arr[i] != arr[i+1]) {
    139             countR++;
    140         }
    141     }
    142  
    143     cout << max(countL, countR) << "\n";
    144 }
    145  
    146 int main() {
    147     ios::sync_with_stdio(0);
    148     cin.tie(0);
    149     int t;
    150     cin>>t;
    151     while(t--) {
    152         solve();
    153     }
    154     return 0;
    155 }
    156 ```
    157 
    158 # [2217C - Grid Covering](/contest/2217/problem/C "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    159 
    160 **Idea:** [biswas](/profile/biswas "Specialist biswas")   
    161  **Problem Setting:** [biswas](/profile/biswas "Specialist biswas"), [SavageFighter001](/profile/SavageFighter001 "Candidate Master SavageFighter001"), [shakr](/profile/shakr "Expert shakr")
    162 
    163 **Hint 1**
    164 
    165 Think of a one-dimensional array that wraps around itself. Check whether repeatedly jumping by a fixed step on such an array can ever let you visit every position or just a subset.
    166 
    167 **Hint 2**
    168 
    169 Treat each position as two states: $(i,j,\text{last move was Down})$ and $(i,j,\text{last move was Right})$. Follow the sequence and count how many such states appear before the path cycles. Compare this with the total possible states, i.e., $2 \cdot n \cdot m$.
    170 
    171 **Solution**
    172 
    173 To visit every row and column, we strictly require $\gcd(n, a) = 1$ and $\gcd(m, b) = 1$. Assume these hold.
    174 
    175 A full cycle of moves (1 Down, 1 Right) yields a displacement of $(+a, +b)$. To return to $A_{1,1}$ with the exact same next move, we need $p$ cycles where:
    176 
    177 $ p \cdot a \equiv 0 \pmod n, \quad p \cdot b \equiv 0 \pmod m $
    178 
    179 The minimal such $p$ is $\text{lcm}(n, m)$. Thus, the path loops entirely after $2 \cdot \text{lcm}(n, m)$ moves.
    180 
    181 Because the maximum number of unique states Prakul can visit is $2 \cdot \text{lcm}(n, m)$, we compare this with the total number of grid tiles.
    182 
    183 * **If $\gcd(n, m) \ge 3$:**  
    184    The grid size is $n \cdot m = \gcd(n, m) \cdot \text{lcm}(n, m) \ge 3 \cdot \text{lcm}(n, m)$.  
    185    This strictly exceeds the maximum visitable states ($2 \cdot \text{lcm}(n, m)$), so covering the grid is impossible.
    186   
    187 * **If $\gcd(n, m) = 1$:**  
    188    Here, $2 \cdot \text{lcm}(n, m) = 2 \cdot n \cdot m$.  
    189    The loop length is twice the number of grid tiles. By symmetry, every tile is visited exactly twice (once in each direction). Hence, the grid is fully covered.
    190   
    191 * **If $\gcd(n, m) = 2$:**  
    192    Here, $2 \cdot \text{lcm}(n, m) = n \cdot m$.  
    193    Prakul covers the grid if and only if he never visits a tile in both direction states. Let's assume a tile is visited in both states.   
    194     
    195    In State 1 (ready to move Right), after $k_1$ full cycles, his displacement is $k_1 \cdot a$ rows and $k_1 \cdot b$ columns.  
    196    In State 2 (ready to move Down), he has completed $k_2$ full cycles **plus** one extra Right move, making his displacement $k_2 \cdot a$ rows and $(k_2 + 1) \cdot b$ columns.  
    197     
    198    For these to be the exact same tile in the wrapping grid, their displacements must be equivalent: $ k_1 \cdot a \equiv k_2 \cdot a \pmod n \Rightarrow k_1 \equiv k_2 \pmod n $ $ k_1 \cdot b \equiv (k_2 + 1)\cdot b \pmod m \Rightarrow k_1 \equiv k_2 + 1 \pmod m $ Letting the difference in cycles be $x = k_1 - k_2$. Then: $ x \equiv 0 \pmod n, \quad x \equiv 1 \pmod m $ This implies: $ c \cdot n - d \cdot m = 1 $ By Bézout's identity, this is possible only if $\gcd(n, m)$ divides $1$. But $\gcd(n, m) = 2$, so this is impossible. Hence, no tile is visited in both states, and exactly $n \cdot m$ distinct tiles are visited.
    199 
    200 Therefore, Prakul covers the grid if and only if $\gcd(n, a) = 1$, $\gcd(m, b) = 1$, and $\gcd(n, m) \le 2$.
    201 
    202 **C++ Code**
    203 
    204 ```
    205 #include <iostream>
    206 #include <numeric>
    207  
    208 int main()
    209 {
    210     int t = 1;
    211     std::cin >> t;
    212  
    213     while (t--) {
    214         long long n, m, a, b;
    215         std::cin >> n >> m >> a >> b;
    216         bool possible = (
    217             std::gcd(n, a) == 1 and
    218             std::gcd(m, b) == 1 and
    219             std::gcd(n, m) <= 2
    220         );
    221         std::cout << (possible ? "YES" : "NO") << std::endl;
    222     }
    223  
    224     return 0;
    225 }
    226 ```
    227 
    228 # [2217D - Flip the Bit (Hard Version)](/contest/2217/problem/D "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    229 
    230 **Idea:** [Prakul_Agrawal](/profile/Prakul_Agrawal "Expert Prakul_Agrawal")   
    231  **Problem Setting:** [h2rsh](/profile/h2rsh "Master h2rsh"), [Prakul_Agrawal](/profile/Prakul_Agrawal "Expert Prakul_Agrawal")
    232 
    233 **Hint 1**
    234 
    235 Similar to the easy version, think in terms of the boundaries where adjacent values differ. But now, the special indices divide the array into multiple regions.
    236 
    237 **Hint 2**
    238 
    239 You want to maximize how many times you can pair two boundaries from different regions (removing two in one operation). When is this always possible?
    240 
    241 **Hint 3**
    242 
    243 Let $S$ be the total number of boundaries and $X$ the maximum number in any region. When does one region have too many boundaries compared to the rest?
    244 
    245 **Hint 4**
    246 
    247 If one region dominates (has more than half the total boundaries), some boundaries are forced to be removed individually. Otherwise, all boundaries can be paired.
    248 
    249 **Solution**
    250 
    251 Similar to the easy version, construct a padded binary array $b$ where $b_i = 1$ if $a_i$ matches the target value, else $0$. A boundary exists at $j$ if $b_j \neq b_{j+1}$. Flipping $[l, r]$ toggles boundaries at $l-1$ and $r$.
    252 
    253 The constraint that $[l, r]$ must contain at least one pivot $p_i$ means we can only pair two boundaries in a single operation if they are separated by at least one pivot.
    254 
    255 The $k$ pivots divide the boundaries into $k + 1$ independent regions:
    256 
    257 * Region 1: $[0, p_1 - 1]$
    258 * Region $i$: $[p_{i-1}, p_i - 1]$ for $2 \le i \le k$
    259 * Region $k+1$: $[p_k, n]$
    260 
    261 Let $S$ be the total number of boundaries across all regions, and $X$ be the maximum number of boundaries in any single region.
    262 
    263 We want to maximize pairing boundaries across different regions (which removes 2 boundaries for 1 operation). Removing a boundary stuck in its own region costs 1 operation per boundary.
    264 
    265 1. **Case 1 ($X \le S/2$):** No region dominates. We can optimally pair every boundary with one from a different region. Total operations: $S / 2$.
    266 2. **Case 2 ($X \gt S/2$):** One region has more boundaries than the rest combined. We pair all $S - X$ "outsider" boundaries with boundaries from the majority region. The remaining $X - (S - X) = 2X - S$ boundaries in the majority region must be resolved individually. Total operations: $(S - X) + (2X - S) = X$.
    267 
    268 Combining these conditions gives the minimum number of operations:
    269 
    270 $ \max(S / 2, X) $
    271 
    272 **Time complexity:** $O(n)$
    273 
    274 **C++ Code**
    275 
    276 ```
    277 #include <bits/stdc++.h>
    278 using namespace std;
    279  
    280 void solve() {
    281     int n, k;
    282     cin >> n >> k;
    283     vector<int> arr(n+2);
    284     for (int i = 1; i <= n; i++) {
    285         cin >> arr[i];
    286     }
    287     vector<int> pivots(k+2);
    288     for (int i = 1; i <= k; i++) {
    289         cin >> pivots[i];
    290     }
    291     arr[0] = arr[n+1] = arr[pivots[1]];
    292     pivots[k+1] = n+1;
    293  
    294     int S = 0, X = 0;
    295     for (int i = 0; i <= k; i++) {
    296         int count = 0;
    297         for (int j = pivots[i]; j < pivots[i+1]; j++) {
    298             if (arr[j] != arr[j+1]) {
    299                 count++;
    300             }
    301         }
    302         S += count;
    303         X = max(X, count);
    304     }
    305  
    306     cout << max(S / 2, X) << "\n";
    307 }
    308  
    309 int main() {
    310     ios::sync_with_stdio(0);
    311     cin.tie(0);
    312     int t;
    313     cin>>t;
    314     while(t--) {
    315         solve();
    316     }
    317     return 0;
    318 }
    319 ```
    320 
    321 # [2217E - Definitely Larger](/contest/2217/problem/E "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    322 
    323 **Idea:** [shiven](/profile/shiven "International Master shiven")   
    324  **Problem Setting:** [tanaygad](/profile/tanaygad "Candidate Master tanaygad"), [kevaljain](/profile/kevaljain "Expert kevaljain")
    325 
    326 **Hint 1**
    327 
    328 For each index $i$, the only indices that can ever contribute to $d_i$ are those with $j \gt i$ and $p_j \gt p_i$; so first check whether $d_i$ exceeds their count.
    329 
    330 **Hint 2**
    331 
    332 What happens if you process indices in decreasing order of $p_i$? Then one part of the domination condition is already automatically satisfied.
    333 
    334 **Solution**
    335 
    336 There are a few ways to approach this problem, but the most elegant solutions involve greedy construction. We will discuss two distinct but equally valid greedy strategies.
    337 
    338 **Method 1: Insertion by Decreasing $p_i$**  
    339  This method determines the relative order of the elements in $q$ by processing the array based on the values of $p_i$.
    340 
    341 Let's process the indices $i$ in decreasing order of their $p_i$ values (from $n$ down to $1$). We will maintain a list, ord, of the already processed indices. This list represents the elements sorted by their future $q$ values.
    342 
    343 When we process the current index $i$, every index $j$ already in ord satisfies $p_j \gt p_i$. This perfectly handles the second condition of domination. Now we just need to satisfy the remaining conditions: $j \gt i$ and $q_j \gt q_i$.
    344 
    345 Let $m$ be the number of indices $j$ currently in ord such that $j \gt i$. These are the only candidates that could possibly dominate $i$.
    346 
    347 * If $d_i \gt m$, it is impossible to satisfy the condition, and we should output -1.
    348 * Otherwise, to ensure exactly $d_i$ elements dominate $i$, we need exactly $d_i$ of these valid $j$ indices to have a larger $q$ value (meaning they are placed *after* $i$ in ord).
    349 * Consequently, exactly $m - d_i$ of these valid $j$ indices must be placed *before* $i$ in ord.
    350 
    351 We can simply iterate through ord, count until we have passed $m - d_i$ elements that satisfy $j \gt i$, and insert $i$ immediately after them. Once all $n$ indices are inserted into ord, their 1-based positions in the list become their actual $q_i$ values.
    352 
    353 **Method 2: Assigning $q_i$ from Large to Small**  
    354  Alternatively, we can build $q$ directly by deciding which index receives the value $n$, then $n-1$, down to $1$.
    355 
    356 Suppose we are trying to place the largest available value. The index $i$ that receives this value will have $q_i$ greater than all remaining unassigned elements. Therefore, nothing processed *after* $i$ can possibly dominate it. For $i$ to be a valid choice, its current $d_i$ must be exactly $0$.
    357 
    358 If there are multiple indices with $d_i = 0$, which one should we pick? We should greedily pick the one with the **smallest** index $i$. Picking a smaller index avoids "blocking" elements to its left that might need to be dominated by it later.
    359 
    360 Once we select this index $i$ and assign it the current maximum value, it becomes a valid dominator for any unassigned index $j$ that sits to its left ($j \lt i$) and has a smaller $p$ value ($p_j \lt p_i$). We simulate this by decrementing $d_j$ by $1$ for all such valid $j$. We repeat this process until all elements are assigned. If at any step no unassigned element has $d_i = 0$, the array is invalid, and we output -1.
    361 
    362 **C++ Code**
    363 
    364 ```
    365 #include <bits/stdc++.h>
    366 using namespace std;
    367 
    368 int main() {
    369     ios::sync_with_stdio(false);
    370     cin.tie(nullptr);
    371 
    372     int t;
    373     cin >> t; 
    374 
    375     while (t--) {
    376         int N;
    377         cin >> N;
    378 
    379         vector<int> P(N + 1), pos(N + 1);
    380         for (int i = 1; i <= N; i++) {
    381             cin >> P[i];
    382             pos[P[i]] = i; 
    383         }
    384 
    385         vector<int> D(N + 1);
    386         for (int i = 1; i <= N; i++) cin >> D[i];
    387 
    388         vector<int> ord(N);
    389 
    390         bool ok = true;
    391 
    392         for (int val = N; val >= 1 && ok; --val) {
    393             int i = pos[val];
    394 
    395             int m = 0;
    396             for (int idx : ord) if (idx > i) ++m;
    397 
    398             if (D[i] > m) {
    399                 ok = false;
    400                 break;
    401             }
    402 
    403             int needBefore = m - D[i]; 
    404             int cnt = 0;
    405             int insertPos = 0;
    406 
    407             while (insertPos < (int)ord.size() && cnt < needBefore) {
    408                 if (ord[insertPos] > i) ++cnt;
    409                 ++insertPos;
    410             }
    411 
    412             ord.insert(ord.begin() + insertPos, i);
    413         }
    414 
    415         if (!ok) {
    416             cout << -1 << '\n';
    417             continue;
    418         }
    419 
    420         vector<int> A(N + 1, 0);
    421         for (int k = 0; k < N; k++) {
    422             A[ord[k]] = k + 1;
    423         }
    424 
    425         for (int i = 1; i <= N; i++) {
    426             cout << A[i] << (i == N ? '\n' : ' ');
    427         }
    428     }
    429 
    430     return 0;
    431 }
    432 ```
    433 
    434 # [2217F - Interval Game](/contest/2217/problem/F "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    435 
    436 **Idea:** [Prakul_Agrawal](/profile/Prakul_Agrawal "Expert Prakul_Agrawal")   
    437  **Problem Setting:** [Prakul_Agrawal](/profile/Prakul_Agrawal "Expert Prakul_Agrawal")
    438 
    439 **Hint 1**
    440 
    441 Model the game as a Nim game. Each interval contributes two independent piles. The whole game becomes a 4-pile Nim game. Who wins depends only on the XOR (Nim-sum) of all piles.
    442 
    443 **Hint 2**
    444 
    445 Alice can control the XOR contribution of the first interval. What values of XOR can she achieve?
    446 
    447 **Hint 3**
    448 
    449 Let $X$ be Alice's XOR and $Z$ be the XOR from the random interval. Alice loses only when $X = Z$. So instead of maximizing wins directly, minimize how often $Z = X$ happens.
    450 
    451 **Hint 4**
    452 
    453 Fix a value of $X$. Count how many pairs $(a, b)$ (derived from the second interval) satisfy $a \oplus b = X$ under the constraint $a + b \le x_2 - 1$.
    454 
    455 **Hint 5**
    456 
    457 Use the identity:
    458 
    459 $ a + b = (a \oplus b) + 2(a \ \& \ b) $
    460 
    461 This reduces the problem to counting integers with a bitmask constraint.
    462 
    463 **Solution**
    464 
    465 We can model this problem using the standard Game of Nim. Consider a single interval $[l, r]$ constrained within $[1, x]$.
    466 
    467 * Decreasing $l$ (shifting left boundary) is equivalent to reducing a pile of size $l-1$.
    468 * Increasing $r$ (shifting right boundary) is equivalent to reducing a pile of size $x-r$.
    469 
    470 Thus, the game is played on 4 piles of stones with sizes:
    471 
    472 $ l_1 - 1, \quad x_1 - r_1, \quad l_2 - 1, \quad x_2 - r_2 $
    473 
    474 The game ends when no moves are possible (all piles are size 0). Alice wins if the Nim-sum (XOR sum) of all pile sizes is non-zero.
    475 
    476 Let $X$ be the XOR sum of the first interval's piles:
    477 
    478 $ X = (l_1 - 1) \oplus (x_1 - r_1) $
    479 
    480 Let $Z$ be the XOR sum of the second interval's piles:
    481 
    482 $ Z = (l_2 - 1) \oplus (x_2 - r_2) $
    483 
    484 Alice wins if $X \oplus Z \neq 0$, which implies $Z \neq X$. Since the second interval is chosen uniformly at random, to maximize her winning probability, Alice must choose $l_1, r_1$ (and thus determine $X$) such that the number of outcomes where $Z = X$ is minimized.
    485 
    486 Alice can produce any XOR value $X$ in the range $[0, x_1 - 1]$. A simple construction to achieve a specific XOR value $X$ is to set the first pile to 0 and the second to $X$.
    487 
    488 * Set $l_1 = 1$ (Pile size $1-1=0$)
    489 * Set $r_1 = x_1 - X$ (Pile size $x_1 - (x_1 - X) = X$)
    490 
    491 This gives an interval $[1, x_1 - X]$, which is valid for any $X \lt x_1$.
    492 
    493 We need to count how many valid intervals $[l_2, r_2]$ produce an XOR sum equal to Alice's chosen $X$. Let the pile sizes for the second interval be $a = l_2 - 1$ and $b = x_2 - r_2$. The constraints on the second interval are:
    494 
    495 $ a \ge 0, \quad b \ge 0, \quad a + b \le x_2 - 1 $
    496 
    497 We are looking for the count of pairs $(a, b)$ such that $a \oplus b = X$ and their sum fits in the range. We use the fundamental relationship between sum and XOR:
    498 
    499 $ a + b = (a \oplus b) + 2(a \ \& \ b) $
    500 
    501 Let $Y = a + b$. Substituting $a \oplus b = X$, we get:
    502 
    503 $ Y = X + 2(a \ \& \ b) $
    504 
    505 Rearranging for the AND term:
    506 
    507 $ 2(a \ \& \ b) = Y - X $
    508 
    509 This equation gives us the necessary conditions for a valid sum $Y$:
    510 
    511 1. $Y \ge X$ (since $a \ \& \ b \ge 0$)
    512 2. $Y - X$ must be divisible by 2
    513 3. **Crucial Condition:** The bits set in $(a \ \& \ b)$ cannot be set in $(a \oplus b)$. Mathematically: $((Y - X) / 2) \ \& \ X = 0$
    514 
    515 If these conditions are met, how many pairs $(a, b)$ sum to $Y$ with XOR $X$? For every bit set in $X$, exactly one of $a$ or $b$ must have that bit set (2 choices: $1/0$ or $0/1$). The bits in the Bitwise-AND of $a$ and $b$ are fixed to 1 for both. Thus, for a valid $Y$, there are $2^{\text{popcount}(X)}$ ways to form the pairs.
    516 
    517 We can simplify the condition by letting $K = (Y - X) / 2$. The condition $Y \le x_2 - 1$ becomes:
    518 
    519 $ X + 2K \le x_2 - 1 \implies K \le \left\lfloor \frac{x_2 - 1 - X}{2} \right\rfloor $
    520 
    521 Let $Limit = \left\lfloor \frac{x_2 - 1 - X}{2} \right\rfloor$. The problem reduces to finding the count of integers $K$ such that:
    522 
    523 1. $0 \le K \le Limit$
    524 2. $K \ \& \ X = 0$
    525 
    526 This specific counting problem (finding numbers less than a limit with a mask constraint) can be solved using simple bitwise logic (Greedy or Digit DP style) in $O(\log(\text{limit}))$.
    527 
    528 Therefore:
    529 
    530 * Iterate $X$ from $0$ to $x_1 - 1$
    531 * Calculate $Limit = (x_2 - 1 - X) / 2$
    532 * Count valid $K$'s in $[0, Limit]$ disjoint from $X$
    533 * Total configurations for this $X$ is: $(\text{Count of } K) \times 2^{\text{popcount}(X)}$
    534 * Pick the $X$ that minimizes this total
    535 
    536 There are $x_1$ choices for $X$. The counting step takes $O(\log x_2)$. **Total Complexity:** $O(x_1 \log x_2)$.
    537 
    538 **C++ Code**
    539 
    540 ```
    541 #include <bits/stdc++.h>
    542 using namespace std;
    543  
    544 long long count_valid_k(int limit, int mask) {
    545     if (limit < 0) return 0;
    546  
    547     long long count = 0;
    548  
    549     for (int i = 20; i >= 0; i--) {
    550         int bit_limit = (limit >> i) & 1;
    551         int bit_mask = (mask >> i) & 1;
    552  
    553         int lower_free_bits = 0;
    554         for (int j = 0; j < i; j++) {
    555             if (!((mask >> j) & 1)) {
    556                 lower_free_bits++;
    557             }
    558         }
    559  
    560         if (bit_mask == 1) {
    561             if (bit_limit == 1) {
    562                 count += (1LL << lower_free_bits);
    563                 return count;
    564             }
    565         } else {
    566             if (bit_limit == 1) {
    567                 count += (1LL << lower_free_bits);
    568             }
    569         }
    570     }
    571  
    572     return count + 1;
    573 }
    574  
    575 void solve() {
    576     int x1, x2;
    577     cin >> x1 >> x2;
    578  
    579     long long min_matching_outcomes = -1;
    580     int best_X = -1;
    581  
    582     for (int X = 0; X < x1; X++) {
    583         int val = x2 - 1 - X;
    584         long long current_matching_outcomes = 0;
    585  
    586         if (val < 0) {
    587             current_matching_outcomes = 0;
    588         } else {
    589             int limit = val / 2;
    590             long long k_count = count_valid_k(limit, X);
    591             current_matching_outcomes = k_count * (1LL << __builtin_popcount(X));
    592         }
    593  
    594         if (min_matching_outcomes == -1 || current_matching_outcomes < min_matching_outcomes) {
    595             min_matching_outcomes = current_matching_outcomes;
    596             best_X = X;
    597         }
    598  
    599         if (min_matching_outcomes == 0) break;
    600     }
    601  
    602     int l1 = 1;
    603     int r1 = x1 - best_X;
    604  
    605     cout << l1 << " " << r1 << "\n";
    606 }
    607  
    608 int main() {
    609     int t;
    610     cin >> t;
    611     while (t--) {
    612         solve();
    613     }
    614     return 0;
    615 }
    616 ```
    617 
    618 # [2217G - Down the Pivot](/contest/2217/problem/G "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    619 
    620 **Idea:** [SilverTongue1729](/profile/SilverTongue1729 "Candidate Master SilverTongue1729")   
    621  **Problem Setting:** [Faizal](/profile/Faizal "Candidate Master Faizal"), [SilverTongue1729](/profile/SilverTongue1729 "Candidate Master SilverTongue1729")
    622 
    623 **Hint 1**
    624 
    625 If we consider only flipping on root-to-$u$ paths, how many labellings are possible such that the cost is exactly $k$?
    626 
    627 Answer: There will be exactly $\binom{n}{k}$ labellings for a tree of size $n$, regardless of the tree's shape.
    628 
    629 **Hint 2**
    630 
    631 A path through the root $r$ consists of a root-to-node path in the left subtree $L$, the root $r$ itself, and a root-to-node path in the right subtree $R$ (where either subtree path can be empty).
    632 
    633 **Hint 3**
    634 
    635 Because we can pair one needed flip in $L$ with one needed flip in $R$ into a single operation, clearing both subtrees requires exactly $m = \max(S(L), S(R))$ operations.
    636 
    637 These $m$ operations will flip the root's label exactly $m$ times. If the root's final label is still $1$, we require exactly $1$ additional operation (flipping just the root itself, using empty paths for $L$ and $R$).
    638 
    639 Thus, the total cost to clear the tree is:
    640 
    641 $\text{Cost} = m + (a(r) \oplus (m \bmod 2))$
    642 
    643 **Hint 4**
    644 
    645 For a fixed pair of subtrees (which fixes $m$), we have two choices for the root's initial label $a(r) \in {0, 1}$. Exactly one choice results in a total cost of $m$, and the other results in a cost of $m + 1$.
    646 
    647 Consequently, the tree will have a cost of exactly $k$ if and only if $m \in {k, k-1}$. This is mathematically equivalent to the condition $m \le k$ minus the condition $m \le k - 2$.
    648 
    649 **Hint 5**
    650 
    651 For a fixed split of sizes $i$ and $j = n - 1 - i$, what is the number of valid $(L, R)$ pairs such that $\max(S(L), S(R)) \le t$? Calculate this, then iterate $i$ from $0$ to $n-1$.
    652 
    653 **Solution**
    654 
    655 The problem can be drastically simplified by transforming the tree labels into a different state. Let $a(v) \in {0, 1}$ be the initial label of node $v$. For any node $v$, define a new value:
    656 
    657 $x(v) = a(v) \oplus a(\text{left}(v)) \oplus a(\text{right}(v))$
    658 
    659 (If a child does not exist, we treat its label as $0$).
    660 
    661 Why is this transformation useful? Consider what happens to $x(v)$ when we perform an operation on a simple path from the root to some node $u$: * If $v$ is on the path but is *not* the endpoint $u$, both $a(v)$ and exactly one of its children's labels are flipped. Thus, $x(v)$ changes by $1 \oplus 1 = 0$. * If $v$ is the endpoint $u$, $a(v)$ is flipped, but neither of its children is on the path. Thus, $x(v)$ changes by $1 \oplus 0 = 1$. * If $v$ is not on the path, neither $a(v)$ nor its children are flipped. Thus, $x(v)$ changes by $0$.
    662 
    663 An operation on a root-to-$u$ path toggles *exactly* $x(u)$ and leaves all other $x(v)$ values unchanged!
    664 
    665 Furthermore, the mapping from $a(v)$ to $x(v)$ is a perfect bijection for any fixed tree structure (you can uniquely reconstruct $a(v)$ from $x(v)$ working bottom-up). Therefore, to zero-out a subtree $T$ using only paths starting from its root, we must flip exactly the paths ending at nodes where $x(v) = 1$. The minimum number of operations for a subtree $T$ is simply $S(T) = \sum_{v \in T} x(v)$. Since $x(v) \in {0, 1}$, the number of labelings of a tree of size $m$ that yield exactly $S(T) = s$ is $\binom{m}{s}$, independent of the tree's shape.
    666 
    667 *Evaluating the Whole Tree:* An allowed operation is a path through the root $r$. This path consists of a root-to-node path in the left subtree $L$, the root $r$ itself, and a root-to-node path in the right subtree $R$ (where either subtree path can be empty).
    668 
    669 Because we can pair one needed flip in $L$ with one needed flip in $R$ into a single operation, clearing both subtrees requires exactly $m = \max(S(L), S(R))$ operations.
    670 
    671 These $m$ operations will flip the root's label exactly $m$ times. If the root's final label is still $1$, we require exactly $1$ additional operation (flipping just the root itself, using empty paths for $L$ and $R$). Thus, the total cost to clear the tree is:
    672 
    673 $\text{Cost} = m + (a(r) \oplus (m \bmod 2))$
    674 
    675 For a fixed pair of subtrees (which fixes $m$), we have two choices for the root's initial label $a(r) \in {0, 1}$. Exactly one choice results in a total cost of $m$, and the other results in a cost of $m + 1$. Consequently, the tree will have a cost of exactly $k$ if and only if $m \in {k, k-1}$. This is mathematically equivalent to the condition $m \le k$ minus the condition $m \le k - 2$.
    676 
    677 *Counting the Trees:* Let $C_t$ be the $t$-th Catalan number (the number of binary tree structures on $t$ nodes). Define the prefix sum of binomial coefficients as:
    678 
    679 $BS(m, t) = \sum_{s=0}^{\min(m, t)} \binom{m}{s}$
    680 
    681 (with $BS(m, t) = 0$ for $t \lt 0$).
    682 
    683 For a fixed split of sizes $i$ and $j = n - 1 - i$, the number of valid $(L, R)$ pairs such that $\max(S(L), S(R)) \le t$ is given by:
    684 
    685 $C_i \cdot C_j \cdot BS(i, t) \cdot BS(j, t)$
    686 
    687 To find the number of trees with cost exactly $k$, we subtract the valid pairs for $t = k-2$ from the valid pairs for $t = k$:
    688 
    689 $F(n, k) = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} \cdot \Big( BS(i, k) \cdot BS(n-1-i, k) - BS(i, k-2) \cdot BS(n-1-i, k-2) \Big) \pmod{10^9+7}$
    690 
    691 *Complexity and Optimization:* We need to calculate $BS(m, t)$ for all $m$ up to $n$, for fixed values of $t \in {k, k-2}$. Recomputing the sum naively would be too slow. Instead, we can use the identity:
    692 
    693 $BS(m, t) = 2 \cdot BS(m-1, t) - \binom{m-1}{t}$
    694 
    695 This allows us to compute $BS(m, k)$ and $BS(m, k-2)$ iteratively in $\mathcal{O}(1)$ transitions. The Catalan numbers can also be precomputed in linear time. Thus, the entire summation takes $\mathcal{O}(n)$ time per test case.
    696 
    697 **C++ Code**
    698 
    699 ```
    700 #include <bits/stdc++.h>
    701 #include <ext/pb_ds/assoc_container.hpp>
    702  
    703 using namespace std;
    704 #define int long long
    705 #define all(s) s.begin(), s.end()
    706 #define sz(s) (int)s.size()
    707 #define testcases \
    708     cin >> tt;    \
    709     for (i = 1; i <= tt; i++)
    710 #define fast                      \
    711     ios_base::sync_with_stdio(0); \
    712     cin.tie(NULL);                \
    713     cout.tie(NULL)
    714  
    715 const int M = 1e9 + 7;
    716  
    717 using i32 = int32_t;
    718 template <const auto mod>
    719 struct mint {
    720     template<typename T = i32>
    721     constexpr mint(T x = 0) : val(x % mod + (x < 0) * mod) {}
    722     mint &operator+=(const mint &b) {
    723         val += b.val;
    724         val -= mod * (val >= mod);
    725         return *this;
    726     }
    727     mint &operator-=(const mint &b) {
    728         val -= b.val;
    729         val += mod * (val < 0);
    730         return *this;
    731     }
    732     mint &operator*=(const mint &b) {
    733         val = 1ll * val * b.val % mod;
    734         return *this;
    735     }
    736     mint &operator/=(const mint &b) { return *this *= b.inv(); }
    737     mint inv() const {
    738         i32 x = 1, y = 0, t;
    739         for (i32 a = val, b = mod; b; swap(a, b), swap(x, y))
    740             t = a / b, a -= t * b, x -= t * y;
    741         return mint(x);
    742     }
    743     mint pow(int b) const {
    744         mint a = *this, res(1);
    745         for (; b; a *= a, b /= 2)
    746             if (b & 1) res *= a;
    747         return res;
    748     }
    749     friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
    750     friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
    751     friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
    752     friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    753     friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
    754     friend bool operator!=(const mint &a, const mint &b) { return a.val != b.val; }
    755     friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }
    756     friend ostream &operator<<(ostream &os, const mint &a) { return os << a.val; }
    757     friend string to_string(const mint& a) { return to_string(a.val); } 
    758     i32 val;
    759 };
    760 using Mint = mint<M>;
    761 typedef vector<Mint> vm;
    762 typedef vector<vm> vvm;
    763  
    764 #define PREC_TILL (int) 2'000'000
    765 vector<Mint> factorials(PREC_TILL + 1);
    766 vector<Mint> invFactorials(PREC_TILL + 1);
    767 void prec() {
    768     factorials[0] = 1;
    769     for (int i = 1; i <= PREC_TILL; i++) factorials[i] = factorials[i - 1] * i;
    770     invFactorials.back() = factorials.back().inv();
    771     for (int i = PREC_TILL - 1; i >= 0; i--) {
    772         invFactorials[i] = invFactorials[i + 1] * (i + 1);
    773     }
    774 }
    775  
    776 Mint nCr(int n, int r) {
    777     if (r < 0 or r > n) return 0;
    778     return factorials[n] * invFactorials[n - r] * invFactorials[r];
    779 }
    780  
    781 Mint catalan(int n) {
    782     if (n < 0) return Mint(0);
    783     return factorials[2 * n] * invFactorials[n] * invFactorials[n + 1];    
    784 }
    785  
    786 void solve(__attribute__((unused)) int tt) {
    787     int n, k; cin >> n >> k;
    788     
    789     Mint ans = 0;
    790     
    791     for (auto y : {k - 1, k}) {
    792         vm prefbinom(n + 1);
    793         prefbinom[0] = 1;
    794         for (int i = 1; i <= n; i++) {
    795             prefbinom[i] = 2 * prefbinom[i - 1] - nCr(i - 1, y);
    796         }
    797  
    798         for (int i = 0, j = n - 1; i <= n - 1; i++, j--) {
    799             ans += 2 * catalan(i) * catalan(j) * nCr(i, y) * (prefbinom[j] - nCr(j, y));
    800         }
    801     
    802         for (int i = 0, j = n - 1; i <= n - 1; i++, j--) {
    803             ans += catalan(i) * catalan(j) * nCr(i, y) * nCr(j, y);
    804         }
    805     }
    806  
    807     cout << ans << "\n";
    808 }
    809  
    810 int32_t main() {
    811     fast;
    812     prec();
    813     int tt = 1;
    814     int i = 1;
    815     testcases
    816         solve(i);
    817 }
    818 ```
    819 
    820 # [2217H - Closer](/contest/2217/problem/H "Codeforces Round 1091 (Div. 2) and CodeCraft 26")
    821 
    822 **Idea:** [shiven](/profile/shiven "International Master shiven")   
    823  **Problem Setting:** [shiven](/profile/shiven "International Master shiven")
    824 
    825 **Solution**
    826 
    827 The key observation is that every chosen edge belongs to a matching, so every vertex can participate in at most one swap. If the two copies of some badge are initially at distance at least $4$, then even after moving both of them by one edge, they still cannot become adjacent. Any deal that can ever be sealed must come from a very small neighbourhood. This suggests a tree DP.
    828 
    829 Root the tree at vertex $1$. For a node $u$, after all swaps, the badge finally sitting on $u$ can only have come from:
    830 
    831 * $u$ itself,
    832 * $\mathrm{par}(u)$,
    833 * or one of the children of $u$.
    834 
    835 For every such vertex $x$, let $\text{f}[u][x]$ be the maximum total profit contributed by sealed deals whose upper endpoint lies inside the subtree of $u$, under the condition that after the reshuffle, vertex $u$ contains the badge that originally stood on vertex $x$.
    836 
    837 Now define $\text{best}[u] = \max_{x \ne \mathrm{par}(u)} \text{f}[u][x]$, and $\text{sum}[u] = \sum_{v \text{ child of } u} \text{best}[v].$
    838 
    839 Here, $\text{sum}[u]$ is the value obtained if every child subtree behaves independently in its best possible way.
    840 
    841 Let's compute some state $\text{f}[u][x]$. Let $c = a_x$, i.e. the badge that ends up at $u$.
    842 
    843 First, we account for how this badge arrives at $u$. If $x=u$ or $x=\mathrm{par}(u)$, no child subtree is forced yet. If $x$ is a child $v$ of $u$, then edge $(u,v)$ must be chosen in the matching. In that case, subtree $v$ cannot simply contribute $\text{best}[v]$; instead, after the swap, vertex $v$ must receive the old badge of $u$, so we must use the state $\text{f}[v][u]$. So compared to the default value $\text{sum}[u]$, bringing the badge from a child $v$ changes the contribution of that child by $\text{f}[v][u] - \text{best}[v]$.
    844 
    845 Now we ask whether the deal with badge $c$ can be sealed at $u$. Let $y$ be the other occurrence of badge $c$.
    846 
    847 Since one copy of $c$ already ends at $u$, the only way to count this deal at $u$ is for the other copy to end at some child of $u$. Because each badge moves by at most one edge, only two cases are possible.
    848 
    849 The first case is that $y$ is already a child $t$ of $u$. Then we can seal badge $c$ on edge $(u,t)$. Inside subtree $t$, vertex $t$ must keep its own badge, so we replace $\text{best}[t]$ by $\text{f}[t][t]$, and gain $w_c$. The extra profit from this is $\text{f}[t][t] - \text{best}[t] + w_c$.
    850 
    851 The second case is that $y$ is a grandchild of $u$: say $y$ is a child of $t$ and $t$ is a child of $u$. Then we can move the badge from $y$ up to $t$, and seal badge $c$ on edge $(u,t)$. In this case we replace $\text{best}[t]$ by $\text{f}[t][y]$, so the extra profit is $\text{f}[t][y] - \text{best}[t] + w_c$.
    852 
    853 There is one important restriction here: this second case is invalid if $t=x$, because then $t$ would need to participate in two swaps, which is impossible since the chosen edges must form a matching.
    854 
    855 If neither of the above cases applies, then badge $c$ cannot form a sealed deal at $u$.
    856 
    857 Therefore, each transition is very small:
    858 
    859 * start with $\text{sum}[u]$,
    860 * maybe modify one child because its badge is sent to $u$,
    861 * maybe modify one child because it helps seal the deal of the badge now at $u$,
    862 * take the second modification only if it is profitable.
    863 
    864 So the transition is essentially: $\text{f}[u][x] = \text{sum}[u] + \text{arrival adjustment} + \max(0,\text{sealing bonus})$.
    865 
    866 That's the whole idea. Once we fix which badge ends up at $u$, all child subtrees are independent except for at most two of them.
    867 
    868 We process the tree bottom-up. After computing all states for $u$, we set $\text{best}[u] = \max_{x \ne \mathrm{par}(u)} \text{f}[u][x]$. The answer for the whole test case is simply $\text{best}[1]$.
    869 
    870 The number of states is linear: for each node, we only keep states corresponding to the node itself, its parent, and its children. Each transition is $O(1)$. With the map-based implementation in the reference code, the total complexity is $O(N \log N)$ per test case. If you want it enough, you can make it $O(N)$ :)
    871 
    872 **C++ Code**
    873 
    874 Original code from [_istil](/profile/_istil "Grandmaster _istil"), cleaned up for reference.
    875 
    876 ```
    877 #include <bits/stdc++.h>
    878 using namespace std;
    879 
    880 using ll = long long;
    881 
    882 constexpr int MAXN = 200005;
    883 
    884 vector<int> g[MAXN];
    885 int a[MAXN], w[MAXN], parent_[MAXN], pos[MAXN][2];
    886 map<int, ll> dp[MAXN];
    887 ll sum[MAXN], best[MAXN];
    888 
    889 // Stores the parent of each node in the rooted tree.
    890 void dfs_parent(int u, int p) {
    891     parent_[u] = p;
    892     for (int v : g[u]) {
    893         if (v != p) {
    894             dfs_parent(v, u);
    895         }
    896     }
    897 }
    898 
    899 // Computes dp[u][from]:
    900 // the badge currently at u originally came from vertex 'from'.
    901 void update_state(int u, int color, int from, ll delta) {
    902     int other = pos[color][0] ^ pos[color][1] ^ from;
    903 
    904     if (parent_[other] == u) {
    905         dp[u][from] = sum[u] + delta + max(dp[other][other] - best[other] + w[color], 0LL);
    906     } else if (parent_[parent_[other]] == u && parent_[other] != from) {
    907         int mid = parent_[other];
    908         dp[u][from] = sum[u] + delta + max(dp[mid][other] - best[mid] + w[color], 0LL);
    909     } else {
    910         dp[u][from] = sum[u] + delta;
    911     }
    912 }
    913 
    914 void dfs_dp(int u) {
    915     sum[u] = 0;
    916 
    917     for (int v : g[u]) {
    918         if (v == parent_[u]) continue;
    919         dfs_dp(v);
    920         sum[u] += best[v];
    921     }
    922 
    923     // Badge at u stays at u.
    924     update_state(u, a[u], u, 0);
    925 
    926     // Badge at parent(u) moves to u.
    927     if (parent_[u] != 0) {
    928         update_state(u, a[parent_[u]], parent_[u], 0);
    929     }
    930 
    931     // Badge at child v moves to u.
    932     for (int v : g[u]) {
    933         if (v == parent_[u]) continue;
    934         update_state(u, a[v], v, dp[v][u] - best[v]);
    935     }
    936 
    937     best[u] = 0;
    938     for (auto [from, value] : dp[u]) {
    939         if (from != parent_[u]) {
    940             best[u] = max(best[u], value);
    941         }
    942     }
    943 }
    944 
    945 void solve() {
    946     int n;
    947     cin >> n;
    948     int N = 2 * n;
    949 
    950     for (int i = 1; i <= n; ++i) {
    951         cin >> w[i];
    952         pos[i][0] = pos[i][1] = 0;
    953     }
    954 
    955     for (int i = 1; i <= N; ++i) {
    956         cin >> a[i];
    957         pos[a[i]][pos[a[i]][0] == 0 ? 0 : 1] = i;
    958     }
    959 
    960     for (int i = 1; i <= N; ++i) {
    961         g[i].clear();
    962         dp[i].clear();
    963     }
    964 
    965     for (int i = 1; i < N; ++i) {
    966         int u, v;
    967         cin >> u >> v;
    968         g[u].push_back(v);
    969         g[v].push_back(u);
    970     }
    971 
    972     dfs_parent(1, 0);
    973     dfs_dp(1);
    974 
    975     cout << best[1] << '\n';
    976 }
    977 
    978 int main() {
    979     ios::sync_with_stdio(false);
    980     cin.tie(nullptr);
    981 
    982     int T;
    983     cin >> T;
    984     while (T--) {
    985         solve();
    986     }
    987     return 0;
    988 }
    989 ```