If there are two consecutive zeroes, can you ever change either of them?

Awesome!

Okay...

I would have rather watched cricket world cup

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(input())
    for i in range(1,n-1):
        if (s[i-1] == '1' and s[i+1] == '1'):
            s[i] = '1'
    ans1 = 0
    for i in range(n):
        if s[i] == '1':
            ans1 += 1
    
    for i in range(1,n-1):
        if (s[i-1] == '1' and s[i+1] == '1'):
            s[i] = '0'
    
    for i in range(1,n-1):
        if (s[i-1] == '1' and s[i+1] == '1'):
            s[i] = '0'
    ans = 0
    for i in range(n):
        if s[i] == '1':
            ans += 1
    print(ans, ans1)

Which animatronic should you choose with your flashlight?

How many animatronics are worth incrementing when there are $$$k$$$ flashes remaining?

Write an expression for the ending danger level in terms of the night length and the danger levels of the animatronics that get flashed.

t = int(input())
 
while (t > 0):
    t -= 1
    n, m, l = map(int, input().split())
    a = list(map(int, input().split()))
    lvls = [0] * m
    curr = n
    for i in range(l):
        lvls[min(m,curr+1)-1] += 1
        lvls.sort()
        lvls = lvls[::-1]
        if (curr > 0 and a[n-curr]-1 == i):
            lvls[0] = 0
            lvls.sort()
            lvls = lvls[::-1]
            curr -= 1
 
    print(lvls[0])

Awesome!

Okay...

I would have rather watched cricket world cup

Solve the case of one drain first! You should aim for $$$O(n)$$$.

If you pick two drains, what's the shape of their overlap?

Brute force.

Implementation by misteg168.

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve() {
	int n, h; cin >> n >> h;
	vector<int> v(n);
	for (auto &x : v) cin >> x;
	vector<int> cnt(n);
	for (int i = 0; i < n; i++) {
		int curr = v[i];
		cnt[i] = h - curr;
		for (int j = i+1; j < n; j++)
			curr = max(curr, v[j]), cnt[i] += h - curr;
		curr = v[i];
		for (int j = i-1; j >= 0; j--)
			curr = max(curr, v[j]), cnt[i] += h - curr;
	}
	
	//~ for (int i = 0; i < n; i++)
		//~ cout << v[i] << "\n";
	
	int best = 0;
	for (int i = 0; i < n; i++) {
		int mx = v[i], arg = i;
		for (int j = i; j < n; j++) {
			if (v[j] > mx) {
				mx = v[j];
				arg = j;
			}
			best = max(cnt[i] + cnt[j] - cnt[arg], best);
		}
	}
	cout << best << "\n";
}
 
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t; cin >> t;
	while (t--) solve();
}

Awesome!

Okay...

I would have rather watched cricket world cup

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?

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?

Let's first think about path graphs. For some $$$k$$$, what are the $$$n$$$ for which an $$$n$$$-path wins for Cyndaquil?

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?

Why did we ask for only vertex $$$v$$$, and not for all nodes?

Tree DP.

#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
 
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;

#define INF 1e9
 
vector<vector<int>> adj;
 
int N, K, V;
 
int dfs(int v, int p = -1) {
    int l1 = INF;
    int l2 = INF;
    for (int u : adj[v]) {
        if (u != p) {
            int guy = dfs(u, v);
            if (guy < l2) swap(l2, guy);
            if (l2 < l1) swap(l1, l2);
        }
    }
    if (l1 == INF) {
        return 0;
    } else if (l2 == INF) {
        return 1 + l1;
    } else {
        int s = 1 + l1;
        if (l1 + l2 < K) s = 0;
        return s;
    }
 
    // what
    return -1;
}
 
