1

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.

  • 3
    You appear to have a variation of the pancake sorting problem there with identical pancakes, one side toasting, and an arbitrary starting condition. This is a reasonably well known math problem: en.wikipedia.org/wiki/Pancake_sorting – user40980 Apr 8 '15 at 0:30
  • @MichaelT But in Stefan's question, there is limit on how many cards can be flipped in one go. – Euphoric Apr 8 '15 at 7:24
  • I should also mention, that there is possibility that some combinations of input and parameters might be unsolvable. – Euphoric Apr 8 '15 at 7:28
2

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.

  • Well that was my idea behind the algorithm. Anyway this is a contest problem and the test case was used in that contest. The supposed right answer is 30, while my output is -1, i.e. it's not solvable. – Stefan4024 Apr 8 '15 at 12:33
  • @Stefan4024 Are you sure you understood (and rewritten) the assignment properly and that you copied the input data without errors. – Euphoric Apr 8 '15 at 13:02
  • @Stefan4024 For example, the solution is 30 when you assume you can flip less than K cards if you are at end of the array. – Euphoric Apr 8 '15 at 13:10
  • I've checked the problem again and it's translated and posted as it should be. Also you can check the new test case I've posted. – Stefan4024 Apr 8 '15 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.