Optimal Shifts

The operation looks more complicated than it is. Strip away the wording and it says this:

If a position is currently 1, then choosing shift $d$ can make the position $d$ steps to its right become 1 too. This happens for all current 1s at once.

So 1s spread clockwise around the cyclic string.

The obvious strategy is already optimal

Suppose we choose $d=1$.

Then every current 1 copies itself one position to the right. If we do that again, the newly created 1s also copy themselves one more position to the right.

After doing shift $1$ exactly $k$ times, every position whose nearest original 1 on the left is at distance at most $k$ becomes 1.

That means the only thing stopping us is the longest cyclic block of consecutive 0s.

Let that length be $g$.

For example, in:

10101010100

there is a cyclic zero block of length $2$ at the end: 00. So the answer is $2$.

Do shift $1$ twice, and every zero gets swallowed. Very cinematic. Very low budget.

Why the answer is at most $g$

Every block of zeros sits immediately after some 1 on the circle.

If a zero block has length $x$, then doing shift $1$ repeatedly fills it from left to right:

• after $1$ coin, the first zero becomes 1
• after $2$ coins, the second zero becomes 1
• and so on

Since every zero block has length at most $g$, after $g$ shifts of size $1$, all zero blocks are gone.

So:

Why the answer is at least $g$

Now take one longest cyclic block of zeros, length $g$.

It looks like this around the circle:

1 0 0 0 ... 0 1
  <--- g zeros --->

Focus on the last zero in this block, the one right before the next original 1.

From the original 1 on the left, this zero is exactly $g$ steps to the right. There is no original 1 closer to it from the left, because this whole stretch is zeros.

Now imagine trying to make this position 1 with total cost less than $g$.

Each operation shifts copied 1s to the right by its chosen $d$, and costs exactly $d$. If the total cost is less than $g$, then along any chain of copied 1s, you have moved less than $g$ total steps to the right.

So you cannot reach that last zero from the previous original 1. And no other original 1 reaches it faster clockwise, because this was a longest zero gap and this target is inside it.

Therefore any successful plan must spend at least $g$ coins:

Combine both sides:

So the entire problem is just: find the longest cyclic run of 0s. The scary operation text was mostly there to mug you in an alley.

How to compute the longest cyclic zero run

Because the string is cyclic, a zero run can wrap around the end into the beginning.

The clean trick is to scan s + s and count consecutive zeros, while capping the answer at $n$.

Since the statement guarantees at least one 1, the true answer is never $n$, but the cap keeps the scan honest.

For each character in s+s:

• if it is 0, increase the current zero-run length
• otherwise reset it to $0$
• update the best answer with min(current, n)

That best value is the answer.

Complexity

For each test case, we scan $2n$ characters, so the time complexity is:

The sum of all $n$ is at most $2\cdot 10^5$, so this is easily fast enough.