codeforces-scrape

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

2184.md (15312B)


      1 Source: https://codeforces.com/blog/entry/150033
      2 
      3 We hope you enjoyed the contest! Thank you for participating! This is our third official round on Codeforces, so we would be happy to hear your feedback in the comments and in the mini-survey below.
      4 
      5 **How did you like the contest?**
      6 
      7 * Excellent:
      8 * Good:
      9 * Average:
     10 * Bad:
     11 * Terrible:
     12 
     13 **Which problems did you like (you can choose multiple)?**
     14 
     15 * A:
     16 * B:
     17 * C:
     18 * D:
     19 * E:
     20 * F:
     21 * G:
     22 
     23 **Which problems did you not like (you can choose multiple)?**
     24 
     25 * A:
     26 * B:
     27 * C:
     28 * D:
     29 * E:
     30 * F:
     31 * G:
     32 
     33 [2184A - Social Experiment](/contest/2184/problem/A "Codeforces Round 1072 (Div. 3)")
     34 
     35 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus")
     36 
     37 **Hint**
     38 
     39 How many people can be in one civilization?
     40 
     41 **Answer**
     42 
     43 Any non-negative number of people, except for the number $1$.
     44 
     45 **Editorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53  
     54 using namespace std;
     55  
     56 int main() {
     57     int t;
     58     cin >> t;
     59     
     60     while (t--) {
     61         int n;
     62         cin >> n;
     63         if (n == 2) cout << "2\n";
     64         if (n == 3) cout << "3\n";
     65         if (n >= 4) cout << n % 2 << '\n';
     66     }
     67     
     68     return 0;
     69 }
     70 ```
     71 
     72 [2184B - Hourglass](/contest/2184/problem/B "Codeforces Round 1072 (Div. 3)")
     73 
     74 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus")
     75 
     76 **Hint**
     77 
     78 How many minutes of sand will remain in the upper half of the hourglass immediately after the second flip?
     79 
     80 **Answer**
     81 
     82 $s$ minutes.
     83 
     84 **Editorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92  
     93 using namespace std;
     94  
     95 int main() {
     96     int t;
     97     cin >> t;
     98     
     99     while (t--) {
    100         int s, k, m;
    101         cin >> s >> k >> m;
    102         
    103         if (s <= k) cout << max(0, s - m % k) << '\n';
    104 	else cout << (((m % (2 * k)) < k) ? s - m % k : k - m % k) << '\n';
    105     }
    106     
    107     return 0;
    108 }
    109 ```
    110 
    111 [2184C - Huge Pile](/contest/2184/problem/C "Codeforces Round 1072 (Div. 3)")
    112 
    113 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [fstilus](/profile/fstilus "Expert fstilus")
    114 
    115 **Hint 1**
    116 
    117 Why is brute force ineffective? How can it be improved?
    118 
    119 **Answer**
    120 
    121 Because the same numbers are visited multiple times.
    122 
    123 **Hint 2**
    124 
    125 How many distinct values can be obtained starting from the number $n$?
    126 
    127 **Answer**
    128 
    129 $O(\log n)$.
    130 
    131 **Editorial**
    132 
    133 Tutorial is loading...
    134 
    135 **Solution**
    136 
    137 ```
    138 #include <bits/stdc++.h>
    139  
    140 using namespace std;
    141  
    142 int main() {
    143     int t;
    144     cin >> t;
    145     
    146     while (t--) {
    147         int n, k;
    148         cin >> n >> k;
    149         
    150         int l = n, r = n;
    151         int cnt = 0;
    152         while (r != 1) {
    153             if (l <= k && k <= r) break;
    154             l = l / 2;
    155             r = r / 2 + r % 2;
    156             cnt++;
    157         }
    158         if (l <= k && k <= r) cout << cnt << '\n';
    159         else cout << -1 << '\n';
    160     }
    161     
    162     return 0;
    163 }
    164 ```
    165 
    166 [2184D - Unfair Game](/contest/2184/problem/D "Codeforces Round 1072 (Div. 3)")
    167 
    168 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [Friendiks](/profile/Friendiks "Grandmaster Friendiks")
    169 
    170 **Hint 1**
    171 
    172 Alice's winning strategy is related to bits.
    173 
    174 **Hint 2**
    175 
    176 Alice's optimal number of moves depends only on the most significant bit and the number of set bits.
    177 
    178 **Hint 3**
    179 
    180 The number $n$ is a power of two, which means if you subtract $1$, any subset of bits of $n-1$ will not exceed $n-1$.
    181 
    182 **Editorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190  
    191 using namespace std;
    192  
    193 int c_n_k[31][31];
    194 
    195 int main() {
    196     for (int i = 0; i < 30; ++i) {
    197         for (int j = 0; j < 30; ++j) {
    198             if (i < j) c_n_k[i][j] = 0;
    199             else if (j == 0) c_n_k[i][j] = 1;
    200             else c_n_k[i][j] = c_n_k[i - 1][j] + c_n_k[i - 1][j - 1];
    201         }
    202     }
    203 
    204     int t;
    205     cin >> t;
    206 
    207     while (t--) {
    208         int n, k;
    209         cin >> n >> k;
    210 
    211         int d = 0;
    212         while (n % 2 == 0) {
    213             n /= 2;
    214             ++d;
    215         }
    216 
    217         int ans = 0;
    218         for (int max_bit = 0; max_bit < d; ++max_bit) {
    219             for (int cnt_bit = 1; cnt_bit <= max_bit + 1; ++cnt_bit) {
    220                 if (max_bit + cnt_bit <= k) continue;
    221                 ans += c_n_k[max_bit][cnt_bit - 1];
    222             }
    223         }
    224 
    225         if (d + 1 > k) ++ans;
    226         cout << ans << "\n";
    227     }
    228 
    229     return 0;
    230 }
    231 ```
    232 
    233 **Bonus**
    234 
    235 Solve the problem when $n$ is any integer from $1$ to $10^9$, not necessarily a power of two.
    236 
    237 [2184E - Exquisite Array](/contest/2184/problem/E "Codeforces Round 1072 (Div. 3)")
    238 
    239 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus")
    240 
    241 **Hint 1**
    242 
    243 If some array is $k$-exquisite, then any of its subsegments of length at least $2$ is also $k$-exquisite.
    244 
    245 **Hint 2**
    246 
    247 If $k_1 \gt k_2$ and some array is $k_1$-exquisite, then it is also $k_2$-exquisite.
    248 
    249 **Hint 3**
    250 
    251 If some array of length $m$ is $k$-exquisite, how many $k$-exquisite subsegments does it have?
    252 
    253 **Answer**
    254 
    255 $\frac{m \cdot (m - 1)}{2}$.
    256 
    257 **Hint 4**
    258 
    259 For a fixed $k$, come up with a way to divide the entire original permutation into segments, each of which is either $k$-exquisite or of length $1$, so that you can use the formula from the previous hint.
    260 
    261 **Hint 5**
    262 
    263 How to transition from the segmentation for $k+1$ to the segmentation for $k$?
    264 
    265 **Answer**
    266 
    267 You need to find all positions where the difference between the elements of the permutation equals $k$, and merge the corresponding segments.
    268 
    269 **Hint 6**
    270 
    271 Determine how the answer changes with each merging of two segments.
    272 
    273 **Editorial**
    274 
    275 Tutorial is loading...
    276 
    277 **Solution**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 
    282 using namespace std;
    283 
    284 vector <int> parent;
    285 vector <int> rnk;
    286 vector <int> sz;
    287 
    288 void make_set(int v) {
    289     parent[v] = v;
    290     rnk[v] = 0;
    291     sz[v] = 1;
    292 }
    293 
    294 int find_set(int v) {
    295     if (v == parent[v])
    296         return v;
    297     return parent[v] = find_set(parent[v]);
    298 }
    299 
    300 void union_sets(int a, int b) {
    301     a = find_set(a);
    302     b = find_set(b);
    303     if (a != b) {
    304         if (rnk[a] < rnk[b])
    305             swap (a, b);
    306         parent[b] = a;
    307         if (rnk[a] == rnk[b])
    308             ++rnk[a];
    309         sz[a] += sz[b];
    310     }
    311 }
    312 
    313 long long cnt(int x) {
    314     x = find_set(x);
    315     return (long long)sz[x] * (sz[x] - 1) / 2;
    316 }
    317 
    318 int main() {
    319     int t;
    320     cin >> t;
    321     
    322     while (t--) {
    323         int n;
    324         cin >> n;
    325         
    326         map <int, vector <int>> m;
    327         int pr;
    328         for (int i = 0; i < n; i++) {
    329             int a;
    330             cin >> a;
    331             if (i > 0)
    332                 m[abs(a - pr)].push_back(i);
    333             pr = a;
    334         }
    335         
    336         parent.resize(n);
    337         rnk.resize(n);
    338         sz.resize(n);
    339         for (int i = 0; i < n; i++) make_set(i);
    340         
    341         vector <long long> ans;
    342         long long cur = 0;
    343         for (int i = n - 1; i > 0; i--) {
    344             for (auto y : m[i]) {
    345                 cur -= cnt(y);
    346                 cur -= cnt(y - 1);
    347                 union_sets(y, y - 1);
    348                 cur += cnt(y);
    349             }
    350             ans.push_back(cur);
    351         }
    352         
    353         reverse(ans.begin(), ans.end());
    354         for (auto x : ans) cout << x << ' ';
    355         cout << '\n';
    356         
    357         parent.clear();
    358         rnk.clear();
    359         sz.clear();
    360     }
    361 
    362     return 0;
    363 }
    364 ```
    365 
    366 [2184F - Cherry Tree](/contest/2184/problem/F "Codeforces Round 1072 (Div. 3)")
    367 
    368 Idea: [gravitsapa](/profile/gravitsapa "International Master gravitsapa"); developer: [gravitsapa](/profile/gravitsapa "International Master gravitsapa")
    369 
    370 **Hints for the first method**
    371 
    372 **Hint 1**
    373 
    374 Come up with a dynamic programming array $dp[u][k]$ with $O(n^2)$ states, where $u$ is the vertex number, $k$ is an additional parameter, and $dp[u][k]$ indicates whether it is possible to collect all the cherries in the subtree of vertex $u$ given that the additional parameter equals $k$.
    375 
    376 **Answer**
    377 
    378 You can use an additional parameter equal to the number of vertices in the subtree of vertex $u$ that were shaken.
    379 
    380 **Hint 2**
    381 
    382 The parameter $k$ should be considered modulo $3$. Thus, the number of states in the dynamic programming becomes $O(n)$.
    383 
    384 **Hint 3**
    385 
    386 Where will the answer to the problem be located?
    387 
    388 **Answer**
    389 
    390 The answer to the problem is located in $dp[1][0]$.
    391 
    392 **Hint 4**
    393 
    394 What will be the base case for the dynamic programming?
    395 
    396 **Answer**
    397 
    398 If vertex $u$ is a leaf, then $dp[u][0] = False, dp[u][1] = True, dp[u][2] = False$.
    399 
    400 **Hint 5**
    401 
    402 To recalculate the dynamic programming $dp[u]$, two cases need to be considered: whether vertex $u$ was shaken or not. If vertex $u$ was shaken, then it is obviously the only vertex in the entire subtree that was shaken.
    403 
    404 **Hint 6**
    405 
    406 If vertex $u$ was not shaken, then it is necessary to collect cherries in each of its children independently. The information on how this can be done for child $v$ is stored in $dp[v]$.
    407 
    408 **Hint 7**
    409 
    410 To recalculate $dp[u]$ through its children, dynamic programming needs to be used again.
    411 
    412 **Hints for the second method**
    413 
    414 **Hint 1**
    415 
    416 Initially, we will only shake the root vertex. Then we will take some vertex that needs to be shaken and replace it with its children. This way, we can obtain any correct solution.
    417 
    418 **Hint 2**
    419 
    420 During this process, the number of selected vertices changes depending on the number of children of the vertex being replaced. Only the number of children modulo $3$ matters.
    421 
    422 **Hint 3**
    423 
    424 For each vertex that is not a leaf, we can record the number of its children modulo $3$ and find a pattern between the answer and these numbers.
    425 
    426 **Editorial**
    427 
    428 Tutorial is loading...
    429 
    430 **Solution 1**
    431 
    432 ```
    433 #include <bits/stdc++.h>
    434  
    435 using namespace std;
    436  
    437 const int MAXN = 200001;
    438 
    439 int n;
    440 vector <int> graph[MAXN];
    441 vector <bool> dp[MAXN];
    442 
    443 void merge_dp(vector <bool>& lhs, vector <bool>& rhs, vector <bool>& result) {
    444     for (int i = 0; i < 3; ++i) {
    445         if (!lhs[i]) continue;
    446         for (int j = 0; j < 3; ++j) {
    447             if (!rhs[j]) continue;
    448             result[(i + j) % 3] = true;
    449         }
    450     }
    451 }
    452 
    453 void dfs(int u, int p) {
    454     vector <int> child;
    455 
    456     for (auto v : graph[u]) if (v != p) {
    457         dfs(v, u);
    458         child.push_back(v);
    459     }
    460 
    461     dp[u].resize(3);
    462 
    463     if (!child.empty()) {
    464         dp[u][0] = true;
    465         for (auto v : child) {
    466             vector <bool> result(3, false);
    467  
    468             merge_dp(dp[u], dp[v], result);
    469             dp[u] = result;
    470         }
    471     }
    472 
    473     dp[u][1] = true;
    474 }
    475 
    476 signed main() {
    477     ios::sync_with_stdio(false);
    478     cin.tie(0);
    479 
    480     int t;
    481     cin >> t;
    482     while (t--) {
    483         cin >> n;
    484         for (int i = 1; i <= n; ++i) {
    485             graph[i].clear();
    486             dp[i].clear();
    487         }
    488         for (int i = 0; i < n - 1; ++i) {
    489             int u, v;
    490             cin >> u >> v;
    491             graph[u].push_back(v);
    492             graph[v].push_back(u);
    493         }
    494 
    495         dfs(1, -1);
    496 
    497         cout << (dp[1][0] ? "YES" : "NO") << '\n';
    498     }
    499 
    500     return 0;
    501 }
    502 ```
    503 
    504 **Solution 2**
    505 
    506 ```
    507 #include <bits/stdc++.h>
    508  
    509 using namespace std;
    510  
    511 const int MAXN = 200001;
    512 
    513 int n;
    514 vector <int> graph[MAXN];
    515 bool ans;
    516 
    517 int dfs(int u, int p) {
    518     vector <int> child;
    519     int cnt = 0;
    520 
    521     for (auto v : graph[u]) if (v != p) {
    522         cnt++;
    523         auto t = dfs(v, u);
    524         if (t != 0) {
    525             child.push_back(t);
    526         }
    527     }
    528 
    529     if (child.size() > 1) {
    530         ans = true;
    531         return 0;
    532     }
    533 
    534     int type = cnt == 0 ? 0 : (cnt + 2) % 3;
    535     vector <int> ord;
    536     if (type) {
    537         ord.push_back(type);
    538     }
    539     if (!child.empty()) {
    540         ord.push_back(child[0]);
    541     }
    542     if (ord.size() == 2 && ord[0] + ord[1] != 3) {
    543         ans = true;
    544         return 0;
    545     }
    546     if (ord.size() >= 1) return ord[0];
    547     return 0;
    548 }
    549 
    550 signed main() {
    551     ios::sync_with_stdio(false);
    552     cin.tie(0);
    553 
    554     int t;
    555     cin >> t;
    556 
    557     while (t--) {
    558         cin >> n;
    559         for (int i = 1; i <= n; ++i) {
    560             graph[i].clear();
    561         }
    562  
    563         for (int i = 0; i < n - 1; ++i) {
    564             int u, v;
    565             cin >> u >> v;
    566             graph[u].push_back(v);
    567             graph[v].push_back(u);
    568         }
    569 
    570         ans = false;
    571         int res = dfs(1, 1);
    572         if (res == 2) {
    573             ans = true;
    574         }
    575      
    576         cout << (ans ? "YES" : "NO") << '\n';
    577     }
    578 
    579     return 0;
    580 }
    581 ```
    582 
    583 [2184G - Nastiness of Segments](/contest/2184/problem/G "Codeforces Round 1072 (Div. 3)")
    584 
    585 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [Friendiks](/profile/Friendiks "Grandmaster Friendiks")
    586 
    587 **Hint 1**
    588 
    589 Fix $L$ and $R$ and define functions of integer $d$: $f(d) = d$, $g(d) = \min(a_L, \dots, a_{L+d})$, where $0 \le d \le R-L$. What can be said about these functions?
    590 
    591 **Answer**
    592 
    593 $f(d)$ is increasing, $g(d)$ is non-increasing.
    594 
    595 **Hint 2**
    596 
    597 How many times can the problem condition be satisfied if expressed through $f$ and $g$?
    598 
    599 **Answer**
    600 
    601 The condition is equivalent to the intersection of $f(d)$ and $g(d)$, meaning there is at most one suitable point.
    602 
    603 **Hint 3**
    604 
    605 Since the function $h(d) = f(d) - g(d)$ is monotonic, the only candidate for the intersection point is the minimum $d$ such that $h(d) \ge 0$ (or $f(d) \ge g(d)$).
    606 
    607 **Hint 4**
    608 
    609 Segment tree.
    610 
    611 **Editorial**
    612 
    613 Tutorial is loading...
    614 
    615 **Solution**
    616 
    617 ```
    618 #include <bits/stdc++.h>
    619  
    620 using namespace std;
    621  
    622 const int MAXN = 2e5 + 7;
    623 
    624 int a[MAXN], st[4 * MAXN];
    625 
    626 void build(int v, int l, int r) {
    627     if (l + 1 == r) {
    628         st[v] = a[l];
    629         return;
    630     }
    631     int m = (r + l) / 2;
    632     build(v * 2 + 1, l, m);
    633     build(v * 2 + 2, m, r);
    634     st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
    635 }
    636 
    637 void upd(int v, int l, int r, int i, int x) {
    638     if (i < l || r <= i) return;
    639     if (l + 1 == r) {
    640         a[i] = x;
    641         st[v] = x;
    642         return;
    643     }
    644     int m = (r + l) / 2;
    645     upd(v * 2 + 1, l, m, i, x);
    646     upd(v * 2 + 2, m, r, i, x);
    647     st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
    648 }
    649 
    650 int getMin(int v, int l, int r, int lq, int rq) {
    651     if (rq <= l || r <= lq) return (int) 1e6;
    652     if (lq <= l && r <= rq) return st[v];
    653     int m = (r + l) / 2;
    654     return min(getMin(v * 2 + 1, l, m, lq, rq), getMin(v * 2 + 2, m, r, lq, rq));
    655 }
    656 
    657 int ans, currMn;
    658 
    659 void findInter(int v, int l, int r, int lq, int rq) {
    660     if (rq <= l || r <= lq || ans != (int) 1e6) return;
    661     if (lq <= l && r <= rq && min(currMn, st[v]) > r - lq - 1) {
    662         currMn = min(currMn, st[v]);
    663         return;
    664     }
    665     if (l + 1 == r) {
    666         ans = l;
    667         return;
    668     }
    669     int m = (r + l) / 2;
    670     findInter(v * 2 + 1, l, m, lq, rq);
    671     findInter(v * 2 + 2, m, r, lq, rq);
    672 }
    673 
    674 int main() {
    675     int t;
    676     cin >> t;
    677 
    678     while (t--) {
    679         int n, q;
    680         cin >> n >> q;
    681         for (int i = 0; i < n; ++i) cin >> a[i];
    682 
    683         build(0, 0, n);
    684         while (q--) {
    685             int idx;
    686             cin >> idx;
    687 
    688             if (idx == 1) {
    689                 int i, x;
    690                 cin >> i >> x;
    691                 upd(0, 0, n, i - 1, x);
    692             } else {
    693                 int l, r;
    694                 cin >> l >> r;
    695                 l--;
    696 
    697                 if (getMin(0, 0, n, l, r) > r - l) {
    698                     cout << "0\n";
    699                     continue;
    700                 }
    701 
    702                 ans = currMn = (int) 1e6;
    703                 findInter(0, 0, n, l, r);
    704                 cout << (ans != (int) 1e6 && getMin(0, 0, n, l, ans + 1) == ans - l) << "\n";
    705             }
    706         }
    707     }
    708 
    709     return 0;
    710 }
    711 ```