codeforces-scrape

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

1856.md (10510B)


      1 Source: https://codeforces.com/blog/entry/119058
      2 
      3 Hope you liked the problems!
      4 
      5 [1856A - Сказка о сортировке](/contest/1856/problem/A "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
      6 
      7 **Hints**
      8 
      9 **Hint 1**
     10 
     11 How many operations are needed to make $a_i \le a_{i + 1}$ if initially, $a_i \gt a_{i + 1}$?
     12 
     13 **Tutorial**
     14 
     15 Tutorial is loading...
     16 
     17 **Solution**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 
     22 #define all(x) (x).begin(), (x).end()
     23 #define allr(x) (x).rbegin(), (x).rend()
     24 #define gsize(x) (int)((x).size())
     25 
     26 const char nl = '\n';
     27 typedef long long ll;
     28 typedef long double ld;
     29 
     30 using namespace std;
     31 
     32 void solve() {
     33     int n;
     34     cin >> n;
     35     
     36     vector<int> a(n);
     37     for (int i = 0; i < n; i++) cin >> a[i];
     38     
     39     int ans = 0;
     40     for (int i = 0; i < n - 1; i++) {
     41         if (a[i] > a[i + 1]) {
     42             ans = max(ans, a[i]);
     43         }
     44     }
     45     
     46     cout << ans << nl;
     47 }
     48 
     49 int main() {
     50 	ios::sync_with_stdio(0); cin.tie(0);
     51     
     52     int T;
     53     cin >> T;
     54     while (T--) {
     55         solve();
     56     }
     57 }
     58 ```
     59 
     60 **Feedback**
     61 
     62 * Good problem
     63 * Average problem
     64 * Bad problem
     65 
     66 [1856B - Хорошие массивы](/contest/1856/problem/B "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
     67 
     68 **Hints**
     69 
     70 **Hint 1**
     71 
     72 Consider the case $n = 1$ separately.
     73 
     74 **Hint 2**
     75 
     76 Count the number of elements equal to $1$.
     77 
     78 **Hint 3**
     79 
     80 Find the sum of the array.
     81 
     82 **Hint 4**
     83 
     84 When there are a lot of elements equal to $1$ and the sum is not very big, the answer is no.
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 
     95 #define all(x) (x).begin(), (x).end()
     96 #define allr(x) (x).rbegin(), (x).rend()
     97 #define gsize(x) (int)((x).size())
     98 
     99 const char nl = '\n';
    100 typedef long long ll;
    101 typedef long double ld;
    102 
    103 using namespace std;
    104 
    105 void solve() {
    106     int n;
    107     cin >> n;
    108     
    109     vector<int> a(n);
    110     for (int i = 0; i < n; i++) cin >> a[i];
    111     
    112     ll sum_a = 0, cnt_1 = 0;
    113     for (int x: a) {
    114         sum_a += x;
    115         if (x == 1) cnt_1++;
    116     }
    117     
    118     if (sum_a >= cnt_1 + n && n > 1) {
    119         cout << "YES" << nl;
    120     } else {
    121         cout << "NO" << nl;
    122     }
    123 }
    124 
    125 int main() {
    126 	ios::sync_with_stdio(0); cin.tie(0);
    127     
    128     int T;
    129     cin >> T;
    130     while (T--) {
    131         solve();
    132     }
    133 }
    134 ```
    135 
    136 **Feedback**
    137 
    138 * Good problem
    139 * Average problem
    140 * Bad problem
    141 
    142 [1856C - Стать максимумом](/contest/1856/problem/C "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
    143 
    144 **Hints**
    145 
    146 **Hint 1**
    147 
    148 Binary search on the answer.
    149 
    150 **Hint 1.1**
    151 
    152 Check if it is possible to have $\max(a_1,\ldots, a_n) \ge x$ for some $x$.
    153 
    154 **Hint 2**
    155 
    156 Fix some possible index that will be the position of the maximum in the final array.
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution**
    163 
    164 ```
    165 #include <bits/stdc++.h>
    166  
    167 #define all(x) (x).begin(), (x).end()
    168 #define allr(x) (x).rbegin(), (x).rend()
    169 #define gsize(x) (int)((x).size())
    170  
    171 const char nl = '\n';
    172 typedef long long ll;
    173 typedef long double ld;
    174  
    175 using namespace std;
    176  
    177 void solve() {
    178     ll n, k;
    179     cin >> n >> k;
    180     
    181     vector<ll> a(n);
    182     for (int i = 0; i < n; i++) cin >> a[i];
    183     
    184     ll lb = 0, ub = *max_element(all(a)) + k, ans = 0;
    185     while (lb <= ub) {
    186         ll tm = (lb + ub) / 2;
    187         bool good = false;
    188         
    189         for (int i = 0; i < n; i++) {
    190             vector<ll> min_needed(n);
    191             min_needed[i] = tm;
    192             
    193             ll c_used = 0;
    194             for (int j = i; j < n; j++) {
    195                 if (min_needed[j] <= a[j]) break;
    196                 
    197                 if (j + 1 >= n) {
    198                     c_used = k + 1;
    199                     break;
    200                 }
    201                 
    202                 c_used += min_needed[j] - a[j];
    203                 min_needed[j + 1] = max(0LL, min_needed[j] - 1);
    204             }
    205             
    206             if (c_used <= k) good = true;
    207         }
    208         
    209         if (good) {
    210             ans = tm;
    211             lb = tm + 1;
    212         } else {
    213             ub = tm - 1;
    214         }
    215     }
    216     
    217     cout << ans << nl;
    218 }
    219  
    220 int main() {
    221 	ios::sync_with_stdio(0); cin.tie(0);
    222 	
    223 	int T;
    224 	cin >> T;
    225 	while (T--) solve();
    226 }
    227 ```
    228 
    229 **Feedback**
    230 
    231 * Good problem
    232 * Average problem
    233 * Bad problem
    234 
    235 [1856D - Более неправильно](/contest/1856/problem/D "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
    236 
    237 **Hints**
    238 
    239 **Hint 1**
    240 
    241 What can you say about index $j$ if the number of inversion in $[p_i, p_{i + 1}, \ldots, p_{j - 1}]$ is the same as in $[p_i, p_{i + 1}, \ldots, p_j]$?
    242 
    243 **Hint 2**
    244 
    245 Define a function to calculate $f(l, r)=$ the position of the maximum in $[p_l, p_{l + 1}, \ldots, p_{r}]$.
    246 
    247 **Hint 3**
    248 
    249 Divide and conquer.
    250 
    251 **Tutorial**
    252 
    253 Tutorial is loading...
    254 
    255 **Solution**
    256 
    257 ```
    258 #include <bits/stdc++.h>
    259 
    260 #define all(x) (x).begin(), (x).end()
    261 #define allr(x) (x).rbegin(), (x).rend()
    262 #define gsize(x) (int)((x).size())
    263 
    264 const char nl = '\n';
    265 typedef long long ll;
    266 typedef long double ld;
    267 
    268 using namespace std;
    269 
    270 int query(int l, int r) {
    271     if (l == r) return 0;
    272     cout << "? " << l << ' ' << r << endl;
    273     
    274     int res;
    275     cin >> res;
    276     return res;
    277 }
    278 
    279 // Finds max on p[l; r]
    280 int solve(int l, int r) {
    281     if (l == r) return l;
    282     
    283     int m = (l + r) / 2;
    284     int a = solve(l, m);
    285     int b = solve(m + 1, r);
    286     
    287     int r1, r2;
    288     r1 = query(a, b - 1);
    289     r2 = query(a, b);
    290     
    291     if (r1 == r2) {
    292         return b;
    293     } else {
    294         return a;
    295     }
    296 }
    297 
    298 void solve() {
    299     int n;
    300     cin >> n;
    301     
    302     int ans = solve(1, n);
    303     cout << "! " << ans << endl;
    304 }
    305 
    306 int main() {
    307 	ios::sync_with_stdio(0); cin.tie(0);
    308     
    309     int T;
    310     cin >> T;
    311     while (T--) {
    312         solve();
    313     }
    314 }
    315 ```
    316 
    317 **Feedback**
    318 
    319 * Good problem
    320 * Average problem
    321 * Bad problem
    322 
    323 [1856E1 - ПерестановДерево (простая версия)](/contest/1856/problem/E1 "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
    324 
    325 **Hints**
    326 
    327 **Hint 1**
    328 
    329 Fix the value of $\operatorname{lca}(u, v)$.
    330 
    331 **Hint 2**
    332 
    333 You can solve the problem independently for each value of $\operatorname{lca}(u, v)$.
    334 
    335 **Hint 3**
    336 
    337 Do dynamic programming.
    338 
    339 **Hint 4**
    340 
    341 For each subtree of $\operatorname{lca}(u, v)$, we only care about how many vertices are $ \gt $ or $ \lt $ less than $a_{\operatorname{lca}(u, v)}$.
    342 
    343 **Hint 5**
    344 
    345 This dynamic programming solution can actually be made to work in $\mathcal{O}(n^2)$.
    346 
    347 **Tutorial**
    348 
    349 Tutorial is loading...
    350 
    351 **Solution**
    352 
    353 ```
    354 #include <bits/stdc++.h>
    355 
    356 #define all(x) (x).begin(), (x).end()
    357 #define allr(x) (x).rbegin(), (x).rend()
    358 #define gsize(x) (int)((x).size())
    359 
    360 const char nl = '\n';
    361 typedef long long ll;
    362 typedef long double ld;
    363 
    364 using namespace std;
    365 
    366 const int maxn = 1000000;
    367 
    368 vector<int> g[maxn];
    369 int s[maxn];
    370 ll ans = 0;
    371 
    372 void dfs(int v, int p = -1) {
    373     vector<ll> a;
    374     s[v] = 1;
    375     
    376     for (int u: g[v]) {
    377         if (u == p) continue;
    378         dfs(u, v);
    379         s[v] += s[u];
    380         
    381         a.push_back(s[u]);
    382     }
    383     
    384     vector<ll> dp(s[v]);
    385     ll cs = 0;
    386     for (int x: a) {
    387         for (ll i = cs + x; i >= 0; i--) {
    388             for (ll pr = min(cs, i); pr >= max(0LL, i - x); pr--) {
    389                 ll j = i - pr;
    390                 dp[i] = max(dp[i], dp[pr] + j * (cs - pr) + pr * (x - j));
    391             }
    392         } 
    393         cs += x;
    394     }
    395     
    396     ans += *max_element(all(dp));
    397     dp.clear();
    398     a.clear();
    399 }
    400 
    401 int main() {
    402 	ios::sync_with_stdio(0); cin.tie(0);
    403     
    404     int n;
    405     cin >> n;
    406     for (int i = 1; i < n; i++) {
    407         int x;
    408         cin >> x;
    409         g[x - 1].push_back(i);
    410     }
    411     
    412     dfs(0);
    413     
    414     cout << ans << nl;
    415 }
    416 ```
    417 
    418 **Feedback**
    419 
    420 * Good problem
    421 * Average problem
    422 * Bad problem
    423 
    424 [1856E2 - ПерестановДерево (сложная версия)](/contest/1856/problem/E2 "Codeforces Round 890 (Div. 2) при поддержке Constructor Institute")
    425 
    426 **Hints**
    427 
    428 **Hint 0**
    429 
    430 Read hints for the easy version.
    431 
    432 **Hint 1**
    433 
    434 For each $\operatorname{lca}(u, v)$, we actually need to do subset sum on the subtree sizes.
    435 
    436 **Hint 2**
    437 
    438 If there is a very subtree that is bigger than the sum of the sizes of the other subtrees, you don't have to do subset sum.
    439 
    440 **Hint 3**
    441 
    442 Optimize subset sum to $\mathcal{O}(s \sqrt s)$, where s is the sum of the sizes of the subtrees for some fixed $\operatorname{lca}(u, v)$.
    443 
    444 **Hint 4**
    445 
    446 Use bitset to optimize subset sum even more.
    447 
    448 **Tutorial**
    449 
    450 Tutorial is loading...
    451 
    452 **Solution**
    453 
    454 ```
    455 #include <bits/stdc++.h>
    456 
    457 #define all(x) (x).begin(), (x).end()
    458 #define allr(x) (x).rbegin(), (x).rend()
    459 #define gsize(x) (int)((x).size())
    460 
    461 const char nl = '\n';
    462 typedef long long ll;
    463 typedef long double ld;
    464 
    465 using namespace std;
    466 
    467 const int maxn = 1000000;
    468 
    469 vector<int> g[maxn];
    470 int s[maxn];
    471 ll ans = 0;
    472 vector<ll> b;
    473 ll closest;
    474 
    475 template <int len = 1>
    476 void subset_sum(int n) {
    477     if (n >= len) {
    478         subset_sum<std::min(len*2, maxn)>(n);
    479         return;
    480     }
    481     
    482     bitset<len> dp;
    483     
    484     dp[0] = 1;
    485     for (ll x: b) {
    486         dp = dp | (dp << x);
    487     }
    488     
    489     ll cv = n;
    490     closest = 0;
    491     for (int i = 0; i <= n; i++) {
    492         if (dp[i] && abs(i - (n - i)) < cv) {
    493             closest = i;
    494             cv = abs(i - (n - i));
    495         }
    496     }
    497 }
    498 
    499 ll solve(vector<ll> &a) {
    500     if (a.empty()) return 0;
    501     
    502     sort(allr(a));
    503     ll cs = 0;
    504     for (ll x: a) cs += x;
    505     
    506     if (a[0] * 2 >= cs) {
    507         return a[0];
    508     }
    509     
    510     int n = gsize(a);
    511     a.push_back(0);
    512     
    513     b.clear();
    514     int pi = 0;
    515     for (int i = 1; i <= n; i++) {
    516         if (a[i] != a[i - 1]) {
    517             ll cnt = i - pi;
    518             ll x = a[i - 1];
    519             
    520             ll j = 1;
    521             while (j < cnt) {
    522                 b.push_back(x * j);
    523                 cnt -= j;
    524                 j *= 2;
    525             }            
    526             b.push_back(x * cnt);
    527 
    528             pi = i;
    529         }
    530     }
    531     
    532     subset_sum(cs);
    533     return closest;
    534 }
    535 
    536 void dfs(int v, int p = -1) {
    537     vector<ll> a;
    538     s[v] = 1;
    539     
    540     for (int u: g[v]) {
    541         if (u == p) continue;
    542         dfs(u, v);
    543         s[v] += s[u];
    544         
    545         a.push_back(s[u]);
    546     }
    547     
    548     ll x = solve(a);
    549     ans += x * (s[v] - 1 - x);
    550     a.clear();
    551 }
    552 
    553 int main() {
    554 	ios::sync_with_stdio(0); cin.tie(0);
    555     
    556     int n;
    557     cin >> n;
    558     for (int i = 1; i < n; i++) {
    559         int x;
    560         cin >> x;
    561         g[x - 1].push_back(i);
    562     }
    563     
    564     dfs(0);
    565     
    566     cout << ans << nl;
    567 }
    568 ```
    569 
    570 **Feedback**
    571 
    572 * Good problem
    573 * Average problem
    574 * Bad problem
    575 
    576 **UPD: Tutorial for E1 has been added.**
    577 
    578 **UPD2: Tutorial for E2 has been added.**