codeforces-scrape

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

2167.md (10852B)


      1 Source: https://codeforces.com/blog/entry/147869
      2 
      3 #### Thanks everybody for participating in the round!
      4 
      5 You are free to leave feedback in the comments as well!
      6 
      7 **What is your feedback about the contest?**
      8 
      9 * Excellent:
     10 * Great:
     11 * Good:
     12 * Average:
     13 * Bad:
     14 * Trash:
     15 * Worst:
     16 
     17 **Which problem did you like the most?**
     18 
     19 * A:
     20 * B:
     21 * C:
     22 * D:
     23 * E:
     24 * F:
     25 * G:
     26 
     27 **Which problem did you find least enjoyable?**
     28 
     29 * A:
     30 * B:
     31 * C:
     32 * D:
     33 * E:
     34 * F:
     35 * G:
     36 
     37 ### [A. Square?](/contest/2167/problem/A)
     38 
     39 Author: [JahonaliX](/profile/JahonaliX "Master JahonaliX") Preparation: [khba](/profile/khba "Expert khba")
     40 
     41 **Solution**
     42 
     43 Tutorial is loading...
     44 
     45 **Code (Python)**
     46 
     47 ```
     48 # author: khba
     49 for _ in range(int(input())):
     50     a, b, c, d = map(int, input().split())
     51     print('YES' if a == b == c == d else 'NO')
     52 ```
     53 
     54 ### [B. Your name](/contest/2167/problem/B)
     55 
     56 Author: [khba](/profile/khba "Expert khba") Preparation: [khba](/profile/khba "Expert khba")
     57 
     58 **Solution**
     59 
     60 Tutorial is loading...
     61 
     62 **Code (C++)**
     63 
     64 ```
     65 // author: khba
     66 #include <iostream>
     67 using namespace std;
     68 
     69 int cnt1[26], cnt2[26];
     70 int main()
     71 {
     72     int t;
     73     cin >> t;
     74     while (t--)
     75     {
     76         for (int i = 0; i < 26; ++i) cnt1[i] = cnt2[i] = 0;
     77         int n;
     78         cin >> n;
     79         string s, t;
     80         cin >> s >> t;
     81         for (char &c : s) cnt1[c - 'a'] ++;
     82         for (char &c : t) cnt2[c - 'a'] ++;
     83         bool answer = true;
     84         for (int i = 0; i < 26; ++i)
     85             if (cnt1[i] != cnt2[i]) 
     86                 answer = false;
     87         puts(answer ? "YES" : "NO");
     88     }
     89 }
     90 ```
     91 
     92 ### [C. Isamatdin and His Magic Wand!](/contest/2167/problem/C)
     93 
     94 Author: [Isamatdin](/profile/Isamatdin "Expert Isamatdin") Preparation: [Isamatdin](/profile/Isamatdin "Expert Isamatdin")
     95 
     96 **Solution**
     97 
     98 Tutorial is loading...
     99 
    100 **Code (C++)**
    101 
    102 ```
    103 // author: khba
    104 #include <iostream>
    105 using namespace std;
    106 
    107 int main()
    108 {
    109     int t; 
    110     cin >> t;
    111     while (t--) {
    112         
    113         int n;
    114         cin >> n;
    115         bool odd = false, even = false;
    116         int a[n];
    117         for (int i = 0, x; i < n; ++i) {
    118             cin >> a[i];
    119             if (a[i] % 2 == 0) even = true;
    120             else odd = true;
    121         }
    122         if (odd and even) sort(a, a + n);
    123         for (int i = 0; i < n; ++i) cout << a[i] << " \n"[i == n - 1]; 
    124     }
    125 }
    126 ```
    127 
    128 ### [D. Yet Another Array Problem](/contest/2167/problem/D)
    129 
    130 Author: [Nasa](/profile/Nasa "Specialist Nasa") Preparation: [Muhammadali__](/profile/Muhammadali__ "Expert Muhammadali__") & [Nasa](/profile/Nasa "Specialist Nasa")
    131 
    132 **Hint 1**
    133 
    134 Answer is always prime number, try to prove why.
    135 
    136 **Hint 2**
    137 
    138 Notice how equation works if $x$ does not satisfy property.
    139 
    140 **Hint 3**
    141 
    142 It means that for each $i$, $a_{i} \equiv 0 \ (mod \ x)$
    143 
    144 **Solution**
    145 
    146 Tutorial is loading...
    147 
    148 **Code (C++)**
    149 
    150 ```
    151 // Author: BehruzbekX
    152 #include <bits/stdc++.h>
    153 using namespace std;
    154 int main() {
    155     ios::sync_with_stdio(false);
    156     cin.tie(0);
    157     using ll = long long;
    158     int t;
    159     cin >> t;
    160     while (t--) {
    161         int n;
    162         cin >> n;
    163         vector<ll> a(n);
    164         for (auto &i: a) cin >> i;
    165         for (ll x : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}) {
    166             int ok = 0;
    167             for (ll i : a) {
    168                 if (i % x) {
    169                     ok = 1;
    170                     break;
    171                 }
    172             }
    173             if (ok) {
    174                 cout << x << '\n';
    175                 break;
    176             }
    177         }
    178     }
    179 }
    180 ```
    181 
    182 ### [E. khba Loves to Sleep!](/contest/2167/problem/E)
    183 
    184 Author: [Isamatdin](/profile/Isamatdin "Expert Isamatdin") Preparation: [Isamatdin](/profile/Isamatdin "Expert Isamatdin")
    185 
    186 **Solution**
    187 
    188 Tutorial is loading...
    189 
    190 **Code (C++)**
    191 
    192 ```
    193 #include <bits/stdc++.h>
    194 
    195 using namespace std;
    196 
    197 int main() {
    198     ios::sync_with_stdio(false);
    199     cin.tie(nullptr);
    200     cout.tie(nullptr);
    201     int t;
    202     cin >> t;
    203     while (t--) {
    204         int n, k, x;
    205         cin >> n >> k >> x;
    206         vector<int> a(n);
    207         for (int &i : a) cin >> i;
    208         a.push_back(-1e9);
    209         a.push_back(1e9);
    210         n += 2;
    211         sort(a.begin(), a.end());
    212         int l = 0, r = x + 1;
    213         while (l + 1 < r) {
    214             int m = (l + r) >> 1, f = 0;
    215             a[0] = - m, a[n - 1] = x + m;
    216             for (int i = 1; i < n; ++i) f += max(0, (a[i] - m) - (a[i - 1] + m) + 1);
    217             if (f >= k) l = m;
    218             else r = m;
    219         }
    220         a[0] = - l, a[n - 1] = x + l;
    221         int j = 0;
    222         for (int i = 1; i < n; i++)
    223     		for (j = max(j, a[i - 1] + l); j <= min((a[i] - l), x) && k; j++)
    224     			cout << j << ' ', k--;
    225     	cout << '\n';
    226     }
    227     return 0;
    228 }
    229 ```
    230 
    231 ### [F. Tree, TREE!!!](/contest/2167/problem/F)
    232 
    233 Author: [Nasa](/profile/Nasa "Specialist Nasa") Preparation: [Nasa](/profile/Nasa "Specialist Nasa")
    234 
    235 **Hint 1**
    236 
    237 We don't need to know *lowest common ancestor (LCA)* to solve this problem. Think of subtree sizes to replace *LCA*.
    238 
    239 **Hint 2**
    240 
    241 Let $sz_{i} = $ subtree size of $i$ when root is $r$. In order for $i$ to be able to be in the $S_{r}$: $sz_{i} \geq k$ must hold.
    242 
    243 **Hint 3**
    244 
    245 Notice how instead of calculating the answer for each root, we can calculate contribution of $i$ when root is $1 \ldots n$.
    246 
    247 **Solution**
    248 
    249 Tutorial is loading...
    250 
    251 **Code (C++)**
    252 
    253 ```
    254 // Author: BehruzbekX
    255 #include <bits/stdc++.h>
    256 using namespace std;
    257 int main() {
    258     ios::sync_with_stdio(false);
    259     cin.tie(0);
    260     using ll = long long;
    261     int t;
    262     cin >> t;
    263     while (t--) {
    264         int n, k;
    265         cin >> n >> k;
    266         vector<vector<int>> a(n);
    267         for (int i = 1; i < n; i++) {
    268             int u, v;
    269             cin >> u >> v, --u, --v;
    270             a[u].emplace_back(v);
    271             a[v].emplace_back(u);
    272         }
    273         ll ans = 0; 
    274         vector<int> sz(n, 1); // initial subtree sizes
    275         auto dfs = [&] (auto &dfs, int v, int p) -> void{ // performing DFS in the tree
    276             for (int u : a[v]) {
    277                 if (u != p) { // to avoid visiting parent again
    278                     dfs(dfs, u, v); // recursively visit subtree
    279                     sz[v] += sz[u]; // merge
    280                 }
    281             }
    282         };
    283         /*
    284             |S_1| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 1)
    285             |S_2| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 2)
    286             |S_3| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is 3)
    287             ...                                                    (root is i)
    288             |S_n| = (sz[1] >= k) + (sz[2] >= k) + ... (sz[n] >= k) (root is n)
    289             We should add them for each node (calculating contribution):
    290         */
    291         dfs(dfs, 0, -1); // Arbitrary starting point
    292         for (int i = 0; i < n; i++) {
    293             if (n - sz[i] >= k) ans += sz[i]; 
    294             if (sz[i] >= k) ans += n - sz[i]; 
    295         }
    296         cout << ans + n << '\n';  
    297     }
    298 }
    299 ```
    300 
    301 **Bonus**
    302 
    303 Find the answer for each $i$ ($|S_{1}|, |S_{2}|, |S_{3}|, \ldots , |S_{n}|$).
    304 
    305 **Hint for bonus 1**
    306 
    307 Let us have the answer for $dp_{v} = $ answer when root is $v$, let $u$ be the directly connected node to $v$. How $dp_{v}$ changes when we make root $u$ ($dp_{u}$)?
    308 
    309 **Solution for bonus**
    310 
    311 First, we calculate the answer for each $i$ (the subtree of $i$) and subtree sizes, where the starting point is arbitrary.
    312 
    313 Let's go back to our hint. Suppose we already have the answer for $dp_{v}$.  
    314 To get the answer for $dp_{u}$, we need to understand how the answer changes based on the subtree of $u$ and the part outside it.
    315 
    316 This technique is known as *Rerooting*. When we transition from $v$ to $u$, we divide the total contribution into two parts:  
    317 1. inside the subtree of $u$, and  
    318 2. outside the subtree of $u$.
    319 
    320 If $n - sz_{u} \lt k$, then we should subtract that contribution from $dp_{v}$ — this corresponds to the part outside the subtree of $u$, because when $u$ becomes root, $v$ have no longer subtree of $u$ as a subtree, which implies that we need to remove contribution of it. As for the subtree of $u$: if $sz_{u} \lt k$, then the answer increases by one because $n \ge k$.
    321 
    322 Finally, the transition becomes:
    323 
    324 $ dp_{u} = dp_{v} - (n - sz_{u} \lt k) + (sz_{u} \lt k) $
    325 
    326 **Code (C++) for bonus**
    327 
    328 ```
    329 // Author: BehruzbekX
    330 #include <bits/stdc++.h>
    331 using namespace std;
    332 int main() {
    333     ios::sync_with_stdio(false);
    334     cin.tie(0);
    335     using ll = long long;
    336     int t;
    337     cin >> t;
    338     while (t--) {
    339         int n, k;
    340         cin >> n >> k;
    341         vector<vector<int>> a(n);
    342         for (int i = 1; i < n; i++) {
    343             int u, v;
    344             cin >> u >> v, --u, --v;
    345             a[u].emplace_back(v);
    346             a[v].emplace_back(u);
    347         }
    348         ll ans = 0; 
    349         vector<int> sz(n, 1), dp(n); // initial subtree sizes and dp[i] = |S_i|
    350         auto dfs = [&] (auto &dfs, int v, int p) -> void{ // performing DFS in the tree
    351             for (int u : a[v]) {
    352                 if (u != p) { // to avoid visiting parent again
    353                     dfs(dfs, u, v); // recursively visit subtree
    354                     dp[v] += dp[u]; // answer for subtree of v (merge)
    355                     sz[v] += sz[u]; // merge
    356                 }
    357             }
    358             dp[v] += sz[v] >= k;
    359         };
    360         dfs(dfs, 0, -1); // arbitrary starting point
    361         auto reroot = [&] (auto &reroot, int v, int p) -> void{
    362             for (int u : a[v]) {
    363                 if (u != p) {
    364                     int add = dp[v] - dp[u] - (n - sz[u] < k); // value of v other than subtree of u
    365                     dp[u] = add + (dp[u] + (sz[u] < k));  
    366                     reroot(reroot, u, v); //continue rerooting
    367                     // Actually you don't need dp[v] for each subtree (because dp[u] cancels out), I did it for clarity. 
    368                 }
    369             }
    370         };
    371         reroot(reroot, 0, -1);
    372         cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n'; // print the answer
    373     }
    374 }
    375 ```
    376 
    377 ### [G. Mukhammadali and the Smooth Array](/contest/2167/problem/G)
    378 
    379 Author: [Muhammadali__](/profile/Muhammadali__ "Expert Muhammadali__") Preparation: [Muhammadali__](/profile/Muhammadali__ "Expert Muhammadali__")
    380 
    381 **Hint 1**
    382 
    383 Think of longest non-decreasing sequence
    384 
    385 **Hint 2**
    386 
    387 In finding simple LNDS, all elements have the same "weights". But here we are given weights.
    388 
    389 **Solution**
    390 
    391 Tutorial is loading...
    392 
    393 **Code (C++)**
    394 
    395 ```
    396 // author: khba
    397 
    398 #include "bits/stdc++.h"
    399 using namespace std;
    400 
    401 int main()
    402 {
    403     int t;
    404     cin >> t;
    405     while (t--) {
    406         int n;
    407         cin >> n;
    408         int64_t a[n], c[n], dp[n];
    409         for (int64_t &i : a) cin >> i;
    410         for (int64_t &i : c) cin >> i;
    411         for (int i = 0; i < n; ++i) dp[i] = c[i];
    412         for (int i = 0; i < n; ++i)
    413             for (int j = 0; j < i; ++j)
    414                 if (a[j] <= a[i]) dp[i] = max(dp[i], dp[j] + c[i]);
    415         cout << accumulate(c, c + n, 0LL) - *max_element(dp, dp + n) << '\n';
    416     }
    417 }
    418 ```
    419 
    420 **Bonus**
    421 
    422 Solve for $n \le 2 * 10^5$