A. El Ecualizador

La estrategia óptima depende de la paridad de la suma inicial de los elementos. Si la suma total es impar, el jugador actual puede asegurar la victoria. En caso contrario, el jugador debe intentar transformar la suma en \(n \times k\). Para que esto sea favorable, el producto \(n \times k\) debe ser par, permitiendo que el estado pase al oponente bajo condiciones específicas.

#include <iostream>
#include <vector>

using namespace std;

void ejecutar_caso() {
    long long num_elementos, multiplicador;
    if (!(cin >> num_elementos >> multiplicador)) return;
    
    long long acumulado = 0;
    for (int i = 0; i < num_elementos; ++i) {
        long long valor;
        cin >> valor;
        acumulado += valor;
    }

    if ((acumulado % 2 != 0) || ((num_elementos * multiplicador) % 2 == 0)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int casos;
    cin >> casos;
    while (casos--) {
        ejecutar_caso();
    }
    return 0;
}

B. Inversión de Bits (Versión Fácil)

El objetivo es determinar el número máximo de operaciones de inversión necesarias considerando un índice pivot. Se evalúan las inversiones requeridas tanto a la izquierda como a la derecha del índice dado, comparando los bits con el valor objetivo. Es crucial verifciar si el estado final del bit en la posición de referencia coincide con el deseado tras las inversiones propagadas.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void procesar() {
    int n, indice_p;
    cin >> n >> indice_p;
    vector<int> bits(n + 1);
    for (int i = 1; i <= n; ++i) cin >> bits[i];
    
    int ref_idx;
    cin >> ref_idx;
    int objetivo = bits[ref_idx];
    
    auto calcular_ops = [&](int inicio, int fin, int paso) {
        int ops = 0;
        bool invertido = false;
        for (int i = inicio; i != fin; i += paso) {
            int actual = bits[i] ^ (invertido ? 1 : 0);
            if (actual != objetivo) {
                ops++;
                invertido = !invertido;
            }
        }
        return ops + (invertido ? 1 : 0);
    };

    int ops_derecha = calcular_ops(n, ref_idx, -1);
    int ops_izquierda = calcular_ops(1, ref_idx, 1);
    
    cout << max(ops_derecha, ops_izquierda) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) procesar();
    return 0;
}

C. Cubrimiento de Cuadrícula

Para garantizar que un recorrido basado en saltos de tamaño \(a\) (horizontal) y \(b\) (vertical) cubra todas las celdas de una cuadrícula de \(n \times m\), se deben cumplir condiciones de coprimalidad: \(gcd(n, a) = 1\) y \(gcd(m, b) = 1\). El ciclo completo de movimiento se repite después de \(2 \cdot mcm(n, m)\) pasos. Si el máximo común divisor entre las dimensiones de la cuadrícula es 1 o 2, la estructura del ciclo permite visitar cada celda de manera exhaustiva.

#include <iostream>
#include <numeric>

using namespace std;

long long obtener_mcd(long long x, long long y) {
    while (y) {
        x %= y;
        swap(x, y);
    }
    return x;
}

void resolver_geometria() {
    long long filas, cols, salto_f, salto_c;
    cin >> filas >> cols >> salto_f >> salto_c;
    
    bool coprimos_f = (obtener_mcd(filas, salto_f) == 1);
    bool coprimos_c = (obtener_mcd(cols, salto_c) == 1);
    
    long long mcd_dims = obtener_mcd(filas, cols);
    // Verificamos si el ciclo es suficiente para cubrir n*m
    if (coprimos_f && coprimos_c && (2 * filas * cols / mcd_dims >= filas * cols)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) resolver_geometria();
    return 0;
}

D. Inversión de Bits (Versión Difícil)

Este problema se modela eficientemente utilizando un arreglo de diferencias sobre una transformación XOR. Al definir \(b_i = a_i \oplus a_{p_1}\), el objetiov es llevar el arreglo \(b\) a un estado de ceros. En el arreglo de diferencias \(c_i = b_i \oplus b_{i-1}\), cada operación de inversión sobre un rango \([l, r]\) equivale a conmutar los valores en \(c_l\) y \(c_{r+1}\).

Los índices con valor 1 en el arreglo de diferencias deben ser eliminados en parejas:

• Costo 1: Si la pareja cruza al menos un índice especial \(p_i\).
• Costo 2: Si ambos índices están en la misma región delimitada por los puntos especiales.

La solución óptima se obtiene mediante una estrategia codiciosa. Si \(S\) es el número total de unos en el arreglo de diferencias y \(L\) es la cantidad máxima de unos concentrados en una sola región, el costo mínimo es \(\max(S/2, L)\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void resolver_complejo() {
    int n, k;
    cin >> n >> k;
    
    vector<int> original(n + 1);
    for (int i = 1; i <= n; ++i) cin >> original[i];
    
    vector<int> pivotes(k);
    for (int i = 0; i < k; ++i) cin >> pivotes[i];
    
    int valor_base = original[pivotes[0]];
    vector<int> dif(n + 2, 0);
    int total_unos = 0;
    
    // Generación del arreglo de diferencias basado en XOR
    int prev_b = 0;
    for (int i = 1; i <= n + 1; ++i) {
        int curr_b = (i <= n) ? (original[i] ^ valor_base) : 0;
        dif[i] = curr_b ^ prev_b;
        if (dif[i] == 1) total_unos++;
        prev_b = curr_b;
    }
    
    vector<int> conteo_regiones(k + 1, 0);
    int p_ptr = 0;
    for (int i = 1; i <= n + 1; ++i) {
        if (dif[i] == 1) {
            while (p_ptr < k && i > pivotes[p_ptr]) {
                p_ptr++;
            }
            conteo_regiones[p_ptr]++;
        }
    }
    
    int max_region = 0;
    for (int c : conteo_regiones) {
        max_region = max(max_region, c);
    }
    
    cout << max(total_unos / 2, max_region) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (cin >> t) {
        while (t--) resolver_complejo();
    }
    return 0;
}