Aliens trick (optimización lagrangiana)
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué hace
Quita la restricción de ‘exactamente k partes’ cobrando una penalización λ por cada parte, resuelve el problema libre (que es mucho más barato) y busca por búsqueda binaria el λ que hace que el óptimo use k partes. Solo es válido si el óptimo f(k) es convexo en k.
Complejidad: O(costo del DP sin restricción × log(rango de λ)). Con el DP interno en O(n) u O(n log n), reemplaza un O(n·k) por algo casi independiente de k.
Cuándo usarlo
DPs de la forma ‘parte esto en exactamente k pedazos minimizando un costo’, cuando k es grande y el costo por cantidad de pedazos es convexo. Es la técnica que da nombre al problema Aliens de la IOI 2016.
Implementación recomendada (C++)
// Ejemplo: partir a[0..n) en EXACTAMENTE k trozos contiguos minimizando la
// suma de (suma del trozo)². Con valores no negativos, f(k) es CONVEXA en k,
// que es justo lo que habilita el truco.
int n; vector<long long> pre; // pre[i] = suma de a[0..i)
long long w(int i, int j) { // costo del trozo [i, j)
long long s = pre[j] - pre[i];
return s * s;
}
// Resuelve SIN la restricción de cantidad, cobrando `lam` por cada trozo.
// Devuelve {costo penalizado mínimo, MENOR cantidad de trozos que lo alcanza}.
pair<long long,int> sin_restriccion(long long lam) {
vector<long long> dp(n + 1, 0);
vector<int> cnt(n + 1, 0);
for (int j = 1; j <= n; j++) {
dp[j] = LLONG_MAX;
for (int i = 0; i < j; i++) {
long long val = dp[i] + w(i, j) + lam;
// ante empate, quedarse con MENOS trozos: de eso depende el truco
if (val < dp[j] || (val == dp[j] && cnt[i] + 1 < cnt[j])) {
dp[j] = val; cnt[j] = cnt[i] + 1;
}
}
}
return {dp[n], cnt[n]};
}
// lam_max: cualquier cota superior de la mayor "ganancia por trozo extra".
long long aliens(int k, long long lam_max) {
long long lo = 0, hi = lam_max; // el menor lam cuyo conteo mínimo ya no pasa de k
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (sin_restriccion(mid).second <= k) hi = mid;
else lo = mid + 1;
}
return sin_restriccion(lo).first - (long long)k * lo; // devolver las k penalizaciones
}⚠️ Notas
La convexidad es la hipótesis, no un detalle. Si f(k) no es convexa, el método igual devuelve un número — y está mal, en silencio. La intuición de por qué funciona: min_k (f(k) + λ·k) te da siempre un punto de la envolvente convexa inferior de f; subir λ empuja el óptimo hacia menos trozos, bajarlo hacia más. Buscas el λ donde el óptimo aterriza en k, y recuperas f(k) restando las k penalizaciones que cobraste de más. El Syllabus IOI pide exactamente esto para las optimizaciones de DP: debe poder probarse que la técnica aplica.
⚠️ Los empates son el bug clásico, y son la mayoría de los casos cuando hay ceros o valores repetidos. Cuando varias particiones logran el mismo costo penalizado, hay que quedarse con la de menos trozos, y buscar el menor λ cuyo conteo mínimo ya no pase de k. Con el desempate al revés, el resultado se cae justo en esos casos (probado: invertirlo rompe uno de cada cuatro). Este cuidado es lo que hace que el truco funcione incluso cuando ningún λ da exactamente k trozos, porque k queda entre el conteo mínimo y el máximo.
No olvides la resta final: f(k) = g(λ) − k·λ. Sin ella el resultado queda inflado por las penalizaciones. Con costos enteros basta buscar λ entero.
El DP interno de arriba es O(n²) por claridad; en un problema de verdad se combina con Convex hull trick (Li Chao) o con Optimización divide y vencerás (DP) para que cada evaluación sea O(n) u O(n log n) — ahí está la ganancia real frente al O(n·k) directo.
📍 Estatus en el syllabus: el Syllabus IOI nombra explícitamente el convex hull trick, Knuth-Yao y divide & conquer, pero no menciona la relajación lagrangiana. No está excluida —apareció en un problema oficial, Aliens (IOI 2016)— pero es material avanzado: entra a estudiarla cuando ya domines las otras tres.