codeforces-scrape

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

1637.md (12854B)


      1 Source: https://codeforces.com/blog/entry/99883
      2 
      3 We hope you enjoyed the contest! We recommend you to read all tutorials even if you solve the problem, maybe you will learn something new.
      4 
      5 [1637A - Sorting Parts](/contest/1637/problem/A "Codeforces Global Round 19")  
      6  Idea: [__JustMe__](/profile/__JustMe__ "Master __JustMe__").
      7 
      8 **Hint 1**
      9 
     10 What does happen if the array is already sorted?
     11 
     12 **Hint 2**
     13 
     14 What does happen if there are two indexes $i$ and $j$, such that $i \lt j$ and $a_i \gt a_j$?
     15 
     16 **Tutorial**
     17 
     18 Tutorial is loading...
     19 
     20 **Solution**
     21 
     22 ```
     23 #include <bits/stdc++.h>
     24 using namespace std;
     25  
     26 int main() {
     27     int t;
     28     cin >> t;
     29     for (int i = 0; i < t; i++) {
     30         int n;
     31         cin >> n;
     32         vector<int> a(n);
     33         for (auto& u : a)
     34             cin >> u;
     35         if (!is_sorted(a.begin(), a.end()))
     36             cout << "YES\n";
     37         else
     38             cout << "NO\n";
     39     }
     40 }
     41 ```
     42 
     43 [1637B - MEX and Array](/contest/1637/problem/B "Codeforces Global Round 19")  
     44  Idea: [__JustMe__](/profile/__JustMe__ "Master __JustMe__") and [Mangooste](/profile/Mangooste "Grandmaster Mangooste").
     45 
     46 **Hint 1**
     47 
     48 What does happen after replacing a segment of length greater than $1$ with segments of length $1$?
     49 
     50 **Hint 2**
     51 
     52 The cost of the array $b_1, b_2, \ldots, b_k$ equals to $k + \sum_{i=1}^{k} mex(${$b_i$}$)$.
     53 
     54 **Tutorial**
     55 
     56 Tutorial is loading...
     57 
     58 **Solution**
     59 
     60 ```
     61 #include <bits/stdc++.h>
     62 using namespace std;
     63  
     64 int main() {
     65     int t;
     66     cin >> t;
     67     for (int i = 0; i < t; i++) {
     68         int n;
     69         cin >> n;
     70         vector<int> a(n);
     71         for (auto& u : a)
     72             cin >> u;
     73  
     74         int ans = 0;
     75         for (int i = 0; i < n; i++) {
     76             ans += (i + 1) * (n - i);
     77             if (a[i] == 0)
     78                 ans += (i + 1) * (n - i);
     79         }
     80         cout << ans << '\n';
     81     }
     82 }
     83 ```
     84 
     85 [1637C - Andrew and Stones](/contest/1637/problem/C "Codeforces Global Round 19")  
     86  Idea: [TeaTime](/profile/TeaTime "Master TeaTime").
     87 
     88 **Hint 1**
     89 
     90 The answer is $-1$ in two cases. If $n = 3$ and $a_2$ is odd. Also if for all $1 \lt i \lt n$: $a_i = 1$.
     91 
     92 **Hint 2**
     93 
     94 It is not optimal to add $1$ to an odd number more than once.
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105  
    106 void solve() {
    107     int n;
    108     cin >> n;
    109     vector<int> a(n);
    110     for (auto &x : a)
    111         cin >> x;
    112  
    113     if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2 == 1)) {
    114         cout << "-1\n";
    115         return;
    116     }
    117  
    118     long long answer = 0;
    119     for (int i = 1; i < n - 1; i++)
    120         answer += (a[i] + 1) / 2;
    121  
    122     cout << answer << '\n';
    123 }
    124  
    125 int main() {
    126     ios::sync_with_stdio(false), cin.tie(nullptr);
    127     int tests;
    128     cin >> tests;
    129     while (tests--)
    130         solve();
    131 }
    132 ```
    133 
    134 [1637D - Yet Another Minimization Problem](/contest/1637/problem/D "Codeforces Global Round 19")  
    135  Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste").
    136 
    137 **Hint 1**
    138 
    139 Try to simplify the array cost formula.
    140 
    141 **Hint 2**
    142 
    143 The total cost of two arrays equals to $(n - 2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^n a_i)^2 + (\sum_{i=1}^n b_i)^2$.
    144 
    145 **Hint 3**
    146 
    147 Find all possible sums of the array $a$ after some operations.
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution**
    154 
    155 ```
    156 #include <bits/stdc++.h>
    157 using namespace std;
    158  
    159 constexpr int MAXSUM = 100 * 100 + 10;
    160  
    161 int sqr(int x) {
    162     return x * x;
    163 }
    164  
    165 void solve() {
    166     int n;
    167     cin >> n;
    168     vector<int> a(n), b(n);
    169     for (auto& u : a)
    170         cin >> u;
    171  
    172     for (auto& u : b)
    173         cin >> u;
    174  
    175     int sumMin = 0, sumMax = 0, sumSq = 0;
    176     for (int i = 0; i < n; i++) {
    177         if (a[i] > b[i])
    178             swap(a[i], b[i]);
    179  
    180         sumSq += sqr(a[i]) + sqr(b[i]);
    181         sumMin += a[i];
    182         sumMax += b[i];
    183     }
    184  
    185     bitset<MAXSUM> dp;
    186     dp[0] = 1;
    187     for (int i = 0; i < n; i++)
    188         dp |= dp << (b[i] - a[i]);
    189  
    190     int ans = sqr(sumMin) + sqr(sumMax);
    191     for (int i = 0; i <= sumMax - sumMin; i++)
    192         if (dp[i])
    193             ans = min(ans, sqr(sumMin + i) + sqr(sumMax - i));
    194  
    195     cout << sumSq * (n - 2) + ans << '\n';
    196 }
    197  
    198 int main() {
    199     int t;
    200     cin >> t;
    201     while (t--)
    202         solve();
    203 }
    204 ```
    205 
    206 [1637E - Best Pair](/contest/1637/problem/E "Codeforces Global Round 19")  
    207  Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste").
    208 
    209 **Hint 1**
    210 
    211 Fix $x$ and iterate over all $cnt_y \le cnt_x$. It works in $O(n)$ summary.
    212 
    213 **Hint 2**
    214 
    215 When you fix $x$ and $cnt_y$, interate over all $y$ in the non increasing order while $x = y$ or the pair $(x, y)$ is bad.
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Solution**
    222 
    223 ```
    224 #include <bits/stdc++.h>
    225 using namespace std;
    226  
    227 void solve() {
    228     int n, m;
    229     cin >> n >> m;
    230     vector<int> a(n);
    231     map<int, int> cnt;
    232     for (auto &x : a) {
    233         cin >> x;
    234         cnt[x]++;
    235     }
    236  
    237     vector<pair<int, int>> bad_pairs;
    238     bad_pairs.reserve(2 * m);
    239     for (int i = 0; i < m; i++) {
    240         int x, y;
    241         cin >> x >> y;
    242         bad_pairs.emplace_back(x, y);
    243         bad_pairs.emplace_back(y, x);
    244     }
    245     sort(bad_pairs.begin(), bad_pairs.end());
    246  
    247     vector<vector<int>> occ(n);
    248     for (auto &[x, c] : cnt)
    249         occ[c].push_back(x);
    250  
    251     for (auto &v : occ)
    252         reverse(v.begin(), v.end());
    253  
    254     long long answer = 0;
    255     for (int cnt_x = 1; cnt_x < n; cnt_x++)
    256         for (int x : occ[cnt_x])
    257             for (int cnt_y = 1; cnt_y <= cnt_x; cnt_y++)
    258                 for (auto y : occ[cnt_y])
    259                     if (x != y && !binary_search(bad_pairs.begin(), bad_pairs.end(), pair<int, int>{x, y})) {
    260                         answer = max(answer, 1ll * (cnt_x + cnt_y) * (x + y));
    261                         break;
    262                     }
    263  
    264     cout << answer << '\n';
    265 }
    266  
    267 int main() {
    268     ios::sync_with_stdio(false), cin.tie(nullptr);
    269     int tests;
    270     cin >> tests;
    271     while (tests--)
    272         solve();
    273 }
    274 ```
    275 
    276 [1637F - Towers](/contest/1637/problem/F "Codeforces Global Round 19")  
    277  Idea: [TeaTime](/profile/TeaTime "Master TeaTime").
    278 
    279 **Hint 1**
    280 
    281 Find the answer when heights of all vertices are equal to $1$.
    282 
    283 **Hint 2**
    284 
    285 Consider tree where all heights are either $1$ or $0$. What is the answer in this case?
    286 
    287 **Tutorial**
    288 
    289 Tutorial is loading...
    290 
    291 **Solution**
    292 
    293 ```
    294 #include <iostream>
    295 #include <vector>
    296 #include <algorithm>
    297 #include <set>
    298 #include <map>
    299  
    300 using namespace std;
    301  
    302 typedef long long ll;
    303  
    304 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    305  
    306 ll n;
    307 vector<vector<ll>> gr;
    308 vector<ll> vec;
    309  
    310 void input() {
    311 	cin >> n;
    312 	vec.resize(n);
    313 	for (auto& c : vec) cin >> c;
    314  
    315 	gr.resize(n);
    316  
    317 	for (int i = 0; i < n - 1; i++) {
    318 		ll u, v;
    319 		cin >> u >> v;
    320 		u--; v--;
    321 		gr[u].push_back(v);
    322 		gr[v].push_back(u);
    323 	}
    324 }
    325  
    326 ll sol() {
    327 	ll ans = 0;
    328  
    329 	set<pair<ll, ll>> leaves;
    330 	vector<pair<ll, ll>> srt;
    331 	vector<ll> degree(n);
    332  
    333 	srt.push_back({ 0, -1 });
    334 	for (int i = 0; i < n; i++) {
    335 		degree[i] = gr[i].size();
    336  
    337 		srt.push_back({ vec[i], i });
    338 		if (gr[i].size() == 1) {
    339 			leaves.insert({vec[i], i});
    340 		}
    341 	}
    342  
    343 	sort(srt.begin(), srt.end());
    344  
    345 	for (int i = 1; i <= n; i++) {
    346 		while (leaves.size() > 0 && (*leaves.begin()).first < srt[i].first) {
    347 			ll v = (*leaves.begin()).second;
    348 			degree[v] = -2;
    349 			leaves.erase(leaves.begin());
    350  
    351 			for (auto to : gr[v]) {
    352 				degree[to]--;
    353 				if (degree[to] == 1 || degree[to] == 0) leaves.insert({ vec[to], to });
    354 			}
    355 		}
    356  
    357 		ans += max(2ll, ll(leaves.size())) * (srt[i].first - srt[i - 1].first);
    358 	}
    359  
    360 	return ans;
    361 }
    362  
    363 int main() {
    364 	fastInp;
    365  
    366 	input();
    367 	cout << sol();
    368  
    369 	return 0;
    370 }
    371 ```
    372 
    373 **Alternative solution**
    374 
    375 ```
    376 #include <bits/stdc++.h>
    377 using namespace std;
    378  
    379 typedef long long ll;
    380  
    381 int main() {
    382   ios_base::sync_with_stdio(false); cin.tie(0);
    383   int n;
    384   cin >> n;
    385   vector<int> h(n);
    386   for (int i = 0; i < n; ++i) cin >> h[i];
    387   vector<vector<int>> g(n);
    388   for (int i = 0; i + 1 < n; ++i) {
    389     int u, v;
    390     cin >> u >> v;
    391     --u, --v;
    392     g[u].push_back(v);
    393     g[v].push_back(u);
    394   }
    395   int rt = 0;
    396   for (int i = 0; i < n; ++i) {
    397     if (h[i] > h[rt]) {
    398       rt = i;
    399     }
    400   }
    401   ll ans = 0;
    402   function<int(int, int)> dfs = [&](int u, int p) {
    403     int mx1 = 0, mx2 = 0;
    404     vector<int> have;
    405     for (auto v : g[u]) {
    406       if (v != p) {
    407         int cur = dfs(v, u);
    408         if (cur > mx1) swap(cur, mx1);
    409         if (cur > mx2) swap(cur, mx2);
    410       }
    411     }
    412     if (p != -1) {
    413       int delta = max(0, h[u] - mx1);
    414       ans += delta;
    415       mx1 += delta;
    416     } else {
    417       ans += max(0, h[u] - mx1) + max(0, h[u] - mx2);
    418     }
    419     return mx1;
    420   };
    421   dfs(rt, -1);
    422   cout << ans << '\n';
    423 }
    424 ```
    425 
    426 [1637G - Birthday](/contest/1637/problem/G "Codeforces Global Round 19")  
    427  Idea: [EvgeniyPonasenkov](/profile/EvgeniyPonasenkov "Master EvgeniyPonasenkov").
    428 
    429 **Hint 1**
    430 
    431 It's impossible to construct a sequence of operations only when $n = 2$.
    432 
    433 **Hint 2**
    434 
    435 Answer is the smallest power of two which is at least $n$.
    436 
    437 **Hint 3**
    438 
    439 Try to transform all numbers into the powers of two (maybe different).
    440 
    441 **Tutorial**
    442 
    443 Tutorial is loading...
    444 
    445 **Solution**
    446 
    447 ```
    448 #include <bits/stdc++.h>
    449 using namespace std;
    450  
    451 vector<pair<int, int>> ops;
    452 vector<int> a;
    453  
    454 void rec(int n, int coeff) {
    455     if (n <= 2) {
    456         for (int i = 1; i <= n; i++)
    457             a.push_back(i * coeff);
    458         return;
    459     }
    460  
    461     int p = 1;
    462     while (p * 2 <= n) p *= 2;
    463  
    464     if (p == n) {
    465         a.push_back(n * coeff);
    466         n--, p /= 2;
    467     }
    468  
    469     a.push_back(p * coeff);
    470     for (int i = p + 1; i <= n; i++) {
    471         a.push_back(2 * p * coeff);
    472         ops.emplace_back(i * coeff, (2 * p - i) * coeff);
    473     }
    474  
    475     rec(2 * p - n - 1, coeff);
    476     rec(n - p, coeff * 2);
    477 }
    478  
    479 void solve() {
    480     int n;
    481     cin >> n;
    482     if (n == 2) {
    483         cout << "-1\n";
    484         return;
    485     }
    486  
    487     ops.clear();
    488     a.clear();
    489     rec(n, 1);
    490     sort(a.begin(), a.end());
    491  
    492     int answer = 1;
    493     while (answer < n)
    494         answer *= 2;
    495  
    496     for (int i = 0;; i++)
    497         if (a[i] == a[i + 1]) {
    498             assert(a[i] != answer);
    499             ops.emplace_back(a[i], a[i]);
    500             a[i + 1] *= 2;
    501             a.erase(a.begin() + i);
    502             break;
    503         }
    504  
    505     for (auto x : a)
    506         while (x != answer) {
    507             ops.emplace_back(0, x);
    508             ops.emplace_back(x, x);
    509             x *= 2;
    510         }
    511  
    512     ops.emplace_back(0, answer);
    513     cout << ops.size() << '\n';
    514     for (auto &[x, y] : ops)
    515         cout << x << ' ' << y << '\n';
    516 }
    517  
    518 int main() {
    519     int tests;
    520     cin >> tests;
    521     while (tests--)
    522         solve();
    523 }
    524 ```
    525 
    526 [1637H - Minimize Inversions Number](/contest/1637/problem/H "Codeforces Global Round 19")  
    527  Idea: [Mangooste](/profile/Mangooste "Grandmaster Mangooste").
    528 
    529 **Hint 1**
    530 
    531 We have a proof that for each length, in the optimal sequence the following condition is satisfied: if the element $i$ is selected, then all elements $j \gt i$ and $p_j \lt p_i$ are also selected.
    532 
    533 **Hint 2**
    534 
    535 Let $d_i$ is a number by which the number of inversions will decrease after moving only the element with index $i$ to the beginning. Then, if sequence $seq$ is selected, then the number of inversions in a new permutation will be equal to $invs - \sum_{i \in seq} d_i + seqInvs - (\frac{|seq| \cdot (|seq| - 1)}{2} - seqInvs) = invs - \sum_{i \in seq} d_i + 2 \cdot seqInvs - \frac{|seq| \cdot (|seq| - 1)}{2}$. Here $invs$ — the number of inversions in the initial permutation, and $seqInvs$ — the number of inversions over all elements in the $seq$.
    536 
    537 **Hint 3**
    538 
    539 Assume that the number of inversions equals to $invs - \sum_{i \in seq} c_i - \frac{|seq| \cdot (|seq| - 1)}{2}$. What is $c_i$?
    540 
    541 **Hint 4**
    542 
    543 If $i \gt j$ and $p_i \gt p_j$ then $c_i \lt c_j$. So for the length $len$ it's optimal to choose $len$ maxmum elements by the value of $c_i$.
    544 
    545 **Tutorial**
    546 
    547 Tutorial is loading...
    548 
    549 **Solution**
    550 
    551 ```
    552 #include <bits/stdc++.h>
    553 using namespace std;
    554  
    555 struct binary_index_tree {
    556     int n;
    557     vector<int> bit;
    558  
    559     binary_index_tree(int n) : n(n), bit(n + 1) {}
    560  
    561     void increase(int pos) {
    562         for (pos++; pos <= n; pos += pos & -pos)
    563             bit[pos]++;
    564     }
    565  
    566     int query(int pref) const {
    567         int sum = 0;
    568         for (; pref; pref -= pref & -pref)
    569             sum += bit[pref];
    570  
    571         return sum;
    572     }
    573 };
    574  
    575 void solve() {
    576     int n;
    577     cin >> n;
    578  
    579     vector<int> d(n);
    580     binary_index_tree bit(n);
    581     long long inversions = 0;
    582  
    583     for (int i = 0; i < n; i++) {
    584         int p;
    585         cin >> p;
    586         p--;
    587  
    588         d[i] = i - 2 * p;
    589         inversions += i - bit.query(p);
    590         bit.increase(p);
    591     }
    592     sort(d.rbegin(), d.rend());
    593  
    594     cout << inversions;
    595     long long sum = 0;
    596     for (int i = 0; i < n; i++) {
    597         sum += d[i];
    598         cout << ' ' << inversions - sum - 1ll * i * (i + 1) / 2;
    599     }
    600  
    601     cout << '\n';
    602 }
    603  
    604 int main() {
    605     ios::sync_with_stdio(false), cin.tie(nullptr);
    606  
    607     int tests;
    608     cin >> tests;
    609     while (tests--)
    610         solve();
    611 }
    612 ```