Here is the Atcoder ARC/ABC — D problem from today's contest.

https://arc088.contest.atcoder.jp/tasks/arc088_b

The editorial describes an O(n) solution.

My question is about a different solution. When I first saw this problem I thought binary search on the radius would work, but quickly discarded the idea because I could not think of a correct "check" function to see if a given radius works.

However, minimario proved me wrong.

Here is his code: https://hastebin.com/qefuquxoke.cpp

In his check function, he assumes that "k to n is fixed" and "0 to n-k-1 fixed", which seems to be the basis of the function's logic. (I ran his code by hand, but it still feels like magic to me)

Can anybody elaborate on the reasoning behind this solution?

I'll use 1-base index, because it's easier to explain.

If

Kis fixed, then for anyiin range [K+1, N] it's possible to flip the bit at positioni: first flip segment [1, i], then flip segment [1, i-1]. So you can set bits at positions [K+1, N] to any value you want.The same applies for any

iin range [1, N-K]. To flip the bit at positioni: first flip segment [i, N], then flip segment [i+1, N].But you cannot use this method to change values in range [N-K+1, K], so all bits in this range must be equal.