Problema 1: Optimización de Posicionamiento de Postes

En este problema, se nos presentan $n$ postes ubicados en una línea numérica en posiciones $p_i$. Cada poste tiene una altura $h_i$. Un poste puede permanecer vertical (ocupando solo el punto $p_i$), caer hacia la izquierda (ocupando el intervalo $[p_i - h_i, p_i]$) o caer hacia la derecha (ocupando $[p_i, p_i + h_i]$). El objetivo es maximizar la cantidad de postes derribados sin que sus intervalos de ocupación se traslapen.

Para resolverlo, empleamos un enfoque de programación dinámica. Definimos un estado $f[i][state]$, donde $i$ representa el poste actual y $state \in \{0, 1, 2\}$ indica si el poste está vertical, caído a la izquierda o caído a la derecha, respectivamente.

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

using namespace std;

const long long INF_LL = 2e18;

struct Elemento {
    long long pos, alt;
    bool operator<(const Elemento& otro) const {
        return pos < otro.pos;
    }
};

int main() {
    int total;
    cin >> total;
    vector<Elemento> lista(total + 1);
    for (int i = 1; i <= total; i++) {
        cin >> lista[i].pos >> lista[i].alt;
    }
    sort(lista.begin() + 1, lista.end());

    lista[0].pos = -INF_LL;
    vector<vector<int>> memo(total + 1, vector<int>(3, 0));

    for (int i = 1; i <= total; i++) {
        // Caso 0: Vertical
        memo[i][0] = max(memo[i-1][0], memo[i-1][1]);
        if (lista[i].pos - lista[i-1].pos > lista[i-1].alt) {
            memo[i][0] = max(memo[i][0], memo[i-1][2]);
        }

        // Caso 1: Izquierda
        if (lista[i].pos - lista[i-1].pos > lista[i].alt) {
            memo[i][1] = max(memo[i-1][0], memo[i-1][1]) + 1;
        }
        if (lista[i].pos - lista[i-1].pos > lista[i].alt + lista[i-1].alt) {
            memo[i][1] = max(memo[i][1], memo[i-1][2] + 1);
        }

        // Caso 2: Derecha
        memo[i][2] = max(memo[i-1][0], memo[i-1][1]) + 1;
        if (lista[i].pos - lista[i-1].pos > lista[i-1].alt) {
            memo[i][2] = max(memo[i][2], memo[i-1][2] + 1);
        }
    }

    cout << max({memo[total][0], memo[total][1], memo[total][2]}) << endl;
    return 0;
}

Problema 2: Emparejamiento Perfecto en Grafo Bipartito Completo

Se define un grafo bipartito con $n+1$ nodos en cada conujnto. Los pesos de los nodos izquierdos son $a_i$ y los de los derechos $b_i$. El peso de una arista $(i, j)$ es $\max(0, b_j - a_i)$. Dado que $a_{n+1} = +\infty$, cualquier arista conectada a este nodo tendrá un peso efectivo de 0 en términos de contribución al valor del emparejamiento (si buscamos minimizar el máximo). Debemos determinar, para cada $i$, el peso mínimo de un emparejamiento perfecto si $a_{n+1}$ se empareja con $b_i$.

La estrategia consiste en ordenar los pesos y utilizar una estructura de datos (como un multiset) para gestionar los valores máximos de forma dinámica a medida que iteramos sobre las posibles conexiones del nodo infinito.

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

using namespace std;

struct Punto {
    int valor, idx;
    bool operator<(const Punto& p) const { return valor < p.valor; }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    vector<Punto> b(n + 2);
    vector<int> a(n + 1);
    for (int i = 1; i <= n + 1; i++) { cin >> b[i].valor; b[i].idx = i; }
    for (int i = 1; i <= n; i++) cin >> a[i];

    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    multiset<int> diferencias;
    for (int i = 1; i <= n; i++) {
        diferencias.insert(max(0, b[i+1].valor - a[i]));
    }
    
    vector<int> res(n + 2);
    res[b[1].idx] = *diferencias.rbegin();
    
    int max_acumulado = 0;
    for (int i = 2; i <= n + 1; i++) {
        auto it = diferencias.find(max(0, b[i].valor - a[i-1]));
        if (it != diferencias.end()) diferencias.erase(it);
        
        max_acumulado = max(max_acumulado, max(0, b[i-1].valor - a[i-1]));
        res[b[i].idx] = max(max_acumulado, diferencias.empty() ? 0 : *diferencias.rbegin());
    }

    for (int i = 1; i <= n + 1; i++) cout << res[i] << (i == n + 1 ? "" : " ");
    return 0;
}

Problema 3: Suma XOR de Divisores

El reto consiste en calcular el XOR total de la suma XOR de todos los divisores para cada número entre $1$ y $n$. Una solución ingenua de $O(n)$ es insuficiente para valores grandes de $n$. Aplicamos una técnica de descomposición de raíz cuadrada (Square Root Decomposition) para optimizar el conteo de frecuencias de cada factor.

Sabemos que un factor $x$ contribuye al XOR total si aparece una cantidad impar de veces como divisor en el rango $[1, n]$. El número de múltiplos de $x$ en el rango es $\lfloor n/x \rfloor$.

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

ll obtener_xor_prefijo(ll v) {
    if (v <= 0) return 0;
    ll residuo = v % 4;
    if (residuo == 0) return v;
    if (residuo == 1) return 1;
    if (residuo == 2) return v + 1;
    return 0;
}

void procesar() {
    ll n;
    if (!(cin >> n)) return;
    ll acumulado = 0;
    ll limite = sqrt(n);
    ll d = 1;

    // Procesamiento hasta la raíz cuadrada
    for (; d <= limite; d++) {
        if ((n / d) % 2 != 0) {
            acumulado ^= d;
        }
    }

    // Procesamiento de bloques de cocientes constantes
    while (d <= n) {
        ll cociente = n / d;
        ll siguiente = n / cociente;
        if (cociente % 2 != 0) {
            acumulado ^= obtener_xor_prefijo(siguiente) ^ obtener_xor_prefijo(d - 1);
        }
        d = siguiente + 1;
    }
    cout << acumulado << endl;
}

int main() {
    procesar();
    return 0;
}