int main() {
    bool debug = 0;
	ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T; cin >> T;
    while (T--) {
        cin >> N >> K >> V;
        adj = vector<vector<int>>(N+1);
        for (int i = 1; i < N; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        cout << (dfs(V) ? "NO" : "YES") << endl;
    }
 
    return 0;
}

Awesome!

Okay...

I would have rather watched cricket world cup

Write some bounds for the $$$a_i$$$. What's the biggest/smallest each one can be?

Try to pick only numbers that aren't in the $$$a_i$$$, and $$$+\infty$$$.

INF = 10**9
 
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    taken = [False] * (N + 1)
    ok = True
    for i in range(N):
        if not (N - i - 1 <= A[i] <= N):
            ok = False
        if i > 0 and A[i] > A[i - 1]:
            ok = False
        if not ok:
            break
        taken[A[i]] = True
    if ok:
        print("YES")
        ptr = N
        prev = N
        for i in range(N):
            if prev > A[i]:
                print(INF, end=" ")
            else:
                ptr -= 1
                while taken[ptr]:
                    ptr -= 1
                print(ptr, end=" ")
            prev = A[i]
        print()
    else:
        print("NO")

Awesome!

Okay...

I would have rather watched cricket world cup

Read E1's hints first.

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$$$?

Implementation by awesomeguy856.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long 
#define mod MOD
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
// b banned, j used
// condition is that at 0, j+b = v[0]? 
// b increases every index, j decreases when v[i]=v[i+1]
 
const int mod = 1e9+7; 
 
void solve() {
    int n; cin >> n; 
    vector<int> v(n);
    for (int &r:v) cin >> r; 
    for (int i = 0; i < n; i++) {
        if (v[i]<n-i-1||v[i]>n||i&&v[i]>v[i-1]) {
            cout << "0\n"; return; 
        }
    }
    int ans=1; 
    for (int i = 0; i < n; i++) {
        if (i&&v[i]==v[i-1]) ans=(ans*(v[i]-(n-i-1)))%mod;
        else ans=(ans*(i+1))%mod; 
    }
    cout << ans << "\n"; 
}
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t=1; cin >> t;
    while (t--) solve(); 
}

Awesome!

Okay...

I would have rather watched cricket world cup

Think about how you'd play in the case of only one color. Once you have that, how would you do two colors?

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?

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$$$?

There is an $$$O(n^2)$$$ dp. How can we speed it up?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define f first
// #define s second
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll, ll>
 
