2027.md (18521B)
1 Source: https://codeforces.com/blog/entry/135558 2 3 Thank you so much for participating in our round! We really hope you enjoyed it. For us, it was an amazing and educational experience, and we look forward to the possibility that we could one day help to or hold a round again. Thanks again to [abc864197532](/profile/abc864197532 "International Grandmaster abc864197532") and [Vladithur](/profile/Vladithur "International Master Vladithur") for making the process so smooth and enjoyable. 4 5 [2027A - Rectangle Arrangement](/contest/2027/problem/A "Codeforces Round 982 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Code** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 cin.tie(0)->sync_with_stdio(0); 20 int t; 21 cin >> t; 22 while (t--) { 23 int n; 24 cin >> n; 25 int maxw = 0, maxh = 0; 26 for (int i=0; i<n; i++) { 27 int w, h; 28 cin >> w >> h; 29 maxw = max(maxw, w); 30 maxh = max(maxh, h); 31 } 32 cout << 2 * (maxw + maxh) << "\n"; 33 } 34 return 0; 35 } 36 ``` 37 38 [2027B - Stalin Sort](/contest/2027/problem/B "Codeforces Round 982 (Div. 2)") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Code** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 cin.tie(0)->sync_with_stdio(0); 53 int t; 54 cin >> t; 55 while (t--) { 56 int n; 57 cin >> n; 58 vector<int> A(n); 59 for (int i=0; i<n; i++) cin >> A[i]; 60 int best = 0; 61 for (int i=0; i<n; i++) { 62 int curr = 0; 63 for (int j=i; j<n; j++) { 64 if (A[j] <= A[i]) { 65 curr += 1; 66 } 67 } 68 best = max(best, curr); 69 } 70 cout << n - best << "\n"; 71 } 72 return 0; 73 } 74 ``` 75 76 [2027C - Add Zeros](/contest/2027/problem/C "Codeforces Round 982 (Div. 2)") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Code** 83 84 ``` 85 #include <bits/stdc++.h> 86 87 using namespace std; 88 using ll = long long; 89 90 int main() { 91 cin.tie(0)->sync_with_stdio(0); 92 int t; 93 cin >> t; 94 while (t--) { 95 int n; 96 cin >> n; 97 vector<ll> A(n); 98 for (int i=0; i<n; i++) cin >> A[i]; 99 map<ll,vector<ll>> adj; 100 for (int i=1; i<n; i++) { 101 ll u = A[i] + i; 102 ll v = u + i; 103 adj[u].push_back(v); 104 } 105 set<ll> vis; 106 function<void(ll)> dfs = [&](ll u) -> void { 107 if (vis.count(u)) return; 108 vis.insert(u); 109 for (ll v : adj[u]) dfs(v); 110 }; 111 dfs(n); 112 cout << *vis.rbegin() << "\n"; 113 } 114 return 0; 115 } 116 ``` 117 118 [2027D1 - The Endspeaker (Easy Version)](/contest/2027/problem/D1 "Codeforces Round 982 (Div. 2)") 119 120 **Tutorial** 121 122 ## [2027D1 - The Endspeaker (Easy Version)](/contest/2027/problem/D1 "Codeforces Round 982 (Div. 2)") 123 124 Let's use dynamic programming. We will have $\operatorname{dp}_{i,j}$ be the minimum cost to remove the prefix of length $i$, where the current value of $k$ is $j$. By a type $1$ operation, we can transition from $\operatorname{dp}_{i,j}$ to $\operatorname{dp}_{i,j+1}$ at no cost. Otherwise, by a type $2$ operation, we need to remove some contiguous subarray $a_{i+1}, a_{i+2}, \dots, a_{x}$ (a prefix of the current array), to transition to $\operatorname{dp}_{x,j}$ with a cost of $m - k$. 125 126 Let $r$ be the largest value of $x$ possible. Given we're spending $m - k$ whatever value of $x$ we choose, it's clear to see that we only need to transition to $\operatorname{dp}_{r,j}$. To find $r$ for each value of $i$ and $j$, we can either binary search over the prefix sums or simply maintain $r$ as we increase $i$ for a fixed value of $k$. The answer is then $\operatorname{dp}_{n,k}$. The latter method solves the problem in $\mathcal{O}(nm)$. 127 128 **Code** 129 130 ``` 131 #include <bits/stdc++.h> 132 133 using namespace std; 134 using ll = long long; 135 136 const int inf = 1 << 30; 137 138 void chmin(int &a, int b) { 139 a = min(a, b); 140 } 141 142 int main() { 143 cin.tie(0)->sync_with_stdio(0); 144 int t; 145 cin >> t; 146 while (t--) { 147 int n, m; 148 cin >> n >> m; 149 vector<int> A(n+1); 150 for (int i=0; i<n; i++) cin >> A[i]; 151 vector<int> B(m); 152 for (int i=0; i<m; i++) cin >> B[i]; 153 vector nxt(n, vector<int>(m)); 154 for (int k=0; k<m; k++) { 155 int r = -1, sum = 0; 156 for (int i=0; i<n; i++) { 157 while (r < n && sum <= B[k]) sum += A[++r]; 158 nxt[i][k] = r; 159 sum -= A[i]; 160 } 161 } 162 vector dp(n+1, vector<int>(m, inf)); 163 dp[0][0] = 0; 164 for (int k=0; k<m; k++) { 165 for (int i=0; i<n; i++) { 166 chmin(dp[nxt[i][k]][k], dp[i][k] + m - k - 1); 167 if (k < m-1) 168 chmin(dp[i][k+1], dp[i][k]); 169 } 170 } 171 int ans = inf; 172 for (int k=0; k<m; k++) { 173 chmin(ans, dp[n][k]); 174 } 175 if (ans == inf) { 176 cout << "-1\n"; 177 } else { 178 cout << ans << "\n"; 179 } 180 } 181 return 0; 182 } 183 ``` 184 185 [2027D2 - The Endspeaker (Hard Version)](/contest/2027/problem/D2 "Codeforces Round 982 (Div. 2)") 186 187 **Tutorial** 188 189 ## [2027D2 - The Endspeaker (Hard Version)](/contest/2027/problem/D2 "Codeforces Round 982 (Div. 2)") 190 191 Following on from the editorial for D1. Let's have the $\operatorname{dp}$ table store a pair of the minimum cost and the number of ways. Since we're now counting the ways, it's not enough just to consider the transition to $\operatorname{dp}_{r,j}$; we also need to transition to all $\operatorname{dp}_{x,j}$. Doing this naively is too slow, so let's instead find a way to perform range updates. 192 193 Let's say we want to range update $\operatorname{dp}_{l,j}, \operatorname{dp}_{l+1,j}, ..., \operatorname{dp}_{r,j}$. We'll store some updates in another table at either end of the range. Then, for a fixed value of $k$ as we iterate through increasing $i$-values, let's maintain a map of cost to ways. Whenever the number of ways falls to zero, we can remove it from the map. On each iteration, we can set $\operatorname{dp}_{i,j}$ to the smallest entry in the map, and then perform the transitions. This works in $\mathcal{O}(nm \log n)$. 194 195 Bonus: It's also possible to solve without the $\log n$ factor. We can use the fact that $\operatorname{dp}_{i,k}$ is non-increasing for a fixed value of $k$ to make the range updates non-intersecting by updating a range strictly after the previous iteration. Then we can just update a prefix sum array, instead of using a map. 196 197 **Code** 198 199 ``` 200 #include <bits/stdc++.h> 201 202 using namespace std; 203 using ll = long long; 204 205 const int inf = 1 << 30; 206 const int MOD = 1000000007; 207 208 int main() { 209 cin.tie(0)->sync_with_stdio(0); 210 int t; 211 cin >> t; 212 while (t--) { 213 int n, m; 214 cin >> n >> m; 215 vector<int> A(n+1); 216 for (int i=0; i<n; i++) cin >> A[i]; 217 vector<int> B(m); 218 for (int i=0; i<m; i++) cin >> B[i]; 219 vector nxt(n, vector<int>(m)); 220 for (int k=0; k<m; k++) { 221 int r = -1, sum = 0; 222 for (int i=0; i<n; i++) { 223 while (r < n && sum <= B[k]) sum += A[++r]; 224 nxt[i][k] = r; 225 sum -= A[i]; 226 } 227 } 228 vector dp(n+1, vector<array<int,2>>(m, {inf, 0})); 229 vector upd(n+1, vector(m, vector<array<int,3>>())); 230 upd[0][0].push_back({0, 0, 1}); 231 upd[1][0].push_back({1, 0, 1}); 232 for (int k=0; k<m; k++) { 233 map<int,array<int,2>> mp; 234 for (int i=0; i<=n; i++) { 235 for (auto [t, move, count] : upd[i][k]) { 236 if (t == 0) { 237 auto &[a, b] = mp[move]; 238 a += 1; 239 (b += count) %= MOD; 240 } else { 241 auto &[a, b] = mp[move]; 242 a -= 1; 243 (b += MOD - count) %= MOD; 244 if (a == 0) mp.erase(move); 245 } 246 } 247 if (mp.empty()) continue; 248 auto &[move, info] = *mp.begin(); 249 dp[i][k] = {move, info[1]}; 250 if (i == n) continue; 251 if (k < m-1) { 252 upd[i][k+1].push_back({0, move, info[1]}); 253 upd[i+1][k+1].push_back({1, move, info[1]}); 254 } 255 if (nxt[i][k] > i) { 256 upd[i+1][k].push_back({0, move + (m - k - 1), info[1]}); 257 if (nxt[i][k] < n) { 258 upd[nxt[i][k]+1][k].push_back({1, move + (m - k - 1), info[1]}); 259 } 260 } 261 } 262 } 263 map<int,int> mp; 264 for (int k=0; k<m; k++) { 265 auto &[move, count] = dp[n][k]; 266 (mp[move] += count) %= MOD; 267 } 268 auto &[move, count] = *mp.begin(); 269 if (move == inf) { 270 cout << "-1\n"; 271 } else { 272 cout << move << " " << count << "\n"; 273 } 274 } 275 return 0; 276 } 277 ``` 278 279 **Tutorial (Segment Tree)** 280 281 There exists an alternative solution for D1 & D2, using segment tree. We can actually consider the process in reverse; let's reformulate $\operatorname{dp}_{i,j}$ to represent the minimum score required to remove all elements after the $i$-th element, given that the current value of $k$ is $j$. 282 283 Instead of using a dp table, we maintain $m$ segment trees, each of length $n$. The $i$-th segment tree will represent the $i$-th column of the dp table. 284 285 We precalculate for each $i$ and $j$ the furthest position we can remove starting from $i$ — specifically, the maximum subarray starting from $i$ with a sum less than $b_j$. We store this in $\operatorname{nxt}_{i,j}$. This calculation can be done in $\mathcal{O}(nm)$ time using a sliding window. 286 287 To transition in the dp, we have: 288 289 $ \operatorname{dp}_{i,j} = \min\left( \operatorname{dp}_{i, j + 1}, \, \min(\operatorname{dp}_{i + 1, j}, \operatorname{dp}_{i + 2, j}, \ldots, \operatorname{dp}_{{\operatorname{nxt}_{i,j}}, j}) + m - j + 1 \right) $ 290 291 This transition can be computed in $\mathcal{O}(\log n)$ time thanks to range querying on the segment tree, so our total complexity is $\mathcal{O}(nm \log n)$. For D2, we can store the count of minimums within each segment, and simply sum these counts to get the total number of ways. 292 293 **Code (Segment Tree)** 294 295 ``` 296 #include <bits/stdc++.h> 297 using namespace std; 298 299 #define int long long 300 int modN = 1e9 + 7; 301 302 int mod(int n) { 303 return (n + modN) % modN; 304 } 305 306 struct SegmentTree { 307 struct Node { 308 int val = 1e18; 309 int cnt = 1; 310 }; 311 312 vector<Node> st; 313 int n; 314 SegmentTree(int n): n(n) { 315 st.resize(4 * n + 1, Node()); 316 } 317 318 SegmentTree(vector<int> a): n(a.size()) { 319 st.resize(4 * n + 1, Node()); 320 build(a, 1, 0, n - 1); 321 } 322 323 void merge(Node& a, Node& b, Node& c) { 324 a.val = min(b.val, c.val); 325 if (b.val == c.val) 326 a.cnt = mod(b.cnt + c.cnt); 327 else if (b.val < c.val) 328 a.cnt = b.cnt; 329 else if (b.val > c.val) 330 a.cnt = c.cnt; 331 } 332 333 void build(vector<int>& a, int id, int l, int r) { 334 if (l == r) { 335 st[id].val = a[l]; 336 return; 337 } 338 int mid = (l + r) / 2; 339 build(a, id * 2, l, mid); 340 build(a, id * 2 + 1, mid + 1, r); 341 merge(st[id], st[id * 2], st[id * 2 + 1]); 342 } 343 344 void update(int id, int l, int r, int u, int val, int cnt) { 345 if (l == r) { 346 st[id].val = val; // or st[id].sum += val 347 st[id].cnt = cnt; 348 return; 349 } 350 int mid = (l + r) / 2; 351 if (u <= mid) update(id * 2, l, mid, u, val, cnt); 352 else update(id * 2 + 1, mid + 1, r, u, val, cnt); 353 merge(st[id], st[id * 2], st[id * 2 + 1]); 354 } 355 356 void update(int idx, int val, int cnt) { //wrapper 357 update(1, 0, n - 1, idx, val, cnt); 358 } 359 360 Node query(int id, int l, int r, int u, int v) { //give 0, n - 1 as l and r and 1 as id 361 if (v < l || r < u) return Node(); 362 if (u <= l && r <= v) { 363 return st[id]; 364 } 365 int mid = (l + r) / 2; 366 auto a = query(id * 2, l, mid, u, v); 367 auto b = query(id * 2 + 1, mid + 1, r, u, v); 368 Node res; 369 merge(res, a, b); 370 return res; 371 } 372 373 Node query(int l, int r) { //wrapper 374 return query(1, 0, n - 1, l, r); 375 } 376 }; 377 378 void solve() { 379 int n, m; 380 cin >> n >> m; 381 vector<int> a(n), b(m); 382 for (int &A : a) cin >> A; 383 for (int &B : b) cin >> B; 384 if (*max_element(a.begin(), a.end()) > b[0]) { 385 cout << -1 << '\n'; 386 return; 387 } 388 vector<vector<int>> nxt(m, vector<int>(n)); 389 for (int i = 0; i < m; i++) { 390 int curr = 0, r = -1; 391 for (int j = 0; j < n; j++) { 392 while (r + 1 < n && curr + a[r + 1] <= b[i]) 393 curr += a[r + 1], r += 1; 394 nxt[i][j] = r + 1; 395 if (j <= r) curr -= a[j]; 396 r = max(r, j); 397 } 398 } 399 vector<SegmentTree> dp(m, SegmentTree(vector<int>(n + 1, 1e18))); 400 for (int i = 0; i < m; i++) 401 dp[i].update(n, 0, 1); 402 for (int i = n - 1; i >= 0; i--) { 403 for (int j = m - 1; j >= 0; j--) { 404 auto q1 = dp[j].query(i + 1, nxt[j][i]); 405 int v1 = q1.val + m - (j + 1), ps1 = q1.cnt; 406 if (i + 1 <= nxt[j][i]) dp[j].update(i, v1, ps1); 407 if (j != m - 1) { 408 auto q2 = dp[j + 1].query(i, i); 409 int v2 = q2.val, ps2 = q2.cnt; 410 auto q3 = dp[j].query(i, i); 411 if (v2 < q3.val) 412 dp[j].update(i, v2, ps2); 413 else if (v2 == q3.val) 414 dp[j].update(i, v2, mod(ps2 + q3.cnt)); 415 } 416 } 417 } 418 cout << dp[0].query(0, 0).val << ' ' << dp[0].query(0, 0).cnt << '\n'; 419 } 420 421 signed main() { 422 cin.tie(0) -> sync_with_stdio(false); 423 int t; 424 cin >> t; 425 while (t--) 426 solve(); 427 return 0; 428 } 429 ``` 430 431 [2027E1 - Bit Game (Easy Version)](/contest/2027/problem/E1 "Codeforces Round 982 (Div. 2)") 432 433 **Tutorial** 434 435 Tutorial is loading... 436 437 **Code** 438 439 ``` 440 #include <bits/stdc++.h> 441 442 using namespace std; 443 444 int nimber(int x, int a) { 445 int aprime = 0; 446 bool goodbit = false; 447 for (int bit=30; bit>=0; bit--) { 448 if (x & (1 << bit)) { 449 aprime *= 2; 450 if (goodbit || (a & (1 << bit))) { 451 aprime += 1; 452 } 453 } else if (a & (1 << bit)) { 454 goodbit = true; 455 } 456 } 457 458 // g(2^k - 2) = 0, for all k >= 1. 459 for (int k=1; k<=30; k++) { 460 if (aprime == (1 << k) - 2) { 461 return 0; 462 } 463 } 464 465 // g(2^k - 1) = k, for all k >= 1. 466 for (int k=1; k<=30; k++) { 467 if (aprime == (1 << k) - 1) { 468 return k; 469 } 470 } 471 472 // g(2^k) = k + (-1)^k, for all k >= 0. 473 for (int k=1; k<=30; k++) { 474 if (aprime == (1 << k)) { 475 if (k % 2) return k - 1; 476 else return k + 1; 477 } 478 } 479 480 // g(2^k+1) = g(2^k+2) = ... = g(2^{k+1} - 3) = k + 1, for all k >= 2. 481 for (int k=2; k<=30; k++) { 482 if ((1 << k) < aprime && aprime <= (2 << k) - 3) { 483 return k + 1; 484 } 485 } 486 487 // should never get to this point 488 assert(false); 489 return -1; 490 } 491 492 int main() { 493 cin.tie(0)->sync_with_stdio(0); 494 int t; 495 cin >> t; 496 while (t--) { 497 int n; 498 cin >> n; 499 vector<int> A(n); 500 for (int i=0; i<n; i++) cin >> A[i]; 501 vector<int> X(n); 502 for (int i=0; i<n; i++) cin >> X[i]; 503 int curr = 0; 504 for (int i=0; i<n; i++) curr ^= nimber(X[i], A[i]); 505 cout << (curr ? "Alice" : "Bob") << "\n"; 506 } 507 return 0; 508 } 509 ``` 510 511 [2027E2 - Bit Game (Hard Version)](/contest/2027/problem/E2 "Codeforces Round 982 (Div. 2)") 512 513 **Tutorial** 514 515 Tutorial is loading... 516 517 **Code** 518 519 ``` 520 #include <bits/stdc++.h> 521 522 using namespace std; 523 524 int dp[32][32][6][2][2]; 525 526 const int mod = 1000000007; 527 528 int main() { 529 cin.tie(0)->sync_with_stdio(0); 530 int t; 531 cin >> t; 532 while (t--) { 533 int n; 534 cin >> n; 535 vector<int> A(n); 536 for (int i=0; i<n; i++) cin >> A[i]; 537 vector<int> B(n); 538 for (int i=0; i<n; i++) cin >> B[i]; 539 vector<int> curr(32); 540 curr[0] = 1; // identity 541 for (int i=0; i<n; i++) { 542 memset(dp, 0, sizeof dp); 543 dp[0][0][0][0][0] = 1; 544 for (int j=0; j<=29; j++) { 545 int p = 29 - j; // place we are going to add a bit in 546 for (int k=0; k<=29; k++) { // position of most significant one in a' 547 for (int type=0; type<6; type++) { // 0, 1, 11111, 11110, 10000, else 548 for (int good=0; good<2; good++) { // good=1 iff good bit has occured 549 for (int low=0; low<2; low++) { // low=1 iff prefix below b 550 for (int bit=0; bit<2; bit++) { // bit in x 551 if (dp[j][k][type][good][low] == 0) 552 continue; // no point in transition since count is 0 553 if (!low && (B[i] & (1 << p)) == 0 && bit == 1) 554 continue; // x can't go higher than B[i] 555 if (bit == 0) { 556 int good2 = good || (A[i] & (1 << p)) != 0; // check good bit 557 int low2 = low || (B[i] & (1 << p)) != 0; // check if low 558 // nothing added to a' so nothing else changes 559 (dp[j+1][k][type][good2][low2] += dp[j][k][type][good][low]) %= mod; 560 } else { 561 int bita = good || (A[i] & (1 << p)) != 0; // bit in a' 562 int k2 = type == 0 ? 0 : k + 1; // increase if MSOne exists 563 int type2 = bita ? 564 ( 565 type == 0 ? 1 : // add first one 566 (type == 1 || type == 2) ? 2 : // 11111 567 5 // can't add 1 after a 0 568 ) : ( 569 (type == 0) ? 0 : // 0 570 (type == 1 || type == 4) ? 4 : // 10000 571 (type == 2) ? 3 : // 11110 572 5 // can't have a zero in any other case 573 ); 574 (dp[j+1][k2][type2][good][low] += dp[j][k][type][good][low]) %= mod; 575 } 576 } 577 } 578 } 579 } 580 } 581 } 582 vector<int> count(32); // number of x-values for each nimber 583 for (int k=0; k<=29; k++) { // position of MSOne 584 for (int good=0; good<2; good++) { // doesn't matter 585 for (int low=0; low<2; low++) { // doesn't matter 586 (count[0] += dp[30][k][0][good][low]) %= mod; // 0 587 (count[1] += dp[30][k][1][good][low]) %= mod; // 1 588 (count[k+1] += dp[30][k][2][good][low]) %= mod; // 11111 589 (count[0] += dp[30][k][3][good][low]) %= mod; // 11110 590 (count[k+(k%2?-1:1)] += dp[30][k][4][good][low]) %= mod; // 10000 591 (count[k+1] += dp[30][k][5][good][low]) %= mod; // else 592 } 593 } 594 } 595 count[0] -= 1; // remove when x=0 596 vector<int> next(32); // knapsack after adding this pile 597 for (int j=0; j<32; j++) 598 for (int k=0; k<32; k++) 599 (next[j ^ k] += 1LL * curr[j] * count[k] % mod) %= mod; 600 swap(curr, next); 601 } 602 cout << curr[0] << "\n"; 603 } 604 return 0; 605 } 606 ```