Técnicas Avanzadas de Optimización y Algoritmia
Este artículo compila una colección de técnicas y trucos avanzados utilizados en programación competitiva, abarcando desde algoritmos poco comunes hasta optimizaciones esenciales para problemas complejos.
1. Enumeración de Subconjuntos en Subconjuntos
Al iterar sobre todos los subconjuntos de una sceuencia de longitud $n$ y, a su vez, sobre los subconjuntos de cada uno de ellos, la complejidad temporal resulta ser $O(3^n)$, ya que cada situación corresponde a una cifra en base 3. Una forma eficiente de implementar esto (usando máscara de bits) es la siguiente:
for (int mascara = 0; mascara < (1 << n); ++mascara) {
for (int sub = mascara; sub > 0; sub = (mascara & (sub - 1))) {
procesar(sub);
}
procesar(0); // El conjunto vacío no se itera en el bucle anterior
}
2. Multiplicación de Matrices con Bitset (XOR)
Si redefinimos la suma y la multiplicación matricial utilizando operaciones de XOR (suma módulo 2) en lugar de la aritmética estándar, podemos optimizar el cálculo utilizando bitsets. Esto es especialmente útil cuando las matrices solo contienen 0s y 1s.
bitset<max> res[MAX], A[MAX], B[MAX];
// Transposición de B para optimizar acceso
for (int i = 0; i < k; ++i)
for (int j = i + 1; j < k; ++j)
swap(B[i][j], B[j][i]);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
// La operación (A[i] & B[j]) realiza las multiplicaciones y sumas en paralelo
res[i][j] = (A[i] & B[j]).count() & 1;
}
}</max>
3. Árbol de Expansión Mínima Estrictamente Segundo Mejor
Para encontrar el segundo árbol de expansión mínima (MST) con peso estrictamente mayor al MST, primero construimos el MST original. Luego, utilizamos preprocesamiento con binary lifting para calcular los ancestros comunes (LCA). Para cada arista que no está en el MST, al añadirla se forma un ciclo entre los nodos $u$ y $v$. El objetivo es eliminar la arista de máximo peso en este ciclo que sea distinta a la nueva arista añadida. Mantenemos los valores máximos y estrictamente segundos máximos durante el preprocesamiento del LCA para realizar esta consulta eficientemente.
4. Riesgos de unordered_set y unordered_map
Si bien los contenedores unordered_set y unordered_map ofrecen una complejidad promedio de $O(1)$ basada en tablas hash, en programación competitiva son vulnerables a ataques de colisiones (hacks) diseñados por los creadores de problemas. Si no se requiere garantía de tiempo logarítmico y el riesgo de hacks es alto, es preferible implementar una tabla hash personalizada o utilizar set/$map estándar ($O(\log n)$) para asegurar la corrección.
3. Complejidad en "Knapsack" sobre Árboles
En problemas de programación dinámica en árboles (Tree DP) donde se combinan subárboles (similar a una mochila), la complejidad a menudo parece ser $O(n^3)$ o $O(n^2)$. Sin embargo, si el tamaño de los subárboles está limitado por un valor constante $L$, la complejidad se reduce a $O(nL)$. Esto ocurre porque el número de pares de nodos en rutas simples de longitud menor a $L$ en un árbol de $n$ nodos es $O(nL)$.
6. Intercambio de Bucles según Restricciones de Producto
Cuando el rango de datos está limitado por un producto (ej. $n \times m \le 10^5$), y se dispone de dos algoritmos con complejidades $O(n^2 m)$ y $O(n m^2)$, se debe elegir el algoritmo que itere más sobre la dimensión más pequeña. El peor caso ocurre cuando $n \approx m$, lo que garantiza que la complejidad total no excederá los límites seguros.
7. Problemas de Caminos Eulerianos
Aunque poco frecuentes, los caminos eulerianos permiten estrategias únicas de orientación o coloreado de aristas para satisfacer condiciones específicas del problema, aprovechando las propiedades de grado de los nodos.
8. Suma Prefija de la Sucesión de Fibonacci
Sea $f(i)$ el i-ésimo número de Fibonacci. La suma de los primeros $n$ términos puede obtenerse mediante la identidad telescópica:
$\sum_{i=1}^{n} f(i) = f(n+2) - f(2)$
Esto permite calcular la suma rápidamente utilizando métodos de exponenciación de matrices para obtener $f(n+2)$.
9. Cálculo Rápido de XOR Prefijo
Para calcular $1 \oplus 2 \oplus 3 \oplus \dots \oplus x$, existe un patrón basado en el residuo de $x$ módulo 4:
long long sumaXor(long long x) {
if (x % 4 == 0) return x;
if (x % 4 == 1) return 1;
if (x % 4 == 2) return x + 1;
return 0;
}
10. Algoritmo de Stein (GCD Binario)
Para optimizar el cálculo del MCD cuando la operación es un cuello de botella, el algoritmo de Stein utiliza operaciones de bits y desplazamientos, evitando la división lenta. La lógica se basa en:
- Si ambos son pares: $gcd(a, b) = 2 \cdot gcd(a/2, b/2)$
- Si solo uno es par: dividir el par por 2.
- Si ambos son impares: $gcd(a, b) = gcd(|a-b|, \min(a, b))$
long long gcd_binario(long long u, long long v) {
if (!u) return v;
if (!v) return u;
int shift = __builtin_ctzll(u | v);
u >>= __builtin_ctzll(u);
do {
v >>= __builtin_ctzll(v);
if (u > v) swap(u, v);
v -= u;
} while (v);
return u << shift;
}
11. Suma Prefijo de Alta Dimensión (SOS DP)
Para calcular sumas prefijadas en arrays multidimensionales (ej. $f[a_1][a_2]...$), en lugar de usar $n$ bucles anidados, se puede realizar una transformación iterando sobre cada dimensión por separado. Esta técnica es fundamental en problemas que requieren sumar sobre submáscaras o divisores de un número.
12. Encontrar el Periodo Mínimo con KMP
Utilizando el arreglo de fallo ($Next$ o $pi$) del algoritmo KMP en una cadena $s$ de longitud $i$, la longitud del periodo mínimo se determina así:
int periodo = i - next[i];
if (i % periodo == 0) {
cout << "El periodo minimo es: " << periodo << endl;
} else {
cout << "No existe periodo que repita la cadena completa" << endl;
}
13. Distancia Máxima en un Árbol (Diámetro)
Para encontrar el punto más lejano de cualquier nodo en un árbol, primero se calcula el diámetro del árbol. La distancia máxima desde cualquier nodo arbitrario $x$ será $\max(\text{dist}(x, \text{endpunto1}), \text{dist}(x, \text{endpunto2}))$. Si se conectan dos árboles, el nuevo diámetro tendrá como extremos uno de los cuatro extremos posibles de los diámetros originales.
14. Aritmética Modular con Irracionales
Si las operaciones intermedias involucran números de la forma $a + b\sqrt{5}$ y se requiere modularidad, se pueden definir operaciones de suma y producto. Para la división, se racionaliza el denominador multiplicando por el conjugado $(a - b\sqrt{5})$, convirtiendo el denominador en un entero $(a^2 - 5b^2)$, permitiendo así calcular el inverso modular.
15. Traversal en Matrices Dispersas
En una matriz muy grande ($N, M \le 10^5$) con pocos puntos clave ($K \le 10^5$), intentar recorrer toda la matriz es inviable. La solución consiste en construir un grafo virtual conectando solo los puntos clave y sus vecinos relevantes (adyacentes), ignorando el espacio vacío entre ellos.
16. Grafos de Camino Más Corto
Un arco $(u, v)$ con peso $w$ pertenece al grafo de camino más corto (de $s$ a $t$) si y solo si $dist[s] + w + dist[v] == dist[t]$. Identificar estas aristas permite construir un DAG (grafo acíclico dirigido) sobre el cual se pueden ejecutar algoritmos de flujo o DP. Un concepto similar aplica para grafos de segundo camino más corto.
17. Optimización Divide and Conquer DP
Cuando la función de costo satisface la desigualdad cuadrilátero (monotonicidad en los puntos de decisión), se puede aplicar la optimización "Divide and Conquer DP". Esto permite calcular la tabla de DP en $O(N \log N)$ en lugar de $O(N^2)$.
18. Construcción de Grafos con Segment Tree
Para optimizar la construcción de grafos donde se conectan rangos completos de nodos (ej. conectar $[1, 2]$ con $[3, 5]$), se utiliza un Segment Tree virtual. Los nodos reales se conectan a los nodos del segment tree ($O(\log N)$), y los nodos del segment tree se conectan entre sí para representar el rango en $O(1)$ por intervalo, reduciendo drasticamente el número de aristas.
19. Comparación de Fracciones
Para verificar si $\frac{a}{b} = \frac{c}{d}$ sin utilizar punto flotante (para evitar errores de precisión), simplemente compare los productos cruzados: $a \cdot d == b \cdot c$.
20. Comparación Léxica con Vectores
En C++, el contenedor std::vector sobrecarga el operador < para realizar comparación léxica elmeento por elemento. Esto es muy útil para ordenar listas de números o cadenas.
21. Hashing de Estructuras Conmutativas
Para comparar multiconjuntos o estructuras donde el orden no importa, se puede diseñar un hash que sea independiente del orden (ej. sumar hashes de elementos o usar polinomios con potencias asignadas por posición en un orden fijo como el valor numérico). Esto permite determinar equivalencia rápida.
22. Optimización DFS con Resolución de Ecuaciones
En búsquedas exhaustivas, si el espacio de estados es muy grande, se pueden asignar variables algebraicas a partes de la solución y derivar ecuaciones para reducir la ramificación. Por ejemplo, al faltar pocas variables, plantear una ecuación lineal puede permitir determinar el valor de una variable sin enumerar todas las posibilidades.
23. Union-Find Ponderado
El DSU (Disjoint Set Union) se puede extender para mantener pesos o distancias relativas entre nodos y su padre. Al usar "path compression", estos pesos deben actualizarse en consecuencia. Es útil para problemas de conectividad con restricciones de distancia modular.
24. Conteo de Componentes Conexas en Árboles
Un método alternativo al DP para contar componentes específicos (como subárboles inducidos por condiciones) es usar la fórmula de características de Euler para grafos (puntos - aristas = componentes) sumando contribuciones individuales.
25. Búsqueda Minimax
En juegos de suma cero entre dos jugadores, el algoritmo Minimax busca maximizar la ganancia del jugador actual minimizando la ganancia del oponente (asumiendo juego óptimo). Se suele implementar con poda Alpha-Beta para mejorar el rendimiento.
26. Descomposición por Cadena Larga
Similar a la descomposición de cadenas pesadas (HLD), pero basada en la longitud del camino hacia la hoja más profunda en lugar del tamaño del subárbol. Es útil para optimizar DP en árboles donde la complejidad depende de la longitud de los caminos.
27. Cálculo Offline de Inversos
Para calcular el inverso modular de un rango de números $[1, N]$ eficientemente, se pueden usar productos prefijos y sufijos. Sea $P[i] = \prod_{k=1}^i k$. El inverso de $P[N]$ se calcula con Fermat. Luego, $inv[i] = P[i-1] \cdot inv(P[N]) \cdot P[i+1..N]$. Esto permite calcular todos los inversos en $O(N)$.
28. Operaciones Globales y Puntuales
Para mantener una secuencia con operaciones de asignación puntual y suma/multiplicación global, se puede usar una estructura de datos (como un Segment Tree) que mantenga etiquetas de "pereza" (lazy tags) para las operaciones globales, aplicando la operación puntual sobre el valor acumulado globalmente.
29. DSU on Tree vs Fusión de Segment Trees
Para consultas sobre subárboles, "DSU on Tree" (small to large) tiene complejidda $O(N \log N)$ en la mayoría de casos, mientras que la fusión de Segment Trees es $O(N \log^2 N)$ o peor dependiendo de la implementación. Sin embargo, DSU on Tree es más difícil de implementar con persistencia, mientras que la fusión de Segment Trees la soporta naturalmente.
30. Estructuras de Datos con Reversión (Rollback)
En algoritmos que requieren retroceder cambios en una estructura de datos (como en divide and conquer en grafos), se implementa un Stack de cambios. Cada modificación guarda la información necesaria para deshacerla, permitiendo volver al estado anterior en tiempo $O(1)$ por operación.
31. Divide and Conquer en Aristas
Esta técnica divide el árbol recursivamente buscando una arista central que divida el árbol en subárboles de tamaño balanceado. Es útil para problemas de conteo de caminos que pasan por ciertos puntos o aristas.
32. Algoritmo X y Dancing Links (DLX)
Una implementación altamente optimizada usando listas doblemente enlazadas para resolver el problema de "Exact Cover". Aunque es un método de búsqueda con retroceso (backtracking), es extremadamente eficiente para su clase específica de problemas.
33. Descomposición de Cadenas en DAG
Generalización de la descomposición de árboles a Grafos Acíclicos Dirigidos (DAG), útil para procesar consultas sobre caminos o ancestros en estructuras jerárquicas que no son estrictamente árboles.
34. Algoritmo de Voto de Mayoría (Boyer-Moore)
Para encontrar el elemento que aparece más de la mitad de las veces en una secuencia en tiempo $O(N)$ y espacio $O(1)$, se utiliza un contador de "votos". Se reduce el contador cuando el elemento actual es diferente del candidato y se aumenta cuando es igual. Si el contador llega a cero, se cambia el candidato. Al final, se debe verificar si el candidato确实是众数。
35. Hashing de Enteros (SplitMix64)
Para evitar colisiones en tablas hash implementadas manualmente, se utiliza una función de mezcla de bits de alta calidad. SplitMix64 es un algoritmo simple y rápido que utiliza operaciones XOR, rotaciones y desplazamientos con una máscara aleatoria.
uint64_t mezcla(uint64_t x) {
const uint64_t mask = chrono::steady_clock::now().time_since_epoch().count();
x ^= mask;
x ^= x >> 30;
x *= 0xbf58476d1ce4e5b9;
x ^= x >> 27;
x *= 0x94d049bb133111eb;
x ^= x >> 31;
return x;
}
36. Amortización en Árbol Tipo Segment Tree
En ciertas estructuras tipo "árbol de segmentes" donde actualizar una hoja actualiza $O(\log N)$ ancestros, si las operaciones tienen propiedades especiales, se puede demostrar que cada nodo se actualiza un número amortizado de veces constante (ej. $O(N \log N)$ total en lugar de $O(N \log^2 N)$).
38. Transformación de DAG a Árbol
Si un DAG tiene un único punto de entrada (fuente) y solo nos interesan relaciones de alcance (ancestría), se puede realizar una ordenación topológica y tratar las conexiones de alcance inmediato como bordes de árbol, transformando la estructura en un árbol para simplificar el procesamiento.
39. Optimización de DP por Intervalos con Memorización
A menudo, la programación dinámica por intervalos se implementa iterativamente. Sin embargo, si se utiliza "memoization" (recursivo con caché), es posible que no se visiten todos los estados $[i, j]$, sino solo aquellos necesarios para llegar a $[1, N]$, lo que puede reducir el tiempo de ejecución en casos específicos.
40. Segment Tree con Búsqueda Binaria Interna
Se refiere a una variante de Segment Tree donde la operación query o update requiere realizar una búsqueda binaria dentro de los nodos del árbol para mantener propiedades globales. Esto suele resultar en una complejidad de $O(N \log^2 N)$ para construcción y consultas.