struct Tree {
    typedef ll T;
    static constexpr T unit = 1e9;
    T f(T a, T b) { return min(a,b); }
    vector<T> s; ll n;
    Tree(ll n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(ll pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(ll b, ll e) {
        ll ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
    T val (ll x) {
        return query(x, x+1);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t; cin >> t;
    while (t--) {
        // inpute processing
        ll n, m; cin >> n >> m;
        ll nm = n * m;
 
        ll cards [nm][2];
        vector<int> order [m+1];
 
        for (int i = 0; i < nm; i++) cin >> cards[i][1];
        for (int i = 0; i < nm; i++) cin >> cards[i][0];
 
        for (int i = 0; i < nm; i++) {
            order[cards[i][0]].pb(cards[i][1]);
        }
 
        // compute fix clues
        set<int> fixes [m+1];
        for (int i = 1; i <= m; i++) {
            int curr = 1;
            for (int j = 0; j < n; j++) {
                while (order[i][j] > curr) {
                    fixes[i].insert(curr);
                    curr++;
                }
                if (order[i][j] == curr) curr++;
            }
            fixes[i].insert(0);
            fixes[i].insert(n+1);
        }
 
        set<int> global_fixes;
        for (int i = 1; i <= m; i++) for (ll x : fixes[i]) global_fixes.insert(x);
 
        // segtree dp
        ll dp [n+1][2];
        dp[0][0] = 0; dp[0][1] = 0;
        // cout << dp[0][0] << " " << dp[0][1] << endl;
 
        Tree dpc (n+1); dpc.update(0, n);
 
        for (int i = 1; i <= n; i++) {
            dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 1;
            dp[i][1] = 1e9;
            if (global_fixes.count(i)) {
                // cout << dp[i][0] << " " << dp[i][1] << endl;
                continue;
            }
 
            int colors = m;
            vector<int> bounds;
            for (int j = 1; j <= m; j++) {
                auto it = fixes[j].upper_bound(i); it--;
                bounds.pb(*it);
            }
            bounds.pb(-1);
 
            sort(bounds.begin(), bounds.end());
 
            for (int j = m; j >= 0; j--) {
                // cout << "B " << j << " " << bounds[j] << " " << dpc.query(bounds[j], i) << endl;
                dp[i][1] = min(dp[i][1], dpc.query(bounds[j]+1, i) - (n-i+1) + m - j);
            }
            dpc.update(i, dp[i][1] + (n-i));
            // cout << dp[i][0] << " " << dp[i][1] << endl;
        }
 
        cout << min(dp[n][0], dp[n][1]) - 1 << endl;
    }
}

Awesome!

Okay...

I would have rather watched cricket world cup

As suggested by the editorial, this problem was originally about Squid Game! Until we made the round about the 2010s, that is.

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?

Use Pigeonhole to first solve for the case of no needy cells.

How can you adjust your solution when there are needy cells?

The graph is planar. Recall the Euler characteristic formula.

Implementation by Hori.

#include <bits/stdc++.h>
using namespace std;
#ifdef HORI
#include "../lib/hori.h"
#else
#define debug(...)
#endif
using vi = vector<int>;
using pi = array<int, 2>;
using vpi = vector<pi>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define nl '\n'
auto vec(auto&& v, int n) {return vector(n, v);}
auto vec(auto&& v, int n, auto... m) {return vector(n, vec(v, m...));}
template <class T> concept C = !is_same<T, string>::value && !is_same_v<std::remove_all_extents_t<T>, char> && ranges::range<T>;
template <C T> ostream& operator<<(ostream &os, const T &v) {for (auto x : v) os << x << ' '; return os << nl;}
template <C T> istream &operator>>(istream &in, T &v) {for (auto& x : v) in >> x; return in;}
#define L(x, ...) ([&] (auto&& x) -> decltype(auto) {return __VA_ARGS__;})
template <class... T> void re(T &...a) {(cin >> ... >> a);}
template <class... T> void pr(T... a) {((cout << ' ' << a), ...);}
#define def(t, a...) t a; re(a);
 
vi dx = {-1, 0, 1, 0};
vi dy = {0, -1, 0, 1};
void solve() {
  def(int, n, m, a, b);
  vector<string> g(n); re(g);
 
  auto get = [&] (int x) {
    auto v = vec(0ll, n, m);
    FOR(i, 0, n) FOR(j, 0, m) v[i][j] = (i + j) % 3 != x or g[i][j] == '#';  
    FOR(i, 0, n) FOR(j, 0, m) if ((i + j) % 3 == x) {
      while (true) {
        auto prv = vec(pi{-1, -1}, n, m);
        auto dfs = [&] (this auto dfs, int r, int c) -> void {
          FOR(k, 0, 4) {
            int nr = r + dx[k], nc = c + dy[k];
            if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
            if (pi{nr, nc} == prv[r][c] or prv[nr][nc] != pi{-1, -1}) continue;
            if (!v[nr][nc]) continue;
            prv[nr][nc] = {r, c};
            dfs(nr, nc);
          }
        };
        dfs(i, j);
        if (prv[i][j] == pi{-1, -1}) break;
        int r = i, c = j;
        while (g[r][c] != '.') {
          auto [nr, nc] = prv[r][c];
          r = nr, c = nc;
        }
        v[r][c] = 0;
      }
    }
    int val = 0;
    FOR(i, 0, n) FOR(j, 0, m) if (v[i][j]) val += (g[i][j] == 'x' ? b : a);
    return pair{val, v};
  };
  auto [val, ret] = max({get(0), get(1), get(2)});
  debug(val);
  debug(grid_mode, ret);
  auto vis = vec(0ll, n, m);
  vpi v;
  auto dfs = [&] (this auto dfs, int r, int c) -> void {
    v.push_back({r + 1, c + 1});
    vis[r][c] = 1;
    FOR(k, 0, 4) {
      int nr = r + dx[k], nc = c + dy[k];
      if (nr < 0 or nr >= n or nc < 0 or nc >= m) continue;
      if (vis[nr][nc] or !ret[nr][nc]) continue;
      dfs(nr, nc);
    }
  };
  FOR(i, 0, n) FOR(j, 0, m) if (ret[i][j] and !vis[i][j]) dfs(i, j);
  pr(sz(v), nl, v);
}
 
signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  def(int, t); while (t--) solve();
}

Awesome!

Okay...

I would have rather watched cricket world cup

It is open to us whether the following cheese is actually provably correct:

• 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.

• Second attempt to fill in the cells, but with special cells first, in reading order, adding if it doesn't form a cycle.

We conjecture that one of the two always passes.

Use 0-1 sorting to make the structure a little simpler. What's a concise way to visualize a min max function?

The min max function is a tree that alternates min/max across depths. Can you determine the type of the top operation?

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.

#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
 
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define INF 1e9
 
int get_int() {
    int x; cin >> x;
    if (x == -1) {
        cout << "Wrong answer" << endl;
        exit(0);
    }
    return x;
}
 
int ask(vector<int> Q) {
    cout << "? ";
    int clip = 100000;
    for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
    cout << endl; cout.flush();
    return get_int() - clip - 1;
}
 
struct MMT {
    int L, R; // range of variables acted on
    vector<MMT*> subdivisions; // subfamilies
    bool up, leaf; // type
    int evals;
    MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
        this->L = L;
        this->R = R;
        this->subdivisions = subdivisions;
        this->up = up;
        this->evals = 0;
        this->leaf = (L == R);
    }
    MMT(int L, int R, bool up, float p = 0.5) {
        this->L = L;
        this->R = R;
        this->up = up;
        this->evals = 0;
        this->leaf = (L == R);
        if (leaf) return;
        subdivisions = vector<MMT*>();
        int prev = L-1;
        for (int i = L; i < R; i++) {
            if (rand() < RAND_MAX * p) {
                subdivisions.push_back(new MMT(prev+1, i, !up, p));
                prev = i;
            }
        }
        if (prev == L-1) {
            for (int i = L; i <= R; i++) {
                subdivisions.push_back(new MMT(prev+1, i, !up, p));
                prev = i;
            }
        } else if (prev != R) {
            subdivisions.push_back(new MMT(prev+1, R, !up, p));
        }
    }
    string vis() {
        if (leaf) return "x"+to_string(L);
        else {
            string ret;
            if (up) ret += "max";
            else ret += "min";
            ret += "(";
            for (int i = 0; i < subdivisions.size(); i++) {
                ret += subdivisions[i]->vis();
                if (i != subdivisions.size() - 1) ret += ", ";
            }
            ret += ")";
            return ret;
        }
        return "error";
    }
    int eval(const vector<int>& x) {
        ++evals;
        if (leaf) return x[L];
        int ret;
        if (up) ret = -INF;
        else ret = INF;
        for (auto f : subdivisions) {
            if (up) ret = max(ret, f->eval(x));
            else ret = min(ret, f->eval(x));
        }
        return ret;
    }
    void flatten() {
        if (leaf) return;
        vector<MMT*> new_subdivisions;
        for (auto f : subdivisions) {
            f->flatten();
            if (f->up == up && !f->leaf) {
                for (auto x : f->subdivisions) {
                    new_subdivisions.push_back(x);
                }
            } else {
                new_subdivisions.push_back(f);
            }
        }
        subdivisions = new_subdivisions;
    }
    void prune_right() {
        --R;
        if (leaf) return;
        else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) {
            subdivisions.erase(--subdivisions.end());
        }
        else {
            (*--subdivisions.end())->prune_right();
        }
    }
 
    void prune_left() {
        ++L;
        if (leaf) return;
        else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) {
            subdivisions.erase(subdivisions.begin());
        }
        else {
            (*subdivisions.begin())->prune_left();
        }
    }
};
 
