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.**