2106.md (26893B)
1 Source: https://codeforces.com/blog/entry/142254 2 3 Thanks for the participation. I hope you enjoyed the problems, or at the very least learned something new. 4 5 **Rate Contest Quality** 6 7 * Amazing 8 * Good 9 * Average 10 * Bad 11 12 **Rate Contest Difficulty** 13 14 * Very Hard 15 * Hard 16 * Average 17 * Easy 18 * Very Easy 19 20 **Favorite Problem** 21 22 * A 23 * B 24 * C 25 * D 26 * E 27 * F 28 * G1 29 * G2 30 31 **Worst Problem** 32 33 * A 34 * B 35 * C 36 * D 37 * E 38 * F 39 * G1 40 * G2 41 42 ~~The codes will be posted after the hacking phase is over.~~ Codes have been posted. 43 44 [Problem A — DR. TC](https://codeforces.com/contest/2106/problem/A) 45 46 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 47 48 **Solution** 49 50 Every character of $a$ is flipped in exactly one string. Therefore, if $a_i = 1$, we need to add $n-1$ to the answer (since the $i$-$th$ character will stay $1$ for $n-1$ strings), and if $a_i = 0$ we need to add $1$ (since the $i$-$th$ character will be $1$ in exactly one string). 51 52 **Implementation** 53 54 ``` 55 #include <bits/stdc++.h> 56 using namespace std; 57 58 void solve() { 59 int n; cin >> n; 60 string s; cin >> s; 61 int ans = 0; 62 for (auto x: s) { 63 if (x == '0') ans++; 64 else ans += n - 1; 65 } 66 cout << ans << '\n'; 67 } 68 69 int main() { 70 int t; cin >> t; 71 while (t--) solve(); 72 return 0; 73 } 74 ``` 75 76 **Rate the Problem** 77 78 * Amazing 79 * Good 80 * Average 81 * Bad 82 * Didn't Solve 83 84 [Problem B — ST. CHROMA](https://codeforces.com/contest/2106/problem/B) 85 86 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 87 88 **Solution** 89 90 If $x = n$ then we can output any permutation, since in order for the $\operatorname{MEX}$ to be equal to $n$, every value $0, 1, ..., n-1$ must appear. Otherwise, we want to build a permutation $p$ such that two main conditions hold. 91 92 Firstly, we want $x$ to appear on the final strip as soon as possible. In other words, the first index $i$ such that $\operatorname{MEX}(p_1, p_2, ..., p_i) = x$ must be minimized. In addition, the index $j$ such that $p_j = x$ must be maximized, since the $\operatorname{MEX}$ of a set that contains $x$ cannot be equal to $x$. 93 94 There are a lot of constructions that satisfy those conditions. One of them is the permutation $p = [0, 1, ..., x-1, x+1, ..., n-1, x]$. 95 96 **Implementation** 97 98 ``` 99 #include <bits/stdc++.h> 100 using namespace std; 101 102 void solve() { 103 int n, x; cin >> n >> x; 104 for (int i = 0; i < x; i++) cout << i << " "; 105 for (int i = x+1; i < n; i++) cout << i << " "; 106 if (x < n) cout << x; 107 cout << '\n'; 108 } 109 110 int main() { 111 int t; cin >> t; 112 while (t--) solve(); 113 return 0; 114 } 115 ``` 116 117 **Rate the Problem** 118 119 * Amazing 120 * Good 121 * Average 122 * Bad 123 * Didn't Solve 124 125 [Problem C — CHERRY BOMB](https://codeforces.com/contest/2106/problem/C) 126 127 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 128 129 **Solution** 130 131 Suppose that the two arrays $a$ and $b$ of size $n$ are called $s$-complementary if and only if $a_i + b_i = s$ for all $1 \le i \le n$. 132 133 **Observation 1:** If we know every element of $a$, and we know $s$, we can uniquely determine the elements of $b$. 134 135 We split the problem into two cases. 136 137 The first case is if there exists at least one element in $b$ that is not missing. Then we know the required sum $s = a_i + b_i$ for every $1 \le i \le n$. For every index $i$, we know $b_i = s - a_i$. If $0 \le s - a_i \le k$ doesn't hold for some index, the answer is $0$, since it is impossible for the two arrays to be complementary while $0 \le b_i \le k$. Otherwise, the answer is $1$ from Observation 1. 138 139 The second case is if every element of $b$ is missing: 140 141 **Observation 2:** if $a$ and $b$ are $s$-complementary, then the maximum element of $b$ is positioned at the index where the minimum element of $a$ is positioned at. That is because in order for $a_i + b_i = s$ to hold when $a_i$ is minimum, $b_i$ must be maximized. 142 143 **Observation 3:** The maximum element of $b$ must be at least $mx_a - mn_a$, i.e. the difference between the maximum and minimum elements of $a$. 144 145 **Proof** 146 147 Suppose that the maximum of $b$ is positioned at index $i$, and $b_i \lt mx_a - mn_a$. From Observation 2, $a_i = mn_a$, since the position of the maximum element of $b$ is the position of the minimum element of $a$. Then $s = a_i + b_i$, and $a_i + b_i \lt a_i + mx_a - mn_a$ (since $b_i \lt mx_a - mn_a$), so $s \lt mn_a + mx_a - mn_a = mx_a$ (since $a_i = mn_a$). However, $s \lt mx_a$ cannot hold (since elements of $b$ cannot be negative), therefore this is a contradiciton. 148 149 From Observation 3 and 1, we can set the maximum element of $b$ to $mx_a - mn_a, mx_a - mn_a + 1, ..., k$, which results to $k - (mx_a - mn_a) + 1$ different solutions. 150 151 **Implementation** 152 153 ``` 154 #include <bits/stdc++.h> 155 using namespace std; 156 157 void solve() { 158 int n, k; cin >> n >> k; 159 int a[n], b[n]; 160 for (int i = 0; i < n; i++) cin >> a[i]; 161 for (int i = 0; i < n; i++) cin >> b[i]; 162 int s = -1; 163 for (int i = 0; i < n; i++) { 164 if (b[i] != -1) { 165 if (s == -1) s = a[i] + b[i]; 166 else { 167 if (s != a[i] + b[i]) { 168 cout << 0 << '\n'; 169 return; 170 } 171 } 172 } 173 } 174 if (s == -1) { 175 sort(a, a+n); 176 int mx = a[n-1] - a[0]; 177 cout << k - mx + 1 << '\n'; 178 return; 179 } 180 for (int i = 0; i < n; i++) { 181 if (a[i] > s || s - a[i] > k) { 182 cout << 0 << '\n'; 183 return; 184 } 185 } 186 cout << 1 << '\n'; 187 } 188 189 int main() { 190 int t; cin >> t; 191 while (t--) solve(); 192 return 0; 193 } 194 ``` 195 196 **Rate the Problem** 197 198 * Amazing 199 * Good 200 * Average 201 * Bad 202 * Didn't Solve 203 204 [Problem D — IGOR / FLOWER BOY](https://codeforces.com/contest/2106/problem/D) 205 206 (Author: [cry](/profile/cry "International Master cry"), Analysis: [cowthecow](/profile/cowthecow "Expert cowthecow")) 207 208 **Solution** 209 210 There is a greedy strategy. Every time you see some flower in $a$, if its beauty is not less than the beauty of next flower you must pick from $b$, you will pick it. The answer is $0$ if we run the greedy without inserting a new flower in $a$ and still collecting all $m$ needed flowers. 211 212 Now, consider what inserting a new flower of beauty $k$ in $a$ will do. It will allow you to "skip" some flower listed in $b$, as you can place it anywhere in $a$ and just pick it up when necessary. Therefore, instead of inserting a new element, we can reconsider the problem as deleting some element listed in $b$. So, one slow solution would be to try deleting $b_1$, then running the greedy on $a$, and repeat for $b_2$, $b_3, ..., b_m$. Then, we can keep the minimum $b_i$ such that the greedy was successful when deleting that flower. 213 214 The solution is too slow. Instead, we can compute for every index $1 \le i \le m$ the minimum index $j$ such that if we run the greedy on the prefix $a_1, a_2, ..., a_j$, we will have collected flowers $b_1, b_2, ..., b_i$. Let this value for index $i$ of $b$ be $p_i$. Do the same for each suffix of $a$. Specifically, let $s_i$ be the maximum index $j$ such that if we run the greedy on the suffix $a_j, a_{j+1}, ..., a_n$ we would have collected the flowers $b_i, b_{i+1}, ..., b_m$. These values can be calculated with two pointers. 215 216 Now, we can delete $b_j$ if $p_{j-1} \lt s_{j+1}$ (to delete $b_1$, it must be that $s_{2} \gt 0$ and to delete $b_m$ that $p_{m-1} \le n$). We keep the minimum among all deletable values in $b$. If there does not exist such a value the answer is $-1$. 217 218 **Implementation** 219 220 ``` 221 #include <bits/stdc++.h> 222 using namespace std; 223 const int INF = 1e9 + 5; 224 225 int main(){ 226 int T; cin >> T; 227 while(T--){ 228 int N, M; cin >> N >> M; 229 vector<int> a(N), b(M); 230 for(int i = 0; i < N; i++) cin >> a[i]; 231 for(int i = 0; i < M; i++) cin >> b[i]; 232 vector<int> backwards_match(M); 233 int j = N - 1; 234 for(int i = M - 1; i >= 0; i--){ 235 while(j >= 0 && a[j] < b[i]) j--; 236 backwards_match[i] = j--; 237 } 238 vector<int> forwards_match(M); 239 j = 0; 240 for(int i = 0; i < M; i++){ 241 while(j < N && a[j] < b[i]) j++; 242 forwards_match[i] = j++; 243 } 244 if(forwards_match.back() < N){ 245 cout << 0 << endl; 246 continue; 247 } 248 int ans = INF; 249 for(int i = 0; i < M; i++){ 250 int match_previous = i == 0 ? -1 : forwards_match[i - 1]; 251 int match_next = i + 1 == M ? N : backwards_match[i + 1]; 252 if(match_next > match_previous){ 253 ans = min(ans, b[i]); 254 } 255 } 256 cout << (ans == INF ? -1 : ans) << "\n"; 257 } 258 } 259 ``` 260 261 **Rate the Problem** 262 263 * Amazing 264 * Good 265 * Average 266 * Bad 267 * Didn't Solve 268 269 [Problem E — WOLF](https://codeforces.com/contest/2106/problem/E) 270 271 (Author: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv"), Analysis: [cowthecow](/profile/cowthecow "Expert cowthecow")) 272 273 **Solution** 274 275 Consider some permutation $p_1, p_2, ..., p_n$. Before answering queries, precompute the index of integer $i$ $(1 \le i \le n)$, suppose it is represented as $idx_i$. 276 277 Let's see how to answer some query $l, r, x$. Obviously, if $idx_x$ does not belong in the range $[l, r]$, the answer is $-1$. Otherwise, we want to somehow manipulate the elements so the binary search ends up checking $idx_x$. 278 279 Suppose the binary search is currently working on some range $[a, b]$. Let $m = \lfloor\frac{a + b}{2}\rfloor$. If $p_m = x$, we are done. Otherwise, consider the following cases: 280 281 * $p_m \lt x$ and $m \lt idx_x$: the binary search will continue on $[m+1, b]$, and since $idx_x$ belongs in that range, we simply let it continue. **We must not swap this value**. 282 * $p_m \lt x$ and $m \gt idx_x$: the binary search will continue on $[m+1, b]$, but $idx_x$ does not belong in that range. To fix this, we must replace $p_m$ with a value that is greater than $x$, in which case the search will continue on $[a, m-1]$. 283 * $p_m \gt x$ and $m \lt idx_x$: the binary search will continue on $[a, m-1]$, but $idx_x$ does not belong in that range. To fix this, we must replace $p_m$ with a value that is less than $x$, in which case the search will continue on $[m+1, b]$. 284 * $p_m \gt x$ and $m \gt idx_x$: the binary search will continue on $[a, m-1]$, and since $idx_x$ belongs in that range, we simply let it continue. **We must not swap this value**. 285 286 Keep doing this process until $p_m = x$. Suppose that the amount of integers less than $x$ needed are $s$, and the amount of integers greater than $x$ needed are $b$. In addition, let the values smaller than $x$ that we can't swap (because they already lead to the wanted direction) be denoted by $ss$ and those bigger as $bb$. There are $n - x$ greater values available in $p$, and $x-1$ smaller values available. Therefore, if $b \gt n - x - bb$ or $s \gt x - 1 - ss$, the answer is $-1$. 287 288 If the answer is not $-1$, we swap as many values as possible from $b$ and $s$ (which will be $\min{(b, s)} * 2$) and those that are still left after that (which will be $(\max{(b, s)} - \min{(b, s)}) * 2)$. The final answer is $(\max{(b, s)} - \min{(b, s)}) * 2 + \min{(b, s)} * 2$. 289 290 **Implementation** 291 292 ``` 293 #include <bits/stdc++.h> 294 using namespace std; 295 #define int long long 296 297 void solve() { 298 int n, q; cin >> n >> q; 299 int arr[n+1]; 300 vector<int> idx(n+1, 0); 301 for (int i = 1; i <= n; i++) { 302 cin >> arr[i]; 303 idx[arr[i]] = i; 304 } 305 while (q--) { 306 int l, r, k; cin >> l >> r >> k; 307 if (idx[k] > r || idx[k] < l) { 308 cout << -1 << " "; 309 continue; 310 } 311 int big = n - k, small = k - 1; 312 int needBig = 0, needSmall = 0; 313 int bigAv = n - k, smallAv = k - 1; 314 int lo = l, hi = r; 315 while (lo <= hi) { 316 int mid = (lo + hi) / 2; 317 if (arr[mid] == k) break; 318 if (mid < idx[k]) { // i want to go right 319 if (k < arr[mid]) { 320 needSmall++; 321 } 322 else smallAv--; 323 small--; 324 lo = mid+1; 325 } 326 else { // i want to go left 327 if (k > arr[mid]) { 328 needBig++; 329 } 330 else bigAv--; 331 big--; 332 hi = mid-1; 333 } 334 } 335 if (big < 0 || small < 0) { 336 cout << -1 << " "; 337 continue; 338 } 339 int ans = 2 * min(needBig, needSmall); 340 int diff = abs(needBig - needSmall); 341 if (needBig > needSmall) { 342 if (bigAv < diff) cout << -1 << " "; 343 else cout << ans + 2 * diff << " "; 344 } 345 else { 346 if (smallAv < diff) cout << -1 << " "; 347 else cout << ans + 2 * diff << " "; 348 } 349 } 350 } 351 352 signed main() { 353 int t; cin >> t; 354 while (t--){ 355 solve(); 356 cout << "\n"; 357 } 358 return 0; 359 } 360 ``` 361 362 **Rate the Problem** 363 364 * Amazing 365 * Good 366 * Average 367 * Bad 368 * Didn't Solve 369 370 [Problem F — GOBLIN](https://codeforces.com/contest/2106/problem/F) 371 372 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 373 374 **Solution** 375 376 Each column can be broken down to $3$ components: 377 378 * If $a_i = 0$, the top-most component will contain $i-1$ zeros, the second component a single one, and the third component $n-i$ zeros. 379 * If $a_i = 1$, the top-most component will contain $i-1$ ones, the second component a single zero, and the third component $n-i$ ones. 380 381 The easiest way to visualize is with DSU. For each column, create $3$ components, and for each component implicitly store the number of $0$s in it. Now, we will try to merge all adjacent components that both consist of zeros. Consider the following transitions, for every $1 \lt i \le n$: 382 383 * If $a_i = 0$ and $a_{i-1} = 0$, then the top-most component of column $i-1$ will be merged with the top-most component of column $i$. The same goes for the two bottom-most components. 384 * If $a_i = 0$ and $a_{i-1} = 1$, then the top-most component of column $i$ will be merged with the top-most component of column $i-1$. 385 * If $a_i = 1$ and $a_{i-1} = 0$, then the bottom-most component of column $i$ will be merged with the bottom-most component of column $i-1$. 386 * If $a_i = 1$ and $a_{i-1} = 1$, we merge nothing. 387 388 After we finish the merging, we just take the component with the maximum number of zeros, which will be the answer to this problem. Note that you do not actually have to use DSU; we only care about the sizes and not the representatives, so we can also use simple prefix sums. 389 390 **Implementation (Prefix Sums)** 391 392 ``` 393 #include <bits/stdc++.h> 394 using namespace std; 395 #define int long long 396 397 void solve() { 398 int n; cin >> n; 399 string s; cin >> s; 400 s = " " + s; 401 vector<int> top(n+1, 0), bot(n+1, 0); 402 int ans = 0; 403 for (int i = 1; i <= n; i++) { 404 if (s[i] == '1') { 405 top[i] = bot[i-1] + 1; 406 } 407 else { 408 top[i] = top[i-1] + (i - 1); 409 bot[i] = bot[i-1] + (n - i); 410 } 411 ans = max(ans, max(top[i], bot[i])); 412 } 413 cout << ans << "\n"; 414 } 415 416 signed main() { 417 ios_base::sync_with_stdio(0); 418 cin.tie(0); 419 int t; cin >> t; 420 while (t--) solve(); 421 return 0; 422 } 423 ``` 424 425 **Implementation (DSU)** 426 427 ``` 428 #include<bits/stdc++.h> 429 using namespace std; 430 typedef long long ll; 431 #define debug(x) cout << #x << " = " << x << "\n"; 432 #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; 433 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 434 int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); } 435 ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); } 436 437 struct DSU{ 438 vector<int> p, sz; 439 vector<ll> score; 440 441 DSU(int n){ 442 p.assign(n, 0); 443 sz.assign(n, 1); 444 score.assign(n, 0); 445 446 for (int i = 0; i < n; i++) p[i] = i; 447 } 448 449 int find(int u){ 450 if (p[u] == u) return u; 451 p[u] = find(p[u]); 452 return p[u]; 453 } 454 455 void unite(int u, int v){ 456 u = find(u); 457 v = find(v); 458 if (u == v) return; 459 460 if (sz[u] < sz[v]) swap(u, v); 461 p[v] = u; 462 sz[u] += sz[v]; 463 score[u] += score[v]; 464 } 465 466 bool same(int u, int v){ 467 return find(u) == find(v); 468 } 469 470 int size(int u){ 471 u = find(u); 472 return sz[u]; 473 } 474 }; 475 476 void solve(){ 477 int n; 478 cin >> n; 479 480 string s; 481 cin >> s; 482 483 DSU dsu(2 * n); 484 vector<array<int, 2>> prev; 485 for (int i = 0; i < n; i++){ 486 if (s[i] == '1'){ 487 dsu.score[2 * i] = 1; 488 dsu.unite(2 * i, 2 * i + 1); 489 490 for (int j = 0; j < prev.size(); j++){ 491 int l = prev[j][0]; 492 int r = prev[j][1]; 493 if (i >= l && i <= r) 494 dsu.unite(2 * i, 2 * (i - 1) + j); 495 } 496 prev = {{i, i}}; 497 continue; 498 } 499 500 vector<array<int, 2>> nxt = {{0, i - 1}, {i + 1, n - 1}}; 501 for (int j = 0; j < nxt.size(); j++){ 502 auto [l, r] = nxt[j]; 503 dsu.score[2 * i + j] = r - l + 1; 504 } 505 506 for (int j = 0; j < prev.size(); j++){ 507 for (int k = 0; k < nxt.size(); k++){ 508 auto [l1, r1] = prev[j]; 509 auto [l2, r2] = nxt[k]; 510 511 if (l2 > r1 || r2 < l1) 512 continue; 513 514 dsu.unite(2 * i + k, 2 * (i - 1) + j); 515 } 516 } 517 prev = nxt; 518 } 519 520 ll ans = 0; 521 for (int i = 0; i < 2 * n; i++) 522 ans = max(ans, dsu.score[i]); 523 cout << ans << "\n"; 524 } 525 526 int main(){ 527 ios::sync_with_stdio(false); 528 cin.tie(0); 529 cout.tie(0); 530 531 int t; 532 cin >> t; 533 while (t--) solve(); 534 } 535 ``` 536 537 **Rate the Problem** 538 539 * Amazing 540 * Good 541 * Average 542 * Bad 543 * Didn't Solve 544 545 [Problem G1 — BAUDELAIRE (Easy Version)](https://codeforces.com/contest/2106/problem/G1) 546 547 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 548 549 **Solution** 550 551 For some node $u$, let $v_u$ be its value and $s_u$ be the sum of the values of all nodes on the simple path from the root of the tree to node $u$ ($s_u$ will also be referenced as "the sum of node $u$" for the purposes of this solution). Also, let $p_u$ be the parent of node $u$ (if $u$ is not the root). 552 553 Suppose that we know which node is the root of the tree. Then, we can make $n$ queries to find $s_1, s_2, ..., s_n$, which is sufficient to figure out $v_1, v_2, ..., v_n$: it holds that $s_u = s_{p_u} + v_u$, therefore $v_u = s_u - s_{p_u}$. 554 555 Then, we have $200$ queries left to find the actual root of the tree. Consider some node $u$, and all of its neighbor nodes $c_1, c_2, ..., c_k$. 556 557 **Observation 1:** Toggling the value of node $u$ will change the sum of every adjacent node to $u$ that is not the parent. 558 559 **Observation 2:** We can find the parent of node $u$ within $3\log k$ queries. Consider doing binary search to find which node does not change its sum when toggling the value of $u$. In order to check if the prefix $c_1, c_2, ..., c_m$ includes the parent of $u$, we do the following: query for $s1 = s_{c_1} + s_{c_2} + ... + s_{c_m}$, toggle the value of $u$, and query for $s2 = s_{c_1}' + s_{c_2}' + ... + s_{c_m}'$ again. Let $D = |s1 - s2|$. From Observation 1, if every node among $c_1, c_2, ..., c_m$ changed its value, then $D = 2m$, so we know that the parent does not belong in that prefix. Otherwise, there is a node that did not change its sum, so we can continue our binary search on that prefix. This takes $3$ queries performed $\log k$ times. Note that if we never find the parent, it must mean that $u$ is the root of the tree. 560 561 Since the tree is a star, if we find the parent of node $1$, we will find the root. If there does not exist a parent, then $1$ is the root. The problem has been solved in $n + 3 \log(n)$ queries, which comfortably fits the query limit. 562 563 There are a lot of other (better) solutions for this version (for example, [this solution](https://codeforces.com/blog/entry/142254?#comment-1269097)), but this solution helps best for coming up with the idea for G2. 564 565 **Implementation** 566 567 ``` 568 #include <bits/stdc++.h> 569 using i64 = long long; 570 571 void solve() { 572 int n; 573 std::cin >> n; 574 std::vector<int> a(n+1), son(n-1); 575 for (int i = 1; i < n; ++i) { 576 int u, v; 577 std::cin >> u >> v; 578 son[i-1] = i + 1; 579 } 580 int Q = 0; 581 auto ask = [&](int op, const std::vector<int> &v) { 582 if (++Q > n + 200) { 583 assert(false); 584 } 585 std::cout << "? " << op; 586 if (op == 1) { 587 std::cout << ' ' << v.size(); 588 for (auto u: v) std::cout << ' ' << u; 589 std::cout << std::endl; 590 int res = 0; 591 std::cin >> res; 592 return res; 593 } else { 594 std::cout << ' ' << v[0] << std::endl; 595 return 0; 596 } 597 }; 598 int rt = 0; 599 int bef = ask(1, son); 600 ask(2, std::vector<int>{1}); 601 int af = ask(1, son); 602 if (std::abs(bef - af) == 2 * son.size()) { 603 rt = 1; 604 } else { 605 int l = 0, r = son.size() - 1; 606 while (l < r) { 607 int mid = l + (r - l) / 2; 608 std::vector<int> query(son.begin() + l, son.begin() + mid + 1); 609 int bef = ask(1, query); 610 ask(2, std::vector<int>{1}); 611 int af = ask(1, query); 612 if (std::abs(bef - af) != 2 * (mid - l + 1)) { 613 r = mid; 614 } else { 615 l = mid + 1; 616 } 617 } 618 rt = son[l]; 619 } 620 for (int i = 1; i <= n; ++i) { 621 a[i] = ask(1, std::vector<int>{i}); 622 } 623 for (int i = 2; i <= n; ++i) { 624 if (rt != i) { 625 a[i] -= a[1]; 626 } 627 } 628 if (rt > 1) a[1] -= a[rt]; 629 std::cout << '!'; 630 for (int i = 1; i <= n; ++i) { 631 std::cout << ' ' << a[i]; 632 } 633 std::cout << std::endl; 634 } 635 636 int main() { 637 std::cin.tie(nullptr)->sync_with_stdio(false); 638 int T = 1; 639 std::cin >> T; 640 while (T--) solve(); 641 return 0; 642 } 643 ``` 644 645 **Rate the Problem** 646 647 * Amazing 648 * Good 649 * Average 650 * Bad 651 * Didn't Solve 652 653 [Problem G2 — BAUDELAIRE (Hard Version)](https://codeforces.com/contest/2106/problem/G2) 654 655 (Author & Analysis: [SpyrosAliv](/profile/SpyrosAliv "Expert SpyrosAliv")) 656 657 **Solution** 658 659 Read the solution to the Easy Version first. 660 661 Obviously, if we know the parent of some node, we know which nodes are under that node's subtree, so we never have to consider them as candidates for the root of the tree. Let's use this to choose nodes in a way such that each time we eliminate as many candidates as possible, even in the worst case. 662 663 Specifically, consider querying for the centroid of the tree (a centroid of a tree is a node that if it is deleted, every connected component left has size no more than half of the original tree). When querying for the centroid, there are two cases: either it is the root of the tree, in which case we are finished, or we find its parent, which eliminates at least half of the current candidates. Then, we delete all nodes that could not possibly be the root, and query for the new centroid. 664 665 Since the candidates get halved each time, we repeat the above process no more than $\log n$ times. In the absolute worst case (which is not realistic), we make $3\log (n) + 3\log (\frac{n}{2}) + 3\log (\frac{n}{4}) + ... + 3$ queries. For $n = 1000$, this is about $165$ queries. I do want to stress that this case is impossible; the $200$ queries are pretty loose but I want to allow a lot of different solutions (there are some even better ones than the one I described here, feel free to describe better solutions in the comments). 666 667 **Implementation** 668 669 ``` 670 #include <bits/stdc++.h> 671 using namespace std; 672 #define int long long 673 674 vector<vector<int>> tree, cd; 675 vector<int> sub, val; 676 vector<bool> del; 677 int n, cdRoot = -1; 678 679 int ask(vector<int> a) { 680 int k = a.size(); 681 cout << "? 1 " << k << " "; 682 for (auto x: a) { 683 cout << x << " "; 684 } 685 cout << endl; 686 int ans; cin >> ans; 687 return ans; 688 } 689 690 void toggle(int u) { 691 cout << "? 2 " << u << endl; 692 } 693 694 void answer(vector<int> ans) { 695 cout << "! "; 696 for (int i = 1; i <= n; i++) cout << ans[i] << " "; 697 cout << endl; 698 } 699 700 void calc_sums(int node, int par = 0) { 701 sub[node] = 0; 702 if (del[node]) return; 703 for (auto next: tree[node]) { 704 if (next == par) continue; 705 calc_sums(next, node); 706 sub[node] += sub[next]; 707 } 708 sub[node]++; 709 } 710 711 int find_centroid(int node, int sz, int par = 0) { 712 for (auto next: tree[node]) { 713 if (next == par || del[next]) continue; 714 if (sub[next] * 2 >= sz) return find_centroid(next, sz, node); 715 } 716 return node; 717 } 718 719 void build(int node, int prev) { 720 cd[prev].push_back(node); 721 del[node] = true; 722 for (auto next: tree[node]) { 723 if (del[next]) continue; 724 calc_sums(next, node); 725 int cent = find_centroid(next, sub[next], node); 726 build(cent, node); 727 } 728 } 729 730 bool inspect(vector<int> a, int tog) { 731 int b4 = ask(a); 732 toggle(tog); 733 int aft = ask(a); 734 int k = a.size(); 735 int must = b4; 736 if (aft < b4) { 737 must -= 2 * k; 738 } 739 else must += 2 * k; 740 if (aft != must) return true; 741 else return false; 742 } 743 744 int find_sus(vector<int> a, int tog) { 745 int k = a.size(); 746 int lo = 0, hi = k-1; 747 int ans = -1; 748 while (lo <= hi) { 749 int mid = (lo + hi) / 2; 750 vector<int> qr; 751 for (int j = 0; j <= mid; j++) { 752 qr.push_back(a[j]); 753 } 754 if (inspect(qr, tog)) { 755 ans = mid; 756 hi = mid-1; 757 } 758 else lo = mid+1; 759 } 760 return ans; 761 } 762 763 int find_root(int node, int par = 0) { 764 if (cd[node].empty()) return node; 765 vector<int> ch; 766 for (auto next: cd[node]) { 767 if (next == par) continue; 768 ch.push_back(next); 769 } 770 int sus = find_sus(ch, node); 771 if (sus == -1) return node; 772 return find_root(ch[sus], node); 773 } 774 775 void find_vals(int node, int par = 0, int above = 0) { 776 val[node] -= above; 777 above += val[node]; 778 for (auto next: tree[node]) { 779 if (next != par) { 780 find_vals(next, node, above); 781 } 782 } 783 } 784 785 void solve() { 786 cin >> n; 787 cd.assign(n+1, {}); 788 tree.assign(n+1, {}); 789 for (int i = 1; i < n; i++) { 790 int u, v; cin >> u >> v; 791 tree[u].push_back(v); 792 tree[v].push_back(u); 793 } 794 del.assign(n+1, false); 795 sub.assign(n+1, 0); 796 calc_sums(1); 797 cdRoot = find_centroid(1, n); 798 build(cdRoot, 0); 799 int root = find_root(cdRoot); 800 val.resize(n+1); 801 for (int i = 1; i <= n; i++) { 802 val[i] = ask({i}); 803 } 804 find_vals(root); 805 answer(val); 806 } 807 808 signed main() { 809 ios_base::sync_with_stdio(0); 810 cin.tie(0); 811 int t; cin >> t; 812 while (t--) solve(); 813 return 0; 814 } 815 ``` 816 817 **Rate the Problem** 818 819 * Amazing 820 * Good 821 * Average 822 * Bad 823 * Didn't Solve