int bs_fwd(int L, int R, bool up, vector<int> defaults) {
    vector<int> Q1;
    int L1 = L;
    int L2 = R;
    while (L1 < L2) {
        int M = (L1 + L2) / 2;
        Q1 = defaults;
        for (int i = L; i <= M; i++) {
            Q1[i] = up;
        }
        for (int i = M+1; i <= R; i++) {
            Q1[i] = !up;
        }
        if (ask(Q1) == up) L2 = M;
        else L1 = M+1;
    }
    return L1;
}
 
int bs_rev(int L, int R, bool up, vector<int> defaults) {
    vector<int> Q1;
    int L1 = L;
    int L2 = R;
    while (L1 < L2) {
        int M = (L1 + L2 + 1) / 2;
        Q1 = defaults;
        for (int i = L; i <= M-1; i++) {
            Q1[i] = !up;
        }
        for (int i = M; i <= R; i++) {
            Q1[i] = up;
        }
        if (ask(Q1) == up) L1 = M;
        else L2 = M-1;
    }
    return L1;
}
 
MMT* mimic_full(int L, int R, vector<int> defaults) {
    // if only one index remains there is nothing to do
    if (L == R) return new MMT(L, R, vector<MMT*>(), 0);
 
    int s = bs_fwd(L, R, 1, defaults);
    int t = bs_rev(L, R, 1, defaults);
    bool up = s < t;
 
    vector<int> upd_defaults = defaults;
    for (int i = L; i <= R; i++) upd_defaults[i] = !up;
 
    int m_fwd = bs_fwd(L, R, up, upd_defaults);
    int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults);
 
    int m_rev = bs_rev(L, R, up, upd_defaults);
    int k_rev = bs_rev(L, m_rev-1, up, upd_defaults);
 
    vector<int> g_fwd = upd_defaults;
    vector<int> g_rev = upd_defaults;
 
    for (int i = L; i < k_fwd; i++) g_fwd[i] = up;
    for (int i = R; i > k_rev; i--) g_rev[i] = up;
 
    int fwd_take = -1, rev_take = -1, cut = -1;
 
    for (int i = 0; i < INF; i++) {
        g_fwd[L+i] = !up;
        if (ask(g_fwd) != up) {
            g_fwd[L+i] = up;
            fwd_take = L+i;
        }
 
        vector<int> check_fwd = g_fwd;
        for (int j = L+i+1; j <= R; j++) {
            check_fwd[j] = !up;
        }
 
        if (ask(check_fwd) == up) {
            cut = fwd_take;
            break;
        }
 
        g_rev[R-i] = !up;
        if (ask(g_rev) != up) {
            g_rev[R-i] = up;
            rev_take = R-i;
        }
 
        vector<int> check_rev = g_rev;
        for (int j = L; j <= R-i-1; j++) {
            check_rev[j] = !up;
        }
 
        if (ask(check_rev) == up) {
            cut = rev_take - 1;
            break;
        }
    }
 
    vector<int> left_defaults = upd_defaults;
    for (int i = cut+1; i <= R; i++) left_defaults[i] = !up;
 
    vector<int> right_defaults = upd_defaults;
    for (int i = L; i <= cut; i++) right_defaults[i] = !up;
 
    vector<MMT*> subdivisions;
    subdivisions.push_back(mimic_full(L, cut, left_defaults));
    subdivisions.push_back(mimic_full(cut+1, R, right_defaults));
    return new MMT(L, R, subdivisions, up);
}
 
