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$