codeforces-scrape

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

2108.md (19841B)


      1 Source: https://codeforces.com/blog/entry/142512
      2 
      3 #### [2108A - Permutation Warm-Up](/contest/2108/problem/A "Codeforces Round 1022 (Div. 2)")
      4 
      5 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0")
      6 
      7 **Solution**
      8 
      9 Let’s start with $p = [1, 2, 3, …, n]$. For this $p$, $f(p) = 0$.
     10 
     11 Let’s move $n$ to the beginning one position at a time. It’s easy to see that we increase the answer by $2$ at each step.
     12 
     13 Now, let’s move $n - 1$ to position $2$, then $n - 2$ to position $3$, and so on, until we reach $p = [n, n - 1, …, 2, 1]$.  
     14 For this $p$, $f(p) = \lfloor \frac{n^2}{2} \rfloor$.
     15 
     16 While doing this, we obtained every even value from $0$ to $\lfloor \frac{n^2}{2} \rfloor$, since we were adding $+2$ at each step.
     17 
     18 Let’s prove that we can’t get any other values.
     19 
     20 First of all, it’s easy to see that we can’t obtain a value less than $0$ or greater than $\lfloor \frac{n^2}{2} \rfloor$.
     21 
     22 Second, we can only obtain even values, because each swap changes the answer by an even number.
     23 
     24 So the answer is $\lfloor \frac{n^2}{4} \rfloor + 1$
     25 
     26 Time complexity : $\text{O}(1)$.
     27 
     28 **Code**
     29 
     30 ```
     31 #include <iostream>
     32 #include <vector>
     33 using namespace std;
     34 typedef long long int ll;
     35 #define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
     36 #define forn(i, n) for (ll i = 0; i < ll(n); ++i)
     37 
     38 void solution(){
     39     ll n;cin>>n;
     40     ll k=n/2;
     41     if (n%2){cout<<k*(k+1)+1;return;}
     42     cout<<k*k+1;
     43 }
     44 
     45 int main() {
     46     SPEEDY;
     47     int t; cin>>t;
     48     while (t--){
     49         solution();
     50         cout << '\n';
     51     } return 0;
     52 }
     53 ```
     54 
     55 #### [2108B - SUMdamental Decomposition](/contest/2108/problem/B "Codeforces Round 1022 (Div. 2)")
     56 
     57 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0")
     58 
     59 **Solution**
     60 
     61 Let $x \gt 1$, and let $c$ denote the number of 1-bits in its binary representation. Clearly, when $n \le c$, it is optimal to simply distribute distinct powers of two across the elements of the array, resulting in the minimum achievable sum of $x$. If, however, $n \gt c$, then it is obviously beneficial to add only ones to the extra $n - c$ elements. In the case where $n - c$ is odd, we will also need to add one more one to one of the $c$ blocks with powers of two so that the $\text{XOR}$ of all ones equals $x$ $\text{mod}$ $2$.
     62 
     63 If $x = 1$, then for odd $n$ we can clearly just fill all array elements with ones. Otherwise, we need to use the pair $[2, 3]$, whose $\text{XOR}$ is $1$, resulting in the minimum score of $n + 3$.
     64 
     65 In the remaining case of $x = 0$, the situation is nearly identical to the previous one, with the exception that no valid example exists for $n = 1$ (this is the only case with an answer of $-1$). So for even $n$, the answer is simply $n$, and otherwise it’s $n + 3$ (since we use the triple $1 \oplus 2 \oplus 3 = 0$).
     66 
     67 The time complexity is $\text{O}(1)$ per test.
     68 
     69 **Code**
     70 
     71 ```
     72 #include <bits/stdc++.h>
     73 using namespace std;
     74 typedef long long int ll;
     75 
     76 void solution(){
     77     int n,x;cin>>n>>x;
     78     int bits=__builtin_popcountll(x);
     79     if (n<=bits){cout<<x;return;}
     80     if ((n-bits)%2==0)cout<<x+n-bits;
     81     else{
     82         if (x>1){cout<<x+n-bits+1;return;}
     83         if (x==1){cout<<n+3;return;}
     84         else{
     85             if (n==1){cout<<-1;return;}
     86             else cout<<n+3;
     87         }
     88     }
     89 }
     90 
     91 int main() {
     92     ios::sync_with_stdio(false);
     93     cin.tie(nullptr);
     94     cout.tie(nullptr);
     95     int t=1; 
     96     cin>>t;
     97     while (t--){
     98         solution();
     99         cout << '\n';
    100     } return 0;
    101 }
    102 ```
    103 
    104 #### [2108C - Neo's Escape](/contest/2108/problem/C "Codeforces Round 1022 (Div. 2)")
    105 
    106 Author: [suprend](/profile/suprend "Expert suprend")
    107 
    108 **Solution**
    109 
    110 Note that consecutive buttons with the same weight do not affect the result, so we will keep only one of them in such sequences.
    111 
    112 In the resulting array, we find peaks (local maxima — elements that are strictly greater than both of their neighbors). The number of such peaks is the answer, because:
    113 
    114 — Each peak is separated from others by smaller elements. Therefore, the only way to reach a peak is by creating a clone there.
    115 
    116 — If a button was visited, we can return to it.
    117 
    118 — Any element other than a peak can be reached from a larger neighbor, since we have already visited it. Thus, creating clones in all other elements is not necessary.
    119 
    120 Complexity: $\text{O}(n)$
    121 
    122 **Code**
    123 
    124 ```
    125 #include <iostream>
    126 #include <vector>
    127  
    128 using namespace std;
    129  
    130 int main() {
    131     int tt = 1;
    132     cin >> tt;
    133     while(tt--){
    134         int n; cin >> n;
    135         vector<int> a;
    136         a.push_back(-1e9);
    137         for (int i = 0; i < n; i++){
    138             int x; cin >> x;
    139             if (a.back() == x);
    140             else a.push_back(x);
    141         }
    142         a.push_back(-1e9);
    143         
    144         int ans = 0;
    145         for (int i = 1; i < a.size() - 1; i++) 
    146             if (a[i - 1] < a[i] && a[i] > a[i + 1]) ans++;
    147  
    148         cout << ans << endl;
    149     }
    150 }
    151 ```
    152 
    153 #### [2108D - Needle in a Numstack](/contest/2108/problem/D "Codeforces Round 1022 (Div. 2)")
    154 
    155 Author: [m3tr0](/profile/m3tr0 "Expert m3tr0")
    156 
    157 **Solution**
    158 
    159 Let $k = 4$ and the following array is guessed:
    160 
    161 [  2   4   3   1   2   4   3   1   2   1   3   2   4   1   3   2   4   1  ]
    162 
    163 For clarity, let's divide it into groups of $k$ elements:
    164 
    165 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]
    166 
    167 By statement, the lengths of the left and right sides are at least $k$. Let's request the left $k$ and right $k$ elements. We will mark all the elements of the left array in red, and all the elements of the right array in blue:
    168 
    169 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]
    170 
    171 Let's add two numbers to our array on the right (for clarity of permutations):
    172 
    173 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    174 
    175 We got the permutations in a "normalized" form: $[2, 4, 3, 1]$ and $[4, 1, 3, 2]$. Let's take any position where the elements in the permutations differ. Let it be the second position. Note all the elements at the selected positions in the guessed array:
    176 
    177 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    178 
    179 Among them, we find boundary elements via **binary search** for $\log\frac{n}{k}$ queries:
    180 
    181 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    182 
    183 Next, consider the segment between these boundary elements:
    184 
    185 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    186 
    187 We are not interested in positions that match in both permutations (in our case, this is only the third position). Let's discard the elements in these positions:
    188 
    189 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    190 
    191 Using binary search, we find the boundary elements for $\log k$ queries:
    192 
    193 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1   3   2  ]
    194 
    195 If there are "no-man's land" between the boundary elements, then there is no single solution and we output $-1$. In our case, there are no such elements, the problem is solved:
    196 
    197 [  2   4   3   1  ] [  2   4   3   1  ] [  2   1   3   2  ] [  4   1   3   2  ] [  4   1  ]
    198 
    199 Total complexity: $2k + \log\frac{n}{k} + \log k$ queries.
    200 
    201 **Code**
    202 
    203 ```
    204 #include <cstdio>
    205 #include <cstdlib>
    206 #define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
    207 #define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
    208 typedef long long l;
    209 
    210 l a[55], b[55], ui[55];
    211 
    212 l ask(l v) {
    213     printf("? %lld\n", v + 1);
    214     fflush(stdout);
    215     l t; scanf("%lld", &t);
    216     return t;
    217 }
    218 
    219 void noans() {
    220     printf("! -1\n");
    221     fflush(stdout);
    222 }
    223 
    224 void ans(l a, l b) {
    225     printf("! %lld %lld\n", a, b);
    226     fflush(stdout);
    227 }
    228 
    229 void solve() {
    230     l n, k; scanf("%lld %lld", &n, &k);
    231 
    232     for (l i = 0; i < k; ++i) a[i] = ask(i);
    233     for (l i = n - k; i < n; ++i) b[i % k] = ask(i);
    234 	
    235     l uc = 0;
    236     for (l i = 0; i < k; ++i) if (a[i] != b[i]) ui[uc++] = i;
    237     
    238     if (!uc) {
    239         if (n == k * 2) ans(k, k);
    240         else noans();
    241         return;
    242     }
    243     
    244     l le = ui[0], ri = ui[0] + (n - 1) / k * k;
    245     while (le + k != ri) {
    246         l mid = le + (ri - le) / k / 2 * k;
    247         if (ask(mid) == a[ui[0]]) le = mid;
    248         else ri = mid;
    249     }
    250     
    251     l lee = 0, rii = uc;
    252     while (lee + 1 != rii) {
    253         l mid = (lee + rii) / 2;
    254         if (ask(le - ui[0] + ui[mid]) == a[ui[mid]]) lee = mid;
    255         else rii = mid;
    256     }
    257     
    258     l pos1 = MAX(le - ui[0] + ui[lee], k - 1);
    259     l pos2 = MIN(le - ui[0] + ((rii == uc) ? (ui[0] + k) : ui[rii]), n - k);
    260     
    261     if (pos1 + 1 != pos2) { noans(); return; }
    262     ans(pos2, n - pos2);
    263 }
    264 
    265 int main() {
    266     l t; scanf("%lld", &t);
    267     while (t--) solve();
    268 }
    269 ```
    270 
    271 #### [2108E - Spruce Dispute](/contest/2108/problem/E "Codeforces Round 1022 (Div. 2)")
    272 
    273 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0")
    274 
    275 **Solution**
    276 
    277 Let’s assume we have already removed one of the edges from the original tree. Then, we are left with a tree containing an even number of vertices, namely $n - 1$.  
    278 Note that the maximum possible sum of distances between same-colored balls in this tree will be achieved if, for every edge, all vertices in its smaller subtree are of different colors. In that case, the edge will contribute the maximum possible number of times to the answer — specifically, $\min(a, b)$, where $a$ and $b$ are the sizes of the subtrees connected by this edge (since, obviously, no more paths can pass through this edge).  
    279 Great — now let’s root our tree at its centroid, which is a vertex that splits the tree into subtrees whose sizes do not exceed half of the total size. It can be proven that such a vertex always exists in any tree (and if there are two such vertices, we can pick either).  
    280 Now, let’s divide all vertices into groups based on which child subtree of the centroid they belong to, adding the centroid itself to the smallest group. Notice that the sizes of all groups still do not exceed $\frac{n - 1}{2}$. Therefore, we can pair up the vertices in such a way that each pair contains vertices from different groups. This can be done greedily using a heap in $O(n \log n)$, or by running DFS from the centroid and coloring vertices modulo $\frac{n - 1}{2}$ (clearly, with this method, no group will have two vertices of the same color), which has complexity $O(n)$.  
    281 Thus, we are left to determine which edge we should remove so that the total sum of the minimal subtree sizes across all edges in the original tree decreases as little as possible. Note that, since initially the tree has an odd number of vertices, its centroid is uniquely defined and will not change no matter which edge we remove. At the same time, since all paths pass through the centroid, the total sum of their lengths can be rewritten as the sum of distances to the centroid.  
    282 Now, let’s make two observations:
    283 
    284 1. It is more beneficial to remove a leaf than any other type of vertex.
    285 2. Among all leaves, it is best to remove the one closest to the centroid.
    286 
    287 The second observation follows directly from the first and the earlier remark, so we only need to justify the first one. But this is fairly obvious: when we remove an edge, besides subtracting the depth of its nearest vertex, we also decrease the depths of all vertices in its subtree by one. Therefore, it will always be better to remove deeper edges rather than shallower ones.  
    288 As a result, after finding the centroid in $O(n)$, we get an overall complexity of $O(n \log n)$ (if we use a heap) or $O(n)$.
    289 
    290 **Code**
    291 
    292 ```
    293 #include <cstdio>
    294 #include <vector>
    295 
    296 #define S 200005
    297 
    298 using namespace std;
    299 typedef long long l;
    300 
    301 l coloring[S], centroid, best, best_dist, n, color;
    302 vector<vector<l>> g;
    303 
    304 l search_centroid(l u, l from) {
    305   l sum = 0;
    306   bool f = true;
    307   for (l v : g[u]) if (v != from) {
    308     l t = search_centroid(v, u);
    309     if (t > n / 2) f = false;
    310     sum += t;
    311   }
    312   
    313   if (f && n - 1 - sum <= n / 2) centroid = u;
    314   return sum + 1;
    315 }
    316 
    317 void make_coloring(l u, l from, l dist) {
    318   coloring[u] = (color++) % (n / 2) + 1;
    319   if (g[u].size() == 1 && dist < best_dist) {
    320     best_dist = dist;
    321     best = u;
    322   }
    323   for (l v : g[u]) if (v != from)
    324     make_coloring(v, u, dist + 1);
    325 }
    326 
    327 void solve() {
    328   centroid = -1, best_dist = S, color = 0;
    329   scanf("%lld", &n);
    330   g.assign(n, vector<l>());
    331   for (l i = 0; i < n - 1; ++i) {
    332     l u, v; scanf("%lld %lld", &u, &v); --u, --v;
    333     g[u].push_back(v); g[v].push_back(u);
    334   }
    335   
    336   search_centroid(1543 % n, -1);
    337   make_coloring(centroid, -1, 0);
    338   
    339   l bbest = max(best, g[best][0]);
    340   coloring[centroid] = coloring[bbest];
    341   coloring[bbest] = 0;
    342   
    343   printf("%lld %lld\n", best + 1, g[best][0] + 1);
    344   for (l i = 0; i < n; ++i) {
    345     if (i) printf(" ");
    346     printf("%lld", coloring[i]);
    347   }
    348   printf("\n");
    349 }
    350 
    351 int main() {
    352   l tc; scanf("%lld", &tc);
    353   while (tc--) solve();
    354 }
    355 ```
    356 
    357 #### [2108F - Fallen Towers](/contest/2108/problem/F "Codeforces Round 1022 (Div. 2)")
    358 
    359 Author: [m3tr0](/profile/m3tr0 "Expert m3tr0")
    360 
    361 **Solution**
    362 
    363 It can be shown that for any array $ A $ obtained after collapsing all $ n $ towers, we can also obtain any other array $ B $ whose elements do not exceed the elements of $ A $. A strict formal proof is provided in the spoiler below; here is a brief explanation. Suppose $ k $ blocks fell onto the $ i $-th tower over the entire process. Then, for its height in the final array to be $ A_i $, $ A_i $ blocks must have fallen after its collapse, while the remaining $ k - A_i $ blocks fell before. Thus, we can always rearrange the order in which the towers collapse so that its height becomes $ B_i \leq A_i $. In other words, we ensure that $ B_i $ blocks fall onto the $ i $-th tower after its collapse, and $ k - B_i $ fall before.
    364 
    365 From this claim about the possibility of obtaining a smaller array, two facts follow:
    366 
    367 1. For any answer $\text{MEX} = x$, we can also obtain the answer $ x - 1 $. This means we can apply **binary search on the answer**.
    368 2. For any answer $\text{MEX} = x$, we can achieve it in the form $[0, 0, 0, 0, \ldots, 1, 2, 3, \ldots, x - 1]$. Thus, at each iteration of the binary search, we need to check the possibility of obtaining such an array. To do this, we traverse the towers from left to right, tracking the number of cubes that fall onto each tower at some point and collapsing each tower after the required number of cubes have fallen onto it. The most efficient way to track the number of cubes is using the scanline method.
    369 
    370 In total, there are $\text{O}(\log n)$ iterations in the binary search over the answer and $\text{O}(n)$ operations per iteration.
    371 
    372 The final complexity is $\text{O}(n \log n)$.
    373 
    374 **Formal proof**
    375 
    376 Let the array $a$ of length $n$ be some input data for the problem.
    377 
    378 Let $r$ and $r'$ be arrays of length $n$ such that $\forall i : 0 \leq r'_i \leq r_i$.
    379 
    380 **Assertion 1**: Suppose there exists a permutation $p$ such that the tower with index $i$ collapses $p_i$-th in order, resulting in the array $r$. Then, there exists a permutation $p'$ such that the tower with index $i$ collapses $p'_i$-th in order, resulting in the array $r'$.
    381 
    382 $\square$
    383 
    384 Let $s_i$ be the total number of towers that ever fell onto position $i$ when collapsing the towers in the order $p$. Note that out of these, $r_i$ towers were collapsed later than the $i$-th, and the rest were collapsed earlier. The height of the $i$-th tower at the moment of its collapse is $a_i + (s_i - r_i)$.
    385 
    386 **Inductive hypothesis**: There exists a permutation $p^{(k)}$ of numbers from $1$ to $k \leq n$ such that if the $i$-th tower is collapsed $p^{(k)}_i$-th in order, then:
    387 
    388 1. The resulting height at the $i$-th position will be $r'_i$.
    389 2. The number (denoted as $s^{(k)}_i$) of towers that fell onto position $i$ when collapsing the towers in the order $p^{(k)}$ is greater than or equal to $s_i$.
    390 
    391 **Base case**: The permutation $p^{(1)} = [1]$. After collapsing, the tower's height becomes $0$, so $r'_1 = r_1 = 0$ in any resulting array. $s^{(1)}_1 = s_1 = 0$.
    392 
    393 **Inductive step**: Suppose the permutation $p^{(k - 1)}$ exists. We prove the existence of $p^{(k)}$.
    394 
    395 $\forall i \leq k - 1$, the height of the $i$-th tower at the moment of collapse under the order $p^{(k - 1)}$ is no less than under the order $p$:
    396 
    397 $ (s^{(k - 1)}_i \geq s_i \land r'_i \leq r_i) ~~~ \Longrightarrow ~~~ a_i + (s^{(k - 1)}_i - r'_i) \geq a_i + (s_i - r_i) $
    398 
    399 From this, it follows that when collapsing in the order $p^{(k - 1)}$, at least $s_k$ towers will fall onto position $k$ (let their count be $x \geq s_k \geq r'_k$). This is because the heights at the moment of collapse for all towers $i \lt k$ have either remained the same or increased.
    400 
    401 If $x \gt r'_k$, let tower $j$ be the $(x - r'_k)$-th tower among those that fell onto position $k$. Then, collapse tower $k$ immediately after tower $j$. If $x = r'_k$, collapse tower $k$ first. In both cases, after collapsing $k$, $r'_k$ towers will fall onto it, and its height will become $r'_k$.
    402 
    403 Formally, for $x \gt r'_k$, the permutation $p^{(k)}$ is constructed as follows:
    404 
    405 1. $\forall i \lt k : p^{(k - 1)}_i \leq p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i$
    406 2. $p^{(k)}_k = p^{(k - 1)}_j + 1$
    407 3. $\forall i \lt k : p^{(k - 1)}_i \gt p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i + 1$
    408 
    409 For $x = r'_k$:
    410 
    411 1. $p^{(k)}_k = 1$
    412 2. $\forall i \lt k : p^{(k)}_i = p^{(k - 1)}_i + 1$
    413 
    414 The array $s^{(k)}$ is constructed as $\forall i \lt k : s^{(k)}_i = s^{(k - 1)}_i$ and $s^{(k)}_k = x$.
    415 
    416 **The induction is proven**. Thus, we set $p' = p^{(n)}$, and the assertion is proven.
    417 
    418 $\blacksquare$
    419 
    420 **Corollary 1**: If we can obtain $\text{MEX}(r) \gt 0$ as the answer to the problem for the resulting array $r$, then we can also obtain $\text{MEX}(r) - 1$ as the answer to the problem.
    421 
    422 $\square$
    423 
    424 Set $r'_i = \max(0, r_i - 1)$. Then, by Assertion 1, $r'$ can be obtained as the resulting array. $\text{MEX}(r') = \text{MEX}(r) - 1$.
    425 
    426 $\blacksquare$
    427 
    428 **Corollary 2**: If we can obtain $\text{MEX}(r)$ as the answer to the problem for the resulting array $r$, then we can obtain $\text{MEX}(r') = \text{MEX}(r)$ for the resulting array $r'$, where $r'_i = \max(0, (\text{MEX}(r) - 1) - (n - i))$.
    429 
    430 $\square$
    431 
    432 By Assertion 1, $r'$ can be obtained as the resulting array.
    433 
    434 $\blacksquare$
    435 
    436 We can perform binary search on the answer (from Corollary 1), and at each iteration, when checking the answer $x$, verify whether we can obtain the resulting array $r$ of the form $r_i = \max(0, (x - 1) - (n - i))$ (from Corollary 2).
    437 
    438 **Code**
    439 
    440 ```
    441 #include <cstdio>
    442 #include <algorithm>
    443 #include <cstring>
    444 
    445 #define S 100005
    446 
    447 typedef long long l;
    448  
    449 l a[S], d[S], n;
    450 
    451 bool check(l ans) {
    452     memset(d, 0, sizeof(l) * n);
    453     l acc = 0;
    454     
    455     for (l i = 0; i < n; ++i) {
    456         acc -= d[i];
    457         
    458         l need = std::max(0LL, i - (n - ans));
    459         if (acc < need) return false;
    460         
    461         l end = i + a[i] + (acc++) - need + 1;
    462         if (end < n) ++d[end];
    463     }
    464     
    465     return true;
    466 }
    467 
    468 void solve() {
    469     scanf("%lld", &n);
    470     for (l i = 0; i < n; ++i) scanf("%lld", &a[i]);
    471     
    472     l le = 1, ri = n + 1, mid;
    473     while (ri - le > 1) {
    474         mid = (le + ri) / 2;
    475         if (check(mid)) le = mid;
    476         else ri = mid;
    477     }
    478     
    479     printf("%lld\n", le);
    480 }
    481 
    482 int main() {
    483     l tc; scanf("%lld", &tc);
    484     while (tc--) solve();
    485 }
    486 ```