Medical Parity

Editorial oficial 

Explicación

Nótese que $y_i$ es simplemente el XOR de los primeros $i$ bits de $x$. Por la naturaleza acumulativa de la operación, invertir el bit $i$ de $x$ invierte todos los bits de $[i, n]$ en $y$. Por lo tanto, podemos tratar una inversión de bit en $x'$ como invertir un rango sufijo en $y'$, y manipular solo $y'$ para que coincida con un $z$ esperado, el valor-$y$ que produce $x'$ tal cual. El problema pasa a ser manipular $y'$ de una de las siguientes formas para que coincida con $z_i=\bigoplus_{j=1}^i x'_j$:

1. Invertir el rango continuo de dígitos $y'_{[i, n]}$.
2. Invertir un solo dígito $y'_{i}$.

Por simplicidad, transformamos el problema en otro en el que el arreglo esperado es todo $0$. Lo hacemos tomando $d=y'\oplus z$, y como solo importan las diferencias entre el arreglo objetivo y el de origen, el problema es equivalente a transformar un arreglo de $0$s en $d$.

Ahora consideramos la Operación 1. Como las operaciones son todas desde el final, nos inspiramos en las sumas de prefijos para operar sobre un rango arbitrario con $2$ operaciones: Nótese que se puede invertir cualquier rango $d_{[i, j]}$ invirtiendo el rango $[i, n]$ y luego el rango $[j+1, n]$. Esto produce un bloque de $1$s si el rango no se había operado antes. Esto requiere $2$ operaciones, excepto cuando $j=n$, en cuyo caso solo hace falta $1$ operación: invertir $[i, n]$. La cantidad de operaciones se puede tratar como la cantidad de “transiciones” en $d_i$ al recorrerlo de izquierda a derecha, con un valor artificial $0$-ésimo insertado en $0$ (de modo que, si el primer valor es $1$, se considera una transición adicional).

La Operación 2 permite cambiar un solo dígito de $d$ a partir de una construcción que usa solo la Operación 1. Nótese que, al invertir al menos $2$ elementos adyacentes, siempre es más óptimo usar a lo sumo $2$ Operaciones 1 que invertirlos uno por uno con al menos $2$ Operaciones 2. La única optimización que aporta la Operación 2 es, por lo tanto, reducir la cantidad de transiciones de la estrategia con Operación 1 invirtiendo elementos sueltos distintos de ambos vecinos, lo que combina las dos transiciones adyacentes en $1$ inversión.

Primero calculamos $d$ y armamos un arreglo con los índices de todas las transiciones; luego, si las posiciones de dos transiciones están a distancia $1$, reducimos el conteo de operaciones en $1$ porque podemos usar la Operación 2 para invertir el elemento suelto y eliminar la transición.

Implementación

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

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		string x_prime, y_prime;
		cin >> x_prime >> y_prime;
		int n = x_prime.length();
 
		// Indexamos los vectores desde 1 para el 0 centinela inicial al contar.
		vector<bool> d(n + 1);
 
		// El valor dinámico de z_i, el arreglo esperado que produce x'.
		bool z_i = 0;
		for (int i = 0; i < n; i++) {
			// -'0' convierte el dígito ASCII en entero. ^= equivale a
			// sumar y tomar módulo 2
			z_i ^= x_prime[i] - '0';
			// Calculamos el XOR con b para obtener la diferencia; lo guardamos en el índice i+1 porque
			// nuestra DP empieza en 1.
			d[i + 1] = z_i ^ (y_prime[i] - '0');
		}
 
		vector<int> transitions;
		for (int i = 1; i <= n; i++) {
			if (d[i] != d[i - 1]) transitions.push_back(i);
		}
 
		int ans = transitions.size();
 
		// Emparejamos transiciones adyacentes y restamos 1 a la respuesta por el reemplazo
		// con la Operación 2
		for (int i = 0; i + 1 < (int)transitions.size();) {
			if (transitions[i + 1] == transitions[i] + 1) {
				ans--;
				i += 2;
			} else {
				i++;
			}
		}
 
		cout << ans << endl;
	}
	return 0;
}