Interactive RBS (Hard Version)

The problem is interactive, so the solution is about designing queries. The hacked input gives the hidden string to the interactor, not to your program. Your program still only sees $t$, then each $n$, then the answers to its own queries.

The key is to stop thinking of $f$ as some scary bracket DP monster. We only need to manufacture query strings whose $f$ value carries encoded bits.

Tiny primitive

For a string of length $2$:

• $f(\texttt{"()"})=1$,
• every other two-character bracket string has value $0$.

So if we query two indices $(a,b)$, the answer tells us whether $s_a=\texttt{'('}$ and $s_b=\texttt{')'}$.

That is useful, but one bit per query is way too slow for the hard version. We need batching.

Finding one known closing bracket

We first find an index $c$ such that $s_c=\texttt{')'}$.

Ask the whole sequence $1,2,\ldots,n$.

If the answer is $0$, then the original string has no non-empty regular bracket substring. Any non-empty regular bracket sequence contains some adjacent (), so the string has no () substring. Since the string contains both bracket types, all ) must come before all (. Therefore $s_1=\texttt{')'}$, so we can take $c=1$.

Otherwise, the full sequence has answer positive. Now binary search the smallest prefix length $r$ such that

The prefix before it had no regular substring, and after appending $s_r$ one appears. Any newly appearing regular substring must end at position $r$, and every non-empty regular bracket sequence ends with ). So $s_r=\texttt{')'}$. Take $c=r$.

This costs at most

queries.

One position with a triangular number

Suppose $c$ is known to be ). For an unknown position $i$, build this query block:

i c i c i c ... i c

with $m$ copies of $(i,c)$.

If $s_i=\texttt{')'}$, the entire block is only closing brackets, so it contributes $0$.

If $s_i=\texttt{'('}$, the block is

()()...()

with $m$ pairs. In this string, every consecutive group of complete pairs is a regular bracket substring. There are

such substrings.

So this block contributes either $0$ or the triangular number $T_m=\frac{m(m+1)}2$. Nice little payload. Brackets doing binary espionage, basically.

Combining blocks safely

If we just concatenate blocks, regular substrings might span across neighboring blocks, which would corrupt the sum. That is the annoying part.

The fix is simple: after each block, append one extra known closing bracket $c$.

For position $i_j$ with repetition count $m_j$, use:

(i_j c) repeated m_j times, then c

If $i_j$ is (, this looks like $m_j$ copies of () followed by one extra ). If a substring starts inside this block and tries to cross that extra ), its balance eventually drops below zero, so it cannot be regular. If $i_j$ is ), the block is just closing brackets anyway.

Therefore every block is independent, and the query answer is exactly

Now the problem becomes: choose weights $T_{m_j}$ so that every subset sum is uniquely decodable.

Superincreasing weights

Use weights where every weight is larger than the sum of all previous weights. Then decoding is greedy:

• look at the largest weight,
• if the answer is at least that weight, that position was ( and subtract it,
• otherwise it was ),
• continue downward.

The repetition counts

produce triangular weights

and these are superincreasing.

The length of one query for all 12 positions is

which is safely below the limit $1000$.

So each query classifies up to 12 positions.

Query count

• Find one known ) in at most $11$ queries.
• Classify all $n\le 1000$ positions in chunks of $12$, costing at most $\lceil 1000/12\rceil=84$ queries.

Total:

Yes, it fits. Barely enough to feel intentional.

Correctness proof

First, the algorithm correctly finds a closing bracket. If the whole sequence has $f=0$, then it has no regular substring, hence no adjacent (). Since both bracket types exist, all closing brackets must appear before all opening brackets, so position $1$ is ). Otherwise, the algorithm binary searches the first prefix with positive $f$. The newly created regular substring must end at that prefix's last character, and every non-empty regular bracket sequence ends with ), so that position is a closing bracket.

Next, consider one classification block for index $i$ and repetition count $m$. If $s_i=\texttt{')'}$, the block contains only closing brackets and contributes $0$. If $s_i=\texttt{'('}$, the block contains $m$ consecutive copies of (), whose regular substrings are exactly all consecutive groups of complete pairs, so it contributes $T_m=\frac{m(m+1)}2$.

The extra closing bracket after every block prevents any regular substring from crossing between blocks, because any substring that includes this separator after starting before it has negative balance at that separator. Therefore the answer to a batched query is exactly the sum of the weights corresponding to positions that are (.

The chosen weights are superincreasing, so every possible subset has a unique sum, and greedy decoding from largest to smallest recovers exactly which queried positions were (. All other queried positions are ).

Since every position is included in exactly one classification chunk, the algorithm reconstructs every character of $s$ correctly.

Complexity

The algorithm uses at most $95$ queries per test case. Each query length is at most $1000$. The local computation is tiny: $O(n)$ aside from printing query indices.