Sliding Window Summation

Explicación

El valor de $r_i$ es equivalente al XOR de la ventana de longitud $K$ que empieza en $i$ . La única diferencia entre las ventanas de $r_i$ y $r_{i+1}$ es que la ventana de $r_i$ contiene $b_i$ , mientras que la de $r_{i+1}$ contiene $b_{i+k}$ .

(b_i \oplus b_{i+1} \oplus \cdots \oplus b_{i+k-1}) \oplus (b_{i+1} \oplus \cdots \oplus b_{i+k}) = r_i \oplus r_{i+1} = b_i \oplus b_{i+k}

r_i\oplus r_{i+1}\oplus b_i = b_{i+k}

Como nos dan $r$ , elegir el valor de $b_i$ determina $b_{i+k}$ , que a su vez determina $b_{i+2k}$ , $b_{i+3k}$ , y así sucesivamente. Esto parte $b$ en $k$ cadenas binarias, cada una dependiente de uno de los primeros $k$ caracteres de $b$ . Para cada cadena, podemos fijar el primer carácter a 0 o 1, comparando cuál minimiza la cantidad de bits 1.

Lo único que restringe los primeros $k$ bits de $b$ es $r_1$ , que a veces nos obliga a invertir uno de nuestros bits iniciales aunque eso aumente la cantidad de bits 1 en el string. Podemos comprobar si nuestra configuración satisface $r_1$ registrando el XOR bit a bit de los primeros $k$ bits óptimos, y guardando un mínimo corriente $m$ , que representa la cantidad adicional de bits 1 al invertir una cadena. Si el XOR bit a bit de los primeros $k$ bits óptimos no coincide con $r_1$ , entonces podemos invertir de nuevo la cadena seleccionada y sumar $m$ a nuestro conteo.

Luego podemos aplicar la misma idea para maximizar la cantidad de bits 1.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		string r, b;
		cin >> n >> k >> r;
 
		// c[i] = {cantidad de bits 1 en la cadena, tamaño de la cadena}
		vector<pair<int, int>> c(k, {0, 1});
		b = string(k, '0');
		b.reserve(n);
 
		// Construimos las cadenas usando la propiedad del XOR
		for (int i = 0; i < n - k; i++) {
			b += ((b[i] == '1') ^ (r[i] == '1') ^ (r[i + 1] == '1')) + '0';
			c[i % k].first += b[b.size() - 1] - '0';
			c[i % k].second++;
		}
 
		// Calculamos la cantidad mínima de unos
		int m = INT_MAX, count = 0;
		bool p = false;
		for (auto &[ones, len] : c) {
			count += min(ones, len - ones);   // len-ones es la cantidad de bits 0
			m = min(m, abs(2 * ones - len));  // ones-(len-ones)
			p ^= (ones >= len - ones);        // contador de paridad
		}
		if (p != (r[0] == '1')) count += m;
		cout << count << ' ';
 
		// Calculamos la cantidad máxima de unos
		m = INT_MAX;
		count = 0;
		p = false;
		for (auto &[ones, len] : c) {
			count += max(ones, len - ones);
			m = min(m, abs(len - 2 * ones));
			p ^= (2 * ones <= len);  // condición de flip opuesta
		}
		if (p != (r[0] == '1')) count -= m;
		cout << count << endl;
	}
}


import java.io.*;
import java.util.*;
 
public class Main {
	static class Chain {
		int ones;
		int len;
		Chain(int ones, int len) {
			this.ones = ones;
			this.len = len;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
 
		for (int t = 0; t < test; t++) {
			String[] parts = br.readLine().trim().split(" ");
			int n = Integer.parseInt(parts[0]);
			int k = Integer.parseInt(parts[1]);
			String r = br.readLine().trim();
 
			// Inicializamos las cadenas
			Chain[] chains = new Chain[k];
			for (int i = 0; i < k; i++) chains[i] = new Chain(0, 1);
 
			// Construimos el string reconstruido usando la propiedad del XOR
			StringBuilder b = new StringBuilder();
			for (int i = 0; i < k; i++) b.append('0');
 
			for (int i = 0; i < n - k; i++) {
				int bit = ((b.charAt(i) - '0') ^ (r.charAt(i) - '0') ^
				           (r.charAt(i + 1) - '0'));
				b.append((char)(bit + '0'));
 
				int chainIndex = i % k;
				chains[chainIndex].ones += bit;
				chains[chainIndex].len++;
			}
 
			// Calculamos la cantidad mínima de unos
			int m = Integer.MAX_VALUE, count = 0;
			boolean p = false;
			for (Chain c : chains) {
				count += Math.min(c.ones, c.len - c.ones);
				m = Math.min(m, Math.abs(2 * c.ones - c.len));
				p ^= (c.ones >= c.len - c.ones);
			}
			if (p != (r.charAt(0) == '1')) count += m;
			System.out.print(count + " ");
 
			// Calculamos la cantidad máxima de unos
			m = Integer.MAX_VALUE;
			count = 0;
			p = false;
			for (Chain c : chains) {
				count += Math.max(c.ones, c.len - c.ones);
				m = Math.min(m, Math.abs(c.len - 2 * c.ones));
				p ^= (2 * c.ones <= c.len);
			}
			if (p != (r.charAt(0) == '1')) count -= m;
			System.out.println(count);
		}
	}
}


t = int(input())
 
for _ in range(t):
	n, k = map(int, input().split())
	r = input().strip()
 
	# c[i] = [cantidad de bits 1 en la cadena, tamaño de la cadena]
	c = [[0, 1] for _ in range(k)]
 
	# Construimos las cadenas usando la propiedad del XOR
	b = [False] * n  # inicializamos longitud completa, los primeros k bits son '0'
 
	for i in range(n - k):
		b[k + i] = b[i] ^ (r[i] == "1") ^ (r[i + 1] == "1")
		c[i % k][0] += b[k + i]
		c[i % k][1] += 1
 
	# Calculamos la cantidad mínima de unos
	m = float("inf")
	count = 0
	p = False
	for ones, length in c:
		count += min(ones, length - ones)
		m = min(m, abs(2 * ones - length))
		p ^= ones >= length - ones
	if p != (r[0] == "1"):
		count += m
	print(count, end=" ")
 
	# Calculamos la cantidad máxima de unos
	m = float("inf")
	count = 0
	p = False
	for ones, length in c:
		count += max(ones, length - ones)
		m = min(m, abs(length - 2 * ones))
		p ^= 2 * ones <= length
	if p != (r[0] == "1"):
		count -= m
	print(count)