La competencia simulada se llevó a cabo con una duración de tres horas. A cnotinuación, se detallan los puntajes obtenidos para cada problema:

El puntaje total fue de 280 de 450 posibles.

Problema A: Sudoku

El problema consiste en validar una cuadrícula de Sudoku según las reglas estándar. La solución implica leer la entrada, mapear la cuadrícula a una matriz 9x9, y verificar filas, colunmas y subcuadrículas 3x3 para duplicados.

#include <bits/stdc++.h>
using namespace std;

int cuadricula[10][10];
int centros[9][2] = {{2,2}, {2,5}, {2,8}, {5,2}, {5,5}, {5,8}, {8,2}, {8,5}, {8,8}};
int desplazamientos[9][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,0}, {0,1}, {1,-1}, {1,0}, {1,1}};

bool validarFilasColumnas() {
    for (int i = 1; i <= 9; i++) {
        bitset<10> filaUsada, columnaUsada;
        for (int j = 1; j <= 9; j++) {
            if (cuadricula[i][j] != 0) {
                if (filaUsada[cuadricula[i][j]]) return false;
                filaUsada[cuadricula[i][j]] = 1;
            }
            if (cuadricula[j][i] != 0) {
                if (columnaUsada[cuadricula[j][i]]) return false;
                columnaUsada[cuadricula[j][i]] = 1;
            }
        }
    }
    return true;
}

