codeforces-scrape

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

1805.md (11574B)


      1 Source: https://codeforces.com/blog/entry/114644
      2 
      3 Thank you for participating! We hope you enjoyed the problems!
      4 
      5 [1805A - We Need the Zero](/contest/1805/problem/A "Codeforces Round 862 (Div. 2)")  
      6  Idea and preparation: [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
      7 
      8 **Hint 1**
      9 
     10 Recall the basic properties of the $\oplus$ operation: $A \oplus 0 = A$, $A \oplus A = 0$, $A \oplus B = B \oplus A$.
     11 
     12 **Hint 2**
     13 
     14 Consider the cases of even and odd array lengths.
     15 
     16 **Editorial**
     17 
     18 Tutorial is loading...
     19 
     20 **Solution**
     21 
     22 ```
     23 for _ in range(int(input())):
     24     n = int(input())
     25     a = list(map(int, input().split()))
     26     xor = 0
     27     for x in a:
     28         xor ^= x
     29     if xor == 0:
     30         print(0)
     31     else:
     32         if n % 2 == 1:
     33             print(xor)
     34         else:
     35             print(-1)
     36 ```
     37 
     38 **Rate the problem**
     39 
     40 * Didn't solve
     41 * Good task
     42 * Average task
     43 * Bad task
     44 
     45 [1805B - The String Has a Target](/contest/1805/problem/B "Codeforces Round 862 (Div. 2)")  
     46  Idea and preparation: [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
     47 
     48 **Hint 1**
     49 
     50 What should be the first character if we are trying to make the string lexicographically minimal?
     51 
     52 **Hint 2**
     53 
     54 Consider the string «baba». If you choose $i=2$, you get the string «abba», and if you choose $i=4$ you get «abab». Try to generalize this reasoning to any string.
     55 
     56 **Editorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution**
     61 
     62 ```
     63 for _ in range(int(input())):
     64     n = int(input())
     65     s = input()
     66     ind = s.rfind(min(s))  # Find the last ind such that s[ind] = min(s)
     67     print(s[ind] + s[:ind] + s[ind + 1:])
     68 ```
     69 
     70 **Rate the problem**
     71 
     72 * Didn't solve
     73 * Good task
     74 * Average task
     75 * Bad task
     76 
     77 [1805C - Place for a Selfie](/contest/1805/problem/C "Codeforces Round 862 (Div. 2)")  
     78  Idea and preparation: [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
     79 
     80 **Hint 1**
     81 
     82 Note that the distance between the line and the parabola will also be a parabola. Then what is the condition that the line and the parabola have no common points?
     83 
     84 **Hint 2**
     85 
     86 Recall the discriminant formula from school: If a parabola $ax^2 + bx + c$ is given, then calculate $D=b^2 - 4ac$ (discriminant). Then, if $D \gt 0$, the parabola has $2$ roots, if $D=0$, it has one root, if $D \lt 0$, it has no roots.
     87 
     88 **Hint 3**
     89 
     90 If we choose the parabola $ax^2 + bx + c$, then the lines with such coefficient $k$ that $(b-k)^2 \lt 4ac$ have no common points with it. How can we find such $k$ among the given lines?
     91 
     92 **Editorial**
     93 
     94 Tutorial is loading...
     95 
     96 **Solution**
     97 
     98 ```
     99 #include <bits/stdc++.h>
    100 #define int long long
    101 
    102 using namespace std;
    103 
    104 void solve() {
    105     int n, m;
    106     cin >> n >> m;
    107     vector <int> lines(n);
    108     for (int i = 0; i < n; i++) {
    109         cin >> lines[i];
    110     }
    111     sort(lines.begin(), lines.end());
    112 
    113     for (int i = 0; i < m; i++) {
    114         int a, b, c;
    115         cin >> a >> b >> c;
    116 
    117         int ind = lower_bound(lines.begin(), lines.end(), b) - lines.begin();
    118         if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) {
    119             cout << "YES\n" << lines[ind] << "\n";
    120             continue;
    121         }
    122         if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) {
    123             cout << "YES\n" << lines[ind - 1] << "\n";
    124             continue;
    125         }
    126         cout << "NO\n";
    127     }
    128 }
    129 
    130 signed main() {
    131     ios::sync_with_stdio(false);
    132     cin.tie(nullptr);
    133 
    134     int q = 1;
    135     cin >> q;
    136     while (q--) {
    137         solve();
    138     }
    139     return 0;
    140 }
    141 ```
    142 
    143 **Rate the problem**
    144 
    145 * Didn't solve
    146 * Good task
    147 * Average task
    148 * Bad task
    149 
    150 [1805D - A Wide, Wide Graph](/contest/1805/problem/D "Codeforces Round 862 (Div. 2)")  
    151  Idea: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx"), preparation: [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
    152 
    153 **Hint 1**
    154 
    155 At what maximal $k$ does the graph $G_k$ not decompose into single components? What happens if we decrease $k$ by $1$?
    156 
    157 **Hint 2**
    158 
    159 Consider some diameter of a tree (the path of the longest length). If in the graph $G_k$ a vertex has a neighbor, then it is also connected by an edge to one of the ends of the diameter. How can we use this fact to find the answer for $k$ if we know the components of graph $G_{k+1}$?
    160 
    161 **Editorial**
    162 
    163 Tutorial is loading...
    164 
    165 **Solution**
    166 
    167 ```
    168 #include <bits/stdc++.h>
    169 
    170 #define all(a) a.begin(), a.end()
    171 #define rall(a) a.rbegin(), a.rend()
    172 
    173 using namespace std;
    174 
    175 const int N = 1e5 + 228;
    176 
    177 vector<int> G[N];
    178 
    179 void dfs(int v, int par, int h, vector<int> &d) {
    180     d[v] = h;
    181     for (int i : G[v]) {
    182         if (i != par) {
    183             dfs(i, v, h + 1, d);
    184         }
    185     }
    186 }
    187 
    188 int main() {
    189     ios_base::sync_with_stdio(0);
    190     cin.tie(0);
    191 
    192     int n;
    193     cin >> n;
    194     for (int i = 0; i < n - 1; ++i) {
    195         int a, b;
    196         cin >> a >> b;
    197         G[a - 1].push_back(b - 1);
    198         G[b - 1].push_back(a - 1);
    199     }
    200 
    201     vector<int> d1(n), d2(n);
    202     dfs(0, -1, 0, d1);
    203     int a = max_element(all(d1)) - d1.begin();
    204     dfs(a, -1, 0, d1);
    205     int b = max_element(all(d1)) - d1.begin();
    206     dfs(b, -1, 0, d2);
    207     for (int i = 0; i < n; ++i) {
    208         d2[i] = max(d2[i], d1[i]);
    209     }
    210     sort(all(d2));
    211     int ans = 0;
    212     for (int i = 1; i <= n; ++i) {
    213         while (ans < n && d2[ans] < i) {
    214             ++ans;
    215         }
    216         cout << min(n, ans + 1) << ' ';
    217     }
    218     cout << '\n';
    219 }
    220 ```
    221 
    222 **Rate the problem**
    223 
    224 * Didn't solve
    225 * Good task
    226 * Average task
    227 * Bad task
    228 
    229 [1805E - There Should Be a Lot of Maximums](/contest/1805/problem/E "Codeforces Round 862 (Div. 2)")  
    230  Idea and preparation: [Alexdat2000](/profile/Alexdat2000 "Master Alexdat2000")
    231 
    232 **Hint 1**
    233 
    234 Let $M$ — $MAD$ of the whole tree. What is the answer if there are many vertices with value $M$ in the tree?
    235 
    236 **Hint 2**
    237 
    238 Note that for many edges the answer is $M$. And for which edges is it not so?
    239 
    240 **Hint 3**
    241 
    242 Let the tree have only two vertices with value $M$. Then for the edges not on the path between them we know the answer. What about the path between two vertices of $M$? Can we walk along it by calculating the answer for all vertices?
    243 
    244 **Editorial**
    245 
    246 Tutorial is loading...
    247 
    248 **Solution**
    249 
    250 ```
    251 #include <bits/stdc++.h>
    252 
    253 using namespace std;
    254 
    255 const int N = 2e5 + 100;
    256 vector <pair <int, int>> g[N];
    257 int val[N];
    258 
    259 vector <int> ans;
    260 map <int, int> cnt1, cnt2;
    261 set <int> mad1, mad2;
    262 
    263 vector <int> path, path_ind;
    264 bool used[N];
    265 
    266 bool dfs(int v, int tar) {
    267     used[v] = true;
    268     path.push_back(v);
    269     if (v == tar) {
    270         return true;
    271     }
    272     for (auto [i, ind] : g[v]) {
    273         if (!used[i]) {
    274             path_ind.push_back(ind);
    275             if (dfs(i, tar)) {
    276                 return true;
    277             }
    278             path_ind.pop_back();
    279         }
    280     }
    281     path.pop_back();
    282     return false;
    283 }
    284 
    285 int mad() {
    286     int mx = 0;
    287     if (!mad1.empty()) {
    288         mx = max(mx, *mad1.rbegin());
    289     }
    290     if (!mad2.empty()) {
    291         mx = max(mx, *mad2.rbegin());
    292     }
    293     return mx;
    294 }
    295 
    296 void recalc(int v, int ban1, int ban2) {
    297     cnt1[val[v]]++;
    298     if (cnt1[val[v]] == 2) {
    299         mad1.insert(val[v]);
    300     }
    301     cnt2[val[v]]--;
    302     if (cnt2[val[v]] == 1) {
    303         mad2.erase(val[v]);
    304     }
    305     for (auto [i, _] : g[v]) {
    306         if (i != ban1 && i != ban2) {
    307             recalc(i, v, -1);
    308         }
    309     }
    310 }
    311 
    312 signed main() {
    313     ios::sync_with_stdio(false);
    314     cin.tie(nullptr);
    315 
    316     int n;
    317     cin >> n;
    318     for (int i = 0; i < n - 1; i++) {
    319         int a, b;
    320         cin >> a >> b;
    321         a--, b--;
    322         g[a].emplace_back(b, i);
    323         g[b].emplace_back(a, i);
    324     }
    325 
    326     map <int, vector <int>> ind;
    327     for (int i = 0; i < n; i++) {
    328         cin >> val[i];
    329         ind[val[i]].push_back(i);
    330         cnt2[val[i]]++;
    331         if (cnt2[val[i]] == 2) {
    332             mad2.insert(val[i]);
    333         }
    334     }
    335 
    336     while (!ind.empty() && ind.rbegin() -> second.size() == 1) {
    337         ind.erase(prev(ind.end()));
    338     }
    339     if (ind.empty()) {
    340         for (int i = 0; i < n - 1; i++) {
    341             cout << "0\n";
    342         }
    343         return 0;
    344     } else if (ind.rbegin()->second.size() > 2) {
    345         for (int i = 0; i < n - 1; i++) {
    346             cout << ind.rbegin() -> first << "\n";
    347         }
    348         return 0;
    349     }
    350 
    351     int a = ind.rbegin()->second[0], b = ind.rbegin()->second[1];
    352     dfs(a, b);
    353 
    354     ans.assign(n - 1, ind.rbegin() -> first);
    355     recalc(path[0], path[1], -1);
    356     ans[path_ind[0]] = mad();
    357 
    358     for (int i = 1; i + 1 < path.size(); i++) {
    359         recalc(path[i], path[i - 1], path[i + 1]);
    360         ans[path_ind[i]] = mad();
    361     }
    362 
    363     for (int i : ans) {
    364         cout << i << "\n";
    365     }
    366     return 0;
    367 }
    368 ```
    369 
    370 **Rate the problem**
    371 
    372 * Didn't solve
    373 * Good task
    374 * Average task
    375 * Bad task
    376 
    377 [1805F2 - Survival of the Weakest (hard version)](/contest/1805/problem/F2 "Codeforces Round 862 (Div. 2)")  
    378  Idea and preparation: [sevlll777](/profile/sevlll777 "Grandmaster sevlll777")
    379 
    380 Hints for the simple version:
    381 
    382 **Hint 1**
    383 
    384 Figure out how to implement the function $F$ in $O(n log n)$
    385 
    386 **Hint 1.1**
    387 
    388 You'll need $std::priority\_queue$ or $std::set$
    389 
    390 **Hint 2**
    391 
    392 If you run $F$ for $O(n log n)$ $n - 1$ times, we'll get the solution in $O(n^2 log n)$. However, the numbers in the array can grow very fast. Can you somehow modify the numbers in the array so that $F$ changes in a predictable way?
    393 
    394 **Hint 2.2**
    395 
    396 $F([a_1, a_2, \ldots, a_n]) = F([a_1 - x, a_2 - x, \ldots, a_n - x]) + x \cdot 2^{n-1}$
    397 
    398 Hints for the hard version:
    399 
    400 **Hint 3**
    401 
    402 How to solve the problem if $a_i \leq 1$? $\leq 2$? Can you notice anything about these solutions?
    403 
    404 **Hint 4**
    405 
    406 If $n$ is large enough, then $F(F(\ldots F([a_1, a_2, \ldots, a_n])\ldots)) = F(F( \ldots F([a_1, a_2, \ldots, a_{n-1}, X])\ldots))$ where $X$ any number $\geq a_{n-1}$, in other words: the largest element is useless for the final answer
    407 
    408 **Hint 5**
    409 
    410 Only a small number of the smallest elements of the original array will affect the answer
    411 
    412 **Editorial**
    413 
    414 Tutorial is loading...
    415 
    416 **Solution**
    417 
    418 ```
    419 #include <bits/stdc++.h>
    420 #define all(x) x.begin(), (x).end()
    421 
    422 using namespace std;
    423 
    424 const int M = 1000000007;
    425 long long ans = 0;
    426 int real_len = 0;
    427 
    428 long long binpow(long long a, int x) {
    429     long long ans0 = 1;
    430     while (x) {
    431         if (x % 2) {
    432             ans0 *= a;
    433             ans0 %= M;
    434         }
    435         a *= a;
    436         a %= M;
    437         x /= 2;
    438     }
    439     return ans0;
    440 }
    441 
    442 void chill(vector<int> &b) {
    443     int mn = b[0];
    444     ans += (int) ((long long) mn * binpow(2, real_len - 1) % M);
    445     if (ans >= M) {
    446         ans -= M;
    447     }
    448     for (auto &x : b) {
    449         x -= mn;
    450     }
    451 }
    452 
    453 void F(vector<int> &b, int sub = 0) {
    454     --real_len;
    455     vector<int> cnd;
    456     for (int i = 0; i < b.size(); i++) {
    457         for (int j = i + 1; j < b.size(); j++) {
    458             if (i * j >= b.size()) break;
    459             cnd.push_back(b[i] + b[j]);
    460         }
    461     }
    462     sort(all(cnd));
    463     vector<int> b2((int) b.size() - sub);
    464     for (int i = 0; i < (int) b.size() - sub; i++) {
    465         b2[i] = cnd[i];
    466     }
    467     chill(b2);
    468     b = b2;
    469 }
    470 
    471 signed main() {
    472     ios::sync_with_stdio(false);
    473     cin.tie(nullptr);
    474     cout.tie(nullptr);
    475     int n;
    476     cin >> n;
    477     vector<int> a(n);
    478     for (int i = 0; i < n; i++) {
    479         cin >> a[i];
    480     }
    481     sort(all(a));
    482     int L = 64;
    483     vector<int> b(min(n, L));
    484     for (int i = 0; i < min(n, L); i++) {
    485         b[i] = a[i];
    486     }
    487     real_len = n;
    488     chill(b);
    489     while (b.size() < real_len) {
    490         if (b[1] + b[2] > b.back()) {
    491             F(b, 1);
    492             F(b, 1);
    493         } else {
    494             F(b);
    495         }
    496     }
    497     while (real_len > 1) {
    498         F(b, 1);
    499     }
    500     ans += b[0];
    501     ans %= M;
    502     cout << ans << '\n';
    503 }
    504 ```
    505 
    506 **Rate the problem**
    507 
    508 * Didn't solve
    509 * Good task
    510 * Average task
    511 * Bad task