Subtask 1

Since ~K = 0~, we cannot flip any lights before solving the puzzle. Thus, we must simply calculate the minimal number of moves to turn off all of the lights.

Let's consider a simpler example. If all ~N~ lights are on, what is the minimal number of moves to turn off all of the lights?

Case 1: ~N~ is odd.

If ~N~ is odd, here is a simple strategy to turn off all of the lights in ~N~ moves.

Initially, the sequence of lights will look something like 111111...111.

We can turn off two lights at a time with the following moves:

111111...111
101111...111 turn off the second remaining light from the left (2 neighbours on)
001111...111 turn off the first remaining light from the left (0 neighbours on)

Since ~N~ is odd and this strategy removes two lights at a time, repeating this process will eventually leave one light on with 0 of its neighbours on, which we can simply turn off in one move.

...
000000...111
000000...101 turn off the second remaining light from the left (2 neighbours on)
000000...001 turn off the first remaining light from the left (0 neighbours on)
000000...000 turn off last light (0 neighbours on)

You cannot turn off ~N~ lights in less than ~N~ moves since that would imply that multiple lights were turned off in one move, which is not possible. Thus, the minimum possible number of moves in this case is ~N~, and this strategy shows that the lower bound is attainable.

Case 2: ~N~ is even.

If ~N~ is even, we can do something similar, but it will require ~N + 2~ moves to turn off all of the lights.

Again, the initial sequence of lights will look something like 111111...1111.

We can still apply the strategy of turning off two lights at a time:

111111...1111
101111...1111 turn off the second remaining light from the left (2 neighbours on)
001111...1111 turn off the first remaining light from the left (0 neighbours on)

But since ~N~ is even, we will eventually be left with two adjacent lights which are on, instead of one.

...
000000...1111 turn off the second remaining light from the left (2 neighbours on)
000000...1011 turn off the first remaining light from the left (0 neighbours on)
000000...0011

Neither light can be turned off, since both have exactly 1 neighbour which is on. Thus, we are forced to turn on a light to turn the sequence of two adjacent lights to three consecutive lights, after which we can continue with our strategy for odd ~N~. (Note: there may not be a light to turn on here, particularly for ~N=2~. This will become important later when considering impossible cases in the general solution).

000000...0011
000000...0111 turn on light before the leftmost remaining light (1 neighbour on)
000000...0101 turn off the second remaining light from the left (2 neighbours on)
000000...0001 turn off the first remaining light from the left (0 neighbours on)
000000...0000 turn off last light (0 neighbours on)

The number of moves is exactly the same, but we turn on one extra light, which we must also turn off later. This contributes ~2~ extra moves, for a total of ~N + 2~ moves.

Proof that ~N + 2~ moves is minimal

To prove that ~N + 2~ moves is minimal, consider all the possible lights we can turn off from the initial state with all ~N~ lights on. We cannot turn off light ~1~ or light ~N~, since they both have exactly 1 neighbour which is on. Thus, we can only turn off a light in the middle. This will break our sequence of ~N~ on lights into ~X~ on lights + ~1~ off light + ~Y~ on lights. Since ~N~ is even, ~X + 1 + Y~ must be even, too. This implies that ~X + Y~ is odd, which can only happen if exactly one of ~X~ or ~Y~ is even, and the other is odd. Without loss of generality, assume ~X~ is odd. The sequence of ~X~ lights can be turned off in ~X~ moves, as proven in Case 1. However, the remaining ~Y~ lights is either a smaller even sequence which we can repeat this logic on, or eventually, two adjacent lights, neither of which can be turned off! So, no matter what moves we perform on a sequence of ~N~ on lights, where ~N~ is even, we will always end up with ~2~ adjacent lights that we must turn off with ~2~ extra moves. Thus, the minimal number number of moves is ~N + 2~, attainable by any one of these strategies (though we just chose the simplest one for explanation above).

