Binary Strings are Simple?

Observation 1: rotations are not scary

Take a substring $S$ of length $m$ with $k$ ones, and let $x_i$ be the inversion count of the $i$-th left rotation.

When the first character is moved to the end:

• if it is $0$, it gains $k$ inversions;
• if it is $1$, it loses $m-k$ inversions, which is the same as adding $k$ modulo $m$.

So always

$$x_{i+1}\equiv x_i+k\pmod m.$$

The values in $a$ form an arithmetic progression modulo $m$ with step $k$. A step-$k$ walk on a cycle of size $m$ visits exactly

$$\frac{m}{\gcd(m,k)}$$

different residues. Therefore

$$f(l,r)=\frac{m}{\gcd(m,k)}.$$

That is the first slap in the face: the inversion circus only tells us a gcd.

Observation 2: even lengths give parity

Suppose $m$ is even. From the answer we know

$$g=\frac{m}{f(l,r)}=\gcd(m,k).$$

Because $m$ is even, $g$ is odd exactly when $k$ is odd. Hence

$$k\bmod 2 = \left(\frac{m}{f(l,r)}\right)\bmod 2.$$

So any even-length query tells us the XOR of the bits in that substring.

Observation 3: turn it into prefix XORs

Let

$$P_0=0,\qquad P_i=s_1\oplus s_2\oplus\cdots\oplus s_i.$$

For an even-length query $[l,r]$, the number of ones in the substring modulo $2$ is

$$P_r\oplus P_{l-1}.$$

Also, since $r-(l-1)=r-l+1$ is even, the two prefix indices $l-1$ and $r$ have the same parity. So queries only connect even prefix indices to even prefix indices, and odd prefix indices to odd prefix indices. The two worlds never talk. Annoying, but useful.

The missing bit

$P_0$ is fixed as $0$, so the even prefix component has an absolute value. But $P_1$ is unknown, so the odd component can be flipped entirely.

If we choose $P_1=0$, we reconstruct one candidate. If the real value was $P_1=1$, then every odd prefix parity is toggled. Since every bit is

$$s_i=P_i\oplus P_{i-1},$$

and adjacent prefix indices have opposite parity, toggling all odd prefixes flips every bit. Therefore the only ambiguity is between a string and its complement. The statement allows two guesses, so this is not a bug, it is the intended loophole.

Choosing cheap queries

For each parity $c\in\{0,1\}$, consider the prefix indices

$$c,\ c+2,\ c+4,\ldots,\ L,$$

where $L$ is the largest prefix index at most $n$ with parity $c$.

For every node $x\ne c$ in this parity class, connect $x$ to whichever endpoint, $c$ or $L$, is farther away. If the edge is between prefix indices $u<v$, ask the substring $[u+1,v]$. Its length is even, so the returned value gives the edge label

$$P_u\oplus P_v.$$

This graph is connected: $L$ connects to $c$, and every other node connects to either $c$ or $L$. So we can DFS/BFS and recover all prefix parities, up to the single odd-component flip described above.

Cost proof

In one parity class, write $L=c+2M$. There are $M$ queried edges. For node $x=c+2j$, the queried length is

$$d_j=\max(2j,2(M-j)).$$

Since $\max(j,M-j)\ge M/2$, we have

$$d_j\ge M.$$

Thus the total cost inside this parity class is at most

$$\sum_{j=1}^{M}\frac{n}{d_j}\le \sum_{j=1}^{M}\frac{n}{M}=n.$$

There are two parity classes, so the total query cost is at most

$$2n\le \max(30,3n).$$

We use exactly $n-1$ queries and at most $2$ guesses.

Complexity

The number of queries is $O(n)$, the local computation is $O(n)$, and the memory usage is $O(n)$. The cost budget is bounded by $2n$.

Cross-check sources: Codeforces problem statement and official Codeforces tutorial.