Overview

We repeatedly flip the states of \(K\) consecutive light bulbs simultaneously, and determine whether it is possible to turn all light bulbs on. If possible, find the minimum number of operations.

Analysis

In this problem, each operation simultaneously changes the states of \(K\) consecutive light bulbs. Therefore, the final state of a light bulb at a given position depends on the total number of operations that include that position.

A naive approach would be to simulate the process, turning on all light bulbs one by one. However, if we directly flip \(K\) elements each time, the worst-case time complexity becomes \(O(N^2)\), which is too slow since \(N\) can be up to \(2 \times 10^5\).

The key observation is that by managing the effects of operations cumulatively, we can efficiently determine the current state of each light bulb. Specifically, by recording the start and end positions of each operation and managing the range effects using difference updates (similar to the imos method), we can determine the current state of each light bulb in \(O(1)\).

Furthermore, by processing from left to right, if a light bulb at a certain position is off, it is optimal to perform an operation on the interval of length \(K\) starting at that position. This is because performing the operation on that interval later would yield the same result. However, if the interval extends beyond the array (i.e., \(i + K > N\)), the operation cannot be performed, and we output -1 at that point.

Algorithm

1. Prepare a flip_count array (imos-style) to record the effects of each operation. This is used to record the start and end of intervals.
2. Use a current_flip variable to track the parity of the number of operations affecting the current position (i.e., the total number of flips mod 2).
3. Process each light bulb from left to right. If the current state (initial state XOR current flip count) is 1 (off), perform an operation on the interval of length \(K\) starting at that position.
4. When performing an operation:
   • Increment operations
   • Flip current_flip
   • Record the flip operation at flip_count[i + K] (the end point of the interval)
5. If the interval goes out of bounds, output -1 and terminate.
6. Finally, output the number of operations operations.

Time Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• flip_count needs to be allocated with a size of \(N+1\) to have space for recording interval endpoints.

• current_flip must be updated each time by incorporating flip_count[i] (difference update).

• The state of each light bulb can be concisely computed using XOR.

  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])
    A = list(map(int, data[2:]))

    # 0: 点灯, 1: 消灯 → 目標はすべて0にする
    # 各位置について、操作の影響を管理する
    # 差分更新で効率的にシミュレーション
    
    flip_count = [0] * (N + 1)  # imos法で操作回数を記録
    current_flip = 0
    operations = 0
    queue = deque()

    for i in range(N):
        current_flip ^= flip_count[i]
        current_state = A[i] ^ current_flip
        if current_state == 1:  # 消灯状態なら反転が必要
            if i + K > N:
                print(-1)
                return
            # 区間 [i, i+K) に操作を適用
            operations += 1
            current_flip ^= 1
            if i + K < N + 1:
                flip_count[i + K] ^= 1
    print(operations)

if __name__ == "__main__":
    main()

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