General Solution & Impossible Cases

Now that we know the minimum number of moves to get rid of a sequence of on lights, what is the general solution for any initial pattern of lights? Well, any pattern can be broken down into consecutive sequences of on lights, each separated by some number off lights. All of these consecutive runs of on lights can be turned off with one of the strategies above. Note that it is impossible to merge these sequences, since a gap of one off light between two blocks of on lights can only stay off (2 neighbours on). Thus, the minimum number of moves for any general pattern is the sum of the moves for each individual sequence of on lights. This can be simplified to ~2 \times (\text{# of even sequences}) + (\text{# of lights on})~.

But wait, what about the impossible cases? Well, there is one weakness in our strategy for even sequences which can be abused. Our strategy assumed that there exists a light which can be turned on next to the remaining two adjacent lights. If a pattern of lights contains at least one sequence of on lights that is NOT length two, when turning it off, at least two adjacent off lights will be created (the edges can be treated as an off light in this scenario). This gives us enough space to turn on a third light and get rid of sequences of length two. Thus, an impossible case must ONLY contain sequences of length two, and must not have any sequence of two or more adjacent off lights (or off lights on the edges). This naturally gives rise to impossible cases of the form 110110110...11011. No lights in patterns of this type can change their state.

This pattern can be checked with a simple loop, or by checking if ~3 \times (\text{# of even sequences}) - 1 = N~. The number of lights on and number of even sequences can be counted within this loop as well.

Time Complexity: ~\mathcal{O}(N)~

Subtask 2

For brevity, let ~L = (\text{# of lights on})~ and ~E = (\text{# of even sequences})~.

Now that we have a simple formula to calculate the minimum number of moves to solve the puzzle, ~2E + L~, we must determine how to minimize this expression with ~K~ moves.

Observe that it is never optimal to flip a light on. We should only focus on two useful types of flips:

1) Flip a light at the beginning or end of an even sequence, turning it into an odd sequence. ~X \to X-1~

• ~E~ decreases by 1 (decreasing total moves by 2), and ~L~ also decreases by 1 (decreasing total moves by 1).
• Thus, the total number of moves decreases by 3 with this type of flip.
  Note: it is never better to merge two even sequences into a bigger odd sequence by flipping a light on

  While it also decreases the move count by ~3~, it leaves us with an odd sequence with not much potential to decrease the move count further. If we instead reduce one of the even sequences to an odd sequence, this still decreases the move count by ~3~, but leaves us with the second even sequence which can potentially decrease the move count by ~3~, again.

2) Flip a light in the middle of an odd sequence, breaking it into two odd sequences (or removing it entirely if the original sequence is of length 1). This is always possible, e.g. ~X \to 1 + (X-2)~

• ~L~ decreases by 1.
• Thus, the total number of moves decreases by 1 with this type of flip.

Since flips of type 1 reduce the total required moves by 3, they should be done first. The solution involves greedily using as many of the ~K~ moves as possible to reduce even sequences to odd sequences. If there are no more even sequences and there are still some remaining moves, use the rest of them to break odd sequences up into two smaller odd sequences, or get rid of sequences of length 1.

When written as a simplified formula, the answer is:

~ \begin{gather*} \max \big(0, 2\max(0, E-K) + L - K \big) \end{gather*} ~

The inner piece, ~2\max(0, E-K)~, is the contribution from reducing even sequences to odd sequences, and the outer piece, ~\max \big(0, \dots + L - K \big)~, is the contribution from simply reducing the total number of lights in all sequences. Note that if ~K > 0~, then there are no impossible cases. Any pattern of the form 110110110...11011 becomes possible after flipping one of the on lights off.

Time Complexity: ~\mathcal{O}(N)~

Bonus

Python golf solution (161 bytes): https://dmoj.ca/src/6867367

The bitwise XOR setting move is comparable to the Rule 90 elementary cellular automaton, except one cell is updated at a time.