2278.md (19119B)
1 Source: https://codeforces.com/blog/entry/158300 2 3 Thanks for participating in the round. We hope you enjoyed the problems!!! 4 5 #### [2278A - Fraction and Six](/contest/2278/problem/A "Codeforces Round 1131 (Div. 3)") 6 7 **Idea** 8 9 The problem requires the remaining characters in the numerator $p$ to form exactly the string `six` after completely cancelling out the denominator $q$. 10 11 This means the collection of characters in $p$ must be exactly the characters in $q$ combined with the letters `s`, `i`, and `x`. Therefore, if we append the string `six` to $q$, the modified string $q$ must be an exact anagram of $p$. We can check this condition by sorting both strings and verifying if they are identical, or by comparing their character frequency counts. 12 13 Time Complexity: $\mathcal{O}(n + m)$. 14 15 **Implementation** 16 17 ``` 18 #include<bits/stdc++.h> 19 using namespace std; 20 21 int main(){ 22 23 int t; 24 cin >> t; 25 26 while(t--){ 27 int n, m; 28 string p, q; 29 cin >> n >> m >> p >> q; 30 31 q += "six"; 32 33 vector<int> pc(255, 0), qc(255, 0); 34 for(auto& z : p) pc[z]++; 35 for(auto& z : q) qc[z]++; 36 37 if(pc == qc) cout << "YES\n"; 38 else cout << "NO\n"; 39 } 40 41 return 0; 42 } 43 ``` 44 45 **Rate The Problem!** 46 47 * Best Problem 48 * Good Problem 49 * Okay Problem 50 * Bad Problem 51 * Didn't Solve 52 53 #### [2278B - Stakes and Shapes](/contest/2278/problem/B "Codeforces Round 1131 (Div. 3)") 54 55 **Idea** 56 57 Let's consider a strategy where Bob plays the exact same move in all $x+y+z$ rounds. 58 59 If Bob chooses to always play the move that beats Alice's most frequent choice, the number of rounds he wins will be exactly the maximum of $x, y,$ and $z$. 60 61 Alice will only win the rounds where she plays the move that beats Bob's choice. The number of rounds she wins will correspond to one of the other two frequencies. 62 63 Since the maximum frequency is at least as large as the remaining frequencies, the number of rounds Bob wins will always be at least the number of rounds Alice wins. Therefore, the optimal sequence is to simply find the maximum of $x, y,$ and $z$ and output its counter-move $x+y+z$ times. 64 65 Time Complexity: $\mathcal{O}(x+y+z)$. 66 67 **Implementation** 68 69 ``` 70 #include<bits/stdc++.h> 71 using namespace std; 72 73 int main(){ 74 75 int t; 76 cin >> t; 77 78 while(t--){ 79 vector<int> a(3); 80 cin >> a[0] >> a[1] >> a[2]; 81 82 string s = "PRS"; 83 84 int total = a[0] + a[1] + a[2]; 85 for(int i = 0; i < total; i++){ 86 cout << s[max_element(a.begin(), a.end()) - a.begin()]; 87 } 88 89 cout << '\n'; 90 } 91 92 return 0; 93 } 94 ``` 95 96 **Rate The Problem!** 97 98 * Best Problem 99 * Good Problem 100 * Okay Problem 101 * Bad Problem 102 * Didn't Solve 103 104 #### [2278C - Math and Physics](/contest/2278/problem/C "Codeforces Round 1131 (Div. 3)") 105 106 **Idea** 107 108 Let's analyze how the total mass of the array changes during an operation. 109 110 When we choose to operate on an inner core ($1 \lt i \lt k$), its mass $a_i$ is partitioned into two parts $x$ and $y$ ($x, y \ge 1$), which are completely absorbed by the left and right neighbors. Thus, the total mass of the array is perfectly conserved. 111 112 However, if we operate on an edge core ($i = 1$ or $i = k$), one of the split parts falls out of bounds. This means we permanently lose at least $1$ unit of mass to the environment. 113 114 To reduce the array to a single core, we must eventually reach a state with exactly $2$ cores. To merge them, we are forced to operate on one of them. Since both are edge cores at that point, it is strictly impossible to avoid losing at least $1$ unit of mass. Therefore, the theoretical maximum final mass is bounded by $\sum_{i=1}^n a_i - 1$. 115 116 Now, can we always achieve this upper bound? Let's classify the initial state into three cases: 117 118 **Case 1: All initial elements are $1$.** The operation strictly requires an element to be $\ge 2$. No moves can be made, so it is impossible to reduce the array. In this case, we print $-1$. 119 120 **Case 2: There exists at least one inner element $a_i \ge 2$ ($1 \lt i \lt n$).** We can choose this inner core for our first operation. Because $x \ge 1$ and $y \ge 1$, we pass at least $1$ unit of mass to both its left and right neighbors. Since every core initially has a mass of at least $1$, these neighbors will now have a mass of at least $2$. 121 122 This means we can continue expanding outwards, exclusively operating on inner cores. We can reduce the entire array down to $2$ elements without ever losing mass to the environment. The only mass lost is the unavoidable $1$ unit at the very end. The answer is exactly $\sum_{i=1}^n a_i - 1$. 123 124 **Case 3: All inner elements are $1$, but an edge element is $\ge 2$ (or $n = 2$).** Because there are no valid inner cores to start with, we are forced to operate on an edge core. To minimize our losses, we split it into $1$ (which is lost to the void) and $a_i - 1$ (which is added to the adjacent inner $1$). That inner core now has a mass of $a_i \ge 2$ and effectively becomes the new edge of the remaining array. To clear out all $n-2$ inner $1$s, we must repeat this "rolling" process, paying a toll of exactly $1$ unit of mass for every inner element we consume. In total, we lose $n-2$ mass to clear the inner elements, plus the $1$ mass lost during the final merge. The total mass lost is $n-1$. The final mass is $\sum_{i=1}^n a_i - (n - 1) = a_1 + a_n - 1$. 125 126 Time Complexity: $\mathcal{O}(n)$. 127 128 **Implementation** 129 130 ``` 131 #include<bits/stdc++.h> 132 using namespace std; 133 134 int main(){ 135 136 int t; 137 cin >> t; 138 139 while(t--){ 140 int n; 141 cin >> n; 142 143 vector<int> a(n); 144 for(auto& z : a) cin >> z; 145 146 int sum = accumulate(a.begin(), a.end(), 0); 147 if(sum == n) cout << -1 << '\n'; 148 else if(sum == n - 2 + a[0] + a[n - 1]) cout << a[0] + a[n - 1] - 1 << '\n'; 149 else cout << sum - 1 << '\n'; 150 } 151 152 return 0; 153 } 154 ``` 155 156 **Rate The Problem!** 157 158 * Best Problem 159 * Good Problem 160 * Okay Problem 161 * Bad Problem 162 * Didn't Solve 163 164 #### [2278D - Lock and Unlock](/contest/2278/problem/D "Codeforces Round 1131 (Div. 3)") 165 166 **Idea** 167 168 Let $b_1 \le b_2 \le \dots \le b_n$ be the sorted version of the initial array $a$. To make all elements equal, our goal is to reduce the gap $b_{i+1} - b_i$ to zero for all $1 \le i \lt n$. 169 170 To close the gap between $b_i$ and $b_{i+1}$ by $1$ unit, they must move closer relative to each other. Suppose we decide to increase $b_i$. If we do not also increase all elements to its left ($b_1 \dots b_{i-1}$), we will successfully close the gap on the right, but we will simultaneously widen the gaps within the left group. Therefore, to guarantee we never undo our progress or create new gaps, any time we shift elements to close a specific gap $b_{i+1} - b_i$, we must shift the *entire* group of elements on one side of that gap as a single rigid block. 171 172 Now, to reduce $b_{i+1} - b_i$ by $1$ unit, we only have two optimal choices: 173 174 1. **Lock the prefix** $b_1 \dots b_i$ (incurring a cost of $i$) and decrease the entire suffix $b_{i+1} \dots b_n$. 175 2. **Lock the suffix** $b_{i+1} \dots b_n$ (incurring a cost of $n-i$) and increase the entire prefix $b_1 \dots b_i$. 176 177 Since these choices are independent for every gap, we can greedily take the cheaper option. The minimum cost to close the gap $b_{i+1} - b_i$ by $1$ unit is exactly $\min(i, n-i)$. Summing this over all gaps in the array, the minimum possible total cost is exactly: 178 179 $ \sum_{i=1}^{n-1} (b_{i+1} - b_i) \cdot \min(i, n-i) $ 180 181 To find the minimum number of operations needed, note that in any single operation, an element's value changes by $+1, -1$, or $0$. Therefore, the absolute maximum distance in the array, which is initially $b_n - b_1$, can decrease by at most $1$ in a single operation. To make all elements equal, this distance must be reduced to $0$. Thus, we strictly need at least $b_n - b_1$ operations. 182 183 Observe that in any operation, we are either increasing some prefix by $1$ or decreasing some suffix by $1$. In any case, the value of $b_n - b_1$ decreases by $1$. This guarantees that the maximum span shrinks in every operation, achieving the minimum cost in exactly $b_n - b_1$ operations. 184 185 Time Complexity: $\mathcal{O}(n \log n)$. 186 187 **Implementation** 188 189 ``` 190 #include<bits/stdc++.h> 191 using namespace std; 192 193 int main(){ 194 195 int t; 196 cin >> t; 197 198 while(t--){ 199 int n; 200 cin >> n; 201 202 vector<int> a(n); 203 for(auto& z : a) cin >> z; 204 205 sort(a.begin(), a.end()); 206 207 long long cost = 0; 208 for(int i = 0; i < n - 1; i++){ 209 cost += 1ll * (a[i + 1] - a[i]) * min(i + 1, n - i - 1); 210 } 211 212 cout << cost << ' ' << a[n - 1] - a[0] << '\n'; 213 } 214 215 return 0; 216 } 217 ``` 218 219 **Rate The Problem!** 220 221 * Best Problem 222 * Good Problem 223 * Okay Problem 224 * Bad Problem 225 * Didn't Solve 226 227 #### [2278E - Swap and Negate](/contest/2278/problem/E "Codeforces Round 1131 (Div. 3)") 228 229 **Idea** 230 231 Let's define a new array $b$ such that $b_i = (-1)^{i-1} a_i$. 232 233 Now, let's take a look at how the given operation affects this new array $b$. If we apply the operation at index $i$, the new values in $a$ become $a'_i = -a_{i+1}$ and $a'_{i+1} = -a_i$. Observe the corresponding elements in $b$: 234 235 $b'_{i+1} = (-1)^i a'_{i+1} = (-1)^i (-a_i) = (-1)^{i-1} a_i = b_i$$b'_i = (-1)^{i-1} a'_i = (-1)^{i-1} (-a_{i+1}) = (-1)^i a_{i+1} = b_{i+1}$ 236 237 Surprisingly, the operation on $a$ translates to exactly **swapping adjacent elements** in $b$! 238 239 Since we can swap adjacent elements any number of times, we can rearrange $b$ into any permutation we want. This is the core idea of the problem. All that's left is just some math. Now, let's express the sum of the array $a$ in terms of $b$: 240 241 $ \sum_{i=1}^n a_i = b_1 - b_2 + b_3 - b_4 + \dots $ 242 243 To maximize this total sum, we greedily place the smallest $\lfloor \frac{n}{2} \rfloor$ elements of the array $b$ at even indices and the largest $\lceil \frac{n}{2} \rceil$ elements at odd indices. The resulting alternating sum of the array $b$ is the required answer. 244 245 Time Complexity: $\mathcal{O}(n \log n)$. 246 247 **Implementation** 248 249 ``` 250 #include<bits/stdc++.h> 251 using namespace std; 252 253 int main(){ 254 255 int t; 256 cin >> t; 257 258 while(t--){ 259 int n; 260 cin >> n; 261 262 vector<int> a(n); 263 for(auto& z : a) cin >> z; 264 265 vector<int> b = a; 266 for(int i = 1; i < n; i += 2) b[i] = -b[i]; 267 268 sort(b.begin(), b.end()); 269 270 int i = 0; 271 long long ans = 0; 272 for(; i < n / 2; i++) ans -= b[i]; 273 for(; i < n; i++) ans += b[i]; 274 275 cout << ans << '\n'; 276 } 277 278 return 0; 279 } 280 ``` 281 282 **Rate The Problem!** 283 284 * Best Problem 285 * Good Problem 286 * Okay Problem 287 * Bad Problem 288 * Didn't Solve 289 290 #### [2278F - Modulo and Counting](/contest/2278/problem/F "Codeforces Round 1131 (Div. 3)") 291 292 **Idea** 293 294 For any two positive integers $x \ge y$, we can write $x \bmod y = x - k \cdot y$, where $k = \lfloor \frac{x}{y} \rfloor \ge 1$. 295 296 Let $k_i = \lfloor \frac{a_i}{a_{i+1}} \rfloor$. Since the array is non-increasing ($a_i \ge a_{i+1}$), we are guaranteed that $k_i \ge 1$. We can rewrite the modulo sum condition as: 297 298 $ \sum_{i=1}^{n-1} (a_i \bmod a_{i+1}) = \sum_{i=1}^{n-1} (a_i - k_i \cdot a_{i+1}) = m $ 299 300 Upon rearranging, we get: 301 302 $ \sum_{i=1}^{n-1} (k_i - 1)a_{i+1} = a_1 - a_n - m $ 303 304 Let's bound the right-hand side. We are given $a_1 \le m+2$ and $a_n \ge 1$. Thus, the maximum possible value for $a_1 - a_n - m$ is $(m+2) - 1 - m = 1$. Because $k_i \ge 1$ and $a_{i+1} \ge 1$, every term in the summation on the left is non-negative. This strictly bounds the sum to be either exactly $0$ or exactly $1$. Observe that this also imposes the additional constraints $a_n \le 2$ and $a_1 \ge m + 1$. 305 306 Now, if $a_n = 2$, we must have $a_1 = m + 2$. Note that this forces every $k_i$ to be exactly equal to $1$. So, we must have $a_{i+1} \le a_i \lt 2a_{i+1}$. 307 308 If $a_n = 1$, consider the exact step where the sequence drops to $1$ from some value $x \ge 2$. For this specific step, $a_j = x$ and $a_{j+1} = 1$. The quotient is $k_j = \lfloor \frac{x}{1} \rfloor = x$. See that if $x \ge 3$, the left-hand side is at least $2$, and this is not allowed. This forces the constraint $x \le 2$. Thus, we must have $x = 2$. This proves that if the sequence drops to $1$, it must drop exactly from the value $2$. This makes the left-hand side at least $1$, and consequently, the right-hand side of our equation must be exactly $1$, implying $a_1 = m + 2$. Similar to the previous case, every $k_i$ ($i \lt j$) is forced to be exactly equal to $1$. So, we must have $a_{i+1} \le a_i \lt 2a_{i+1}$. 309 310 Generalizing things, an array $a$ is good if and only if it satisfies all of the following conditions: 311 312 * $a_1 = m + 2$; 313 * $a_j = 2$ for some index $j \in [2, n]$; 314 * $a_k = 1$ for all $j + 1 \le k \le n$; 315 * $a_{i+1} \le a_i \lt 2a_{i+1}$ for all $1 \le i \lt j$. 316 317 To count the number of good arrays, we use 2D DP. Let $\text{dp}[i][v]$ ($1 \le i \le n$; $2 \le v \le m + 2$) denote the number of valid prefixes of length $i$ with an additional constraint $a_i = v$. The base case would be $\text{dp}[1][m+2] = 1$ and $\text{dp}[1][x] = 0$ for all $x \neq m + 2$. The transition is straightforward: 318 319 $ \text{dp}[i][v] = \sum_{x=v}^{2v-1} \text{dp}[i-1][x] $ 320 321 Any valid sequence that safely hits $2$ at length $i$ will just be padded with $1$s for the remaining $n-i$ elements. This padding is unique and deterministic. Therefore, to find the total number of good arrays of length $n$, we simply sum the number of ways to reach the value $2$ at any valid length $i$: 322 323 $ \text{Total Good Arrays} = \sum_{i=2}^n \text{dp}[i][2] $ 324 325 This DP has $\mathcal{O}(nm)$ states, and each transition requires a contiguous range sum of the previous row. By maintaining a prefix sum of the DP table, we can compute each state in constant time, yielding an optimal solution in $\mathcal{O}(nm)$ time and space. It is useful to note that one can also optimize the space complexity to $\mathcal{O}(m)$ (refer to the implementation below). 326 327 Time Complexity: $\mathcal{O}(nm)$. 328 329 **Implementation** 330 331 ``` 332 #include<bits/stdc++.h> 333 using namespace std; 334 335 #define ll long long 336 const ll mod = 998'244'353; 337 338 int main(){ 339 340 int t; 341 cin >> t; 342 343 while(t--){ 344 int n, m; 345 cin >> n >> m; 346 347 vector<ll> dp(m + 3, 0); 348 dp[m + 2] = 1; 349 350 ll ans = 0; 351 352 for(int i = 1; i < n; i++){ 353 354 ll sum = (dp[2] + dp[3]) % mod; 355 int left = 2, right = 3; 356 357 for(int j = 2; j < m + 3; j++){ 358 359 ll temp = sum; 360 361 sum += (mod - dp[left]); 362 left++; 363 364 right++; 365 if(right < m + 3) sum += dp[right]; 366 right++; 367 if(right < m + 3) sum += dp[right]; 368 369 sum %= mod; 370 dp[j] = temp; 371 } 372 373 ans += dp[2]; 374 ans %= mod; 375 } 376 377 cout << ans << '\n'; 378 } 379 380 return 0; 381 } 382 ``` 383 384 **Rate The Problem!** 385 386 * Best Problem 387 * Good Problem 388 * Okay Problem 389 * Bad Problem 390 * Didn't Solve 391 392 #### [2278G - 0s and 1s](/contest/2278/problem/G "Codeforces Round 1131 (Div. 3)") 393 394 **Idea** 395 396 Observe the behavior of an injected energy pulse. If a node is at state $0$, it becomes $1$ and stops. If it is $1$, it becomes $0$ and sends a pulse to its children. Notice that this is exactly the mechanism of **binary addition**. Flipping from $0 \to 1$ is adding $1$ without a carry. Flipping from $1 \to 0$ and passing a pulse is adding $1$ and generating a carry to the next significant bit. 397 398 Consider a path from the root down to a node $v$ at depth $d$ (0-indexed). The initial states of the nodes on this path form a binary integer $X_v$, where the root represents the least significant bit (LSB) and $v$ represents the $d$-th bit. Because the carry rules are identical, injecting $K$ pulses at the root is mathematically equivalent to computing the sum $X_v + K$ for every path simultaneously. 399 400 The final state of node $v$ after $K$ pulses will simply be the $d$-th bit of the sum $X_v + K$. We require this final state to be exactly $y_v$. 401 402 Since $K$ is a single global integer, we can determine it bit by bit, level by level. Let $k_d$ be the $d$-th bit of $K$. Let $C_v$ be the incoming carry bit that node $v$ receives from its parent. For the root, $C_{\text{root}} = 0$. 403 404 For any node $v$ at depth $d$, the $d$-th bit of the sum $X_v + K$ is calculated as: 405 406 $ \text{bit}_d(X_v + K) = x_v \oplus k_d \oplus C_v $ 407 408 We need this to equal $y_v$. Rearranging the equation gives us the required $d$-th bit of $K$: 409 410 $ k_d = y_v \oplus x_v \oplus C_v $ 411 412 This creates a strict constraint: **for a valid $K$ to exist, the required $k_d$ must evaluate to the exact same value for all nodes at depth $d$.** If any two nodes at the same depth yield a different $k_d$, it is impossible to satisfy both simultaneously. We print $-1$ in this case. 413 414 If all nodes at depth $d$ agree on $k_d$, we lock in this bit for $K$. We then compute the outgoing carry that node $v$ will pass to its children for the next depth: 415 416 $ C_{\text{child}} = \begin{cases} 1 & \text{if } x_v + k_d + C_v \ge 2, \\ 0 & \text{otherwise}. \end{cases} $ 417 418 The final answer is computed by summing $2^d$ for all depths $d$ where $k_d = 1$. Since we process each node exactly once and only do constant-time bitwise operations, the complexity is linear. 419 420 Time Complexity: $\mathcal{O}(n)$. 421 422 **Implementation** 423 424 ``` 425 #include<bits/stdc++.h> 426 using namespace std; 427 428 const int mod = 998'244'353; 429 430 const int MX = 200005; 431 vector<int> p2(MX, 1); 432 void init(){ 433 for(int i = 1; i < MX; i++) p2[i] = 2 * p2[i - 1] % mod; 434 } 435 436 int main(){ 437 438 init(); 439 440 int t; 441 cin >> t; 442 443 while(t--){ 444 int n; 445 cin >> n; 446 447 vector<vector<int>> v(n + 1); 448 for(int i = 1; i < n; i++){ 449 int x, y; 450 cin >> x >> y; 451 v[x].push_back(y); 452 v[y].push_back(x); 453 } 454 455 string x, y; 456 cin >> x >> y; 457 x = "." + x; 458 y = "." + y; 459 460 vector<int> dep(n + 1, 0), par(n + 1, 0); 461 462 function<void(int, int)> dfs = [&](int u, int p){ 463 for(auto& z : v[u]) if(z != p){ 464 par[z] = u; 465 dep[z] = 1 + dep[u]; 466 dfs(z, u); 467 } 468 }; 469 470 dfs(1, -1); 471 472 vector<int> carry(n + 1, 0); 473 vector<vector<int>> nodes(n); 474 for(int i = 1; i <= n; i++) nodes[dep[i]].push_back(i); 475 476 int ans = 0; 477 bool is = 1; 478 for(int i = 0; i < n && is; i++){ 479 bool req[2] = {0, 0}; 480 for(auto& z : nodes[i]){ 481 int xb = x[z] - '0'; 482 int yb = y[z] - '0'; 483 int cb = carry[par[z]]; 484 int rb = xb ^ yb ^ cb; 485 req[rb] = 1; 486 if(xb + cb + rb > 1) carry[z] = 1; 487 } 488 if(req[0] && req[1]) is = 0; 489 ans += req[1] * p2[i]; 490 ans %= mod; 491 } 492 493 if(!is) ans = -1; 494 cout << ans << '\n'; 495 } 496 497 return 0; 498 } 499 ``` 500 501 **Rate The Problem!** 502 503 * Best Problem 504 * Good Problem 505 * Okay Problem 506 * Bad Problem 507 * Didn't Solve