Overview

A problem where you can flip the state of \(K\) consecutive lights in a single operation, and you need to find the minimum number of operations to turn all lights “on.”

Analysis

The key insight of this problem is that “operations are performed on intervals, but ultimately only whether each light is on or off matters.”

Important Observations

• The final state of each light is determined by how many times it has been flipped.
• If the number of flips is even, the state remains unchanged; if odd, it is toggled.
• Therefore, we only need to consider the “parity (even/odd) of how many times each light was operated on.”

Issues with a Naive Approach

For example, trying all combinations of intervals is not feasible since \(N\) can be up to \(5 \times 10^5\) (it would take exponential time).

One might also wonder whether simply processing greedily from left to right works — and indeed this is the correct approach. The reason is: - Operations act additively on intervals, so by processing from left to right, all operations affecting a given light have already been handled. - If a light is still not turned on, it can be fixed by performing an operation on an interval starting at that position.

Solution Method

• To efficiently manage how many times operations have been applied to an interval, we use a sliding window with difference updates.
• Specifically, we manage operation starting positions with a queue, and when an interval ends, we restore the parity.
• For each light, we greedily decide whether an operation should be performed to ensure it ends up turned on.

Concrete Example

Sample input:

N=5, K=3
S="01000"

Initial state: 0 1 0 0 0

Operation 1: Flip interval [1,3] → 1 0 1 0 0
Operation 2: Flip interval [2,4] → 1 1 0 1 0
Operation 3: Flip interval [3,5] → 1 1 1 0 1
Operation 4: Interval [4,6] is out of range → impossible → -1

In this way, if we cannot turn on all lights by the end, we output -1.

Algorithm

1. Convert the light states into an array of 0 / 1.
2. Process the lights from left to right, maintaining the “parity of the number of operations (flip_parity)” at each point.
3. At the current position \(i\), if the light’s state does not match the goal (on = 1):
   • If an interval of length \(K\) starting at \(i\) exists, perform an operation on that interval.
   • Update the operation parity, add the starting position to the queue.
   • Increment the operation count.
4. If \(i + K > N\), the operation is impossible, so output -1.
5. Finally, output the operation count.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(K)\) (the queue size is at most \(K\))

Implementation Notes

• When processing each light, manage the range of influence of operations (the most recent \(K\) positions) with a queue, and remove old operations to efficiently maintain parity.

• The current state of a light can be obtained as state[i] ^ flip_parity.

• Cases where an operation is impossible (interval goes out of bounds) should be detected early, and -1 should be returned immediately.

  Source Code

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    S = data[2]
    
    # 状態を0/1のリストに変換 (0: 消灯, 1: 点灯)
    state = [int(c) for c in S]
    
    # 目標は全て1（点灯）なので、現在の状態と目標の差分を考える
    # 各位置について、その位置が最終的に1になってほしい
    # つまり、操作の結果、各ビットが奇数回反転されたらよい
    
    # 差分配列 diff[i] := 位置 i での操作回数の parity（偶奇）
    # 実際には、操作は区間 [l, l+K-1] に対して行われるので、差分更新が有効
    
    # 初期状態がすべて1になるように操作回数を調整する
    # つまり、初期状態が0なら反転させたい（操作回数を奇数回）、1ならそのまま（偶数回）
    # ただし、操作は区間に対して行われるため、貪欲に左から処理していく
    
    # 各位置で、その位置が最終的に1になるために操作が必要かどうかを判断
    # 操作の影響範囲は K なので、スライドしながら処理する
    
    # flip_count: 現在の位置に影響を与えている操作の回数の parity
    flip_parity = 0
    # 操作を行った位置を記録するキュー（操作開始位置）
    queue = deque()
    operations = 0
    
    for i in range(N):
        # K個前の操作が範囲外に出た場合は parity から除外
        if queue and queue[0] <= i - K:
            queue.popleft()
            flip_parity ^= 1
        
        # 現在の照明の状態（操作による反転を考慮）
        current = state[i] ^ flip_parity
        
        # 目標は1（点灯）なので、current が 0 なら操作が必要
        if current == 0:
            # 操作は i から始まる K 長の区間に対して行う
            # ただし、i 以降 K 個の区間が存在する必要がある
            if i + K > N:
                print(-1)
                return
            # 操作を行う（実際には parity を更新し、queue に記録）
            flip_parity ^= 1
            queue.append(i)
            operations += 1
    
    print(operations)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.