Минимальное количество шагов, необходимых для перевода всех двоичных битов в одно состояние

Question

Существует массив из M двоичных чисел, и каждое из них находится в состоянии «0» или «1». Вы можете выполнить несколько шагов по изменению состояния чисел, и на каждом шаге вы можете изменять состояние ровно N последовательных чисел. Учитывая числа M, N и массив с членами, конечно, вы собираетесь рассчитать минимальное количество шагов, необходимых для преобразования всех двоичных чисел в одно состояние - 1 или 0.

---

Если M = 6 и N = 3, а массив равен 1 0 0 1 0 0, то решение будет равно 2. Объяснение: Мы можем перевернуть их так, чтобы они все были равны 1 за два шага: мы перевернули индекс с 2 на 4 и преобразовали массив в 111000, а затем перевернули последние три (N) 0 в 1.

Answer 1

Если я правильно понял вопрос, небольшая мысль убедит вас в том, что даже динамическое программирование не нужно - решение совершенно тривиально.

Это вопрос, насколько я понимаю: вам дан массив a [1] .. a [M], равный 0 и 1, и вам разрешены операции в форме S _k , где S _k означает перевернуть N элементов a [k], a [k + 1], ... a [k + N-1]. Это определено только для 1≤k≤M-N + 1, ясно.

Выполняя последовательность этих операций S _k , вы хотите достичь либо состояния всех 0, либо всех 1. Будем решать как отдельно, так и брать меньшее число. Итак, предположим, что мы хотим сделать их все 0 (другой случай, все 1 с, симметричны).

Ключевая идея заключается в том, что вам никогда не захочется выполнять какие-либо операции S _k более одного раза (выполнение этого дважды эквивалентно тому, что вообще не выполняется), и что порядок операций не имеет значения. Поэтому вопрос состоит только в том, чтобы определить, какое подмножество операций вы выполняете, и это легко определить. Посмотрите на [1]. Если это 0, то вы знаете, что не будете выполнять S ₁ . Иначе, вы знаете, что должны выполнить S ₁ (так как это единственная операция, которая перевернет [1]), поэтому выполните ее - это переключит все биты с [1] на [N] , Теперь посмотрите на [2] (после этой операции). В зависимости от того, будет ли это 1 или 0, вы знаете, будете ли вы выполнять S ₂ или нет. И так далее - вы можете определить, сколько операций (и какие) нужно выполнить за линейное время.

Редактировать: Заменен псевдокод на код C ++, поскольку есть тег C ++. Извините за уродливый код; когда в "режиме соревнования" я возвращаюсь к соревновательным привычкам. : -)

#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

Я кодировал алгоритм, предложенный ShreevatsaR, но с добавленным улучшением очереди, чтобы получить его в реальном линейном времени в 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;
}

Просто запустите это на оригинале и перевернутом оригинале и возьмите минимум (если они не -1). Если оба равны -1, то это невозможно.

Обратите внимание, что я не компилировал и не тестировал этот код, но он должен работать.