La línea de medalla dorada en esta competición requería resolver al menos tres problemas, específicamente la mitad de seis. A continuación, se presenta el análisis detallado de los ocho problemas con mayor nivel de dificultad.

Problema C

Este problema de registro mostró diferencias notables en los tiempos de solución según la familiaridad con el formato de competencia. La solución implica una lógica de casos directa.

#include <iostream>
using namespace std;

int calcularResultado(int val1, int val2) {
    if (val1 == 0) {
        if (val2 == 0) return 4;
        else if (val2 == 1) return 4;
        else return 6;
    } else if (val1 == 1) {
        if (val2 == 0) return 3;
        else if (val2 == 1) return 3;
        else return 4;
    } else {
        if (val2 == 0) return 2;
        else if (val2 == 1) return 2;
        else return 2;
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << calcularResultado(a, b) << endl;
    return 0;
}

Problema J

Este problema de teoría de juegos parece intimidante, pero su conclusión es simple. Tras explorar manualmente, se observan dos puntos clave: al mover un nodo u a v, u se convierte en hoja; y si v es hoja, la estructura del árbol no cambia, lo cual no está permitido. Cada operación genera una hoja adicional, por lo que basta con verificar la paridad de nodos no hoja. Un caso especial es n=2.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int numNodos;
    cin >> numNodos;
    vector<int> grado(numNodos + 1, 0);
    for (int i = 1; i < numNodos; ++i) {
        int u, v;
        cin >> u >> v;
        grado[u]++;
        grado[v]++;
    }
    int contadorImpar = 0, hayNoHoja = 0;
    for (int i = 1; i < numNodos; ++i) {
        if (grado[i] > 1) {
            contadorImpar ^= 1;
            hayNoHoja = 1;
        }
    }
    if (!(contadorImpar & 1) && hayNoHoja) cout << "Alice";
    else cout << "Bob";
    return 0;
}

Problema E

Un problema clásico de búsqueda en amplitud que invloucra granjeros, lobos, ovejas y un bote. Se modela con estados definidos por la cantidad de ovejas y lobos en una orilla y la posición del granjero. Se verifica en cada cruce si las condiciones se cumplen.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Estado {
    int pasos, ovejas, lobos, lado;
};

bool esValido(int o, int l, int lado, int cap, int maxOvejas, int maxLobos) {
    if (lado == 1) {
        return (maxLobos - l) <= ((maxOvejas - o) + cap) || o == maxOvejas;
    } else {
        return l <= (o + cap) || o == 0;
    }
}

int main() {
    int X, Y, Q, P;
    cin >> X >> Y >> Q >> P;
    int distancia[101][101][2];
    memset(distancia, 0x3f, sizeof(distancia));
    queue<Estado> cola;
    distancia[0][0][0] = 0;
    cola.push({0, 0, 0, 0});
    while (!cola.empty()) {
        Estado actual = cola.front(); cola.pop();
        if (actual.lado == 0) {
            for (int i = 0; i <= X - actual.ovejas; ++i) {
                for (int j = 0; j <= Y - actual.lobos; ++j) {
                    if (i + j > Q) break;
                    if (!esValido(actual.ovejas + i, actual.lobos + j, 1, Q, X, Y)) continue;
                    if (actual.ovejas + i == X) { cout << actual.pasos + 1; return 0; }
                    if (distancia[actual.ovejas + i][actual.lobos + j][1] > actual.pasos + 1) {
                        distancia[actual.ovejas + i][actual.lobos + j][1] = actual.pasos + 1;
                        cola.push({actual.pasos + 1, actual.ovejas + i, actual.lobos + j, 1});
                    }
                }
            }
        } else {
            for (int i = 0; i <= actual.ovejas; ++i) {
                for (int j = 0; j <= actual.lobos; ++j) {
                    if (i + j > Q) break;
                    if (!esValido(actual.ovejas - i, actual.lobos - j, 0, Q, X, Y)) continue;
                    if (distancia[actual.ovejas - i][actual.lobos - j][0] > actual.pasos + 1) {
                        distancia[actual.ovejas - i][actual.lobos - j][0] = actual.pasos + 1;
                        cola.push({actual.pasos + 1, actual.ovejas - i, actual.lobos - j, 0});
                    }
                }
            }
        }
    }
    cout << -1;
    return 0;
}

Problema K

Un buen problema de estructuras de datos. Se determina que la máxima frecuencia de aumento se logra colocando los concursos de aumento al principio. Si hay k concursos de aumento, se ordenan por valor descendente y se insertan los concursos de decremento para cubrir tantos aumentos como sea posible. Se puede usar un árbol de búsqueda balanceado o un segment tree con búsqueda binaria.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct NodoArbol {
    long long valor, cantidad, suma, tamano;
    NodoArbol *izq, *der;
    NodoArbol(long long v) : valor(v), cantidad(1), suma(v), tamano(1), izq(nullptr), der(nullptr) {}
};

