Help with a dynamic-programming problem

Question

The problem is this: There is an array of M binary numbers and each of them is in state '0' or '1'. You can perform several steps in changing the state of the numbers and in each step you are allowed to change the state of exactly N sequential numbers. Given the numbers M, N and the array with the members of course, you are about to calculate the minimal number of steps needed to turn all the binary numbers into one state - 1 or 0.

EDIT: Ex:

If M = 6 and N = 3 and the array is 1 0 0 1 0 0, then the solution will be 2. Explanation: We can flip them so they all be 1 in two steps: we flipt from index 2 to 4 and we transform the array to 111000, and then flip the last three (N) 0s to 1.

I would like to know if someone here could help me with this. Also i am not from english speaking community so i would like to help me find the correct title of the problem (if there's one). Also i've heard this problem (or some similar one) is on TopCoder, solved. I would like if i could get the link if any of you knows it.

Thank you.

Answer 1

If I've understood the question correctly, a little bit of thought will convince you that even dynamic programming is not necessary — the solution is entirely trivial.

This is the question as I understand it: you are given an array a[1]..a[M] of 0s and 1s, and you are allowed operations of the form S_k, where S_k means to flip the N elements a[k],a[k+1],...a[k+N-1]. This is only defined for 1≤k≤M-N+1, clearly.

By performing a sequence of these operations S_k, you want to reach either the state of all 0s, or all 1s. We'll solve for both separately, and take the smaller number. So suppose we want to make them all 0 (the other case, all 1s, is symmetric).

The crucial idea is that you would never want to perform any operation S_k more than once (doing it twice is equivalent to not doing it at all), and that the order of operations does not matter. So the question is only to determine which subset of the operations you perform, and this is easy to determine. Look at a[1]. If it's 0, then you know you won't perform S₁. Else, you know you must perform S₁ (as this is the only operation that will flip a[1]), so perform it — this will toggle all bits from a[1] to a[N]. Now look at a[2] (after this operation). Depending on whether it is 1 or 0, you know whether you will perform S₂ or not. And so on — you can determine how many operations (and which) to perform, in linear time.

Edit: Replaced pseudo-code with C++ code, since there's a C++ tag. Sorry for the ugly code; when in "contest mode" I revert to contest habits. :-)

#include <iostream>
using namespace std;
const int INF = 20000000;
#define FOR(i,n) for(int i=0,_n=n; i<_n; ++i)

int flips(int a[], int M, int N, int want) {
  int s[M]; FOR(i,M) s[i] = 0;
  int sum=0, ans=0;
  FOR(i,M) {
    s[i] = (a[i]+sum)%2 != want;
    sum += s[i] - (i>=N-1?s[i-N+1]:0);
    ans += s[i];
    if(i>M-N and s[i]!=0) return INF;
  }
  return ans;
}

int main() {
  int M = 6, N = 3;
  int a[] = {1, 0, 0, 1, 0, 0};
  printf("Need %d flips to 0 and and %d flips to 1\n",
         flips(a, M, N, 0), flips(a, M, N, 1));
}

Answer 2

I coded up the algorithm that ShreevatsaR proposed, but with the added queue improvement to get it to real linear time in M.

int solve(vector<bool> bits, int N)
{
  queue<int> flips;
  int moves = 0;

  for (int i = 0; i < bits.size(); ++i)
  {
    if (!flips.empty() && flips.front() <= i - N)
      flips.pop();

    if ((bits[i] ^ (flips.size() % 2 == 0)) == 1)
    {
      if (i > bits.size() - N)
        return -1; // IMPOSSIBLE

      moves++;
      flips.push(i);
    } 
  }

  return moves;
}

Just run that on the original and the inverted original and take the minimum (if they aren't -1). If both are -1 then it is impossible.

Note that I have neither compiled or tested that code, but it should work.