MMT* recover(int N) {
    return mimic_full(1, N, vector<int>(N+1, 0));
}
 
int main() {
    bool debug = 0;
	// ios::sync_with_stdio(0);
	// cin.tie(0);
 
	int T = get_int();
	while (T--) {
        int N = get_int();
        MMT* M = recover(N);
        cout << "!" << endl; cout.flush();
        while (1) {
            vector<int> Q(1, 0);
            for (int i = 0; i < N; i++) {
                int x = get_int();
                if (x == 0) break;
                Q.push_back(x);
            }
            if (Q.size() > 1) {
                cout << M->eval(Q) << endl; cout.flush();
            } else break;
        }
	}
	return 0;
}

Awesome!

Okay...

I would have rather watched cricket world cup

Read the H1 hints.

Go for $$$O(n \log n)$$$; how can we optimize the previous approach?

Determine the top node in $$$O(\log n)$$$ time.

Scan for your split point from both ends simultaneously.

#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
 
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define INF 1e9
 
int get_int() {
    int x; cin >> x;
    if (x == -1) {
        cout << "Wrong answer" << endl;
        exit(0);
    }
    return x;
}
 
int ask(vector<int> Q) {
    cout << "? ";
    int clip = 100000;
    for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
    cout << endl; cout.flush();
    return get_int() - clip - 1;
}
 
