codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](/predownloaded/94/6e/946e024636b88c0e9c5da0b5cba4286bd405add7.jpg)