void actualizarTamano(NodoArbol* nodo) {
    if (!nodo) return;
    nodo->tamano = 1;
    if (nodo->izq) nodo->tamano += nodo->izq->tamano;
    if (nodo->der) nodo->tamano += nodo->der->tamano;
}

void insertar(NodoArbol*& raiz, long long val) {
    if (!raiz) {
        raiz = new NodoArbol(val);
        return;
    }
    if (val == raiz->valor) {
        raiz->cantidad++;
        raiz->suma += val;
        actualizarTamano(raiz);
        return;
    }
    if (val < raiz->valor) insertar(raiz->izq, val);
    else insertar(raiz->der, val);
    actualizarTamano(raiz);
}

long long consulta(NodoArbol* raiz, long long requerido) {
    if (!raiz || requerido <= 0) return 0;
    if (raiz->izq && raiz->izq->suma >= requerido) return consulta(raiz->izq, requerido);
    long long subtotal = raiz->izq ? raiz->izq->suma : 0;
    if (subtotal + raiz->valor * raiz->cantidad >= requerido) {
        long long restante = requerido - subtotal;
        long long cubiertos = (raiz->izq ? raiz->izq->tamano : 0);
        cubiertos += (restante + raiz->valor - 1) / raiz->valor;
        return cubiertos;
    }
    return (raiz->izq ? raiz->izq->tamano : 0) + raiz->cantidad + consulta(raiz->der, requerido - subtotal - raiz->valor * raiz->cantidad);
}

int main() {
    long long n, Q;
    cin >> n >> Q;
    vector<long long> datos(n);
    NodoArbol* raiz = nullptr;
    long long totalDecremento = 0;
    for (int i = 0; i < n; ++i) {
        cin >> datos[i];
        if (datos[i] > 0) insertar(raiz, datos[i]);
        else totalDecremento -= datos[i];
    }
    while (Q--) {
        int idx; long long nuevoValor;
        cin >> idx >> nuevoValor;
        idx--;
        if (datos[idx] > 0) { /* lógica para remover */ }
        else totalDecremento += datos[idx];
        if (nuevoValor > 0) insertar(raiz, nuevoValor);
        else totalDecremento -= nuevoValor;
        datos[idx] = nuevoValor;
        long long resultado = consulta(raiz, totalDecremento) + 1;
        cout << resultado << endl;
    }
    return 0;
}

Problema M

Un problema de exploración manual. Se observa un patrón cíclico cada dos dígitos: 0->1->3->2->0. Para la k-ésima visita a 0, la cantidad de pasos es la suma de una serie geométrica de razón 4. Para otros dígitos, depende del número de ceros finales. Se precalcula la serie y se aplica módulo.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const long long MOD = 1000000007;
const long long INV3 = 333333336;

long long powMod(long long base, long long exp) {
    long long res = 1;
    while (exp) {
        if (exp % 2) res = res * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return res;
}

long long serieGeometrica(long long k) {
    return (powMod(4, k) - 1) % MOD * INV3 % MOD;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s1, s2;
        cin >> s1 >> s2;
        int k;
        cin >> k;
        int len = max(s1.size(), s2.size());
        if (len % 2) len++;
        int diff[5050] = {0};
        for (int i = 1; i <= len; ++i) {
            int bit1 = (i <= s1.size()) ? s1[s1.size() - i] - '0' : 0;
            int bit2 = (i <= s2.size()) ? s2[s2.size() - i] - '0' : 0;
            int xorBit = bit1 ^ bit2;
            if (xorBit == 1) diff[i] = (i % 2 == 1) ? 1 : 3;
            else if (xorBit == 3) diff[i] = 2;
        }
        int primerNoCero = 0;
        for (int i = 1; i <= len; ++i) {
            if (diff[i] != 0) { primerNoCero = i; break; }
        }
        if (primerNoCero == 0) {
            cout << (serieGeometrica(k) - 1 + MOD) % MOD << endl;
            continue;
        }
        if (k > primerNoCero) { cout << -1 << endl; continue; }
        long long resultado = 0;
        for (int i = 1; i <= len; ++i) {
            resultado = (resultado + diff[i] * serieGeometrica(i)) % MOD;
        }
        cout << (resultado % MOD + MOD) % MOD << endl;
    }
    return 0;
}

Problema B

Un problema de medalla dorada. Involucra encontrar la k-ésima permutación lexicográfica con propiedades específicas de ascenso y descenso. Se utiliza programación dinámica para calcular el número de configuraciones válidas para segmentos de datos, y se construye la solución greedymente.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
long long dp[111][111];

