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