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 K is fixed, then for any i in range [K+1, N] it's possible to flip the bit at position i: 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 i in range [1, N-K]. To flip the bit at position i: 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.