struct MMT {
    int L, R; // range of variables acted on
    vector<MMT*> subdivisions; // subfamilies
    bool up, leaf; // type
    int evals;
    MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
        this->L = L;
        this->R = R;
        this->subdivisions = subdivisions;
        this->up = up;
        this->evals = 0;
        this->leaf = (L == R);
    }
    MMT(int L, int R, bool up, float p = 0.5) {
        this->L = L;
        this->R = R;
        this->up = up;
        this->evals = 0;
        this->leaf = (L == R);
        if (leaf) return;
        subdivisions = vector<MMT*>();
        int prev = L-1;
        for (int i = L; i < R; i++) {
            if (rand() < RAND_MAX * p) {
                subdivisions.push_back(new MMT(prev+1, i, !up, p));
                prev = i;
            }
        }
        if (prev == L-1) {
            for (int i = L; i <= R; i++) {
                subdivisions.push_back(new MMT(prev+1, i, !up, p));
                prev = i;
            }
        } else if (prev != R) {
            subdivisions.push_back(new MMT(prev+1, R, !up, p));
        }
    }
    string vis() {
        if (leaf) return "x"+to_string(L);
        else {
            string ret;
            if (up) ret += "max";
            else ret += "min";
            ret += "(";
            for (int i = 0; i < subdivisions.size(); i++) {
                ret += subdivisions[i]->vis();
                if (i != subdivisions.size() - 1) ret += ", ";
            }
            ret += ")";
            return ret;
        }
        return "error";
    }
    int eval(const vector<int>& x) {
        ++evals;
        if (leaf) return x[L];
        int ret;
        if (up) ret = -INF;
        else ret = INF;
        for (auto f : subdivisions) {
            if (up) ret = max(ret, f->eval(x));
            else ret = min(ret, f->eval(x));
        }
        return ret;
    }
    void flatten() {
        if (leaf) return;
        vector<MMT*> new_subdivisions;
        for (auto f : subdivisions) {
            f->flatten();
            if (f->up == up && !f->leaf) {
                for (auto x : f->subdivisions) {
                    new_subdivisions.push_back(x);
                }
            } else {
                new_subdivisions.push_back(f);
            }
        }
        subdivisions = new_subdivisions;
    }
    void prune_right() {
        --R;
        if (leaf) return;
        else if ((*--subdivisions.end())->L == (*--subdivisions.end())->R) {
            subdivisions.erase(--subdivisions.end());
        }
        else {
            (*--subdivisions.end())->prune_right();
        }
    }
 
    void prune_left() {
        ++L;
        if (leaf) return;
        else if ((*subdivisions.begin())->L == (*subdivisions.begin())->R) {
            subdivisions.erase(subdivisions.begin());
        }
        else {
            (*subdivisions.begin())->prune_left();
        }
    }
};
 
int bs_fwd(int L, int R, bool up, vector<int> defaults) {
    vector<int> Q1;
    int L1 = L;
    int L2 = R;
    while (L1 < L2) {
        int M = (L1 + L2) / 2;
        Q1 = defaults;
        for (int i = L; i <= M; i++) {
            Q1[i] = up;
        }
        for (int i = M+1; i <= R; i++) {
            Q1[i] = !up;
        }
        if (ask(Q1) == up) L2 = M;
        else L1 = M+1;
    }
    return L1;
}
 
int bs_rev(int L, int R, bool up, vector<int> defaults) {
    vector<int> Q1;
    int L1 = L;
    int L2 = R;
    while (L1 < L2) {
        int M = (L1 + L2 + 1) / 2;
        Q1 = defaults;
        for (int i = L; i <= M-1; i++) {
            Q1[i] = !up;
        }
        for (int i = M; i <= R; i++) {
            Q1[i] = up;
        }
        if (ask(Q1) == up) L1 = M;
        else L2 = M-1;
    }
    return L1;
}
 
MMT* mimic_full(int L, int R, vector<int> defaults) {
    // if only one index remains there is nothing to do
    if (L == R) return new MMT(L, R, vector<MMT*>(), 0);
 
    int s = bs_fwd(L, R, 1, defaults);
    int t = bs_rev(L, R, 1, defaults);
    bool up = s < t;
 
    vector<int> upd_defaults = defaults;
    for (int i = L; i <= R; i++) upd_defaults[i] = !up;
 
    int m_fwd = bs_fwd(L, R, up, upd_defaults);
    int k_fwd = bs_fwd(m_fwd+1, R, up, upd_defaults);
 
    int m_rev = bs_rev(L, R, up, upd_defaults);
    int k_rev = bs_rev(L, m_rev-1, up, upd_defaults);
 
    vector<int> g_fwd = upd_defaults;
    vector<int> g_rev = upd_defaults;
 
    for (int i = L; i < k_fwd; i++) g_fwd[i] = up;
    for (int i = R; i > k_rev; i--) g_rev[i] = up;
 
    int fwd_take = -1, rev_take = -1, cut = -1;
 
    for (int i = 0; i < INF; i++) {
        g_fwd[L+i] = !up;
        if (ask(g_fwd) != up) {
            g_fwd[L+i] = up;
            fwd_take = L+i;
        }
 
        vector<int> check_fwd = g_fwd;
        for (int j = L+i+1; j <= R; j++) {
            check_fwd[j] = !up;
        }
 
        if (ask(check_fwd) == up) {
            cut = fwd_take;
            break;
        }
 
        g_rev[R-i] = !up;
        if (ask(g_rev) != up) {
            g_rev[R-i] = up;
            rev_take = R-i;
        }
 
        vector<int> check_rev = g_rev;
        for (int j = L; j <= R-i-1; j++) {
            check_rev[j] = !up;
        }
 
        if (ask(check_rev) == up) {
            cut = rev_take - 1;
            break;
        }
    }
 
    vector<int> left_defaults = upd_defaults;
    for (int i = cut+1; i <= R; i++) left_defaults[i] = !up;
 
    vector<int> right_defaults = upd_defaults;
    for (int i = L; i <= cut; i++) right_defaults[i] = !up;
 
    vector<MMT*> subdivisions;
    subdivisions.push_back(mimic_full(L, cut, left_defaults));
    subdivisions.push_back(mimic_full(cut+1, R, right_defaults));
    return new MMT(L, R, subdivisions, up);
}
 
