2207.md (42348B)
1 Source: https://codeforces.com/blog/entry/151886 2 3 | | 4 | --- | 5 | [Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii](https://www.youtube.com/watch?v=HCYKLnT0UNU) | 6 7 **UPD 1:** added hints, problem credits, more specific acknowledgements and some remarks. Implementations are on the way, sorry for making y'all wait! 8 9 **UPD 2:** Implementations are finally here. 10 11 [2207A - 1-1](/contest/2207/problem/A) 12 13 Author: [awang11](/profile/awang11 "International Master awang11") 14 15 Preparers: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 16 17 Analysis: [awang11](/profile/awang11 "International Master awang11") 18 19 **Hint 1** 20 21 If there are two consecutive zeroes, can you ever change either of them? 22 23 **Solution** 24 25 Tutorial is loading... 26 27 **Rate the problem!** 28 29 Awesome! 30 31 Okay... 32 33 I would have rather watched cricket world cup 34 35 **Implementation** 36 37 ``` 38 t = int(input()) 39 for _ in range(t): 40 n = int(input()) 41 s = list(input()) 42 for i in range(1,n-1): 43 if (s[i-1] == '1' and s[i+1] == '1'): 44 s[i] = '1' 45 ans1 = 0 46 for i in range(n): 47 if s[i] == '1': 48 ans1 += 1 49 50 for i in range(1,n-1): 51 if (s[i-1] == '1' and s[i+1] == '1'): 52 s[i] = '0' 53 54 for i in range(1,n-1): 55 if (s[i-1] == '1' and s[i+1] == '1'): 56 s[i] = '0' 57 ans = 0 58 for i in range(n): 59 if s[i] == '1': 60 ans += 1 61 print(ans, ans1) 62 ``` 63 64 [2207B - One Night At Freddy's](/contest/2207/problem/B) 65 66 Author: [awang11](/profile/awang11 "International Master awang11") 67 68 Preparers: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 69 70 (Cool) analysis: [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856") 71 72 **Hint 1** 73 74 Which animatronic should you choose with your flashlight? 75 76 **Hint 2** 77 78 How many animatronics are worth incrementing when there are $k$ flashes remaining? 79 80 **Hint 3** 81 82 Write an expression for the ending danger level in terms of the night length and the danger levels of the animatronics that get flashed. 83 84 **Solution** 85 86 Tutorial is loading... 87 88 **Implementation** 89 90 ``` 91 t = int(input()) 92 93 while (t > 0): 94 t -= 1 95 n, m, l = map(int, input().split()) 96 a = list(map(int, input().split())) 97 lvls = [0] * m 98 curr = n 99 for i in range(l): 100 lvls[min(m,curr+1)-1] += 1 101 lvls.sort() 102 lvls = lvls[::-1] 103 if (curr > 0 and a[n-curr]-1 == i): 104 lvls[0] = 0 105 lvls.sort() 106 lvls = lvls[::-1] 107 curr -= 1 108 109 print(lvls[0]) 110 ``` 111 112 **Rate the problem!** 113 114 Awesome! 115 116 Okay... 117 118 I would have rather watched cricket world cup 119 120 [2207C - Where's My Water?](/contest/2207/problem/C) 121 122 Author: [awang11](/profile/awang11 "International Master awang11") 123 124 Preparer: [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 125 126 Analysis: [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 127 128 **Hint 1** 129 130 Solve the case of one drain first! You should aim for $O(n)$. 131 132 **Hint 2** 133 134 If you pick two drains, what's the shape of their overlap? 135 136 **Hint 3** 137 138 Brute force. 139 140 **Solution** 141 142 Tutorial is loading... 143 144 **Implementation** 145 146 Implementation by [misteg168](/profile/misteg168 "International Master misteg168"). 147 148 ``` 149 #include <bits/stdc++.h> 150 using namespace std; 151 #define int long long 152 153 void solve() { 154 int n, h; cin >> n >> h; 155 vector<int> v(n); 156 for (auto &x : v) cin >> x; 157 vector<int> cnt(n); 158 for (int i = 0; i < n; i++) { 159 int curr = v[i]; 160 cnt[i] = h - curr; 161 for (int j = i+1; j < n; j++) 162 curr = max(curr, v[j]), cnt[i] += h - curr; 163 curr = v[i]; 164 for (int j = i-1; j >= 0; j--) 165 curr = max(curr, v[j]), cnt[i] += h - curr; 166 } 167 168 //~ for (int i = 0; i < n; i++) 169 //~ cout << v[i] << "\n"; 170 171 int best = 0; 172 for (int i = 0; i < n; i++) { 173 int mx = v[i], arg = i; 174 for (int j = i; j < n; j++) { 175 if (v[j] > mx) { 176 mx = v[j]; 177 arg = j; 178 } 179 best = max(cnt[i] + cnt[j] - cnt[arg], best); 180 } 181 } 182 cout << best << "\n"; 183 } 184 185 186 signed main() { 187 ios::sync_with_stdio(false); 188 cin.tie(nullptr); 189 int t; cin >> t; 190 while (t--) solve(); 191 } 192 ``` 193 194 **Rate the problem!** 195 196 Awesome! 197 198 Okay... 199 200 I would have rather watched cricket world cup 201 202 **Remark 1** 203 204 There are tons of ways to do this problem, and chances are you found a different one than most other contestants! This problem is solvable in subquadratic time however, can you do it? 205 206 **Remark 2** 207 208 Also, the diagrams in the problem, as well as the ones in all editorials and other problems, are completely drawn natively in tikzpictures. Did you know you can cram 3-D plots onto 2-D to make textured filling? 209 210 [2207D - Boxed Like a Fish](/contest/2207/problem/D) 211 212 Author: [awang11](/profile/awang11 "International Master awang11") 213 214 Preparers: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 215 216 Analysis: [awang11](/profile/awang11 "International Master awang11") 217 218 **Hint 1** 219 220 Let's first think about path graphs. For some $k$, what are the $n$ for which an $n$-path wins for Cyndaquil? 221 222 **Hint 2** 223 224 Between every pair of Cyndaquil-winning nodes a distance of $k$ apart, all the nodes on the path between them also win. How can we find these efficiently? 225 226 **Hint 3** 227 228 Why did we ask for only vertex $v$, and not for all nodes? 229 230 **Hint 4** 231 232 Tree DP. 233 234 **Solution** 235 236 Tutorial is loading... 237 238 **Implementation** 239 240 ``` 241 #include <bits/stdc++.h> 242 243 #define f first 244 #define s second 245 #define pb push_back 246 247 typedef long long int ll; 248 typedef unsigned long long int ull; 249 using namespace std; 250 typedef pair<int,int> pii; 251 252 #define INF 1e9 253 254 vector<vector<int>> adj; 255 256 int N, K, V; 257 258 int dfs(int v, int p = -1) { 259 int l1 = INF; 260 int l2 = INF; 261 for (int u : adj[v]) { 262 if (u != p) { 263 int guy = dfs(u, v); 264 if (guy < l2) swap(l2, guy); 265 if (l2 < l1) swap(l1, l2); 266 } 267 } 268 if (l1 == INF) { 269 return 0; 270 } else if (l2 == INF) { 271 return 1 + l1; 272 } else { 273 int s = 1 + l1; 274 if (l1 + l2 < K) s = 0; 275 return s; 276 } 277 278 // what 279 return -1; 280 } 281 282 int main() { 283 bool debug = 0; 284 ios::sync_with_stdio(0); 285 cin.tie(0); 286 287 int T; cin >> T; 288 while (T--) { 289 cin >> N >> K >> V; 290 adj = vector<vector<int>>(N+1); 291 for (int i = 1; i < N; i++) { 292 int a, b; cin >> a >> b; 293 adj[a].push_back(b); 294 adj[b].push_back(a); 295 } 296 cout << (dfs(V) ? "NO" : "YES") << endl; 297 } 298 299 return 0; 300 } 301 ``` 302 303 **Rate the problem!** 304 305 Awesome! 306 307 Okay... 308 309 I would have rather watched cricket world cup 310 311 [2207E1 - N-MEX (Constructive Version)](/contest/2207/problem/E1) 312 313 Author: [awang11](/profile/awang11 "International Master awang11") 314 315 Preparers: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 316 317 Analysis: [awang11](/profile/awang11 "International Master awang11") 318 319 **Hint 1** 320 321 Write some bounds for the $a_i$. What's the biggest/smallest each one can be? 322 323 **Hint 2** 324 325 Try to pick only numbers that aren't in the $a_i$, and $+\infty$. 326 327 **Solution** 328 329 Tutorial is loading... 330 331 **Implementation** 332 333 ``` 334 INF = 10**9 335 336 T = int(input()) 337 for _ in range(T): 338 N = int(input()) 339 A = list(map(int, input().split())) 340 taken = [False] * (N + 1) 341 ok = True 342 for i in range(N): 343 if not (N - i - 1 <= A[i] <= N): 344 ok = False 345 if i > 0 and A[i] > A[i - 1]: 346 ok = False 347 if not ok: 348 break 349 taken[A[i]] = True 350 if ok: 351 print("YES") 352 ptr = N 353 prev = N 354 for i in range(N): 355 if prev > A[i]: 356 print(INF, end=" ") 357 else: 358 ptr -= 1 359 while taken[ptr]: 360 ptr -= 1 361 print(ptr, end=" ") 362 prev = A[i] 363 print() 364 else: 365 print("NO") 366 ``` 367 368 **Rate the problem!** 369 370 Awesome! 371 372 Okay... 373 374 I would have rather watched cricket world cup 375 376 [2207E2 - N-MEX (Counting Version)](/contest/2207/problem/E2) 377 378 Same credits as E1. 379 380 **Hint 1** 381 382 Read E1's hints first. 383 384 **Hint 2** 385 386 There are actually a very well-constrained set of working solutions. How many times do we pick each number not present in the $a_i$? 387 388 **Solution** 389 390 Tutorial is loading... 391 392 **Implementation** 393 394 Implementation by [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856"). 395 396 ``` 397 #include <bits/stdc++.h> 398 using namespace std; 399 #define int long long 400 #define ll long long 401 #define mod MOD 402 #define pii pair<int,int> 403 #define piii pair<pii,pii> 404 #define fi first 405 #define se second 406 #pragma GCC optimize("O3,unroll-loops") 407 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 408 409 // b banned, j used 410 // condition is that at 0, j+b = v[0]? 411 // b increases every index, j decreases when v[i]=v[i+1] 412 413 const int mod = 1e9+7; 414 415 void solve() { 416 int n; cin >> n; 417 vector<int> v(n); 418 for (int &r:v) cin >> r; 419 for (int i = 0; i < n; i++) { 420 if (v[i]<n-i-1||v[i]>n||i&&v[i]>v[i-1]) { 421 cout << "0\n"; return; 422 } 423 } 424 int ans=1; 425 for (int i = 0; i < n; i++) { 426 if (i&&v[i]==v[i-1]) ans=(ans*(v[i]-(n-i-1)))%mod; 427 else ans=(ans*(i+1))%mod; 428 } 429 cout << ans << "\n"; 430 } 431 432 int32_t main() { 433 ios::sync_with_stdio(0); cin.tie(0); 434 int t=1; cin >> t; 435 while (t--) solve(); 436 } 437 ``` 438 439 **Rate the problem!** 440 441 Awesome! 442 443 Okay... 444 445 I would have rather watched cricket world cup 446 447 [2207F - Hanabi](/contest/2207/problem/F) 448 449 Author: [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 450 451 Preparers: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 452 453 Analysis: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 454 455 **Hint 1** 456 457 Think about how you'd play in the case of only one color. Once you have that, how would you do two colors? 458 459 **Hint 2** 460 461 Each color has some sequence of clues that will get them to be played correctly. How do we coalesce them into one string of clues? 462 463 **Hint 3** 464 465 Some rank clues must be given for all cards to be played. If two consecutive forced rank clues are for ranks $a, b$, is it ever optimal to only rank clue some of the ones between $a, b$? 466 467 **Hint 4** 468 469 There is an $O(n^2)$ dp. How can we speed it up? 470 471 **Solution** 472 473 Tutorial is loading... 474 475 **Implementation** 476 477 ``` 478 #include <bits/stdc++.h> 479 using namespace std; 480 using ll = long long; 481 using ld = long double; 482 #define f first 483 // #define s second 484 #define pb push_back 485 #define pii pair<int,int> 486 #define pll pair<ll, ll> 487 488 struct Tree { 489 typedef ll T; 490 static constexpr T unit = 1e9; 491 T f(T a, T b) { return min(a,b); } 492 vector<T> s; ll n; 493 Tree(ll n = 0, T def = unit) : s(2*n, def), n(n) {} 494 void update(ll pos, T val) { 495 for (s[pos += n] = val; pos /= 2;) 496 s[pos] = f(s[pos * 2], s[pos * 2 + 1]); 497 } 498 T query(ll b, ll e) { 499 ll ra = unit, rb = unit; 500 for (b += n, e += n; b < e; b /= 2, e /= 2) { 501 if (b % 2) ra = f(ra, s[b++]); 502 if (e % 2) rb = f(s[--e], rb); 503 } 504 return f(ra, rb); 505 } 506 T val (ll x) { 507 return query(x, x+1); 508 } 509 }; 510 511 int main() { 512 ios::sync_with_stdio(false); 513 cin.tie(nullptr); 514 ll t; cin >> t; 515 while (t--) { 516 // inpute processing 517 ll n, m; cin >> n >> m; 518 ll nm = n * m; 519 520 ll cards [nm][2]; 521 vector<int> order [m+1]; 522 523 for (int i = 0; i < nm; i++) cin >> cards[i][1]; 524 for (int i = 0; i < nm; i++) cin >> cards[i][0]; 525 526 for (int i = 0; i < nm; i++) { 527 order[cards[i][0]].pb(cards[i][1]); 528 } 529 530 // compute fix clues 531 set<int> fixes [m+1]; 532 for (int i = 1; i <= m; i++) { 533 int curr = 1; 534 for (int j = 0; j < n; j++) { 535 while (order[i][j] > curr) { 536 fixes[i].insert(curr); 537 curr++; 538 } 539 if (order[i][j] == curr) curr++; 540 } 541 fixes[i].insert(0); 542 fixes[i].insert(n+1); 543 } 544 545 set<int> global_fixes; 546 for (int i = 1; i <= m; i++) for (ll x : fixes[i]) global_fixes.insert(x); 547 548 // segtree dp 549 ll dp [n+1][2]; 550 dp[0][0] = 0; dp[0][1] = 0; 551 // cout << dp[0][0] << " " << dp[0][1] << endl; 552 553 Tree dpc (n+1); dpc.update(0, n); 554 555 for (int i = 1; i <= n; i++) { 556 dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 1; 557 dp[i][1] = 1e9; 558 if (global_fixes.count(i)) { 559 // cout << dp[i][0] << " " << dp[i][1] << endl; 560 continue; 561 } 562 563 int colors = m; 564 vector<int> bounds; 565 for (int j = 1; j <= m; j++) { 566 auto it = fixes[j].upper_bound(i); it--; 567 bounds.pb(*it); 568 } 569 bounds.pb(-1); 570 571 sort(bounds.begin(), bounds.end()); 572 573 for (int j = m; j >= 0; j--) { 574 // cout << "B " << j << " " << bounds[j] << " " << dpc.query(bounds[j], i) << endl; 575 dp[i][1] = min(dp[i][1], dpc.query(bounds[j]+1, i) - (n-i+1) + m - j); 576 } 577 dpc.update(i, dp[i][1] + (n-i)); 578 // cout << dp[i][0] << " " << dp[i][1] << endl; 579 } 580 581 cout << min(dp[n][0], dp[n][1]) - 1 << endl; 582 } 583 } 584 ``` 585 586 **Rate the problem!** 587 588 Awesome! 589 590 Okay... 591 592 I would have rather watched cricket world cup 593 594 **Remark 1** 595 596 As suggested by the editorial, this problem was originally about Squid Game! Until we made the round about the 2010s, that is. 597 598 **Remark 2** 599 600 There's actually a way to do this in $O(nm \sqrt{nm})$ or faster with flows! Can you represent the problem as a flow or matching instance? 601 602 [2207G - Toothless](/contest/2207/problem/G) 603 604 Author: [awang11](/profile/awang11 "International Master awang11") 605 606 Preparer: [awang11](/profile/awang11 "International Master awang11") 607 608 Analysis: [awang11](/profile/awang11 "International Master awang11") 609 610 **Hint 1** 611 612 Use Pigeonhole to first solve for the case of no needy cells. 613 614 **Hint 2** 615 616 How can you adjust your solution when there are needy cells? 617 618 **Hint 3** 619 620 The graph is planar. Recall the Euler characteristic formula. 621 622 **Solution** 623 624 Tutorial is loading... 625 626 **Implementation** 627 628 Implementation by [Hori](/profile/Hori "Candidate Master Hori"). 629 630 ``` 631 #include <bits/stdc++.h> 632 using namespace std; 633 #ifdef HORI 634 #include "../lib/hori.h" 635 #else 636 #define debug(...) 637 #endif 638 using vi = vector<int>; 639 using pi = array<int, 2>; 640 using vpi = vector<pi>; 641 #define FOR(i, a, b) for (int i = (a); i < (b); i++) 642 #define all(x) x.begin(), x.end() 643 #define sz(x) int(x.size()) 644 #define nl '\n' 645 auto vec(auto&& v, int n) {return vector(n, v);} 646 auto vec(auto&& v, int n, auto... m) {return vector(n, vec(v, m...));} 647 template <class T> concept C = !is_same<T, string>::value && !is_same_v<std::remove_all_extents_t<T>, char> && ranges::range<T>; 648 template <C T> ostream& operator<<(ostream &os, const T &v) {for (auto x : v) os << x << ' '; return os << nl;} 649 template <C T> istream &operator>>(istream &in, T &v) {for (auto& x : v) in >> x; return in;} 650 #define L(x, ...) ([&] (auto&& x) -> decltype(auto) {return __VA_ARGS__;}) 651 template <class... T> void re(T &...a) {(cin >> ... >> a);} 652 template <class... T> void pr(T... a) {((cout << ' ' << a), ...);} 653 #define def(t, a...) t a; re(a); 654 655 vi dx = {-1, 0, 1, 0}; 656 vi dy = {0, -1, 0, 1}; 657 void solve() { 658 def(int, n, m, a, b); 659 vector<string> g(n); re(g); 660 661 auto get = [&] (int x) { 662 auto v = vec(0ll, n, m); 663 FOR(i, 0, n) FOR(j, 0, m) v[i][j] = (i + j) % 3 != x or g[i][j] == '#'; 664 FOR(i, 0, n) FOR(j, 0, m) if ((i + j) % 3 == x) { 665 while (true) { 666 auto prv = vec(pi{-1, -1}, n, m); 667 auto dfs = [&] (this auto dfs, int r, int c) -> void { 668 FOR(k, 0, 4) { 669 int nr = r + dx[k], nc = c + dy[k]; 670 if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue; 671 if (pi{nr, nc} == prv[r][c] or prv[nr][nc] != pi{-1, -1}) continue; 672 if (!v[nr][nc]) continue; 673 prv[nr][nc] = {r, c}; 674 dfs(nr, nc); 675 } 676 }; 677 dfs(i, j); 678 if (prv[i][j] == pi{-1, -1}) break; 679 int r = i, c = j; 680 while (g[r][c] != '.') { 681 auto [nr, nc] = prv[r][c]; 682 r = nr, c = nc; 683 } 684 v[r][c] = 0; 685 } 686 } 687 int val = 0; 688 FOR(i, 0, n) FOR(j, 0, m) if (v[i][j]) val += (g[i][j] == 'x' ? b : a); 689 return pair{val, v}; 690 }; 691 auto [val, ret] = max({get(0), get(1), get(2)}); 692 debug(val); 693 debug(grid_mode, ret); 694 auto vis = vec(0ll, n, m); 695 vpi v; 696 auto dfs = [&] (this auto dfs, int r, int c) -> void { 697 v.push_back({r + 1, c + 1}); 698 vis[r][c] = 1; 699 FOR(k, 0, 4) { 700 int nr = r + dx[k], nc = c + dy[k]; 701 if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue; 702 if (vis[nr][nc] or !ret[nr][nc]) continue; 703 dfs(nr, nc); 704 } 705 }; 706 FOR(i, 0, n) FOR(j, 0, m) if (ret[i][j] and !vis[i][j]) dfs(i, j); 707 pr(sz(v), nl, v); 708 } 709 710 signed main() { 711 ios::sync_with_stdio(0); cin.tie(0); 712 def(int, t); while (t--) solve(); 713 } 714 ``` 715 716 **Rate the problem!** 717 718 Awesome! 719 720 Okay... 721 722 I would have rather watched cricket world cup 723 724 **Remark / Conjecture** 725 726 It is open to us whether the following cheese is actually provably correct: 727 728 * First attempt to fill in the cells (blind to whether they are special or not) in reading order, adding if it doesn't form a cycle. 729 * Second attempt to fill in the cells, but with special cells first, in reading order, adding if it doesn't form a cycle. 730 731 We conjecture that one of the two always passes. 732 733 [2207H1 - Bowser's Castle (Easy Version)](/contest/2207/problem/H1) 734 735 Author: [awang11](/profile/awang11 "International Master awang11") 736 737 Preparer: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 738 739 Analysis: [awang11](/profile/awang11 "International Master awang11"), [IceSerpent](/profile/IceSerpent "Expert IceSerpent") 740 741 **Hint 1** 742 743 Use 0-1 sorting to make the structure a little simpler. What's a concise way to visualize a min max function? 744 745 **Hint 2** 746 747 The min max function is a tree that alternates min/max across depths. Can you determine the type of the top operation? 748 749 **Hint 3** 750 751 You will need to try a good number of schemes, but try to find a point where you can split $f = \min(g, h)$ or similar. Then, divide and conquer will win. 752 753 **Solution** 754 755 Tutorial is loading... 756 757 **Implementation** 758 759 ``` 760 #include <bits/stdc++.h> 761 762 #define f first 763 #define s second 764 #define pb push_back 765 766 typedef long long int ll; 767 typedef unsigned long long int ull; 768 using namespace std; 769 typedef pair<int,int> pii; 770 typedef pair<ll,ll> pll; 771 772 #define INF 1e9 773 774 int get_int() { 775 int x; cin >> x; 776 if (x == -1) { 777 cout << "Wrong answer" << endl; 778 exit(0); 779 } 780 return x; 781 } 782 783 int ask(vector<int> Q) { 784 cout << "? "; 785 int clip = 100000; 786 for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " "; 787 cout << endl; cout.flush(); 788 return get_int() - clip - 1; 789 } 790 791 struct MMT { 792 int L, R; // range of variables acted on 793 vector<MMT*> subdivisions; // subfamilies 794 bool up, leaf; // type 795 int evals; 796 MMT(int L, int R, vector<MMT*> subdivisions, bool up) { 797 this->L = L; 798 this->R = R; 799 this->subdivisions = subdivisions; 800 this->up = up; 801 this->evals = 0; 802 this->leaf = (L == R); 803 } 804 MMT(int L, int R, bool up, float p = 0.5) { 805 this->L = L; 806 this->R = R; 807 this->up = up; 808 this->evals = 0; 809 this->leaf = (L == R); 810 if (leaf) return; 811 subdivisions = vector<MMT*>(); 812 int prev = L-1; 813 for (int i = L; i < R; i++) { 814 if (rand() < RAND_MAX * p) { 815 subdivisions.push_back(new MMT(prev+1, i, !up, p)); 816 prev = i; 817 } 818 } 819 if (prev == L-1) { 820 for (int i = L; i <= R; i++) { 821 subdivisions.push_back(new MMT(prev+1, i, !up, p)); 822 prev = i; 823 } 824 } else if (prev != R) { 825 subdivisions.push_back(new MMT(prev+1, R, !up, p)); 826 } 827 } 828 string vis() { 829 if (leaf) return "x"+to_string(L); 830 else { 831 string ret; 832 if (up) ret += "max"; 833 else ret += "min"; 834 ret += "("; 835 for (int i = 0; i < subdivisions.size(); i++) { 836 ret += subdivisions[i]->vis(); 837 if (i != subdivisions.size() - 1) ret += ", "; 838 } 839 ret += ")"; 840 return ret; 841 } 842 return "error"; 843 } 844 int eval(const vector<int>& x) { 845 ++evals; 846 if (leaf) return x[L]; 847 int ret; 848 if (up) ret = -INF; 849 else ret = INF; 850 for (auto f : subdivisions) { 851 if (up) ret = max(ret, f->eval(x)); 852 else ret = min(ret, f->eval(x)); 853 } 854 return ret; 855 } 856 void flatten() { 857 if (leaf) return; 858 vector<MMT*> new_subdivisions; 859 for (auto f : subdivisions) { 860 f->flatten(); 861 if (f->up == up && !f->leaf) { 862 for (auto x : f->subdivisions) { 863 new_subdivisions.push_back(x); 864 } 865 } else { 866 new_subdivisions.push_back(f); 867 } 868 } 869 subdivisions = new_subdivisions; 870 } 871 void prune_right() { 872 --R; 873 if (leaf) return; 874 else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) { 875 subdivisions.erase(--subdivisions.end()); 876 } 877 else { 878 (*--subdivisions.end())->prune_right(); 879 } 880 } 881 882 void prune_left() { 883 ++L; 884 if (leaf) return; 885 else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) { 886 subdivisions.erase(subdivisions.begin()); 887 } 888 else { 889 (*subdivisions.begin())->prune_left(); 890 } 891 } 892 }; 893 894 int bs_fwd(int L, int R, bool up, vector<int> defaults) { 895 vector<int> Q1; 896 int L1 = L; 897 int L2 = R; 898 while (L1 < L2) { 899 int M = (L1 + L2) / 2; 900 Q1 = defaults; 901 for (int i = L; i <= M; i++) { 902 Q1[i] = up; 903 } 904 for (int i = M+1; i <= R; i++) { 905 Q1[i] = !up; 906 } 907 if (ask(Q1) == up) L2 = M; 908 else L1 = M+1; 909 } 910 return L1; 911 } 912 913 int bs_rev(int L, int R, bool up, vector<int> defaults) { 914 vector<int> Q1; 915 int L1 = L; 916 int L2 = R; 917 while (L1 < L2) { 918 int M = (L1 + L2 + 1) / 2; 919 Q1 = defaults; 920 for (int i = L; i <= M-1; i++) { 921 Q1[i] = !up; 922 } 923 for (int i = M; i <= R; i++) { 924 Q1[i] = up; 925 } 926 if (ask(Q1) == up) L1 = M; 927 else L2 = M-1; 928 } 929 return L1; 930 } 931 932 MMT* mimic_full(int L, int R, vector<int> defaults) { 933 // if only one index remains there is nothing to do 934 if (L == R) return new MMT(L, R, vector<MMT*>(), 0); 935 936 int s = bs_fwd(L, R, 1, defaults); 937 int t = bs_rev(L, R, 1, defaults); 938 bool up = s < t; 939 940 vector<int> upd_defaults = defaults; 941 for (int i = L; i <= R; i++) upd_defaults[i] = !up; 942 943 int m_fwd = bs_fwd(L, R, up, upd_defaults); 944 int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults); 945 946 int m_rev = bs_rev(L, R, up, upd_defaults); 947 int k_rev = bs_rev(L, m_rev-1, up, upd_defaults); 948 949 vector<int> g_fwd = upd_defaults; 950 vector<int> g_rev = upd_defaults; 951 952 for (int i = L; i < k_fwd; i++) g_fwd[i] = up; 953 for (int i = R; i > k_rev; i--) g_rev[i] = up; 954 955 int fwd_take = -1, rev_take = -1, cut = -1; 956 957 for (int i = 0; i < INF; i++) { 958 g_fwd[L+i] = !up; 959 if (ask(g_fwd) != up) { 960 g_fwd[L+i] = up; 961 fwd_take = L+i; 962 } 963 964 vector<int> check_fwd = g_fwd; 965 for (int j = L+i+1; j <= R; j++) { 966 check_fwd[j] = !up; 967 } 968 969 if (ask(check_fwd) == up) { 970 cut = fwd_take; 971 break; 972 } 973 974 g_rev[R-i] = !up; 975 if (ask(g_rev) != up) { 976 g_rev[R-i] = up; 977 rev_take = R-i; 978 } 979 980 vector<int> check_rev = g_rev; 981 for (int j = L; j <= R-i-1; j++) { 982 check_rev[j] = !up; 983 } 984 985 if (ask(check_rev) == up) { 986 cut = rev_take - 1; 987 break; 988 } 989 } 990 991 vector<int> left_defaults = upd_defaults; 992 for (int i = cut+1; i <= R; i++) left_defaults[i] = !up; 993 994 vector<int> right_defaults = upd_defaults; 995 for (int i = L; i <= cut; i++) right_defaults[i] = !up; 996 997 vector<MMT*> subdivisions; 998 subdivisions.push_back(mimic_full(L, cut, left_defaults)); 999 subdivisions.push_back(mimic_full(cut+1, R, right_defaults)); 1000 return new MMT(L, R, subdivisions, up); 1001 } 1002 1003 MMT* recover(int N) { 1004 return mimic_full(1, N, vector<int>(N+1, 0)); 1005 } 1006 1007 int main() { 1008 bool debug = 0; 1009 // ios::sync_with_stdio(0); 1010 // cin.tie(0); 1011 1012 int T = get_int(); 1013 while (T--) { 1014 int N = get_int(); 1015 MMT* M = recover(N); 1016 cout << "!" << endl; cout.flush(); 1017 while (1) { 1018 vector<int> Q(1, 0); 1019 for (int i = 0; i < N; i++) { 1020 int x = get_int(); 1021 if (x == 0) break; 1022 Q.push_back(x); 1023 } 1024 if (Q.size() > 1) { 1025 cout << M->eval(Q) << endl; cout.flush(); 1026 } else break; 1027 } 1028 } 1029 return 0; 1030 } 1031 ``` 1032 1033 **Rate the problem!** 1034 1035 Awesome! 1036 1037 Okay... 1038 1039 I would have rather watched cricket world cup 1040 1041 [2207H2 - Bowser's Castle (Medium Version)](/contest/2207/problem/H2) 1042 1043 Same credits as H1, main solution due to [244mhq](/profile/244mhq "International Grandmaster 244mhq"). 1044 1045 **Hint 1** 1046 1047 Read the H1 hints. 1048 1049 **Hint 2** 1050 1051 Go for $O(n \log n)$; how can we optimize the previous approach? 1052 1053 **Hint 3** 1054 1055 Determine the top node in $O(\log n)$ time. 1056 1057 **Hint 4** 1058 1059 Scan for your split point from both ends simultaneously. 1060 1061 **Solution** 1062 1063 Tutorial is loading... 1064 1065 **Implementation** 1066 1067 ``` 1068 #include <bits/stdc++.h> 1069 1070 #define f first 1071 #define s second 1072 #define pb push_back 1073 1074 typedef long long int ll; 1075 typedef unsigned long long int ull; 1076 using namespace std; 1077 typedef pair<int,int> pii; 1078 typedef pair<ll,ll> pll; 1079 1080 #define INF 1e9 1081 1082 int get_int() { 1083 int x; cin >> x; 1084 if (x == -1) { 1085 cout << "Wrong answer" << endl; 1086 exit(0); 1087 } 1088 return x; 1089 } 1090 1091 int ask(vector<int> Q) { 1092 cout << "? "; 1093 int clip = 100000; 1094 for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " "; 1095 cout << endl; cout.flush(); 1096 return get_int() - clip - 1; 1097 } 1098 1099 struct MMT { 1100 int L, R; // range of variables acted on 1101 vector<MMT*> subdivisions; // subfamilies 1102 bool up, leaf; // type 1103 int evals; 1104 MMT(int L, int R, vector<MMT*> subdivisions, bool up) { 1105 this->L = L; 1106 this->R = R; 1107 this->subdivisions = subdivisions; 1108 this->up = up; 1109 this->evals = 0; 1110 this->leaf = (L == R); 1111 } 1112 MMT(int L, int R, bool up, float p = 0.5) { 1113 this->L = L; 1114 this->R = R; 1115 this->up = up; 1116 this->evals = 0; 1117 this->leaf = (L == R); 1118 if (leaf) return; 1119 subdivisions = vector<MMT*>(); 1120 int prev = L-1; 1121 for (int i = L; i < R; i++) { 1122 if (rand() < RAND_MAX * p) { 1123 subdivisions.push_back(new MMT(prev+1, i, !up, p)); 1124 prev = i; 1125 } 1126 } 1127 if (prev == L-1) { 1128 for (int i = L; i <= R; i++) { 1129 subdivisions.push_back(new MMT(prev+1, i, !up, p)); 1130 prev = i; 1131 } 1132 } else if (prev != R) { 1133 subdivisions.push_back(new MMT(prev+1, R, !up, p)); 1134 } 1135 } 1136 string vis() { 1137 if (leaf) return "x"+to_string(L); 1138 else { 1139 string ret; 1140 if (up) ret += "max"; 1141 else ret += "min"; 1142 ret += "("; 1143 for (int i = 0; i < subdivisions.size(); i++) { 1144 ret += subdivisions[i]->vis(); 1145 if (i != subdivisions.size() - 1) ret += ", "; 1146 } 1147 ret += ")"; 1148 return ret; 1149 } 1150 return "error"; 1151 } 1152 int eval(const vector<int>& x) { 1153 ++evals; 1154 if (leaf) return x[L]; 1155 int ret; 1156 if (up) ret = -INF; 1157 else ret = INF; 1158 for (auto f : subdivisions) { 1159 if (up) ret = max(ret, f->eval(x)); 1160 else ret = min(ret, f->eval(x)); 1161 } 1162 return ret; 1163 } 1164 void flatten() { 1165 if (leaf) return; 1166 vector<MMT*> new_subdivisions; 1167 for (auto f : subdivisions) { 1168 f->flatten(); 1169 if (f->up == up && !f->leaf) { 1170 for (auto x : f->subdivisions) { 1171 new_subdivisions.push_back(x); 1172 } 1173 } else { 1174 new_subdivisions.push_back(f); 1175 } 1176 } 1177 subdivisions = new_subdivisions; 1178 } 1179 void prune_right() { 1180 --R; 1181 if (leaf) return; 1182 else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) { 1183 subdivisions.erase(--subdivisions.end()); 1184 } 1185 else { 1186 (*--subdivisions.end())->prune_right(); 1187 } 1188 } 1189 1190 void prune_left() { 1191 ++L; 1192 if (leaf) return; 1193 else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) { 1194 subdivisions.erase(subdivisions.begin()); 1195 } 1196 else { 1197 (*subdivisions.begin())->prune_left(); 1198 } 1199 } 1200 }; 1201 1202 int bs_fwd(int L, int R, bool up, vector<int> defaults) { 1203 vector<int> Q1; 1204 int L1 = L; 1205 int L2 = R; 1206 while (L1 < L2) { 1207 int M = (L1 + L2) / 2; 1208 Q1 = defaults; 1209 for (int i = L; i <= M; i++) { 1210 Q1[i] = up; 1211 } 1212 for (int i = M+1; i <= R; i++) { 1213 Q1[i] = !up; 1214 } 1215 if (ask(Q1) == up) L2 = M; 1216 else L1 = M+1; 1217 } 1218 return L1; 1219 } 1220 1221 int bs_rev(int L, int R, bool up, vector<int> defaults) { 1222 vector<int> Q1; 1223 int L1 = L; 1224 int L2 = R; 1225 while (L1 < L2) { 1226 int M = (L1 + L2 + 1) / 2; 1227 Q1 = defaults; 1228 for (int i = L; i <= M-1; i++) { 1229 Q1[i] = !up; 1230 } 1231 for (int i = M; i <= R; i++) { 1232 Q1[i] = up; 1233 } 1234 if (ask(Q1) == up) L1 = M; 1235 else L2 = M-1; 1236 } 1237 return L1; 1238 } 1239 1240 MMT* mimic_full(int L, int R, vector<int> defaults) { 1241 // if only one index remains there is nothing to do 1242 if (L == R) return new MMT(L, R, vector<MMT*>(), 0); 1243 1244 int s = bs_fwd(L, R, 1, defaults); 1245 int t = bs_rev(L, R, 1, defaults); 1246 bool up = s < t; 1247 1248 vector<int> upd_defaults = defaults; 1249 for (int i = L; i <= R; i++) upd_defaults[i] = !up; 1250 1251 int m_fwd = bs_fwd(L, R, up, upd_defaults); 1252 int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults); 1253 1254 int m_rev = bs_rev(L, R, up, upd_defaults); 1255 int k_rev = bs_rev(L, m_rev-1, up, upd_defaults); 1256 1257 vector<int> g_fwd = upd_defaults; 1258 vector<int> g_rev = upd_defaults; 1259 1260 for (int i = L; i < k_fwd; i++) g_fwd[i] = up; 1261 for (int i = R; i > k_rev; i--) g_rev[i] = up; 1262 1263 int fwd_take = -1, rev_take = -1, cut = -1; 1264 1265 for (int i = 0; i < INF; i++) { 1266 g_fwd[L+i] = !up; 1267 if (ask(g_fwd) != up) { 1268 g_fwd[L+i] = up; 1269 fwd_take = L+i; 1270 } 1271 1272 vector<int> check_fwd = g_fwd; 1273 for (int j = L+i+1; j <= R; j++) { 1274 check_fwd[j] = !up; 1275 } 1276 1277 if (ask(check_fwd) == up) { 1278 cut = fwd_take; 1279 break; 1280 } 1281 1282 g_rev[R-i] = !up; 1283 if (ask(g_rev) != up) { 1284 g_rev[R-i] = up; 1285 rev_take = R-i; 1286 } 1287 1288 vector<int> check_rev = g_rev; 1289 for (int j = L; j <= R-i-1; j++) { 1290 check_rev[j] = !up; 1291 } 1292 1293 if (ask(check_rev) == up) { 1294 cut = rev_take - 1; 1295 break; 1296 } 1297 } 1298 1299 vector<int> left_defaults = upd_defaults; 1300 for (int i = cut+1; i <= R; i++) left_defaults[i] = !up; 1301 1302 vector<int> right_defaults = upd_defaults; 1303 for (int i = L; i <= cut; i++) right_defaults[i] = !up; 1304 1305 vector<MMT*> subdivisions; 1306 subdivisions.push_back(mimic_full(L, cut, left_defaults)); 1307 subdivisions.push_back(mimic_full(cut+1, R, right_defaults)); 1308 return new MMT(L, R, subdivisions, up); 1309 } 1310 1311 MMT* recover(int N) { 1312 return mimic_full(1, N, vector<int>(N+1, 0)); 1313 } 1314 1315 int main() { 1316 bool debug = 0; 1317 // ios::sync_with_stdio(0); 1318 // cin.tie(0); 1319 1320 int T = get_int(); 1321 while (T--) { 1322 int N = get_int(); 1323 MMT* M = recover(N); 1324 cout << "!" << endl; cout.flush(); 1325 while (1) { 1326 vector<int> Q(1, 0); 1327 for (int i = 0; i < N; i++) { 1328 int x = get_int(); 1329 if (x == 0) break; 1330 Q.push_back(x); 1331 } 1332 if (Q.size() > 1) { 1333 cout << M->eval(Q) << endl; cout.flush(); 1334 } else break; 1335 } 1336 } 1337 return 0; 1338 } 1339 ``` 1340 1341 **Rate the problem!** 1342 1343 Awesome! 1344 1345 Okay... 1346 1347 I would have rather watched cricket world cup 1348 1349 **Remark** 1350 1351 The music choice across H1, H2, H3 actually follows the level of the final castle in World 8 of New Super Mario Bros Wii. 1352 1353 [2207H3 - Bowser's Castle (Hard Version)](/contest/2207/problem/H3) 1354 1355 Same credits as H1, main solution inspired by [IceSerpent](/profile/IceSerpent "Expert IceSerpent") and [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856"). 1356 1357 **Hint 1** 1358 1359 Read H1 and H2 first. 1360 1361 **Hint 2** 1362 1363 What is $f(1, \dots, n)$? 1364 1365 **Hint 3** 1366 1367 If $t = f(1, \dots, n)$, then $x_t$ is the leaf at an alternating path from root (max goes right, min goes left.) 1368 1369 **Hint 4** 1370 1371 What is $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$? How does it relate to the tree structure of $f(x_1, \dots, x_n)$? 1372 1373 **Hint 5** 1374 1375 You know the number of variables in each child of $f(x_1, \dots, x_t, +\infty, \dots, +\infty)$ and $f(-\infty, \dots, -\infty, x_t, \dots, x_n)$. Can you use these children to assemble $f(x_1, \dots, x_n)$? 1376 1377 **Hint 6** 1378 1379 Work from the inside (two nearest pieces to $x_t$) to the outside with two pointers. How many queries do we use? The recurrence may look quite terrifying, but... 1380 1381 **Solution** 1382 1383 Tutorial is loading... 1384 1385 **Implementation** 1386 1387 ``` 1388 #include <bits/stdc++.h> 1389 1390 #define f first 1391 #define s second 1392 #define pb push_back 1393 1394 typedef long long int ll; 1395 typedef unsigned long long int ull; 1396 using namespace std; 1397 typedef pair<int,int> pii; 1398 1399 #define INF 1e9 1400 1401 int get_int() { 1402 int x; cin >> x; 1403 if (x == -1) { 1404 cout << "Wrong answer" << endl; 1405 exit(0); 1406 } 1407 return x; 1408 } 1409 1410 int ask(vector<int> Q) { 1411 cout << "? "; 1412 int clip = 100000; 1413 for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " "; 1414 cout << endl; cout.flush(); 1415 return get_int() - clip - 1; 1416 } 1417 1418 struct MMT { 1419 int L, R; // range of variables acted on 1420 vector<MMT*> subdivisions; // subfamilies 1421 bool up, leaf; // type 1422 int evals; 1423 MMT(int L, int R, vector<MMT*> subdivisions, bool up) { 1424 this->L = L; 1425 this->R = R; 1426 this->subdivisions = subdivisions; 1427 this->up = up; 1428 this->evals = 0; 1429 this->leaf = (L == R); 1430 } 1431 string vis() { 1432 if (leaf) return "x"+to_string(L); 1433 else { 1434 string ret; 1435 if (up) ret += "max"; 1436 else ret += "min"; 1437 ret += "("; 1438 for (int i = 0; i < subdivisions.size(); i++) { 1439 ret += subdivisions[i]->vis(); 1440 if (i != subdivisions.size() - 1) ret += ", "; 1441 } 1442 ret += ")"; 1443 return ret; 1444 } 1445 return "error"; 1446 } 1447 int eval(const vector<int>& x) { 1448 ++evals; 1449 if (leaf) return x[L]; 1450 int ret; 1451 if (up) ret = -INF; 1452 else ret = INF; 1453 for (auto f : subdivisions) { 1454 if (up) ret = max(ret, f->eval(x)); 1455 else ret = min(ret, f->eval(x)); 1456 } 1457 return ret; 1458 } 1459 void flatten() { 1460 if (leaf) return; 1461 vector<MMT*> new_subdivisions; 1462 for (auto f : subdivisions) { 1463 f->flatten(); 1464 if (f->up == up && !f->leaf) { 1465 for (auto x : f->subdivisions) { 1466 new_subdivisions.push_back(x); 1467 } 1468 } else { 1469 new_subdivisions.push_back(f); 1470 } 1471 } 1472 subdivisions = new_subdivisions; 1473 } 1474 }; 1475 1476 MMT* mimic_smart(int L, int R, vector<int> defaults) { 1477 /** 1478 Returns nullptr if invalid 1479 Otherwise returns an MMT reconstruction defined on indices L..R 1480 **/ 1481 1482 /// Step 1: find the thing 1483 // if only one index remains there is nothing to do 1484 if (L == R) return new MMT(L, R, vector<MMT*>(), 0); 1485 1486 // get representative 1487 vector<int> Q(defaults.begin(), defaults.end()); 1488 for (int i = L; i <= R; i++) Q[i] = i; 1489 int cut = ask(Q); 1490 1491 if (cut == R) { 1492 vector<int> new_defaults = defaults; 1493 new_defaults = -INF; 1494 MMT* rest = mimic_smart(L, R-1, new_defaults); 1495 vector<MMT*> subs = {rest, new MMT(R, R, vector<MMT*>(), 0)}; 1496 return new MMT(L, R, subs, 1); // MAX 1497 } else if (cut == L) { 1498 vector<int> new_defaults = defaults; 1499 new_defaults[cut] = INF; 1500 MMT* rest = mimic_smart(L+1, R, new_defaults); 1501 vector<MMT*> subs = {new MMT(L, L, vector<MMT*>(), 0), rest}; 1502 return new MMT(L, R, subs, 0); // MIN 1503 } 1504 1505 /// Step 2: recurse 1506 // make new defaults 1507 vector<int> defaults_left = defaults; 1508 for (int i = cut + 1; i <= R; i++) defaults_left[i] = INF; 1509 1510 vector<int> defaults_right = defaults; 1511 for (int i = L; i < cut; i++) defaults_right[i] = -INF; 1512 1513 // subdivisions 1514 vector<MMT*> left_subs, right_subs; 1515 1516 // left side 1517 MMT* left = mimic_smart(L, cut, defaults_left); 1518 left->flatten(); 1519 left_subs = left->subdivisions; 1520 left_subs.pop_back(); 1521 1522 // right side 1523 MMT* right = mimic_smart(cut, R, defaults_right); 1524 right->flatten(); 1525 right_subs = right->subdivisions; 1526 reverse(right_subs.begin(), right_subs.end()); 1527 right_subs.pop_back(); 1528 1529 /// Step 3: merge 1530 // merge loop 1531 MMT* ret = new MMT(cut, cut, vector<MMT*>(), 0); 1532 while (left_subs.size() > 0 && right_subs.size() > 0) { 1533 auto left_candidate = left_subs.back(); 1534 auto right_candidate = right_subs.back(); 1535 vector<int> query = defaults; 1536 for (int i = L; i < left_candidate->L; i++) query[i] = 0; 1537 for (int i = left_candidate->L; i <= left_candidate->R; i++) query[i] = 3; 1538 for (int i = left_candidate->R + 1; i < right_candidate->L; i++) query[i] = 2; 1539 for (int i = right_candidate->L; i <= right_candidate->R; i++) query[i] = 1; 1540 for (int i = right_candidate->R + 1; i <= R; i++) query[i] = 4; 1541 1542 int u = ask(query); 1543 1544 if (u == 3) { // MAX is outside 1545 ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN 1546 ret->flatten(); 1547 right_subs.pop_back(); 1548 } else if (u == 1) { // MIN is outside 1549 ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX 1550 ret->flatten(); 1551 left_subs.pop_back(); 1552 } else { 1553 // something went really wrong 1554 cout << "uh oh, merge died" << endl; 1555 exit(67); 1556 } 1557 } 1558 1559 while (left_subs.size()) { 1560 auto left_candidate = left_subs.back(); 1561 ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX 1562 ret->flatten(); 1563 left_subs.pop_back(); 1564 } 1565 1566 while (right_subs.size()) { 1567 auto right_candidate = right_subs.back(); 1568 ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN 1569 ret->flatten(); 1570 right_subs.pop_back(); 1571 } 1572 1573 return ret; 1574 } 1575 1576 MMT* recover(int N) { 1577 MMT* M = mimic_smart(1, N, vector<int>(N+1, 0)); 1578 return M; 1579 } 1580 1581 int main() { 1582 bool debug = 0; 1583 // ios::sync_with_stdio(0); 1584 // cin.tie(0); 1585 1586 int T; cin >> T; 1587 while (T--) { 1588 int N; cin >> N; 1589 MMT* M = recover(N); 1590 cout << "!" << endl; cout.flush(); 1591 while (1) { 1592 vector<int> Q(1, 0); 1593 for (int i = 0; i < N; i++) { 1594 int x = get_int(); 1595 if (x == 0) break; 1596 Q.push_back(x); 1597 } 1598 if (Q.size() > 1) { 1599 cout << M->eval(Q) << endl; cout.flush(); 1600 } else break; 1601 } 1602 } 1603 return 0; 1604 } 1605 ``` 1606 1607 **Rate the problem!** 1608 1609 Awesome! 1610 1611 Okay... 1612 1613 I would have rather watched cricket world cup 1614 1615 **Remark 1** 1616 1617 The solution due to [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856") and incidentally the one in contest found by [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") actually uses only $2n$ queries! 1618 1619 **Remark 2** 1620 1621 A naive entropy bound gives a lower bound of $n / \log n$ queries; can we push this to linear so our upper bound of $O(n)$ queries becomes asymptotically tight? 1622 1623 We apologize for the unexpectedly difficult B, but we hope you enjoyed thinking about the problems regardless! 1624 1625 Special thanks to [Hori](/profile/Hori "Candidate Master Hori"), [nik_exists](/profile/nik_exists "Specialist nik_exists"), [awesomeguy856](/profile/awesomeguy856 "Grandmaster awesomeguy856"), [shcal](/profile/shcal "Candidate Master shcal") for their assistance with problems F through H3. We also acknowledge [Amazed](/profile/Amazed "Expert Amazed"), [chromate00](/profile/chromate00 "Expert chromate00"), [defnotmee](/profile/defnotmee "Grandmaster defnotmee"), [Noobish_Monk](/profile/Noobish_Monk "Master Noobish_Monk"), [awoo](/profile/awoo "Grandmaster awoo"), [misteg168](/profile/misteg168 "International Master misteg168"), [cduckling](/profile/cduckling "Specialist cduckling") for sticking with us in copy-editing and improving statements up until the contest. Once again, a huge thanks to [flummoxedfeline](/profile/flummoxedfeline "Unrated, flummoxedfeline") for making our round look beautiful. Without them this round wouldn't be complete. 1626 1627 Implementations will be added soon. 1628 1629 