1905.md (18420B)
1 Source: https://codeforces.com/blog/entry/123384 2 3 # [A — Constructive Problems](https://codeforces.com/contest/1905/problem/A) 4 5 Author: [cadmiumky](/profile/cadmiumky "Grandmaster cadmiumky") 6 7 **Solution** 8 9 We can observe an invariant given by the problem is that every time we apply adjacent aid on any state of the matrix, the sets of rows that have at least one rebuilt city, respectively the sets of columns that appear that have at least one rebuilt city remain constant. Therefore, if we want to have a full matrix as consequence of applying adjacent aid multiple times, both of these sets must contain all rows/columns. As such, the answer is bounded by $max(n, m)$. 10 11 We can tighten this bound by finding an example which always satisfies the statement. If we take, without loss of generality, $n \le m$, the following initial setting will satisfy the statement: $(1, 1), (2, 2), (3, 3), ..., (n, n), (n, n + 1), (n, n + 2), .. (n, m)$ 12 13 **Author's Note** 14 15 I have proposed this div2A at 3 contests and after 1 year of waiting I finally was able to propose it (mainly because theoretically, this was supposed to be my round :)). 16 17 As the title suggests, this problem is inspired by one day trying to solve some constructive problem that required to draw some weird grid with some properties. And, as I was drawing multiple grids to try out multiple strategies, I was wondering how to draw these grids more optimally, as actually having to count for every matrix the height/width was pretty annoying, and I could just eyeball it by drawing it next to another drawn (but filled out) grid. As such, I needed an already drawn grid "below" the current one and another "to the left". 18 19 **Code (valeriu)** 20 21 ``` 22 #include <bits/stdc++.h> 23 #define all(x) (x).begin(),(x).end() 24 using namespace std; 25 26 using ll = long long; 27 using ld = long double; 28 29 //#define int ll 30 #define sz(x) ((int)(x).size()) 31 32 using pii = pair<int,int>; 33 using tii = tuple<int,int,int>; 34 35 const int nmax = 1e6 + 5; 36 const int inf = 1e9 + 5; 37 int n, k, m, q; 38 vector<int> g[nmax]; 39 int v[nmax]; 40 41 static void testcase() { 42 cin >> n >> m; 43 cout << max(n, m) << '\n'; 44 return; 45 } 46 47 signed main() { 48 ios::sync_with_stdio(0); 49 cin.tie(0); 50 int t; 51 cin >> t; 52 for (int i = 0; i < t; i++) 53 testcase(); 54 } 55 56 /** 57 Anul asta se da centroid. 58 -- Surse oficiale 59 */ 60 ``` 61 62 **Rate Problem** 63 64 Good problem 65 66 Ok problem 67 68 Bad problem 69 70 Didn't solve it, idk 71 72 # [B — Beginner's Zelda](https://codeforces.com/contest/1905/problem/B) 73 74 Author: [cadmiumky](/profile/cadmiumky "Grandmaster cadmiumky") 75 76 **Solution** 77 78 We can prove by induction that on any tree with $K$ leaves, the answer is $[{\frac{K + 1}{2}}]$, where with $[x]$ we denote the greatest integer smaller than $x$. This can be proven by induction, we will give an overview of what a proof would look like: 79 80 * For two leaves, the answer is clearly $1$. 81 * For three leaves, the answer is clearly $2$. 82 * For more than four leaves, it is always the case that we can find two leaves for which the node that will be created as a result of applying an operation on these two will have degree greater than $1$ (i.e. it will not be a leaf) 83 84 The third argument holds because in a tree with four leaves, we have either at least two nodes with degree at least $3$ (and as such we can choose two leaves which contain these two nodes on their chain), or a node with degree at least $4$. Furthermore, it reduces the number of leaves in the tree by $2$. 85 86 **Code (valeriu)** 87 88 ``` 89 #include <cmath> 90 #include <functional> 91 #include <fstream> 92 #include <iostream> 93 #include <vector> 94 #include <algorithm> 95 #include <string> 96 #include <set> 97 #include <map> 98 #include <list> 99 #include <time.h> 100 #include <math.h> 101 #include <random> 102 #include <deque> 103 #include <queue> 104 #include <unordered_map> 105 #include <unordered_set> 106 #include <iomanip> 107 #include <cassert> 108 #include <bitset> 109 #include <sstream> 110 #include <cstring> 111 #include <numeric> 112 #define all(x) (x).begin(),(x).end() 113 using namespace std; 114 115 using ll = long long; 116 using ld = long double; 117 118 //#define int ll 119 #define sz(x) ((int)(x).size()) 120 121 using pii = pair<int,int>; 122 using tii = tuple<int,int,int>; 123 124 const int nmax = 1e6 + 5; 125 const int inf = 1e9 + 5; 126 int n, k, m, q; 127 int freq[nmax]; 128 129 static void testcase() { 130 cin >> n; 131 for (int i = 1, a, b; i < n; i++) { 132 cin >> a >> b; 133 freq[a]++; 134 freq[b]++; 135 } 136 int cnt = 0; 137 for(int i = 1; i <= n; i++) 138 cnt += (freq[i] == 1), 139 freq[i] = 0; 140 cout << (cnt + 1) / 2 << '\n'; 141 return; 142 } 143 144 signed main() { 145 ios::sync_with_stdio(0); 146 cin.tie(0); 147 int t; 148 cin >> t; 149 for (int i = 0; i < t; i++) 150 testcase(); 151 } 152 153 /** 154 Anul asta se da centroid. 155 -- Surse oficiale 156 */ 157 ``` 158 159 **Rate Problem** 160 161 Good problem 162 163 Ok problem 164 165 Bad problem 166 167 Didn't solve it, idk 168 169 # [C — Largest Subsequence](https://codeforces.com/contest/1905/problem/C) 170 171 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 172 173 **Solution** 174 175 We can notice that this operation will ultimately reverse the lexicographically largest subset of the initial string. 176 177 Thus, we can easily check if the string is sortable, and for finding the number of operations we will subtract the length of the largest prefix of equal values of the subset from its length. 178 179 This solution works in $O(n)$ time. 180 181 **Code (tibinyte)** 182 183 ``` 184 #include <bits/stdc++.h> 185 using namespace std; 186 int main() 187 { 188 cin.tie(nullptr)->sync_with_stdio(false); 189 int q; 190 cin >> q; 191 while (q--) 192 { 193 int n; 194 string s; 195 cin >> n >> s; 196 s = '$' + s; 197 vector<int> subset; 198 for (int i = 1; i <= n; ++i) 199 { 200 while (!subset.empty() && s[subset.back()] < s[i]) 201 { 202 subset.pop_back(); 203 } 204 subset.push_back(i); 205 } 206 int ans = 0; 207 int m = (int)subset.size() - 1; 208 while (ans <= m && s[subset[ans]] == s[subset[0]]) 209 { 210 ans++; 211 } 212 ans = m - ans + 1; 213 214 for (int i = 0; i <= m; ++i) 215 { 216 if (i < m - i) 217 { 218 swap(s[subset[i]], s[subset[m - i]]); 219 } 220 } 221 for (int i = 2; i <= n; ++i) 222 { 223 if (s[i] < s[i - 1]) 224 { 225 ans = -1; 226 break; 227 } 228 } 229 cout << ans << '\n'; 230 } 231 } 232 ``` 233 234 **Rate Problem** 235 236 Good problem 237 238 Ok problem 239 240 Bad problem 241 242 Didn't solve it, idk 243 244 # [D — Cyclic MEX](https://codeforces.com/contest/1905/problem/D) 245 246 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 247 248 **Solution** 249 250 Let's analyze how the values of each prefix mex changes upon performing a cyclic shift to the left: 251 252 * The first prefix mex is popped. 253 * Each prefix mex with a value less than $p_1$ doesn't change. 254 * Each prefix mex with a value greater than $p_1$ becomes $p_1$. 255 * $n$ is appended to the back. 256 257 Let's keep our prefix mexes compressed ( meaning that we keep the value and its frequency instead of keeping multiple same values ). After that, we can simulate the above process naively with a deque, because the potential will decrease by the number of performed operations. 258 259 This solution works in $O(n)$ time. 260 261 **Code (tibinyte)** 262 263 ``` 264 #include <bits/stdc++.h> 265 266 #define int long long 267 268 using namespace std; 269 270 int32_t main() 271 { 272 cin.tie(nullptr)->sync_with_stdio(false); 273 int q; 274 cin >> q; 275 while (q--) 276 { 277 int n; 278 cin >> n; 279 vector<int> a(n + 1); 280 for (int i = 1; i <= n; ++i) 281 { 282 cin >> a[i]; 283 } 284 deque<pair<int, int>> dq; 285 vector<int> f(n + 1); 286 int mex = 0; 287 int sum = 0; 288 for (int i = 1; i <= n; ++i) 289 { 290 f[a[i]]++; 291 while (f[mex]) 292 { 293 mex++; 294 } 295 dq.push_back({mex, 1}); 296 sum += mex; 297 } 298 int ans = sum; 299 for (int i = 1; i < n; ++i) 300 { 301 pair<int, int> me = {a[i], 0}; 302 sum -= dq.front().first; 303 dq.front().second--; 304 if (dq.front().second == 0) 305 { 306 dq.pop_front(); 307 } 308 while (!dq.empty() && dq.back().first >= a[i]) 309 { 310 sum -= dq.back().first * dq.back().second; 311 me.second += dq.back().second; 312 dq.pop_back(); 313 } 314 dq.push_back(me); 315 sum = sum + me.first * me.second; 316 dq.push_back({n, 1}); 317 sum += n; 318 ans = max(ans, sum); 319 } 320 cout << ans << '\n'; 321 } 322 } 323 ``` 324 325 **Rate Problem** 326 327 Good problem 328 329 Ok problem 330 331 Bad problem 332 333 Didn't solve it, idk 334 335 # [E — One-X](https://codeforces.com/contest/1905/problem/E) 336 337 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 338 339 **Solution** 340 341 Let's try to solve a slightly easier problem first: changing the coefficient of the label to be the msb of the label. 342 343 We can note that at each depth, every label will have the same number of digits ( in base 2 ), thus the same msb. And we can notice that for each depth there are at most $2$ different interval lengths. Combining the former with the latter, we can solve this case in $O(log(N))$ time complexity, since the maximum depth is bounded by $log(N)$. 344 345 We can find an easy generalization to this: for the $k$-th most significant bit of each label to be $1$, we have to go right from a node whose depth is $k-1$. Thus the above solution can be extended to find the contribution of the $k$-th most significant bit of each label. 346 347 Doing this for all bits gives us a time complexity of $O(log^2(N))$ which is sufficient to pass the given constraints. 348 349 **Code (tibinyte)** 350 351 ``` 352 #include <bits/stdc++.h> 353 #define int long long 354 using namespace std; 355 const int mod = 998244353; 356 struct Mint 357 { 358 int val; 359 Mint(long long x = 0) 360 { 361 val = x % mod; 362 } 363 Mint operator+(Mint oth) 364 { 365 return val + oth.val; 366 } 367 Mint operator-(Mint oth) 368 { 369 return val - oth.val + mod; 370 } 371 Mint operator*(Mint oth) 372 { 373 return val * oth.val; 374 } 375 }; 376 Mint powmod(int a, int b) 377 { 378 if (b == 0) 379 { 380 return 1; 381 } 382 if (b % 2 == 1) 383 { 384 return powmod(a, b - 1) * a; 385 } 386 Mint P = powmod(a, b / 2); 387 return P * P; 388 } 389 map<int, vector<vector<tuple<int, int, int>>>> memo; 390 vector<vector<tuple<int, int, int>>> find_ranges(int lg) // log^2 391 { 392 if (memo.find(lg) != memo.end()) 393 { 394 return memo[lg]; 395 } 396 if (lg == 1) 397 { 398 return {{{1, 1, 1}}}; 399 } 400 vector<vector<tuple<int, int, int>>> l = find_ranges((lg + 1) / 2); 401 vector<vector<tuple<int, int, int>>> r = find_ranges(lg / 2); 402 vector<vector<tuple<int, int, int>>> ans(max(l.size(), r.size()) + 1); 403 Mint x = (powmod(2, (lg + 1) / 2) - 1) * (powmod(2, lg / 2) - 1); 404 ans[0].push_back({lg, 1, x.val}); 405 for (int i = 0; i < (int)l.size(); ++i) 406 { 407 for (auto j : l[i]) 408 { 409 ans[i + 1].push_back(j); 410 } 411 } 412 for (int i = 0; i < (int)r.size(); ++i) 413 { 414 for (auto j : r[i]) 415 { 416 bool ok = false; 417 for (auto &[size, cnt, ways] : ans[i + 1]) 418 { 419 if (size == get<0>(j)) 420 { 421 ok = true; 422 cnt += get<1>(j); 423 } 424 } 425 if (!ok) 426 { 427 ans[i + 1].push_back(j); 428 } 429 } 430 } 431 return memo[lg] = ans; 432 } 433 Mint count(int lg, int coef) 434 { 435 vector<vector<tuple<int, int, int>>> adam = find_ranges(lg); 436 Mint ans = 0; 437 Mint pow_2 = 1; 438 for (int i = 0; i < (int)adam.size(); ++i) 439 { 440 for (auto [size, cnt, ways] : adam[i]) 441 { 442 ans = ans + pow_2 * coef * cnt * ways; 443 } 444 pow_2 = pow_2 * 2; 445 } 446 return ans; 447 } 448 int32_t main() 449 { 450 cin.tie(nullptr)->sync_with_stdio(false); 451 int q; 452 cin >> q; 453 while (q--) 454 { 455 int n; 456 cin >> n; 457 vector<vector<tuple<int, int, int>>> adam = find_ranges(n); 458 Mint ans = count(n, 1); 459 for (int i = 1; i < (int)adam.size(); ++i) 460 { 461 for (auto [size, cnt, ways] : adam[i - 1]) 462 { 463 int lsize = (size + 1) / 2; 464 int rsize = size / 2; 465 if (rsize) 466 { 467 ans = ans + count(rsize, cnt); 468 } 469 } 470 } 471 cout << ans.val << '\n'; 472 memo.clear(); 473 } 474 } 475 ``` 476 477 **Rate Problem** 478 479 Good problem 480 481 Ok problem 482 483 Bad problem 484 485 Didn't solve it, idk 486 487 # [F — Field Should Not Be Empty](https://codeforces.com/contest/1905/problem/F) 488 489 Author: [tibinyte2006](/profile/tibinyte2006 "Newbie tibinyte2006") 490 491 **Solution** 492 493 The key observation to this problem is that most swaps are useless. In fact, we can find that only $2n$ swaps can increase our initial cost: 494 495 * The first type of meaningful swaps is $(i,p_i)$ 496 * For each $1 \lt i \lt n$, consider $k$ and $l$ such that $p_k = max(p_1,p_2,...,p_{i-1})$ and $p_l = min(p_{i+1},p_{i+2},...,p_n)$. The second type is $(k,l)$. 497 498 The reason why this is true is because the first type of swap can create a new good index ( since every good index must be a fixed point ) and the second type of swap can fix an already good index. It's obvious that if a swap does neither of the above, it can't increase our current cost. 499 500 Calculating $f(p)$ after each swap can be done with a segment tree. Consider adding one on the ranges $(min(i,p_i),max(i,p_i))$. Now an index is good if and only if its value is $1$, which is also the minimum value an index can have. Thus our segment tree has to find the number of minimums while performing range additions which can be easily maintained by lazy propagation. 501 502 This solution works in $O(nlog(n))$ time complexity. 503 504 **Code (tibinyte)** 505 506 ``` 507 #include <bits/stdc++.h> 508 using namespace std; 509 struct aint 510 { 511 vector<pair<int, int>> a; 512 vector<int> lazy; 513 void resize(int n) 514 { 515 a = vector<pair<int, int>>(4 * n); 516 lazy = vector<int>(4 * n); 517 } 518 void init(int node, int left, int right) 519 { 520 a[node].second = (right - left + 1); 521 if (left != right) 522 { 523 int mid = (left + right) / 2; 524 init(2 * node, left, mid); 525 init(2 * node + 1, mid + 1, right); 526 } 527 } 528 void prop(int node, int left, int right) 529 { 530 a[node].first += lazy[node]; 531 if (left != right) 532 { 533 lazy[2 * node] += lazy[node]; 534 lazy[2 * node + 1] += lazy[node]; 535 } 536 lazy[node] = 0; 537 } 538 pair<int, int> merge(pair<int, int> a, pair<int, int> b) 539 { 540 if (a.first == b.first) 541 { 542 return pair<int, int>{a.first, a.second + b.second}; 543 } 544 return min(a, b); 545 } 546 void update(int node, int left, int right, int st, int dr, int val) 547 { 548 prop(node, left, right); 549 if (right < st || left > dr) 550 { 551 return; 552 } 553 if (st <= left && dr >= right) 554 { 555 lazy[node] += val; 556 prop(node, left, right); 557 return; 558 } 559 int mid = (left + right) / 2; 560 update(2 * node, left, mid, st, dr, val); 561 update(2 * node + 1, mid + 1, right, st, dr, val); 562 a[node] = merge(a[2 * node], a[2 * node + 1]); 563 } 564 }; 565 struct bit 566 { 567 vector<int> a; 568 void resize(int n) 569 { 570 a = vector<int>(n + 1); 571 } 572 void update(int pos, int val) 573 { 574 int n = (int)a.size() - 1; 575 for (int i = pos; i <= n; i += i & (-i)) 576 { 577 a[i] += val; 578 } 579 } 580 int query(int pos) 581 { 582 int ans = 0; 583 for (int i = pos; i; i -= i & (-i)) 584 { 585 ans += a[i]; 586 } 587 return ans; 588 } 589 int query(int st, int dr) 590 { 591 return query(dr) - query(st - 1); 592 } 593 }; 594 int32_t main() 595 { 596 cin.tie(nullptr)->sync_with_stdio(false); 597 int q; 598 cin >> q; 599 while (q--) 600 { 601 int n; 602 cin >> n; 603 vector<int> a(n + 1); 604 bool sortat = true; 605 for (int i = 1; i <= n; ++i) 606 { 607 cin >> a[i]; 608 if (a[i] != i) 609 { 610 sortat = false; 611 } 612 } 613 if (sortat) 614 { 615 cout << n - 2 << '\n'; 616 continue; 617 } 618 vector<pair<int, int>> qui(n + 1); 619 stack<int> s; 620 bit tree; 621 tree.resize(n); 622 for (int i = 1; i <= n; ++i) 623 { 624 while (!s.empty() && a[s.top()] < a[i]) 625 { 626 s.pop(); 627 } 628 if (!s.empty()) 629 { 630 qui[i].first = s.top(); 631 } 632 if (tree.query(a[i], n) > 1) 633 { 634 qui[i].first = 0; 635 } 636 tree.update(a[i], 1); 637 s.push(i); 638 } 639 while (!s.empty()) 640 s.pop(); 641 tree.resize(n); 642 for (int i = n; i >= 1; --i) 643 { 644 while (!s.empty() && a[s.top()] > a[i]) 645 { 646 s.pop(); 647 } 648 if (!s.empty()) 649 { 650 qui[i].second = s.top(); 651 } 652 if (tree.query(1, a[i]) > 1) 653 { 654 qui[i].second = 0; 655 } 656 tree.update(a[i], 1); 657 s.push(i); 658 } 659 aint lesgo; 660 lesgo.resize(n); 661 lesgo.init(1, 1, n); 662 function<void(int, int)> upd = [&](int ind, int sign) 663 { 664 lesgo.update(1, 1, n, min(ind, a[ind]), max(ind, a[ind]), sign); 665 }; 666 function<int()> count = [&]() 667 { 668 if (lesgo.a[1].first == 1) 669 { 670 return lesgo.a[1].second; 671 } 672 return 0; 673 }; 674 function<void(int, int)> mySwap = [&](int i, int j) 675 { 676 upd(i, -1); 677 upd(j, -1); 678 swap(a[i], a[j]); 679 upd(i, 1); 680 upd(j, 1); 681 }; 682 for (int i = 1; i <= n; ++i) 683 { 684 upd(i, 1); 685 } 686 int ans = 0; 687 for (int i = 1; i <= n; ++i) 688 { 689 if (qui[i].first && qui[i].second) 690 { 691 mySwap(qui[i].first, qui[i].second); 692 ans = max(ans, count()); 693 mySwap(qui[i].first, qui[i].second); 694 } 695 } 696 vector<int> pos(n + 1); 697 for (int i = 1; i <= n; ++i) 698 { 699 pos[a[i]] = i; 700 } 701 for (int i = 1; i <= n; ++i) 702 { 703 int qui1 = i; 704 int qui2 = pos[i]; 705 mySwap(qui1, qui2); 706 ans = max(ans, count()); 707 mySwap(qui1, qui2); 708 } 709 cout << ans << '\n'; 710 } 711 } 712 ``` 713 714 **Rate Problem** 715 716 Good problem 717 718 Ok problem 719 720 Bad problem 721 722 Didn't solve it, idk