bool validarSubcuadriculas() {
    for (int k = 0; k < 9; k++) {
        int cx = centros[k][0], cy = centros[k][1];
        bitset<10> usados;
        for (int d = 0; d < 9; d++) {
            int nx = cx + desplazamientos[d][0], ny = cy + desplazamientos[d][1];
            if (cuadricula[nx][ny] != 0) {
                if (usados[cuadricula[nx][ny]]) return false;
                usados[cuadricula[nx][ny]] = 1;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i <= 13; i++) {
        string linea;
        cin >> linea;
        if (i == 1 || i == 5 || i == 9 || i == 13) continue;
        int fila;
        if (i == 2) fila = 1;
        else if (i == 3) fila = 2;
        else if (i == 4) fila = 3;
        else if (i == 6) fila = 4;
        else if (i == 7) fila = 5;
        else if (i == 8) fila = 6;
        else if (i == 10) fila = 7;
        else if (i == 11) fila = 8;
        else if (i == 12) fila = 9;
        for (int j = 1; j <= 13; j++) {
            if (j == 1 || j == 5 || j == 9 || j == 13) continue;
            int columna;
            if (j == 2) columna = 1;
            else if (j == 3) columna = 2;
            else if (j == 4) columna = 3;
            else if (j == 6) columna = 4;
            else if (j == 7) columna = 5;
            else if (j == 8) columna = 6;
            else if (j == 10) columna = 7;
            else if (j == 11) columna = 8;
            else if (j == 12) columna = 9;
            cuadricula[fila][columna] = (linea[j-1] == '.') ? 0 : (linea[j-1] - '0');
        }
    }
    if (validarFilasColumnas() && validarSubcuadriculas()) {
        cout << "OK\n";
    } else {
        cout << "ERROR\n";
    }
    return 0;
}

Problema B: Laberinto

Dado un laberinto con celdas de colores, se debe encontrar la mínima cantidad de colores distintos al ir del inicio al final. La solución utiliza BFS con compresión de estado para el conjunto de colores visitdaos, donde el estado es (fila, columna, máscara de colores).

#include <bits/stdc++.h>
using namespace std;

const int MAX_DIM = 105;
int paredesHorizontales[MAX_DIM][MAX_DIM], paredesVerticales[MAX_DIM][MAX_DIM];
int visitado[MAX_DIM][MAX_DIM][16];
int filas, columnas;

int convertirColor(char c) {
    if (c == 'P') return 0;
    if (c == 'C') return 1;
    if (c == 'Z') return 2;
    if (c == 'N') return 3;
    return -1;
}

int contarBits(int mascara) {
    int cnt = 0;
    while (mascara) {
        cnt += (mascara & 1);
        mascara >>= 1;
    }
    return cnt;
}

bool dentroLimites(int x, int y) {
    return x >= 1 && x <= filas && y >= 1 && y <= columnas;
}

int bfs(int inicioX, int inicioY, int finX, int finY) {
    queue<tuple<int,int,int>> cola;
    memset(visitado, 0, sizeof(visitado));
    cola.push({inicioX, inicioY, 0});
    int resultado = 5;
    while (!cola.empty()) {
        auto [x, y, mascara] = cola.front();
        cola.pop();
        if (visitado[x][y][mascara]) continue;
        visitado[x][y][mascara] = 1;
        if (x == finX && y == finY) {
            resultado = min(resultado, contarBits(mascara));
            continue;
        }
        if (dentroLimites(x, y+1) && !visitado[x][y+1][mascara | (1 << paredesHorizontales[x][y])]) {
            cola.push({x, y+1, mascara | (1 << paredesHorizontales[x][y])});
        }
        if (dentroLimites(x+1, y) && !visitado[x+1][y][mascara | (1 << paredesVerticales[x][y])]) {
            cola.push({x+1, y, mascara | (1 << paredesVerticales[x][y])});
        }
        if (dentroLimites(x, y-1) && !visitado[x][y-1][mascara | (1 << paredesHorizontales[x][y-1])]) {
            cola.push({x, y-1, mascara | (1 << paredesHorizontales[x][y-1])});
        }
        if (dentroLimites(x-1, y) && !visitado[x-1][y][mascara | (1 << paredesVerticales[x-1][y])]) {
            cola.push({x-1, y, mascara | (1 << paredesVerticales[x-1][y])});
        }
    }
    return resultado;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> filas >> columnas;
    for (int i = 1; i <= filas; i++) {
        string linea;
        cin >> linea;
        for (int j = 1; j < columnas; j++) {
            paredesHorizontales[i][j] = convertirColor(linea[j-1]);
        }
    }
    for (int i = 1; i < filas; i++) {
        string linea;
        cin >> linea;
        for (int j = 1; j <= columnas; j++) {
            paredesVerticales[i][j] = convertirColor(linea[j-1]);
        }
    }
    int consultas;
    cin >> consultas;
    while (consultas--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << bfs(x1, y1, x2, y2) << '\n';
    }
    return 0;
}

Problema C: RMQ 2D

El problema requiere calcular el máximo en submatrices de tamaño fijo usando una técnica de ventanas deslizantes en 2D. Se preprocesa por columnas y luego por filas para reducir la complejidad a O(n^2).

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 4005;
int matriz[MAX_N][MAX_N], buffer[MAX_N][MAX_N];
int filas, columnas, alturaVentana, anchoVentana;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> filas >> columnas;
    for (int i = 1; i <= filas; i++) {
        for (int j = 1; j <= columnas; j++) {
            cin >> matriz[i][j];
        }
    }
    cin >> alturaVentana >> anchoVentana;
    // Preprocesamiento por columnas
    for (int j = 1; j <= columnas; j++) {
        deque<int> dq;
        for (int i = 1; i <= filas; i++) {
            while (!dq.empty() && dq.front() < i - alturaVentana + 1) dq.pop_front();
            while (!dq.empty() && matriz[dq.back()][j] <= matriz[i][j]) dq.pop_back();
            dq.push_back(i);
            if (i >= alturaVentana) buffer[i - alturaVentana + 1][j] = matriz[dq.front()][j];
        }
    }
    // Preprocesamiento por filas y salida
    for (int i = 1; i <= filas - alturaVentana + 1; i++) {
        deque<int> dq;
        for (int j = 1; j <= columnas; j++) {
            while (!dq.empty() && dq.front() < j - anchoVentana + 1) dq.pop_front();
            while (!dq.empty() && buffer[i][dq.back()] <= buffer[i][j]) dq.pop_back();
            dq.push_back(j);
            if (j >= anchoVentana) cout << buffer[i][dq.front()] << " ";
        }
        cout << '\n';
    }
    return 0;
}

Problema D: Conteo de configuraciones

Se modela con programación dinámica donde dp[i][j] representa el número de formas de colocar j bloques en un intervalo de ancho i. La recurrencia considera colocaciones en los lados y en el mismo lugar.

#include <bits/stdc++.h>
using namespace std;

const int MAX_VAL = 5005;
const int MODULO = 1e9 + 7;
int dp[MAX_VAL][MAX_VAL];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    if (n == 1) {
        cout << k << '\n';
        return 0;
    }
    if (k == 1) {
        cout << 1 << '\n';
        return 0;
    }
    for (int i = 2; i <= n; i++) dp[2][i] = 2;
    for (int i = 3; i <= k; i++) {
        for (int j = i; j <= n; j++) {
            dp[i][j] = ((dp[i-1][j-1] + dp[i-1][j-i+1]) % MODULO + dp[i][j-2]) % MODULO;
        }
    }
    long long respuesta = 0;
    for (int i = 1; i <= k; i++) {
        respuesta = (respuesta + 1LL * dp[i][n] * (k - i + 1)) % MODULO;
    }
    cout << respuesta << '\n';
    return 0;
}