Resultados de entrenamiento

Soluciones técnicas

Problema 1: Minimización de valores máximos

Implementamos una solución de búsqueda binaria para encontrar el valor mínimo posible del máximo elemento después de operaciones permitidas.

#include <algorithm>
#include <vector>

using namespace std;

bool verificar(vector<int>& datos, int objetivo) {
  vector<int> copia = datos;
  for(int i = 1; i < copia.size()-1; i++) {
    if(copia[i] > objetivo) {
      int vecinos = max(copia[i-1], copia[i+1]);
      int reduccion = min((copia[i] - vecinos)/2, copia[i] - objetivo);
      copia[i] -= reduccion;
      copia[i-1] += reduccion;
      copia[i+1] += reduccion;
    }
  }
  return all_of(copia.begin(), copia.end(), [objetivo](int x){return x <= objetivo;});
}

int resolver(vector<int>& datos) {
  int izquierda = 0, derecha = 1e9, respuesta = 0;
  while(izquierda <= derecha) {
    int medio = (izquierda + derecha)/2;
    if(verificar(datos, medio)) {
      respuesta = medio;
      derecha = medio - 1;
    } else {
      izquierda = medio + 1;
    }
  }
  return respuesta;
}

Problema 2: Validación de árbol mágico

Implementamos un algoritmo recursivo que verifica propiedades específicas de los nodos en un árbol.

bool validar_arbol(vector<int>& nodos) {
  unordered_map<int, int> posiciones;
  unordered_map<int, int> distancias;
  int divisor_comun = 0;
  
  for(int i = 0; i < nodos.size(); i++) {
    if(posiciones.count(nodos[i])) {
      int distancia = i - posiciones[nodos[i]];
      posiciones[nodos[i]] = i;
      
      if(distancias[nodos[i]] == 0) {
        distancias[nodos[i]] = distancia;
        divisor_comun = gcd(divisor_comun, distancia);
      } else if(distancias[nodos[i]] != distancia) {
        return false;
      }
    } else {
      posiciones[nodos[i]] = i;
    }
  }
  
  if(divisor_comun == 1) return false;
  
  vector<vector<int>> subarboles(divisor_comun);
  for(int i = 0; i < nodos.size(); i++) {
    subarboles[i % divisor_comun].push_back(nodos[i]);
  }
  
  bool resultado = true;
  for(auto& subarbol : subarboles) {
    resultado &= validar_arbol(subarbol);
  }
  return resultado;
}

Problema 3: Cálculo de expectativas en juegos

Utilizamos técnicas combinatorias avanzadas para calcular valores esperados en configuraciones de juego.

int calcular_expectativa(vector<int>& a, vector<int>& b, int k) {
  sort(a.begin(), a.end());
  sort(b.rbegin(), b.rend());
  
  int max_suma = *max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end());
  vector<vector<int>> dp(a.size()+1, vector<int>(max_suma+2));
  
  for(int suma = 1; suma <= max_suma; suma++) {
    vector<int> posiciones(a.size());
    for(int i = 0; i < a.size(); i++) {
      posiciones[i] = upper_bound(b.begin(), b.end(), suma - a[i], greater<int>()) - b.begin();
    }
    
    vector<int> temp(a.size()+1);
    temp[0] = 1;
    for(int i = 0; i < a.size(); i++) {
      for(int j = min(i, posiciones[i]); j >= 0; j--) {
        temp[j+1] = (temp[j+1] + temp[j] * (posiciones[i] - j)) % MODULO;
      }
    }
    
    for(int i = 1; i <= a.size(); i++) {
      dp[i][suma] = (dp[i][suma] + temp[i]) % MODULO;
    }
  }
  
  int resultado = 0;
  for(int i = k; i <= a.size(); i++) {
    int contribucion = 0;
    for(int suma = 1; suma <= max_suma; suma++) {
      int diferencia = (dp[i][suma] - dp[i][suma+1] + MODULO) % MODULO;
      contribucion = (contribucion + diferencia * suma) % MODULO;
    }
    
    int termino = combinar(i-1, k-1) * contribucion % MODULO;
    termino = termino * inverso(permutar(a.size(), i)) % MODULO;
    
    if((i-k) % 2) {
      resultado = (resultado - termino + MODULO) % MODULO;
    } else {
      resultado = (resultado + termino) % MODULO;
    }
  }
  return resultado;
}

Problema 4: Optimización de conexiones en mallas

Implementamos el algoritmo de Steiner para encontrar la conexión óptima en una malla de puntos discretizados.

struct Punto {
  int x, y;
  int codificar(int columnas) const { return (x-1)*columnas + y; }
};

int resolver_steiner(vector<Punto>& puntos) {
  vector<int> xs, ys;
  for(auto& p : puntos) {
    xs.push_back(p.x);
    ys.push_back(p.y);
  }
  
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  
  int filas = xs.size();
  int columnas = ys.size();
  int nodos = filas * columnas;
  
  vector<vector<pair<int, int>>> grafo(nodos+1);
  // Construcción del grafo omitida por brevedad
  
  vector<vector<int>> dp(1 << puntos.size(), vector<int>(nodos+1, INFINITO));
  
  for(int i = 0; i < puntos.size(); i++) {
    int x = lower_bound(xs.begin(), xs.end(), puntos[i].x) - xs.begin() + 1;
    int y = lower_bound(ys.begin(), ys.end(), puntos[i].y) - ys.begin() + 1;
    dp[1 << i][Punto{x,y}.codificar(columnas)] = 0;
  }
  
  for(int mascara = 1; mascara < (1 << puntos.size()); mascara++) {
    for(int sub = (mascara-1) & mascara; sub; sub = (sub-1) & mascara) {
      for(int nodo = 1; nodo <= nodos; nodo++) {
        dp[mascara][nodo] = min(dp[mascara][nodo], dp[sub][nodo] + dp[mascara^sub][nodo]);
      }
    }
    // Implementación de SPFA omitida por brevedad
  }
  
  int resultado = *min_element(dp[(1 << puntos.size())-1].begin(), dp[(1 << puntos.size())-1].end());
  return resultado + 1;
}