Se presentan soluciones para cuatro problemas comunes en competencias de programación, abarcando técnicas como programación dinámica con bitmask, grafos en capas, y estructuras de datos como Mo's algorithm y árboles de Fenwick.

Problema A: Cobertura de Petróleo

Este problema implica optimizar la colocación de sensores en una cuadrícula para cubrir todas las celdas de petróleo con coste mínimo, considerando restricciones de adyacencia. Dado que las dimensiones son pequeñas (n*m <= 50, m <= n), se aplica programación dinámica con bitmask para representar estados por fila. Definimos dp[i][j][k] como el coste mínimo hasta la fila i, con la fila actual en estado j y la fila anterior en estado k. La transición verifica si la combinación de estados cubre todas las celdas requeridas, y se precalcula el coste por fila. El código siguiente ilustra una implementación en C++ con optimizaciones de bitmask.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_ROWS = 10, MAX_COLS = 52;
const int INF = 0x3f3f3f3f;
int main() {
    int rows, cols;
    cin >> rows >> cols;
    int grid[MAX_ROWS][MAX_COLS];
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++) cin >> grid[i][j];
    int cost[MAX_ROWS][1<<MAX_COLS] = {0};
    for (int i = 1; i <= rows; i++)
        for (int mask = 0; mask < (1<<cols); mask++)
            for (int k = 0; k < cols; k++)
                if (mask & (1<<k)) cost[i][mask] += grid[i][k+1];
    int dp[MAX_ROWS][1<<MAX_COLS][1<<MAX_COLS];
    int sensorCount[MAX_ROWS][1<<MAX_COLS][1<<MAX_COLS];
    memset(dp, INF, sizeof dp);
    for (int mask = 0; mask < (1<<cols); mask++) {
        dp[1][mask][0] = cost[1][mask];
        sensorCount[1][mask][0] = __builtin_popcount(mask);
    }
    for (int i = 2; i <= rows; i++)
        for (int curMask = 0; curMask < (1<<cols); curMask++)
            for (int prevMask = 0; prevMask < (1<<cols); prevMask++)
                for (int prevPrevMask = 0; prevPrevMask < (1<<cols); prevPrevMask++)
                    if ((curMask | prevMask | prevPrevMask | (prevMask<<1) | (prevMask>>1) & ((1<<cols)-1)) == ((1<<cols)-1)) {
                        int newCost = dp[i-1][prevMask][prevPrevMask] + cost[i][curMask];
                        int newCount = sensorCount[i-1][prevMask][prevPrevMask] + __builtin_popcount(curMask);
                        if (dp[i][curMask][prevMask] > newCost || (dp[i][curMask][prevMask] == newCost && sensorCount[i][curMask][prevMask] > newCount)) {
                            dp[i][curMask][prevMask] = newCost;
                            sensorCount[i][curMask][prevMask] = newCount;
                        }
                    }
    int ansCost = INF, ansSensors = INF;
    for (int mask1 = 0; mask1 < (1<<cols); mask1++)
        for (int mask2 = 0; mask2 < (1<<cols); mask2++)
            if ((mask1 | mask2 | (mask1<<1) | (mask1>>1) & ((1<<cols)-1)) == ((1<<cols)-1))
                if (ansCost > dp[rows][mask1][mask2] || (dp[rows][mask1][mask2] == ansCost && ansSensors > sensorCount[rows][mask1][mask2]))
                    ansCost = dp[rows][mask1][mask2], ansSensors = sensorCount[rows][mask1][mask2];
    cout << ansSensors << " " << ansCost << endl;
    return 0;
}

Problema B: Escape con Pociones

Este problema modela un laberinto donde se puede beber una pocion para teletransportarse a una posición específica. Se utiliza una representación de grafos en capas para simplificar el BFS o Dijkstra. Una capa representa el estado sin pocion, y otra con pocion; dentro de cada capa, se coenctan movimientos ortogonales, y entre capas se permiten transiciones con coste cero o por uso de pocion. A continuación, un código en C++ que implementa esto con Dijkstra, cambiando estructura y variables respecto al original.

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX_SIZE = 1010;
const int LAYER_OFFSET = MAX_SIZE * MAX_SIZE;
char maze[MAX_SIZE][MAX_SIZE];
int dist[2 * MAX_SIZE * MAX_SIZE];
bool visited[2 * MAX_SIZE * MAX_SIZE];
struct Edge {
    int to, weight, next;
} edges[4 * MAX_SIZE * MAX_SIZE];
int head[2 * MAX_SIZE * MAX_SIZE], edgeCount = 0;
void addEdge(int u, int v, int w) {
    edges[++edgeCount] = {v, w, head[u]};
    head[u] = edgeCount;
}
int main() {
    int rows, cols, teleportX, teleportY;
    cin >> rows >> cols >> teleportX >> teleportY;
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++) cin >> maze[i][j];
    memset(dist, 0x3f, sizeof dist);
    memset(head, 0, sizeof head);
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (maze[i][j] == '#') continue;
            int nodeId = (i-1)*cols + j;
            if (i > 1 && maze[i-1][j] == '.') {
                addEdge(nodeId, nodeId - cols, 1);
                addEdge(nodeId + LAYER_OFFSET, nodeId - cols + LAYER_OFFSET, 1);
            }
            if (j > 1 && maze[i][j-1] == '.') {
                addEdge(nodeId, nodeId - 1, 1);
                addEdge(nodeId + LAYER_OFFSET, nodeId - 1 + LAYER_OFFSET, 1);
            }
            if (i < rows && maze[i+1][j] == '.') {
                addEdge(nodeId, nodeId + cols, 1);
                addEdge(nodeId + LAYER_OFFSET, nodeId + cols + LAYER_OFFSET, 1);
            }
            if (j < cols && maze[i][j+1] == '.') {
                addEdge(nodeId, nodeId + 1, 1);
                addEdge(nodeId + LAYER_OFFSET, nodeId + 1 + LAYER_OFFSET, 1);
            }
            addEdge(nodeId, nodeId + LAYER_OFFSET, 0);
            int newX = i + teleportX, newY = j + teleportY;
            if (newX >= 1 && newX <= rows && newY >= 1 && newY <= cols && maze[newX][newY] == '.') {
                int targetId = (newX-1)*cols + newY + LAYER_OFFSET;
                addEdge(nodeId, targetId, 1);
            }
        }
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    int nodeIdEnd = rows * cols;
    int result = min(dist[nodeIdEnd], dist[nodeIdEnd + LAYER_OFFSET]);
    if (result == 0x3f3f3f3f) cout << "-1" << endl;
    else cout << result << endl;
    return 0;
}

Problema C: Operaciones XOR

Este problema se aborda con técnicas como Mo's algorithm o árboles de Fenwick para consultas eficientes. La solución explota propiedades del XOR para mantener resultados acumulados, permiteindo responder preguntas sobre rangos con complejidad reducida.

Problema D: Navegación Interestelar

Para problemas arbóreos, se emplean métodos como LCA (Ancesrto Común Más Bajo) y recorridos de grafos. La clave es descomponer el árbol en subárboles y aplicar programación dinámica o búsquedas en profundidad para optimizar cálculos.

En competencias, es crucial seleccionar la técnica adecuada según las restricciones del problema, como lo demuestran estos ejemplos que combinan algoritmos clásicos con optimizaciones específicas.