Overview

Given a 0/1 sequence of length \(N\), determine whether it is possible to make all elements 1 by performing any number of interval flips (0↔1) of length \(K\), and if so, find the minimum number of operations.

Analysis

Key Insight (Greedy from left to right works)

When looking at light \(i\), the only operations that can still change the state of light \(i\) are “interval flips whose left endpoint is at most \(i\).”
Specifically, for an interval flip that includes position \(i\), the left endpoint \(l\) satisfies \(l \le i \le l+K-1\), so \(l \le i\) is required.

Therefore, scanning from left to right:

• If light \(i\) is currently 0, the only way to turn it to 1 is to perform a flip starting exactly at position \(i\) (since all choices for positions to the left have already been decided).
• If light \(i\) is currently 1, performing an unnecessary flip here would turn it to 0, so we do nothing.

This greedy approach is valid. It also automatically guarantees the minimum number of operations (since at each \(i\), the only choices are exactly 1 operation if needed, or 0 otherwise).

Why the naive approach is too slow

If we flip each bit in the length-\(K\) interval every time we perform an operation, each operation costs \(O(K)\). In the worst case, \(O(N)\) operations can occur, leading to a total of \(O(NK)\), which is too slow for \(N \le 5\times 10^5\).

How to solve it efficiently (manage only the parity of flip counts)

Since flipping an even number of times leaves the value unchanged and an odd number of times inverts it, all we need for each position \(i\) is: - The parity (0/1) of the number of flips affecting position \(i\).

To manage this efficiently, we use a difference array (so-called imos method) that records “when a flip’s effect expires.”

Algorithm

Scan from left to right, \(i=0,1,\dots,N-1\) (explained using 0-indexing below).

• parity: the parity of the number of flips currently affecting position \(i\) (0 = even, 1 = odd)
• end[t]: whether parity needs to be flipped when we reach position \(t\) (a marker indicating that an interval flip’s effect ends at \(t\))

Procedure: 1. At each \(i\), first perform parity ^= end[i] to account for expired flip effects. 2. The actual current bit is: $\( \text{bit} = S[i] \oplus \text{parity} \)\( (if `parity=1`, the value appears flipped). 3. If `bit == 0`, then a flip starting at position \)i\( is required to turn light \)i\( on. - If the interval \)[i, i+K-1]\( cannot be formed (\)i+K>N\(), it is impossible, so output `-1`. - Otherwise, increment the operation count: `ops += 1`. - The flip begins, so `parity ^= 1`. - Mark that the flip ends at \)i+K$: end[i+K] ^= 1. 4. If we successfully process all positions, ops is the minimum number of operations.

Concrete Example

Let \(N=5, K=3, S=00101\).

• \(i=0\): Currently 0 → perform operation (flip positions 0..2). ops=1
• \(i=1\): The flip is in effect, so the apparent value changes. If needed, perform an operation… and so on. At each position, the rule “if it’s currently 0, we must flip starting here” is repeated, ensuring no unnecessary operations.

Complexity

• Time complexity: \(O(N)\) (only constant-time updates at each position)
• Space complexity: \(O(N)\) (for the end array)

Implementation Notes

• Since characters S[i] are '0'/'1', we convert to 0/1 using ord(S[i]) - 48 (using int(S[i]) also works).

• The end array is made of length N+1 so that when \(i+K = N\), we can safely write to end[N].

• Since we only use the parity rather than the actual flip count, all updates are done with XOR (^= 1).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = input().strip()

    end = [0] * (N + 1)
    parity = 0
    ops = 0

    for i in range(N):
        parity ^= end[i]
        bit = (ord(S[i]) - 48) ^ parity
        if bit == 0:
            if i + K > N:
                print(-1)
                return
            ops += 1
            parity ^= 1
            end[i + K] ^= 1

    print(ops)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.