MMT* recover(int N) {
    return mimic_full(1, N, vector<int>(N+1, 0));
}
 
int main() {
    bool debug = 0;
	// ios::sync_with_stdio(0);
	// cin.tie(0);
 
	int T = get_int();
	while (T--) {
        int N = get_int();
        MMT* M = recover(N);
        cout << "!" << endl; cout.flush();
        while (1) {
            vector<int> Q(1, 0);
            for (int i = 0; i < N; i++) {
                int x = get_int();
                if (x == 0) break;
                Q.push_back(x);
            }
            if (Q.size() > 1) {
                cout << M->eval(Q) << endl; cout.flush();
            } else break;
        }
	}
	return 0;
}

Awesome!

Okay...

I would have rather watched cricket world cup

The music choice across H1, H2, H3 actually follows the level of the final castle in World 8 of New Super Mario Bros Wii.

Read H1 and H2 first.

What is $$$f(1, \dots, n)$$$?

If $$$t = f(1, \dots, n)$$$, then $$$x_t$$$ is the leaf at an alternating path from root (max goes right, min goes left.)

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)$$$?

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)$$$?

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...

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back

typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
typedef pair<int,int> pii;

#define INF 1e9

int get_int() {
    int x; cin >> x;
    if (x == -1) {
        cout << "Wrong answer" << endl;
        exit(0);
    }
    return x;
}

int ask(vector<int> Q) {
    cout << "? ";
    int clip = 100000;
    for (int i = 1; i < Q.size(); i++) cout << max(-clip, min(clip, Q[i])) + clip + 1 << " ";
    cout << endl; cout.flush();
    return get_int() - clip - 1;
}

struct MMT {
    int L, R; // range of variables acted on
    vector<MMT*> subdivisions; // subfamilies
    bool up, leaf; // type
    int evals;
    MMT(int L, int R, vector<MMT*> subdivisions, bool up) {
        this->L = L;
        this->R = R;
        this->subdivisions = subdivisions;
        this->up = up;
        this->evals = 0;
        this->leaf = (L == R);
    }
    string vis() {
        if (leaf) return "x"+to_string(L);
        else {
            string ret;
            if (up) ret += "max";
            else ret += "min";
            ret += "(";
            for (int i = 0; i < subdivisions.size(); i++) {
                ret += subdivisions[i]->vis();
                if (i != subdivisions.size() - 1) ret += ", ";
            }
            ret += ")";
            return ret;
        }
        return "error";
    }
    int eval(const vector<int>& x) {
        ++evals;
        if (leaf) return x[L];
        int ret;
        if (up) ret = -INF;
        else ret = INF;
        for (auto f : subdivisions) {
            if (up) ret = max(ret, f->eval(x));
            else ret = min(ret, f->eval(x));
        }
        return ret;
    }
    void flatten() {
        if (leaf) return;
        vector<MMT*> new_subdivisions;
        for (auto f : subdivisions) {
            f->flatten();
            if (f->up == up && !f->leaf) {
                for (auto x : f->subdivisions) {
                    new_subdivisions.push_back(x);
                }
            } else {
                new_subdivisions.push_back(f);
            }
        }
        subdivisions = new_subdivisions;
    }
};

