codeforces-scrape

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

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