void precalcular(int maxN) {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= maxN; ++i) dp[i][0] = 1;
    for (int i = 0; i <= maxN; ++i) {
        for (int j = 1; j <= maxN; ++j) {
            for (int k = 1; k <= i + j; ++k) {
                if (j % 2 == 1) {
                    for (int l = 1; l < k; ++l) {
                        dp[i][j] += dp[i + j - k][j - 1];
                        if (dp[i][j] > INF) dp[i][j] = INF;
                    }
                } else {
                    for (int l = k; l <= i + j; ++l) {
                        dp[i][j] += dp[i + j - l][j - 1];
                        if (dp[i][j] > INF) dp[i][j] = INF;
                    }
                }
            }
        }
    }
}

long long contarConfiguraciones(int* arr, int n) {
    long long res = 1;
    int segmentoActual = 0, suma = 0;
    for (int i = 1; i <= n; ++i) {
        if (arr[i] == 0) segmentoActual++;
        if (i == n || arr[i + 1] != 0) {
            if (segmentoActual > 0) {
                if (INF / res < dp[suma][segmentoActual]) { res = INF; break; }
                res *= dp[suma][segmentoActual];
            }
            suma += segmentoActual;
            segmentoActual = 0;
        }
    }
    return res;
}

int main() {
    precalcular(50);
    int n; long long K;
    cin >> n >> K;
    int solucion[111] = {0}, asignado[111] = {0};
    int primerValor = -1;
    long long acumulado = 0;
    for (int j = 1; j <= n; ++j) {
        long long contribucion = dp[0][j - 1] * dp[j - 1][n - j];
        if (K - acumulado <= contribucion) { primerValor = j; break; }
        acumulado += contribucion;
    }
    if (primerValor == -1) { cout << -1; return 0; }
    solucion[1] = primerValor;
    asignado[primerValor] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int candidato = 1; candidato <= n; ++candidato) {
            if (asignado[candidato]) continue;
            bool valido = true;
            if ((candidato % 2) == (primerValor % 2)) valido = false;
            if (candidato == 1 && asignado[2]) valido = false;
            if (candidato == n && asignado[n - 1]) valido = false;
            if (asignado[candidato - 1] && asignado[candidato + 1]) valido = false;
            if (!valido) continue;
            asignado[candidato] = i;
            long long formas = contarConfiguraciones(asignado, n);
            if (acumulado + formas >= K) { solucion[i] = candidato; break; }
            acumulado += formas;
            asignado[candidato] = 0;
        }
    }
    for (int i = 1; i <= n; ++i) cout << solucion[i] << " ";
    return 0;
}

Problema D

Otro problema de medalla dorada. Se requiere seleccionar subcadenas de S y T que al concatenarse formen un cuadrado (cadena de la forma XX). Se precalcula la coincidencia de sufijos y prefijos, y se usa conteo con prefijos para sumar contriubciones.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    int n = S.size(), m = T.size();
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int len = min(n - i, m - j);
            for (int k = 1; k <= len; ++k) {
                if (S.substr(i, k) == T.substr(j, k)) {
                    total++;
                }
            }
        }
    }
    cout << total << endl;
    return 0;
}

Problema I

Un problema de clasificación detallada. La idea clave es que al menos un rectángulo debe cubrir dos esquinas. Se asume que los rectángulos que cubren filas son más numerosos que los que cubren columnas, y se analizan varios casos según el número de rectángulos en cada dirección.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long calcularCaso(int n, int m, int a1, int b1, int a2, int b2, int a3, int b3) {
    if (a1 * b1 == n * m || a2 * b2 == n * m || a3 * b3 == n * m) {
        long long res = 1;
        if (a1 * b1 != n * m) res = res * (n - a1 + 1) % MOD * (m - b1 + 1) % MOD;
        if (a2 * b2 != n * m) res = res * (n - a2 + 1) % MOD * (m - b2 + 1) % MOD;
        if (a3 * b3 != n * m) res = res * (n - a3 + 1) % MOD * (m - b3 + 1) % MOD;
        return res;
    }
    int cubrenFilas = 0, cubrenColumnas = 0;
    if (a1 == n) cubrenFilas++; else if (b1 == m) cubrenColumnas++;
    if (a2 == n) cubrenFilas++; else if (b2 == m) cubrenColumnas++;
    if (a3 == n) cubrenFilas++; else if (b3 == m) cubrenColumnas++;
    if (cubrenFilas == 0 && cubrenColumnas == 0) return 0;
    if (cubrenFilas == 3 || cubrenColumnas == 3) {
        // Lógica para tres rectángulos en una dirección
        return 2; // Simplificado para ejemplo
    }
    if (cubrenFilas == 2 || cubrenColumnas == 2) {
        // Lógica para dos rectángulos en una dirección
        return 4; // Simplificado para ejemplo
    }
    if (cubrenFilas == 1 && cubrenColumnas == 1) return 4;
    if (cubrenFilas + cubrenColumnas == 1) return 4;
    return 0;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, a1, b1, a2, b2, a3, b3;
        cin >> n >> m >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;
        cout << calcularCaso(n, m, a1, b1, a2, b2, a3, b3) << endl;
    }
    return 0;
}