MMT* mimic_smart(int L, int R, vector<int> defaults) {
    /**
        Returns nullptr if invalid
        Otherwise returns an MMT reconstruction defined on indices L..R
    **/

    /// Step 1: find the thing
    // if only one index remains there is nothing to do
    if (L == R) return new MMT(L, R, vector<MMT*>(), 0);

    // get representative
    vector<int> Q(defaults.begin(), defaults.end());
    for (int i = L; i <= R; i++) Q[i] = i;
    int cut = ask(Q);

    if (cut == R) {
        vector<int> new_defaults = defaults;
        new_defaults = -INF;
        MMT* rest = mimic_smart(L, R-1, new_defaults);
        vector<MMT*> subs = {rest, new MMT(R, R, vector<MMT*>(), 0)};
        return new MMT(L, R, subs, 1); // MAX
    } else if (cut == L) {
        vector<int> new_defaults = defaults;
        new_defaults[cut] = INF;
        MMT* rest = mimic_smart(L+1, R, new_defaults);
        vector<MMT*> subs = {new MMT(L, L, vector<MMT*>(), 0), rest};
        return new MMT(L, R, subs, 0); // MIN
    }

    /// Step 2: recurse
    // make new defaults
    vector<int> defaults_left = defaults;
    for (int i = cut + 1; i <= R; i++) defaults_left[i] = INF;

    vector<int> defaults_right = defaults;
    for (int i = L; i < cut; i++) defaults_right[i] = -INF;

    // subdivisions
    vector<MMT*> left_subs, right_subs;

    // left side
    MMT* left = mimic_smart(L, cut, defaults_left);
    left->flatten();
    left_subs = left->subdivisions;
    left_subs.pop_back();

    // right side
    MMT* right = mimic_smart(cut, R, defaults_right);
    right->flatten();
    right_subs = right->subdivisions;
    reverse(right_subs.begin(), right_subs.end());
    right_subs.pop_back();

    /// Step 3: merge
    // merge loop
    MMT* ret = new MMT(cut, cut, vector<MMT*>(), 0);
    while (left_subs.size() > 0 && right_subs.size() > 0) {
        auto left_candidate = left_subs.back();
        auto right_candidate = right_subs.back();
        vector<int> query = defaults;
        for (int i = L; i < left_candidate->L; i++) query[i] = 0;
        for (int i = left_candidate->L; i <= left_candidate->R; i++) query[i] = 3;
        for (int i = left_candidate->R + 1; i < right_candidate->L; i++) query[i] = 2;
        for (int i = right_candidate->L; i <= right_candidate->R; i++) query[i] = 1;
        for (int i = right_candidate->R + 1; i <= R; i++) query[i] = 4;

        int u = ask(query);

        if (u == 3) { // MAX is outside
            ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN
            ret->flatten();
            right_subs.pop_back();
        } else if (u == 1) { // MIN is outside
            ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX
            ret->flatten();
            left_subs.pop_back();
        } else {
            // something went really wrong
            cout << "uh oh, merge died" << endl;
            exit(67);
        }
    }

    while (left_subs.size()) {
        auto left_candidate = left_subs.back();
        ret = new MMT(left_candidate->L, ret->R, {left_candidate, ret}, 1); // MAX
        ret->flatten();
        left_subs.pop_back();
    }

    while (right_subs.size()) {
        auto right_candidate = right_subs.back();
        ret = new MMT(ret->L, right_candidate->R, {ret, right_candidate}, 0); // MIN
        ret->flatten();
        right_subs.pop_back();
    }

    return ret;
}

MMT* recover(int N) {
    MMT* M = mimic_smart(1, N, vector<int>(N+1, 0));
    return M;
}

int main() {
    bool debug = 0;
	// ios::sync_with_stdio(0);
	// cin.tie(0);

	int T; cin >> T;
	while (T--) {
        int N; cin >> N;
        MMT* M = recover(N);
        cout << "!" << endl; cout.flush();
        while (1) {
            vector<int> Q(1, 0);
            for (int i = 0; i < N; i++) {
                int x = get_int();
                if (x == 0) break;
                Q.push_back(x);
            }
            if (Q.size() > 1) {
                cout << M->eval(Q) << endl; cout.flush();
            } else break;
        }
	}
	return 0;
}

Awesome!

Okay...

I would have rather watched cricket world cup

The solution due to awesomeguy856 and incidentally the one in contest found by ecnerwala actually uses only $$$2n$$$ queries!

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?