1566.md (41653B)
1 Source: https://codeforces.com/blog/entry/94803 2 3 We hope that you enjoyed the contest. Let's get right into the editorial: 4 5 **A: Median Maximization** 6 7 [1566A - Median Maximization](/contest/1566/problem/A "Codeforces Global Round 16") 8 9 **First solution** 10 11 **Hint 1** 12 13 Which numbers smaller than the median should be taken? 14 15 **Hint 2** 16 17 Which numbers bigger than the median should be taken? 18 19 **Hint 3** 20 21 Greedy algorithm. 22 23 **Editorial** 24 25 Let's consider the array of $n$ elements in non-decreasing order. We can make numbers before the median equal to zero, after that we have $m = \lfloor {\frac{n}{2}} \rfloor + 1$ numbers, which sum should be $n$ and the minimal of them (i.e. median value) should be maximized. 26 27 To do so, it is enough to make all these numbers equal $\lfloor {\frac{s}{m}} \rfloor$, and then add what's left to the last number ($s \bmod m$). It's easy to see that such array matches all the conditions and it is impossible to make median greater. 28 29 **Implementation (C++, shishin)** 30 31 ``` 32 #include <bits/stdc++.h> 33 using namespace std; 34 35 int main() { 36 int T; 37 cin >> T; 38 while (T --> 0) { 39 int n, s; 40 cin >> n >> s; 41 int m = n / 2 + 1; 42 cout << s / m << '\n'; 43 } 44 return 0; 45 } 46 ``` 47 48 **Implementation (Python 3, shishin)** 49 50 ``` 51 t = int(input()) 52 for test in range(t): 53 n, s = map(int, input().split()) 54 m = n // 2 + 1 55 print(s // m) 56 ``` 57 58 **Second solution** 59 60 **Hint 1** 61 62 If it's possible to make the median element $m \gt 1$ then you can make it $m - 1$. 63 64 **Hint 2** 65 66 It is possible to make the median element any number from $0$ to some $M$. 67 68 **Hint 3** 69 70 We can use the binary search for the answer. 71 72 **Editorial** 73 74 Let's run a binary search for the answer. This will work because if the answer $M$ then we can decrease the median element by $d$ and add $d$ to the max element, so we can get any median element from $1$ to $M$, but we can't get more than $M$. In the binary search we will use the greedy technique. All numbers less than the median can be $0$ and all numbers from the median should be at least $M$. So there are $m = \lfloor {\frac{n}{2}} \rfloor + 1$ numbers and each of them should be at least $M$ and we find the $M$ using the binary search. Number $M$ is reachable if $M \cdot m \leq s$ because we can add $s - M \cdot m$ to the maximal number and the median will be $M$. Otherwise, the median element can not be $M$. 75 76 **Implementation (C++, shishin)** 77 78 ``` 79 #include <bits/stdc++.h> 80 using namespace std; 81 82 int main() { 83 int T; 84 cin >> T; 85 while (T --> 0) { 86 long long n, s; 87 cin >> n >> s; 88 long long L = 0, R = s + 1; 89 while (R - L > 1) { 90 long long M = (L + R) / 2; 91 long long m = n / 2 + 1; 92 if (m * M <= s) { 93 L = M; 94 } else { 95 R = M; 96 } 97 } 98 cout << L << '\n'; 99 } 100 return 0; 101 } 102 ``` 103 104 **Implementation (Python, shishin)** 105 106 ``` 107 t = int(input()) 108 for test in range(t): 109 n, s = map(int, input().split()) 110 L = 0 111 R = 10**10 112 while R - L > 1: 113 M = (L + R) // 2 114 m = n // 2 + 1 115 if m * M <= s: 116 L = M 117 else: 118 R = M 119 print(L) 120 ``` 121 122 **B: MIN-MEX Cut** 123 124 [1566B - MIN-MEX Cut](/contest/1566/problem/B "Codeforces Global Round 16") 125 126 **Hint 1** 127 128 The answer is never greater than $2$. 129 130 **Hint 2** 131 132 If a string consists only of $1$, then the answer is $0$. 133 134 **Hint 3** 135 136 If all zeroes are consequent, then the answer is $1$. 137 138 **Editorial** 139 140 The answer is never greater than $2$, because $\text{MEX}$ of the whole string is not greater than $2$. 141 142 The answer is $0$ only if there are no zeroes in the string. 143 144 Now we need to understand, when the answer is $1$ or when it is $2$. The sum of $\text{MEX}$ is $1$ only if all zeroes create a single segment without ones. Then we can cut this segment out, its $\text{MEX}$ is $1$, everything else is ones, their total $\text{MEX}$ is $0$. 145 146 If the zeroes do not create a single segment without ones, the there are two such zeroes that there is a $1$ between them. Then either these zeroes are in a single segment with the $1$, so total $\text{MEX}$ is not less than $2$ or these zeroes are in different segments and the answer is still not less then $2$. 147 148 **Implementation (C++, shishin)** 149 150 ``` 151 #include <bits/stdc++.h> 152 using namespace std; 153 154 int main() { 155 int T; 156 cin >> T; 157 while (T --> 0) { 158 string s; 159 cin >> s; 160 int zeroes = count(s.begin(), s.end(), '0'); 161 if (zeroes == 0) { 162 cout << 0 << '\n'; 163 continue; 164 } 165 int first = s.find('0'); 166 int last = s.rfind('0'); 167 if (last - first + 1 == zeroes) { 168 cout << 1 << '\n'; 169 } else { 170 cout << 2 << '\n'; 171 } 172 } 173 return 0; 174 } 175 ``` 176 177 **Implementation (Python, shishin)** 178 179 ``` 180 t = int(input()) 181 for test in range(t): 182 s = input() 183 zeroes = s.count('0') 184 if zeroes == 0: 185 print(0) 186 continue 187 188 first = s.find('0') 189 last = s.rfind('0') 190 if last - first + 1 == zeroes: 191 print(1) 192 else: 193 print(2) 194 ``` 195 196 **C: MAX-MEX Cut** 197 198 [1566C - MAX-MEX Cut](/contest/1566/problem/C "Codeforces Global Round 16") 199 200 **First solution** 201 202 **Hint 1** 203 204 You can cut out the columns with both $0$ and $1$. 205 206 **Hint 2** 207 208 Now in each column there are only $0$ or only $1$. We only need to solve the problem for a string because the columns can be replaced by one digit (they consist of equal elements). 209 210 **Hint 3** 211 212 Let's be greedy, to each zero we will "join" not more than one $1$. 213 214 **Editorial** 215 216 Let's solve the same problem but for a string: 217 218 It's needed to cut a binary string into segments so that each its element is in exactly one segment and the sum of $\text{MEX}$ for all segments is maximal. 219 220 Initially we will say that the string is cut into segments of length 1. Then the answer is the number of zeroes in the string. After that the answer is increased every time we merge a segment of $0$ with a segment of $1$. Each such merge increases the answer by $1$. Let's make the merges greedily, maximizing the number of merges. Let's consider the first zero. If the previous element is a $1$, let's merge them and consider the next zero. Else, if the next element is a $1$, let's merge them and consider the next zero. Else, the next element is a zero and we should consider it instead of the current zero the same way. By doing so we get the answer as the number of zeroes + the number of merges. 221 222 Now let's solve the initial problem. We can cut out the columns that contain both $0$ and $1$, because their $\text{MEX}$ is already maximized and the answer will not become worse. 223 224 Now we solve the problem for all remaining bi-tables independently. Each their column consists either only of $0$ or only of $1$ so both rows are equal. We will solve the problem for one row of each remaining bi-table as mentioned before and then sum up the values to get the answer. 225 226 **Implementation (C++, shishin)** 227 228 ``` 229 #include <bits/stdc++.h> 230 using namespace std; 231 232 int solve(string s) { 233 int ans = count(s.begin(), s.end(), '0'); 234 int n = s.size(); 235 bool a = false, b = false; 236 for (int i = 0; i < n; ++i) { 237 if (s[i] == '0') a = true; 238 if (s[i] == '1') b = true; 239 if (a && b) { 240 ++ans; 241 a = b = false; 242 } 243 } 244 return ans; 245 } 246 247 int main() { 248 ios_base::sync_with_stdio(false); 249 cin.tie(nullptr); 250 cout.tie(nullptr); 251 int T; 252 cin >> T; 253 while (T --> 0) { 254 int n, ans = 0; 255 string a, b; 256 cin >> n >> a >> b; 257 string s = ""; 258 for (int i = 0; i < n; ++i) { 259 if (a[i] != b[i]) { 260 ans += 2 + solve(s); 261 s = ""; 262 } else { 263 s += a[i]; 264 } 265 } 266 cout << ans + solve(s) << '\n'; 267 } 268 return 0; 269 } 270 ``` 271 272 **Second solution (two similar solutions)** 273 274 This problem could be solved in many ways using the dp. We will consider these solutions in short. 275 276 Let's say that $dp_i$ — is the answer for a prefix until $i$. Then there are different approaches: 277 278 We can calculate the dp values, iterating through all possible $\operatorname{MEX}$ values on the last segment. For example, if we want to make $\operatorname{MEX}$ equal $2$ on the last segment, then we need to find the closest $0$ and the closest $1$ to position $i$. Let it be $last_0$ and $last_1$. Then we should recalc the dp like this $dp_i = \max(dp_i, dp_{j-1} + 2)$, where $j = \min(last_0, last_1)$, because we take the shortest segment ending in $i$ which has both $0$ and $1$ and after that we add the answer for this segment and for prefix that ends in $j-1$. 279 280 **Implementation(C++, kpw29)** 281 282 ``` 283 #include <bits/stdc++.h> 284 using namespace std; 285 #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) 286 #define rep(i, l, r) for(int i = (l); i < (r); ++i) 287 typedef vector<int> vi; 288 289 //Did you REAALLY consider sample tests? 290 void solve(int tc) { 291 string s[2]; 292 int n; 293 cin >> n; 294 cin >> s[0] >> s[1]; 295 vi dp(n + 1, 0); 296 vi last(2, -1); 297 298 auto take = [&](int i, bool take0, bool take1) { 299 int MEX = 0; 300 if (take0) { 301 if (take1) MEX = 2; 302 else MEX = 1; 303 } 304 305 int index = i; 306 if (take0) index = min(index, last[0]); 307 if (take1) index = min(index, last[1]); 308 309 if (index != -1) return MEX + dp[index - 1]; 310 return -100000; 311 }; 312 313 FOR(i, 1, n) { 314 vi val(2); 315 rep(j, 0, 2) last[s[j][i-1] - '0'] = i; 316 dp[i] = dp[i-1]; 317 dp[i] = max(dp[i], take(i, 1, 0)); 318 dp[i] = max(dp[i], take(i, 0, 1)); 319 dp[i] = max(dp[i], take(i, 1, 1)); 320 } 321 322 cout << dp[n] << "\n"; 323 } 324 325 int main() { 326 int tests; 327 cin >> tests; 328 FOR(test, 1, tests) { 329 solve(test); 330 } 331 } 332 ``` 333 334 Another possible solution with dp is based on the fact that we should not take any segments with length more than $x$, where $x$ is some small number. We can just take some random big enough $x$ and not prove anything. There exists a solution which does not consider segments with length bigger than $5$. 335 336 **Implementation (C++, physics0523)** 337 338 ``` 339 #include<bits/stdc++.h> 340 341 using namespace std; 342 343 int mex(string s){ 344 int fl=0; 345 for(auto &nx : s){ 346 if(nx=='0'){fl|=1;} 347 else if(nx=='1'){fl|=2;} 348 } 349 if(fl==3){return 2;} 350 if(fl==1){return 1;} 351 return 0; 352 } 353 354 int main(){ 355 ios::sync_with_stdio(false); 356 cin.tie(nullptr); 357 int t; 358 cin >> t; 359 while(t>0){ 360 t--; 361 int n; 362 string s1,s2; 363 cin >> n >> s1 >> s2; 364 vector<int> dp(n+1,0); 365 for(int i=0;i<n;i++){ 366 string s; 367 for(int j=0;j<5;j++){ 368 if(i+j>=n){break;} 369 s.push_back(s1[i+j]); 370 s.push_back(s2[i+j]); 371 dp[i+j+1]=max(dp[i+j+1],dp[i]+mex(s)); 372 } 373 } 374 cout << dp[n] << '\n'; 375 } 376 return 0; 377 } 378 ``` 379 380 **D: Seating Arrangements** 381 382 [1566D2 - Seating Arrangements (hard version)](/contest/1566/problem/D2 "Codeforces Global Round 16") 383 384 **Hint 1** 385 386 Each person can be seated on some subsegment of places with people with the same level of sight. 387 388 **Hint 2** 389 390 If $n=1$ we should seat people on the maximal possible place. 391 392 **Hint 3** 393 394 The places available for some person may be a subsegment of a row or a suffix of a row + some full rows + a prefix of a row. 395 396 **Editorial** 397 398 Let's consider all seats in increasing order of their indices. For each seat we can consider the level of sight of a person that takes that seat. The considered sequence is non-decreasing. This means that people with the same level of sight should take consequent seats and for each level of sight $x$ we can determine which seats will be taken by people with level of sight $x$. 399 400 Now we should find out how do people with level of sight $x$ sit in the cinema. For that $x$ we know that people with that level of sight should take places with indices from $l$ to $r$. 401 402 Let's seat people with the same level of sight greedily. If all places from $l$ to $r$ are in the same row, then we should seat people in decreasing order of seat indices. Otherwise, these seats form a suffix of some row (maybe empty), some full rows (maybe zero), a prefix of some row (maybe empty). Firstly we need to seat people on the suffix in decreasing order of seat indices. This is not worse than other seatings, because the seats before that suffix may be taken in future and total inconvenience will increase. Seats on the prefix should be taken last of all in decreasing order of seat indices. This is not worse than other seatings, because if some people sit on that prefix then they will bother people on the right, increasing the total inconvenience. Full rows should be taken in decreasing order of seat indices, this does not increase the total inconvenience at all. So we should start by seating poeple on the suffix, then we should cover full rows and finally we should cover the prefix. In each case places should be taken in decreasing order of seat indices. 403 404 The constraints for $m$ are low, so each time we want to seat someone we can consider all places in the row and find how many people increase our inconvenience. 405 406 **Implementation (C++, pashka)** 407 408 ``` 409 #include <bits/stdc++.h> 410 #define long long long int 411 using namespace std; 412 413 // @author: pashka 414 415 void solve_test() { 416 int n, m; 417 cin >> n >> m; 418 vector<pair<int, int>> a(n * m); 419 for (int i = 0; i < n * m; i++) { 420 cin >> a[i].first; 421 a[i].second = i; 422 } 423 sort(a.begin(), a.end()); 424 for (int i = 0; i < n * m; i++) { 425 a[i].second = -a[i].second; 426 } 427 int res = 0; 428 for (int i = 0; i < n; i++) { 429 sort(a.begin() + (m * i), a.begin() + (m * i + m)); 430 for (int j = 0; j < m; j++) { 431 for (int k = 0; k < j; k++) { 432 if (a[i * m + k].second > a[i * m + j].second) res++; 433 } 434 } 435 } 436 cout <<res << "\n"; 437 } 438 439 int main() { 440 ios::sync_with_stdio(false); 441 442 int n; 443 cin >> n; 444 for (int i = 0; i < n; i++) { 445 solve_test(); 446 } 447 448 return 0; 449 } 450 ``` 451 452 **E: Buds Re-hanging** 453 454 [1566E - Buds Re-hanging](/contest/1566/problem/E "Codeforces Global Round 16") 455 456 **Hint 1** 457 458 Re-hanging a bud to a leaf decreases the total amount of leaves by $1$. 459 460 **Hint 2** 461 462 Buds can be re-hanged that way so in the end there is only a root, buds that are connected to the root and leaves connected to the root or to the buds. 463 464 **Hint 3** 465 466 Now the answer depends only on the total amount of vertices, on the amount of buds and on the fact whether there is a leaf connected to the root or not. 467 468 **Editorial** 469 470 If we re-hang a bud from its parent to the root, the amount of leaves either doesn't change (if the parent has other children), or increases by $1$. By doing that we don't make the answer worse, because if there are leaves except for bud's leaves, then we can re-hang the bud to some leaf, decreasing the amount of leaves by $1$. So let's re-hang all buds to the root, until there are no free buds left. 471 472 Now we will assume that all buds are hung to the root, and their amount is $k$. The answer is either $n - 2 \cdot k$ if there is no leaf, hung to the root, or $n - 2 \cdot k - 1$ if there is a leaf, hung to the root. Why is it so? Initially, there are $n - k - 1$ leaves (total amount of nodes — the amount of buds — root). If there is a leaf, hung to the root, then we can hang a bud to it, then hang a bud to the previous bud's leaf, and keep doing so until we use all $k$ buds. Then there are $k$ re-hangs, each of them decreases the answer by $1$. So the final answer is $n - k - 1 - k = n - 2 \cdot k - 1$. If there is no leaves hung to the root, then we can hang a bud to another bud's leaf, then a bud to the previous bud's leaf, and so on until we use $k - 1$ buds. The final answer in this case is $n - k - 1 - (k - 1) = n - 2 \cdot k$. It is not possible to make the answer less, because each re-hang decreases the answer by \le 1 and each re-hang we make decreases it exactly by 1 and we use all re-hangs. 473 474 **Implementation (C++, shishin)** 475 476 ``` 477 #include <bits/stdc++.h> 478 using namespace std; 479 480 vector<vector<int>> g; 481 vector<int> type; // -1 -- default, 0 -- root, 1 -- leaf, 2 -- bud 482 483 void dfs(int v, int p) { 484 bool leaves = false; 485 for (auto to : g[v]) { 486 if (to == p) continue; 487 dfs(to, v); 488 if (type[to] == 1) leaves = true; 489 } 490 if (v != p) { 491 if (!leaves) type[v] = 1; 492 else type[v] = 2; 493 } 494 } 495 496 int main() { 497 ios_base::sync_with_stdio(false); 498 cout.tie(0); 499 cin.tie(0); 500 int T; 501 cin >> T; 502 while (T --> 0) { 503 int n; 504 cin >> n; 505 g.assign(n, vector<int>()); 506 type.assign(n, -1); 507 for (int i = 0; i < n - 1; ++i) { 508 int x, y; 509 cin >> x >> y; 510 --x; --y; 511 g[x].emplace_back(y); 512 g[y].emplace_back(x); 513 } 514 type[0] = 0; 515 dfs(0, 0); 516 bool root_leaf = false; 517 for (auto v : g[0]) { 518 if (type[v] == 1) { 519 root_leaf = true; 520 } 521 } 522 int k = 0; 523 for (int i = 0; i < n; ++i) { 524 k += (type[i] == 2); 525 } 526 cout << n - 2 * k - root_leaf << '\n'; 527 } 528 return 0; 529 } 530 ``` 531 532 **F: Points Movement** 533 534 [1566F - Points Movement](/contest/1566/problem/F "Codeforces Global Round 16") 535 536 **Hint 1** 537 538 If a segment already contains a point then it can be thrown out of the consideration. 539 540 **Hint 2** 541 542 If there is a segment that contains some segment, we can save only the smaller one. 543 544 **Hint 3** 545 546 If you already know which segments will be visited by some point, how you should calculate the answer for this point? 547 548 **Hint 4** 549 550 For some segment, which points should visit it? 551 552 **Editorial** 553 554 Firstly, if a point has initially visited some segment, then we can throw it out of consideration. It means that all segments that cover at least one point can be thrown out. This can be done using the binary search for each segment separately. 555 556 Secondly, if a segment $A$ is contained in a segment $B$ (i.e. $l_B \le l_A \le r_A \le r_B$), then a point that visited $A$ will visit $B$, too. It means that we should save only those segments that do not contain any other segments. 557 558 This can be done using a Fenwick tree. Initially, all values in the tree are zeroes. We will consider the segments in decreasing order of $l$. Let's assume we are considering segment $i$. If there is an already considered segment $j$ $(r_j \le r_i)$, then segment $j$ is in segment $i$. It is so because $l_i \le l_j$ because of the considering order, so $l_i \le l_j \le r_j \le r_i$. To find the amount of such $j$ it is enough to find the amount of $1$ on a prefix until $r_i$ in the Fenwick tree. Now when we considered the segment $i$ we set $1$ in the Fenwick tree on position $r_i$. 559 560 After that there are only segments that do not contain any other segments and they are not initially visited by any point. We will consider only these segments. 561 562 Let's say that a segment is assigned to a point if that point visits this segment. Let's find out how to calculate the answer for one point if we already know the set of segments that are assigned to it. Let's consider the segments that are on the left to the point and say that the maximal distance from the point to these segments is $a$. In the same way let $b$ be the maximal distance from the point to the segments on the right. Then the answer for the point is $2\cdot min(a, b)+max(a, b)$. 563 564 Now if a segment is between two neighbouring points, then it should be assigned to one of these points. (If a segment is to the left from the leftmost point or to the right from the rightmost point then it should be assigned to the leftmost point or to the rightmost point respectively). Now let's consider the segments between two neighbouring points. These segments are ordered by the left ends and by the right ends at the same time. Some prefix of these segments should be assigned to the left point, other segments (suffix) should be assigned to the right point. 565 566 Now let's solve the problem using the dynamic programming. Let $dp[i][j]$ be the answer if we assigned the segments for first $i$ points and there are $j$ segments assigned to the $i$-th point that are to the right from it. There is a linear amount of dp states. Let's learn to calculate the dp. We will consider the dp states in increasing order of $i$ and, after that, $j$. Let $b$ be the distance from $i$-th point to $j$ segment after it. Then $dp[i][j]=\displaystyle\min_{0 \le k \le x} \Big(dp[i-1][k]+2\cdot min(b, a_{i, k})+max(b, a_{i, k})\Big)$, where $a_{i, k}$ — is the distance from $i$-th point to $(k+1)$-th segment after $(i-1)$-th point and $x$ is the amount of segments between points $i$ and $(i+1)$. But this is a quadratic dp. Now we can find out that for some prefix of segments after $(i-1)$-th point $a_{i, k}$ is greater than $b$ and for some suffix it is less than $b$. The length of that prefix may be found using the binary search or two pointers. For $k$ on that prefix the dp will be $dp[i-1][k] + x_i - r_{k+1}+2\cdot b$, and for $k$ on the suffix — $dp[i-1][k] + 2\cdot(x_i - r_{k+1})+b$. In these formulas everything except $b$ depends on $i$ and $k$. It means that we can calculate dp quickly using prefix and suffix minimums. 567 568 The answer is $dp[n][x]$, where $x$ is the amount of segments to the right of the rightmost point. 569 570 **Implementation (C++, Artyom123)** 571 572 ``` 573 #include <bits/stdc++.h> 574 575 using namespace std; 576 577 #define pb emplace_back 578 #define all(x) (x).begin(), (x).end() 579 #define fi first 580 #define se second 581 #define pii pair<int, int> 582 #define ll long long 583 584 const long long INFLL = 1e18; 585 const int INF = 1e9 + 1; 586 587 struct segment_tree { 588 vector<int> t; 589 590 segment_tree(int n) { 591 t.assign(4 * n, INF); 592 } 593 594 void mod(int v, int vl, int vr, int id, int val) { 595 if (vr - vl == 1) { 596 t[v] = min(t[v], val); 597 return; 598 } 599 int vm = (vl + vr) / 2; 600 if (id < vm) mod(2 * v + 1, vl, vm, id, val); 601 else mod(2 * v + 2, vm, vr, id, val); 602 t[v] = min(t[v], val); 603 } 604 605 int get(int v, int vl, int vr, int l, int r) { 606 if (vl >= l && vr <= r) return t[v]; 607 if (r <= vl || l >= vr) return INF; 608 int vm = (vl + vr) / 2; 609 return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r)); 610 } 611 }; 612 613 bool cmp(const pii &a, const pii &b) { 614 return a.se - a.fi < b.se - b.fi; 615 } 616 617 int main() { 618 ios_base::sync_with_stdio(0); 619 cin.tie(0); 620 cout.tie(0); 621 int t; 622 cin >> t; 623 while (t--) { 624 int n, m; 625 cin >> n >> m; 626 vector<ll> a(n); 627 for (auto &c : a) cin >> c; 628 sort(all(a)); 629 vector<pii> seg1(m); 630 vector<int> dl; 631 for (auto &c : seg1) { 632 cin >> c.fi >> c.se; 633 dl.pb(c.fi); 634 } 635 sort(all(dl)); 636 dl.resize(unique(all(dl)) - dl.begin()); 637 sort(all(seg1), cmp); 638 map<int, int> ma; 639 for (int i = 0; i < (int)dl.size(); i++) ma[dl[i]] = i; 640 segment_tree tr((int)dl.size()); 641 vector<pii> seg; 642 for (auto &c : seg1) { 643 int id = lower_bound(all(a), c.fi) - a.begin(); 644 if (id < (int)a.size() && a[id] <= c.se) continue; 645 if (tr.get(0, 0, dl.size(), ma[c.fi], dl.size()) <= c.se) continue; 646 tr.mod(0, 0, dl.size(), ma[c.fi], c.se); 647 seg.pb(c.fi, c.se); 648 } 649 m = seg.size(); 650 sort(all(seg)); 651 vector<vector<pii>> g(n + 1); 652 int L = -1, R = m; 653 while (R - L > 1) { 654 int M = (L + R) / 2; 655 if (seg[M].se < a[0]) L = M; 656 else R = M; 657 } 658 for (int i = 0; i <= L; i++) g[0].pb(seg[i]); 659 for (int i = 0; i < n; i++) { 660 int RIGHT = INF; 661 if (i + 1 < n) RIGHT = a[i + 1]; 662 int id = upper_bound(all(seg), make_pair((int)a[i], (int)a[i])) - seg.begin(); 663 if (id == m) continue; 664 int L = id - 1, R = m; 665 while (R - L > 1) { 666 int M = (L + R) / 2; 667 if (seg[M].se < RIGHT) L = M; 668 else R = M; 669 } 670 for (int j = id; j <= L; j++) g[i + 1].pb(seg[j]); 671 } 672 vector<vector<ll>> dp(n), pr(n), suff(n); 673 for (int i = 0; i < n; i++) { 674 dp[i].resize(g[i + 1].size() + 1, INFLL); 675 pr[i].resize(g[i + 1].size() + 1, INFLL); 676 suff[i].resize(g[i + 1].size() + 1, INFLL); 677 } 678 for (int j = 0; j <= (int)g[1].size(); j++) { 679 ll x = 0; 680 if (g[0].size()) x = a[0] - g[0][0].se; 681 ll y = 0; 682 if (j) y = g[1][j - 1].fi - a[0]; 683 dp[0][j] = 2 * min(x, y) + max(x, y); 684 } 685 for (int i = 1; i < n; i++) { 686 for (int j = 0; j <= (int)g[i].size(); j++) { 687 if (j > 0) pr[i - 1][j] = pr[i - 1][j - 1]; 688 pr[i - 1][j] = min(pr[i - 1][j], dp[i - 1][j] - (j == (int)g[i].size() ? a[i] : g[i][j].se)); 689 } 690 for (int j = (int)g[i].size(); j >= 0; j--) { 691 if (j + 1 <= (int)g[i].size()) suff[i - 1][j] = suff[i - 1][j + 1]; 692 suff[i - 1][j] = min(suff[i - 1][j], dp[i - 1][j] - 2 * (j == (int)g[i].size() ? a[i] : g[i][j].se)); 693 } 694 int L = (int)g[i].size(); 695 for (int j = 0; j <= (int)g[i + 1].size(); j++) { 696 ll y = 0; 697 if (j) y = g[i + 1][j - 1].fi - a[i]; 698 while (L > 0 && a[i] - g[i][L - 1].se <= y) L--; 699 if (L > 0) dp[i][j] = min(dp[i][j], 2 * y + a[i] + pr[i - 1][L - 1]); 700 dp[i][j] = min(dp[i][j], y + 2 * a[i] + suff[i - 1][L]); 701 } 702 } 703 cout << dp[n - 1].back() << "\n"; 704 } 705 return 0; 706 } 707 ``` 708 709 **G: Four Vertices** 710 711 [1566G - Four Vertices](/contest/1566/problem/G "Codeforces Global Round 16") 712 713 **Hint 1** 714 715 The answer always consists either of three edges with common end or of two edges that don't have any common ends. 716 717 **Hint 2** 718 719 To find the answer of the second type you can leave in the graph only those edges that are in the list of three smallest edges for both ends. 720 721 **Hint 3** 722 723 Let's consider those cases when the minimal edge is in the answer or not in the answer. 724 725 **Editorial** 726 727 Observation: the answer always consists either of three edges that have one common end or of two edges that do not have any common ends. 728 729 To find the answer of the first type it is enough to maintain three minimal edges for each vertex. 730 731 To find the answer of the second type we will use this observation: we can leave in the graph only those edges that are in the set of three minimal edges for each their end. Let's prove that. Let's assume that the answer consists of two edges $(a, b)$ and $(c, d)$ and there are at least three edges $(a, a_1)$, $(a, a_2)$, $(a, a_3)$ less than $(a, b)$. Then the edge $(a, b)$ can be swapped by one of these edges because at least one of te integers $a_1$, $a_2$, $a_3$ is not equal to $c$ and $d$. Then we will maintain the set of all these edges. 732 733 Now let's consider two cases. Let $(a, b)$ be the minimal edge. If it is in the answer then we need to find the minimal edge, that does not have any common vertices with $(a, b)$. In this case there are at most $6$ ``bad'' edges because the degrees of each vertex in the graph that consists only of remaining edges do not exceed $3$. It means that we have to consider $O(1)$ variants. If $(a, b)$ is not in the answer, then there are two edges in the answer that have vertices $a$ and $b$ as one of their ends. But there are at most $9$ such pairs of edges, so we have to consider only $O(1)$ variants. 734 735 So the final answer is the minimum of answers of both types. 736 737 **Implementation (C++, Kirill22)** 738 739 ``` 740 #include<bits/stdc++.h> 741 742 using namespace std; 743 744 #define sz(a) (int) (a).size() 745 746 const int N = 1e5; 747 vector<pair<int, int>> g[N]; 748 map<pair<int, int>, int> cost; 749 set<pair<int, int>> a[N], b[N]; 750 multiset<long long> dp; 751 set<pair<int, pair<int, int>>> dp2; 752 753 void solve() { 754 auto minr = *dp2.begin(); 755 long long ans = 1e18; 756 if (sz(dp)) { 757 ans = min(ans, *dp.begin()); 758 } 759 int v = minr.second.first, u = minr.second.second; 760 auto it = dp2.begin(); 761 for (int i = 0; i < 6 && it != dp2.end(); i++, it = next(it)) { 762 auto res = *it; 763 int v2 = res.second.first, u2 = res.second.second; 764 if (v2 != v && v2 != u && u2 != v && u2 != u) { 765 ans = min(ans, (long long) res.first + minr.first); 766 } 767 } 768 for (auto [w, v2] : a[v]) { 769 for (auto [w2, u2] : a[u]) { 770 if (v2 != u2 && v2 != u && u2 != v) { 771 ans = min(ans, (long long) w + w2); 772 } 773 } 774 } 775 cout << ans << '\n'; 776 } 777 778 void del(int v) { 779 if (sz(a[v]) >= 3) { 780 long long res = 0; 781 for (auto [w, to] : a[v]) { 782 res += w; 783 } 784 dp.erase(dp.find(res)); 785 } 786 for (auto [w, to] : a[v]) { 787 if (dp2.find({w, {min(v, to), max(v, to)}}) != dp2.end()) { 788 dp2.erase({w, {min(v, to), max(v, to)}}); 789 } 790 } 791 } 792 793 void upd(int v) { 794 if (sz(a[v]) >= 3) { 795 long long res = 0; 796 for (auto [w, to] : a[v]) { 797 res += w; 798 } 799 dp.insert(res); 800 } 801 for (auto [w, to] : a[v]) { 802 if (a[to].find({w, v}) != a[to].end()) { 803 dp2.insert({w, {min(v, to), max(v, to)}}); 804 } 805 } 806 } 807 808 void relax(int v) { 809 while (sz(a[v]) && sz(b[v])) { 810 auto A = *a[v].rbegin(), B = *b[v].begin(); 811 if (A.first <= B.first) break; 812 a[v].erase(A); 813 b[v].erase(B); 814 a[v].insert(B); 815 b[v].insert(A); 816 } 817 while (sz(a[v]) < 3 && sz(b[v])) { 818 auto B = *b[v].begin(); 819 b[v].erase(B); 820 a[v].insert(B); 821 } 822 } 823 824 void erase(int v, int u, int w) { 825 del(v); 826 del(u); 827 if (a[v].find({w, u}) != a[v].end()) { 828 a[v].erase({w, u}); 829 } 830 else { 831 b[v].erase({w, u}); 832 } 833 if (a[u].find({w, v}) != a[u].end()) { 834 a[u].erase({w, v}); 835 } 836 else { 837 b[u].erase({w, v}); 838 } 839 relax(v); 840 relax(u); 841 upd(v); 842 upd(u); 843 } 844 845 void add(int v, int u, int w) { 846 del(v); 847 del(u); 848 b[v].insert({w, u}); 849 b[u].insert({w, v}); 850 relax(v); 851 relax(u); 852 upd(v); 853 upd(u); 854 } 855 856 signed main() { 857 ios_base::sync_with_stdio(0); 858 cin.tie(0); 859 cout.tie(0); 860 int n, m; 861 cin >> n >> m; 862 for (int i = 0; i < m; i++) { 863 int x, y, w; 864 cin >> x >> y >> w; 865 x--, y--; 866 if (x > y) swap(x, y); 867 cost[{x, y}] = w; 868 g[x].push_back({w, y}); 869 g[y].push_back({w, x}); 870 } 871 for (int i = 0; i < n; i++) { 872 sort(g[i].begin(), g[i].end()); 873 for (int j = 0; j < sz(g[i]); j++) { 874 if (j <= 2) { 875 a[i].insert(g[i][j]); 876 } 877 else { 878 b[i].insert(g[i][j]); 879 } 880 } 881 if (sz(a[i]) >= 3) { 882 long long res = 0; 883 for (auto [w, to] : a[i]) { 884 res += w; 885 } 886 dp.insert(res); 887 } 888 } 889 for (int i = 0; i < n; i++) { 890 for (int j = 0; j < sz(g[i]); j++) { 891 int v = g[i][j].second; 892 if (j <= 2) { 893 if (a[v].find({g[i][j].first, i}) != a[v].end()) { 894 dp2.insert({g[i][j].first, {min(i, v), max(i, v)}}); 895 } 896 } 897 } 898 } 899 int q; 900 cin >> q; 901 solve(); 902 while (q--) { 903 int t, v, u; 904 cin >> t >> v >> u; 905 v--, u--; 906 if (v > u) swap(v, u); 907 if (t == 0) { 908 int w = cost[{v, u}]; 909 erase(v, u, w); 910 } 911 else { 912 int w; 913 cin >> w; 914 cost[{v, u}] = w; 915 add(v, u, w); 916 } 917 solve(); 918 } 919 } 920 ``` 921 922 **H: Xor-quiz** 923 924 [1566H - Xor-quiz](/contest/1566/problem/H "Codeforces Global Round 16") 925 926 **Hint 1** 927 928 Numbers with the same set of prime divisors may be considered as the same numbers. 929 930 **Hint 2** 931 932 The amount of distinct sets of prime divisors which multiplication does not exceed $C$ for such constraints does not exceed $\lceil 0.65 \cdot C \rceil$. 933 934 **Hint 3** 935 936 How you should find the $xor$ of all numbers that have the same set of prime divisors? 937 938 **Hint 4** 939 940 If you know the $xor$ of all numbers with the same set of prime divisors you can recover these numbers randomly. 941 942 **Editorial** 943 944 Let $f(x)$ be the multiplication of all prime divisors of $x$. Then let's make queries for all such $y$ that there is at least one such $x$, $1 \le x \le C$ and $f(x) = y$. For such constraints there will be at most $\lceil 0.65 \cdot C \rceil$ queries. 945 946 Let's group all numbers by $f(x)$. All numbers in one group in any query will be considered together. Let $ans(x)$ be the answer for the query with number $x$ and $g(x)$ be the $xor$ of all number that are not coprime with $x$. Then $g(x)=ans(x) \oplus ans(1)$. Now let's find out how to calculate the $xor$ of all such $x$ that $f(x)$ is divisible by an arbitrary $y$. Let's take $xor$ of all $g(k)$ where $k$ is a divisor of $y$ greater than $1$. Let's prove that by doing that we will get the needed value. If $f(x)$ is divisible by $y$ then such $x$ will be considered $2^l - 1$ times, where $l$ is the amount of prime divisors of $y$. It means that $x$ will be contained in the final value. Now let's prove that there will be no unintended $x$ values. Let $f(x)$ be not divisible by $y$. It means that there is suche prime $p$ that $y$ is divisible by $p$ and $x$ is not divisible by $p$. Then for each divisor $a$ of $y$ that is divisible by $p$ we will assign $b=a/p$. Then such $x$ will be considered either for both $a$ and $b$ or for none of them. It means that it will be considered an even amount of times. Now to find the $xor$ of all numbers with an arbitrary $f(x)$ we need to consider all $x$ from $C$ to $1$ and make $f(x) = f(x) \oplus f(2x) \oplus f(3x) \oplus \ldots$. 947 948 Now we only need to find $n$ distinct numbers from $1$ to $C$ such that $xor$ of numbers in each group is equal to a specific number. For each group of numbers with given $f(x)$ we will start the Gaussian elimination. Let $k$ be the size of a group and after the Gaussian elimination there are $b$ non-zero numbers. Then if $b=k$ there is a single way to obtain the needed $xor$. Else there are $2^{k-b}$ ways to obtain the needed $xor$. Now let's take some random sets of numbers with the needed $xor$ and calculate dp on these numbers to get take exactly $n$ numbers. If there are several ways we can choose any of them. 949 950 **Implementation (C++, Artyom123)** 951 952 ``` 953 #include <bits/stdc++.h> 954 955 using namespace std; 956 957 #define pb emplace_back 958 #define all(x) (x).begin(), (x).end() 959 #define fi first 960 #define se second 961 #define pii pair<int, int> 962 #define ll long long 963 #define ld long double 964 965 const long long INFLL = 1e18; 966 const int INF = 1e9 + 1; 967 const int MAXC = 1e6; 968 mt19937 gen(time(0)); 969 970 vector<int> e(MAXC + 5); 971 972 void precalc() { 973 vector<int> p; 974 for (int i = 2; i <= MAXC; i++) { 975 if (e[i] == 0) { 976 e[i] = i; 977 p.pb(i); 978 } 979 for (int j = 0; j < (int)p.size() && p[j] * i <= MAXC && p[j] <= e[i]; j++) { 980 e[p[j] * i] = p[j]; 981 } 982 } 983 } 984 985 int f(int x) { 986 int ans = 1; 987 vector<int> p; 988 while (x > 1) { 989 p.pb(e[x]); 990 x /= e[x]; 991 } 992 for (int i = 0; i < (int)p.size(); i++) { 993 if (i + 1 == (int)p.size() || p[i + 1] != p[i]) ans *= p[i]; 994 } 995 return ans; 996 } 997 998 void gauss(int need, vector<int> &lst, vector<int> &ans, vector<vector<int>> &sz, vector<vector<vector<int>>> &v) { 999 int n = lst.size(); 1000 vector<bitset<20>> a(n); 1001 for (int i = 0; i < n; i++) a[i] = lst[i]; 1002 bitset<20> b = need; 1003 vector<bitset<260>> l(n); 1004 for (int i = 0; i < n; i++) l[i][i] = 1; 1005 int i = 0; 1006 vector<int> col(20, -1); 1007 int bas_sz = 0; 1008 for (int j = 0; j < 20 && i < n; j++) { 1009 int i1 = i; 1010 while (i1 < n && a[i1][j] == 0) i1++; 1011 if (i1 == n) continue; 1012 swap(a[i], a[i1]); 1013 swap(l[i], l[i1]); 1014 bas_sz++; 1015 col[j] = i; 1016 for (int i2 = i + 1; i2 < n; i2++) { 1017 if (a[i2][j]) { 1018 a[i2] ^= a[i]; 1019 l[i2] ^= l[i]; 1020 } 1021 } 1022 i++; 1023 } 1024 bitset<20> res; 1025 bitset<260> path; 1026 for (int j = 0; j < 20; j++) { 1027 if (res[j] != b[j] && col[j] == -1) { 1028 exit(0); 1029 } 1030 if (res[j] == b[j]) continue; 1031 res ^= a[col[j]]; 1032 path ^= l[col[j]]; 1033 } 1034 if (a.back().count() != 0) { 1035 for (int i = 0; i < n; i++) { 1036 if (path[i]) ans.pb(lst[i]); 1037 } 1038 return; 1039 } 1040 vector<int> diff_sz(300); 1041 sz.pb(); 1042 v.pb(); 1043 for (int it = 0; it < 100; it++) { 1044 bitset<260> now = path; 1045 for (int i = 0; i < n - bas_sz; i++) { 1046 if (gen() % 2) now ^= l[bas_sz + i]; 1047 } 1048 int now_sz = now.count(); 1049 if (diff_sz[now_sz]) continue; 1050 v.back().pb(); 1051 for (int i = 0; i < n; i++) { 1052 if (now[i]) v.back().back().pb(lst[i]); 1053 } 1054 diff_sz[now_sz] = 1; 1055 sz.back().pb(now_sz); 1056 } 1057 } 1058 1059 vector<int> mem(2 * MAXC + 5, -1); 1060 1061 int query(int x) { 1062 return mem[x]; 1063 } 1064 1065 void solve(int n, int c) { 1066 vector<int> calc(c + 1); 1067 vector<vector<int>> total(c + 1); 1068 for (int x = 1; x <= c; x++) total[f(x)].pb(x); 1069 vector<int> need; 1070 for (int x = 1; x <= c; x++) { 1071 if (total[x].size()) need.pb(x); 1072 } 1073 cout << need.size() << " "; 1074 for (auto &c : need) cout << c << " "; 1075 cout << endl; 1076 for (auto &c : need) { 1077 int x; 1078 cin >> x; 1079 mem[c] = x; 1080 } 1081 int total_xor = query(1); 1082 for (int x = 1; x <= c; x++) { 1083 if (total[x].empty()) continue; 1084 for (int y = x; y <= c; y += x) calc[y] ^= (query(x) ^ total_xor); 1085 } 1086 calc[1] = total_xor; 1087 for (int x = c; x >= 1; x--) { 1088 if (total[x].empty()) continue; 1089 for (int y = 2 * x; y <= c; y += x) { 1090 if (total[y].size()) calc[x] ^= calc[y]; 1091 } 1092 } 1093 vector<int> ans; 1094 vector<vector<int>> sz; 1095 vector<vector<vector<int>>> v; 1096 for (int x = 1; x <= c; x++) { 1097 if (total[x].empty()) continue; 1098 gauss(calc[x], total[x], ans, sz, v); 1099 } 1100 vector<bitset<40000>> bag(sz.size() + 1); 1101 bag[0][0] = 1; 1102 for (int i = 1; i <= (int)sz.size(); i++) { 1103 for (auto &x : sz[i - 1]) { 1104 bag[i] |= (bag[i - 1] << x); 1105 } 1106 } 1107 int now = n - ans.size(); 1108 for (int i = (int)sz.size(); i >= 1; i--) { 1109 for (int j = 0; j < (int)sz[i - 1].size(); j++) { 1110 int x = sz[i - 1][j]; 1111 if (now - x >= 0 && bag[i - 1][now - x]) { 1112 now -= x; 1113 for (auto &y : v[i - 1][j]) ans.pb(y); 1114 break; 1115 } 1116 } 1117 } 1118 sort(all(ans)); 1119 for (auto &c : ans) cout << c << " "; 1120 cout << endl; 1121 } 1122 1123 int main() { 1124 precalc(); 1125 int c, n; 1126 cin >> c >> n; 1127 solve(n, c); 1128 return 0; 1129 } 1130 ``` 1131 1132 **Who did what?** 1133 1134 * Problem A 1135 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 1136 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 1137 + Editorial: [shishyando](/profile/shishyando "Expert shishyando") 1138 * Problem B 1139 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 1140 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 1141 + Editorial: [shishyando](/profile/shishyando "Expert shishyando") 1142 * Problem C 1143 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 1144 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 1145 + Editorial: [shishyando](/profile/shishyando "Expert shishyando") 1146 * Problem D 1147 + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1148 + Polygon: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1149 + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1150 * Problem E 1151 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 1152 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 1153 + Editorial: [shishyando](/profile/shishyando "Expert shishyando") 1154 * Problem F 1155 + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1156 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 1157 + Editorial: [shishyando](/profile/shishyando "Expert shishyando") + [Artyom123](/profile/Artyom123 "International Master Artyom123") 1158 * Problem G 1159 + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") + [isaf27](/profile/isaf27 "International Grandmaster isaf27") 1160 + Polygon: tests: [Artyom123](/profile/Artyom123 "International Master Artyom123") + other: [shishyando](/profile/shishyando "Expert shishyando") 1161 + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1162 * Problem H 1163 + Idea: [Artyom123](/profile/Artyom123 "International Master Artyom123") + [isaf27](/profile/isaf27 "International Grandmaster isaf27") 1164 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") + [Artyom123](/profile/Artyom123 "International Master Artyom123") 1165 + Editorial: [Artyom123](/profile/Artyom123 "International Master Artyom123") 1166 * English translation: [shishyando](/profile/shishyando "Expert shishyando") 1167 * Edits on Polygon, common enhancements: [KAN](/profile/KAN "Legendary Grandmaster KAN"), [isaf27](/profile/isaf27 "International Grandmaster isaf27"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")