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 ```