Interactive RBS (Medium Version)

For the hacked version, the input literally gives you the hidden bracket sequence. So the AC code can just read $s$ and print it. That feels illegal, but it is exactly how converted interactive problems are hacked: the interactor is gone, and the secret data is now normal input.

Still, the interesting part is the intended interactive idea, so let's unpack that too.

What does a tiny query tell us?

For a string of length $2$:

• $f(\texttt{"()"})=1$
• $f(\texttt{"(("})=f(\texttt{"))"})=f(\texttt{")("})=0$

So a query on two indices $(a,b)$ answers whether $s_a=\texttt{'('}$ and $s_b=\texttt{')'}$.

That is already almost the whole problem. If we somehow know one opening index $O$ and one closing index $C$, then for any index $i$:

• query $(i,C)$
• if the answer is $1$, then $s_i=\texttt{'('}$
• otherwise $s_i=\texttt{')'}$

Why? Because $s_C$ is known to be $\texttt{')'}$, so $s_i s_C$ is regular exactly when $s_i$ is $\texttt{'('}$.

So the problem reduces to: find one known ( and one known ) quickly.

Finding an opposite pair

The string contains at least one ( and one ), but they might be arranged like:

$$\texttt{))))(((}$$

In that case there is no adjacent $\texttt{"()"}$ transition. So searching only for adjacent $\texttt{"()"}$ in the original order is not enough in full generality.

A reliable trick is to compare indices against index $1$ using length-2 queries.

Query $(1,i)$:

• returns $1$ iff $s_1=\texttt{'('}$ and $s_i=\texttt{')'}$

Query $(i,1)$:

• returns $1$ iff $s_i=\texttt{'('}$ and $s_1=\texttt{')'}$

For every $i>1$, if either query returns $1$, then index $1$ and index $i$ are opposite brackets, and we know which is which.

Naively doing both directions for all $i$ costs up to $2(n-1)$ queries, too many for the interactive medium version when $n=1000$.

Batching with powers of two

The key observation is that repeated indices are allowed, and $k\le 1000$. This lets us pack many yes/no tests into one query by using binary weights.

Suppose we want to test whether each index $x_j$ is ) while index $O$ is known or suspected to be (. Build one query like this:

$$(O,x_0),\ (O,x_1),(O,x_1),\ (O,x_2),(O,x_2),(O,x_2),(O,x_2),\ldots$$

More cleanly: include the pair $(O,x_j)$ exactly $2^j$ times.

If $s_O=\texttt{'('}$, then each repeated pair contributes exactly $2^j$ to $f$, because every pair is an isolated $\texttt{"()"}$. The returned value's binary representation tells which $x_j$ are closing brackets.

There is one technical annoyance: regular substrings longer than $2$ could accidentally appear across pair boundaries. To avoid that mess, separate tests with a harmless blocker pattern, or use a construction whose total contribution is known and isolated. This is where the official interactive-style solutions get a bit fiddly: they design query strings so each tested bit has an independent contribution.

For learning purposes, the big idea is the important one: encode many bracket tests into one integer answer using repeated indices and binary weights. That is why the tags include bitmasks.

A simpler 200-query route

There is also a clean conceptual route:

1. Find one pair of opposite brackets using grouped/binary-search queries.
2. Once one ( and one ) are known, classify all positions in batches using weighted repeated pairs.
3. Decode the answer as a bitmask.

This gets comfortably under $200$ queries for $n\le 1000$.

But for the submitted hacked solution

The judge input is:

• $t$
• for each test case: $n$
• then the hidden sequence $s$

There are no actual queries. There is no interactor to answer them. If you print query lines, you are just yelling into the void. The correct non-interactive solution is therefore:

1. read $n$
2. read $s$
3. output $s$

That's not a clever algorithm; it's just the consequence of the hack format. Interactive-to-standard conversions are weird like that.