Bowser's Castle (Easy Version)

Booleanize the castle

The huge value range is bait. We only query values $1$ and $2$ and subtract $1$ from the answer, so every query is a Boolean query:

$b_i=[x_i=2],\quad \max=\lor,\quad \min=\land.$

So the unknown function is an ordered read-once monotone Boolean formula. Every subtree owns a contiguous interval of variables. We will recover some equivalent tree; Bowser does not care whether our parentheses match his, only whether the function matches.

Important for hacks: this is still an interactive solution. The hack expression is read by the interactor, not by your program.

Recovering one interval

Suppose we are learning the restricted function on $[L,R]$, while all variables outside are fixed to values that make ancestor siblings neutral. First determine whether the top operation is $\max$ or $\min$.

Let $A(m)$ be the answer when $L\ldots m$ are $1$ and $m+1\ldots R$ are $0$. Let $s$ be the first $m$ with $A(m)=1$. Let $B(m)$ be the answer when $L\ldots m-1$ are $0$ and $m\ldots R$ are $1$. Let $t$ be the last $m$ with $B(m)=1$.

If the root is $\max$, a left child and a right child can independently make the answer $1$, so $s<t$. If the root is $\min$, making the answer $1$ requires all top children, so any successful prefix must reach far right and any successful suffix must reach far left, giving $s\ge t$. Thus:

$\text{root is }\max \iff s<t.$

Now write $u=1$ for a $\max$ root and $u=0$ for a $\min$ root. The other value $z=1-u$ is neutral for that root operation. The root outputs $u$ iff at least one top child outputs $u$.

Finding a split

We need a cut $c$ such that

$F_{L,R}=\operatorname{op}(F_{L,c},F_{c+1,R}).$

The annoying part is that the first prefix producing $u$ can stop inside the first top child. Example: $\max(\min(x_1,\max(x_2,x_3)),x_4)$ becomes $1$ already at prefix $x_1,x_2$, not at the true boundary after $x_3$. Cute trap. Also rude.

Set every variable in $[L,R]$ to $z$. Find $p$, the first position where setting $L\ldots p$ to $u$ makes the answer $u$. Then find $q$, the first position where setting $p+1\ldots q$ to $u$ makes the answer $u$. The block $L\ldots q-1$ contains enough variables to activate the first top child, but not enough to activate a later top child.

Start with $L\ldots q-1$ set to $u$ and everything else set to $z$. Sweep left to right. Try changing the current variable back to $z$:

• if the answer stays $u$, delete it;
• otherwise restore it and remember this index as the latest forced variable.

After each step, also test whether the current prefix alone still gives $u$ after all variables to its right are reset to $z$. When this first happens, the latest forced variable is exactly the right end of the first top child, so it is a valid cut $c$.

Why? The greedy deletion pushes every witness as far right as possible. In a same-operation subtree, one child is enough, so the witness slides right. In an opposite-operation subtree, every child is needed, so the rightmost child contributes a forced variable. Inductively, the last forced variable lands on the subtree boundary. Sounds magical; it is just min/max being brutally monotone.

Recursion and answering

After finding $c$, recurse on $[L,c]$ and $[c+1,R]$, passing defaults where the other side is neutral. This isolates the child function exactly. A leaf interval is just $x_i$.

After printing !, evaluate the recovered tree on Bowser's real inputs using ordinary $\min$ and $\max$.

Complexity

For an interval of length $m$, we use $O(\log m)$ queries for binary searches and $O(m)$ queries for the greedy sweep. Over a binary recursion tree on $n$ ordered leaves,

$\sum m = O(n^2),$

so the total query count is $O(n^2)$. With $n\le 70$, this is comfortably below $10^4$; no sweaty nonsense required.

Reference checked while writing: official Codeforces editorial.