T1: No Problem

Problema: Una sala de clases de n x m personas, donde cada individuo da la mano a sus vecinos en las ocho direcciones circundantes. Si hay asientos vacíos, el profesor se sienta para maximizar el número total de apretones de mano. Calcular el total de apretones realizados.

En el concurso, implementé una solución directa, pero olvidé manejar el caso cuando todas las celdas están ocupadas desde el inicio, resultando en una puntuación reducida.

Solución: Se puede calcular mediante fuerza bruta iterando sobre todas las posibles posiciones para el profeser. La complejidad es O(n^4), pero es suficiente para los límites del problema.

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX_VAL 0x3f3f3f3f
using namespace std;

int filas, columnas;
vector<vector<int>> aula;
vector<pair<int,int>> direcciones = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}};

int calcularApretones() {
    int total = 0;
    for (int i = 1; i <= filas; ++i) {
        for (int j = 1; j <= columnas; ++j) {
            if (aula[i][j]) {
                for (auto& dir : direcciones) {
                    total += aula[i + dir.first][j + dir.second];
                }
            }
        }
    }
    return total / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> filas >> columnas;
    aula.assign(filas + 2, vector<int>(columnas + 2, 0));
    for (int i = 1; i <= filas; ++i) {
        for (int j = 1; j <= columnas; ++j) {
            char c;
            cin >> c;
            aula[i][j] = (c == '.') ? 0 : 1;
        }
    }

    int respuesta = calcularApretones();
    for (int i = 1; i <= filas; ++i) {
        for (int j = 1; j <= columnas; ++j) {
            if (!aula[i][j]) {
                aula[i][j] = 1;
                respuesta = max(respuesta, calcularApretones());
                aula[i][j] = 0;
            }
        }
    }
    cout << respuesta << "\n";
    return 0;
}

T2: Str

Problema: Dada una transformación de cadena definida como f([s1,s2,...,sn]) = [s1,sn,s2,s_{n-1},...], y una cadena resultante después de k transformaciones, recuperar la cadena original.

Durante el concurso, generé una tabla de valores y encontré la solución rápidamente.

Solución: Se observa que la transformación tiene periodicidad. Consultando secuencias en OEIS, se descubre que corresponde a un "barajado de leche" con un orden periódico. Precomputar el período toma O(n^2), lo que permite resolver el problema eficientemente.

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

int calcularPeriodo(int longitud) {
    vector<int> secuenciaActual(longitud), secuenciaTemporal(longitud);
    for (int i = 0; i < longitud; ++i) secuenciaActual[i] = i + 1;
    int contador = 0;
    bool esOrdenada;
    do {
        esOrdenada = true;
        int indice = 0;
        int izq = 0, der = longitud - 1;
        while (izq <= der) {
            secuenciaTemporal[indice++] = secuenciaActual[izq++];
            if (izq > der) break;
            secuenciaTemporal[indice++] = secuenciaActual[der--];
        }
        for (int i = 1; i < longitud; ++i) {
            if (secuenciaTemporal[i] != secuenciaTemporal[i-1] + 1) {
                esOrdenada = false;
                break;
            }
        }
        contador++;
        secuenciaActual = secuenciaTemporal;
    } while (!esOrdenada);
    return contador;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    string cadena;
    cin >> k >> cadena;
    int n = cadena.length();
    int periodo = calcularPeriodo(n);
    k %= periodo;

    while (k--) {
        string izquierda, derecha;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) izquierda += cadena[i];
            else derecha += cadena[i];
        }
        reverse(derecha.begin(), derecha.end());
        cadena = izquierda + derecha;
    }
    cout << cadena << "\n";
    return 0;
}

T3: Not TSP

Problema: Con n puntos numerados del 1 al n, y distancias d(i,j), visitar todos los puntos exactamente una vez, con la restricción de que al visitar el punto i, todos los puntos anteriores (1 a i-1) deben estar ya visitados o no visitados. Encontrar la ruta más corta.

Durante el concurso, intenté varias ideas, pero ninguna funcionó correctamente.

Solución: Se utiliza programación dinámica. Definir dp[i][j] como la distancia mínima para haber visitado un subconjunto de puntos hasta el máximo de i y j. Se actualizan los estados considerando transiciones entre puntos.

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define LARGO_INF 0x3f3f3f3f3f3f3f3f
using namespace std;

int n;
vector<vector<long long>> distancias;
vector<vector<long long>> dp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    distancias.assign(n + 1, vector<long long>(n + 1, 0));
    dp.assign(n + 1, vector<long long>(n + 1, LARGO_INF));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> distancias[i][j];
        }
    }

    dp[1][1] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int siguiente = max(i, j) + 1;
            if (siguiente > n) continue;
            dp[i][siguiente] = min(dp[i][siguiente], dp[i][j] + distancias[j][siguiente]);
            dp[siguiente][j] = min(dp[siguiente][j], dp[i][j] + distancias[i][siguiente]);
        }
    }

    long long resultado = LARGO_INF;
    for (int i = 1; i <= n; ++i) {
        resultado = min(resultado, min(dp[i][n], dp[n][i]));
    }
    cout << resultado << "\n";
    return 0;
}

T4: Game

Problema: Juego entre Alice y Bob con n puntos en el plano. Alice dibuja primero una línea paralela al eje x o y que pase por un punto. Luego, los jugadores alternan dibujando líneas paralelas a los ejes, intersectando la línea anterior, pasando por algún punto y sin repetir líneas. Pierde quien no pueda mover.

Durante el concurso, no comprendí el problema inmediatamente, pero tras una explicación, se redujo a un análisis simple.

Solución: El número de líneas verticales posibles es igual al número de coordenadas x únicas, y el de horizontales al de coordenadas y únicas. Los jugadores alternan entre líneas verticales y horizontales. Alice pierde si y solo si el número de líneas verticales y horizontales es igual.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_set<int> coordenadasX, coordenadasY;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        coordenadasX.insert(x);
        coordenadasY.insert(y);
    }

    if (coordenadasX.size() == coordenadasY.size()) {
        cout << "Bob\n";
    } else {
        cout << "Alice\n";
    }
    return 0;
}