Overview

When you can flip \(K\) consecutive light bulbs at a time, we use a greedy approach that “fixes each position” from left to right to determine whether all bulbs can be turned on (\(0\)) and find the minimum number of operations.

Analysis

Key Observation

• The state of each bulb is a binary value \(0/1\), and the flip operation is “\(0 \leftrightarrow 1\)”, so for each bulb, only “how many times it has been flipped (even or odd number of times)” matters.
• When scanning from left to right, the operations that can affect bulb at position \(i\) are those with starting positions from \(i-K+1\) to \(i\). In particular, it is impossible to fix position \(i\) by starting an operation further to the right (if the starting position is \(i+1\) or later, it won’t include \(i\)).

Therefore, scanning from left to right: - If the “actual state” at the current point is \(1\) (off), we must start a flip at position \(i\).

This greedy approach is valid. It also yields the minimum number of operations (since we only flip when necessary).

Why the Naive Approach Doesn’t Work

If we actually flip the interval \([i, i+K)\) each time we perform an operation, each operation costs \(O(K)\), leading to \(O(NK)\) in the worst case, which is too slow for \(N=2\times 10^5\).

Solution

We only need to track “how many times (parity) the current position has been flipped by previous operations.” - By maintaining when each flip’s effect “starts and ends” using a difference array, we can process each position in \(O(1)\).

Algorithm

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

1. Let cur be “the parity of the number of flips affecting the current position (0: even, 1: odd).”
2. Prepare an array diff of length \(N+1\), where diff[x]=1 means “toggle the flip effect (cur) at position \(x\)” (difference array).
3. For each position \(i\):
   • Apply cur ^= diff[i] to reflect “flips whose effect ends here.”
   • The actual apparent state is \(A[i] \oplus cur\).
     • If this is \(1\), the bulb is off, so the only way to fix it is to start a flip of length \(K\) at position \(i\).

          - If $i+K > N$, the interval goes out of bounds, so it's impossible → `-1`.
          - Otherwise, increment the operation count and reflect the start of the flip:
       

       • cur ^= 1 (from now on, the next \(K\) positions have one more flip)
       • diff[i+K] ^= 1 (the effect of this flip ends at position \(i+K\))

If we can proceed to the end without contradiction, the obtained operation count is the minimum.

(Example) - If the apparent state at some position \(i\) is \(1\), it is impossible to fix it by starting an operation that includes that position from a later starting point, so there is no choice but to flip at that position.

Complexity

• Time complexity: \(O(N)\) (constant work per position)
• Space complexity: \(O(N)\) (difference array diff)

Implementation Notes

• Since cur and diff only need to track parity, using XOR (^=) instead of addition is concise.

• diff needs to be of length \(N+1\) because we access i+K (and i+K == N is a valid access).

• Since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    diff = [0] * (N + 1)
    cur = 0
    ans = 0

    for i in range(N):
        cur ^= diff[i]
        if (A[i] ^ cur) == 1:
            if i + K > N:
                print(-1)
                return
            ans += 1
            cur ^= 1
            diff[i + K] ^= 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.