Introducción al Análisis Algorítmico

En este documento se presenta una desglose técnico de cuatro desafíos computacionales que abarcan teoría de juegos, algoritmos constructivos, optimización greedy y manipulación de bits. Cada sección detalla la lógica subyacente y proporciona una implementación eficiente en C++.

Problema B: Juego Nim Aleatorio

Descripción del Problema

Se considera una variante del juego Nim donde dos jugadores, A y B, compiten por turnos. En cada turno, el jugador actual selecciona una pila de piedras al azar y retira una cantidad arbitraria de ellas. Gana quien tome la última piedra. El objetivo es calcular la probabilidad de victoria para el primer jugador, bajo la condición de que las elecciones sean aleatorias, expresando el resultado módulo 998244353.

Estrategia de Solución

El análisis de probabilidad revela un comportamiento distintivo dependiendo del tamaño de las pilas. Si existe al menos una pila con más de una piedra, la probabilidad de victoria se estabiliza en 1/2 debido a la capacidad del primer jugador forzar estados favorables. Sin embargo, si todas las pilas tienen exactamente una piedra, el resultado depende exclusivamente de la paridad del número total de pilas. Si la cantidad es impar, el primer jugador gana; de lo contrario, pierde.

Implementación

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;
const int INV_DOS = 499122177; // Inverso modular de 2

void procesarCaso() {
    int n;
    if (!(cin >> n)) return;
    
    bool existePilaGrande = false;
    for (int i = 0; i < n; ++i) {
        int piedras;
        cin >> piedras;
        if (piedras > 1) {
            existePilaGrande = true;
        }
    }

    if (existePilaGrande) {
        cout << INV_DOS << "\n";
    } else {
        cout << (n % 2 ? 1 : 0) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    procesarCaso();
    return 0;
}

Problema D: Contraataque de Medianas

Descripción del Problema

Se define la mediana de una secuencia de longitud n como el elemento cantral si n es impar, o el más frecuente de los dos centrales si es par (con desempate por valor menor). La "densidad" de la secuencia es la máxima frecuencia de la mediana en cualquier subsecuencia continua. El objetivo es construir una secuencia de longitud n con elementos entre 1 y 3 que minimice esta densidad.

Estrategia de Solución

Mediante el análisis de patrones constructivos, se observa que para minimizar la densidad B, se puede estructurar la secuencia alternando bloques de valores 1 y 3, separados por pares de valores 2. La relación entre la longitud máxima de la secuencia L y la densidad permitiad B sigue una fórmula precomputable. Específicamente, para una densidad i, la longitud máxima soportada crece cuadráticamente. Se utiliza búsqueda binaria sobre estos valores precomputados para encontrar la densidad mínima necesaria para una longitud n dada.

Implementación

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

using namespace std;

const int LIMITE_SUPERIOR = 40005;
long long tablaValores[LIMITE_SUPERIOR];

void inicializarDatos() {
    for (int i = 0; i < LIMITE_SUPERIOR; ++i) {
        // Fórmula derivada del patrón constructivo
        tablaValores[i] = (long long)(i / 2 + 1) * i * 2 + i;
    }
}

void ejecutarPrueba() {
    int n;
    cin >> n;
    // Buscar el primer valor precomputado que sea >= n
    int indice = lower_bound(tablaValores, tablaValores + LIMITE_SUPERIOR, n) - tablaValores;
    cout << indice << "\n";
}

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

Problema K: Tres Operaciones

Descripción del Problema

Dados tres enteros x, a, b, se permite reducir x a cero utilizando tres operaciones posibles: decremento en 1, división por 2 tras sumar a, o raíz cuadrada entera tras sumar b. Se busca minimizar el número total de operaciones.

Estrategia de Solución

Las operaciones de división y raíz cuadrada reducen el valor de x logarítmicamente, mientras que el decremento es lineal. La estrategia óptima consiste en elegir greedymente la operación que produzca el menor valor inmediato de x en cada paso. Dado que las operaciones rápidas dominan, el ciclo principal termina cuando la única opción viable es el decremento lineal, momento en el cual se suma el valor restante directamente al contador de operaciones.

Implementación

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

void calcularOperaciones() {
    ll valor, offsetA, offsetB;
    cin >> valor >> offsetA >> offsetB;
    
    ll totalOps = 0;
    
    while (true) {
        ll opcion1 = valor - 1;
        ll opcion2 = (valor + offsetA) / 2;
        ll opcion3 = (ll)sqrt(valor + offsetB);
        
        ll siguienteValor = min({opcion1, opcion2, opcion3});
        totalOps++;
        
        // Si la mejor opción es simplemente restar 1, optimizamos el resto
        if (siguienteValor == opcion1) {
            totalOps += siguienteValor;
            break;
        }
        valor = siguienteValor;
    }
    
    cout << totalOps << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    calcularOperaciones();
    return 0;
}

Problema M: Suma XOR Mínima y Máxima

Descripción del Problema

Se proporciona una permutación de longitud n. Se permite invertir cualquier subsegmento [l, r], con un costo igual a la longitud del segmento. El objetivo es ordenar la permutación (tal que p[i] = i) minimizando y maximizando la suma XOR de los costos de todas las operaciones realizadas.

Estrategia de Solución

La solución depende de la paridad de la permutación, determinada por el número de inversiones. Una permutación par requiere un número par de intercambios simples (costo 2), mientras que una impar requiere un número impar. Para el XOR mínimo: si la permutación es par, el resultado es 0; si es impar, es 2. Para el XOR máximo: se puede aprovechar la propiedad de que invertir y restaurar un segmento de longitud 2^k añade 2^k al XOR sin cambiar la permutación final. Así, se pueden activar todos los bits posibles excepto el bit 1, el cual está restringido por la paridad inicial.

Implementación

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

class Fenwick {
    int size;
    vector<ll> tree;
public:
    Fenwick(int n) : size(n), tree(n + 1, 0) {}
    
    void add(int idx, int val) {
        for (; idx <= size; idx += idx & -idx)
            tree[idx] += val;
    }
    
    ll query(int idx) {
        ll sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};

void resolverXOR() {
    int n;
    cin >> n;
    vector<int> p(n + 1);
    Fenwick bit(n);
    ll inversiones = 0;
    
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        inversiones += (i - 1) - bit.query(p[i]);
        bit.add(p[i], 1);
    }
    
    ll xorMin = (inversiones % 2 != 0) ? 2 : 0;
    ll xorMax = 0;
    int maxBit = log2(n);
    
    for (int i = maxBit; i >= 0; --i) {
        if (i == 1) {
            xorMax += (inversiones % 2 != 0) ? 2 : 0;
        } else {
            xorMax += (1LL << i);
        }
    }
    
    cout << xorMin << " " << xorMax << "\n";
}

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