Número mínimo de pasos necesarios para convertir todos los bits binarios a un estado

Question

Hay una matriz de M números binarios y cada uno de ellos está en estado '0' o '1'. Puede realizar varios pasos para cambiar el estado de los números y en cada paso puede cambiar el estado de exactamente N números secuenciales. Dado el número M, N y la matriz con los miembros del supuesto, están a punto de calcular el número mínimo de pasos necesarios para convertir todos los números binarios en un estado - 1 o 0.

---

Si M = 6 y N = 3 y el conjunto es 1 0 0 1 0 0, entonces la solución será 2. Explicación: Podemos voltearlos para que todos sean 1 en dos pasos: pasamos del índice 2 al 4 y transformamos el array a 111000, y luego invierta los últimos tres (N) 0s a 1.

Answer 1

Si he entendido la pregunta correctamente, un poco de reflexión lo convencerá de que incluso la programación dinámica no es necesaria, la solución es completamente trivial.

Esta es la pregunta como yo lo entiendo: se le da una matriz de una [1] .. a [m] de 0s y 1s, y que se describen las operaciones de la forma S _k, donde S _{k permitido} significa voltear los N elementos a [k], a [k + 1], ... a [k + N-1]. Esto solo está definido para 1≤k≤M-N + 1, claramente.

Al realizar una secuencia de estas operaciones S _k, desea alcanzar el estado de todos los 0, o todos los 1s. Solucionaremos ambos por separado y tomaremos el número más pequeño. Entonces supongamos que queremos hacer que sean todos 0 (el otro caso, todos 1s, es simétrico).

El idea fundamental es que nunca se quiere realizar ninguna operación S _k más de una vez (haciendo dos veces es equivalente a no hacerlo en absoluto), y que el orden de las operaciones, no importa. Entonces la pregunta es solo para determinar qué subconjunto de las operaciones llevas a cabo, y esto es fácil de determinar. Mira un [1]. Si es 0, entonces sabe que no realizará S . De lo contrario, usted sabe que debe realizar S (ya que esta es la única operación que cambiará a [1]), realice esto - esto alternará todos los bits de un [1] a un [N]. Ahora mira a [2] (después de esta operación). Dependiendo de si es 1 o 0, usted sabe si realizará S o no. Y así sucesivamente: puede determinar cuántas operaciones (y cuáles) realizar, en tiempo lineal.

Editar: Se reemplazó el seudo código con el código C++, ya que hay una etiqueta C++. Perdón por el código feo; cuando estoy en el "modo concurso" vuelvo a los hábitos del concurso. :-)

#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

codifiqué el algoritmo que ShreevatsaR propuso, pero con la mejora de colas añadido para conseguir que el tiempo lineal real en 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; 
} 

Sólo tiene que ejecutar que en el original y la invertido original y tomar el mínimo (si no son -1). Si ambos son -1, entonces es imposible.

Tenga en cuenta que no he compilado ni probado ese código, pero debería funcionar.