Turn over cards in minimum number of steps

algorithmsproblem solving

Imagine you're given an array of cards. Some of them are facing down (0), while some of them are facing up (1). Is it possible for given fixed K to turn all the cards face-up by turning over any K consecutive cards? If it's possible what's the minimum number of steps?

For example:

N=6; K=3;
1 0 0 1 0 0

It is possible to make all the cards facing up, by first turning over cards 2-3-4 and then turning over cards 4-5-6. And the minimum number of steps is 2.

My idea was to iterate through the sequence and when I'll find a 0 then I flip the next K cards (if it's possible), including the 0. But it seems that this idea doesn't work always. For example:

N=56; K=5
0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0

is one counter-example. Since after I perform the above-mentioned algorithm I end up with all the cards faced up, except for the last one.

This is a contest problem, so one of the test cases is:

1000 25
0 0 1 0 0 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0

The supposed right answer is 441, while my algorithm says is 443.

Best Answer

First, there is high possibility that combination of parameters and starting cards might be unsolvable. For example

N=3; K=2
1 0 1

Is unsolvable.

Your algorithm doesn't find minimum number of steps, because your example configuration cannot be solved at all.

Now the question is whenever given algorithm does indeed guarantee that it can always find solution if it exists. I don't have rigid proof, but I do believe yes.

The reason for my belief are the edge cards. The moment the edge cards become 1, you cannot apply "flip" function on them and K-1 area next to them. If you did, you would have to apply it again, completely reverting previous flip. They are invariant to flip function. So if you manage to flip an edge card to be 1, you can ignore it, remove it from the list of cards and continue with reduced list. If there is 0 on the edge, you flip it along with K-1 other cards, which gives you 1 which you can then ignore. You are doing exactly that with your algorithm. At end of this algorithm, you end up with list of cards whose length is EndN <= K.

Given that, figuring out whenever the configuration is solvable is easy. The configuration is only solvable if EndN = K and if remaining cards are either up or down.

Related Topic