Pattern Reference
Aliens Trick (Lagrange DP)
"DP optimization using Lagrangian relaxation. Attach penalty lambda for constraint, binary search lambda. k-trades, partition."
Loading...
Deep Dive Tutorial
Problem: dp[k] = minimum cost using exactly k segments. Direct DP is O(nk). WQS binary search: add penalty λ per segment → dp_λ(n) = min cost using any number of segments, each adding λ to cost. The function dp_λ is convex in λ. Binary search for λ* such that optimal number of segments = k. Then answer = dp_λ*(n) - k×λ*. Requires: dp[k] is convex (decreasing marginal benefit for each additional segment).
Aliens trick template
// dp[k] = min cost to partition array into exactly k groups
// Requires dp[k] to be convex in k (each extra group helps less)
// Template: binary search on penalty lambda
function aliensTrick(arr, k, solve) {
// solve(lambda) = {cost, count}
// where cost = minimum cost with penalty lambda per group
// and count = optimal number of groups at that lambda
// Binary search for lambda where count = k
let lo = -1e9, hi = 1e9;
let ans = 0;
for (let iter = 0; iter < 200; iter++) { // 200 iterations for precision
const mid = (lo + hi) / 2;
const { cost, count } = solve(mid);
if (count >= k) lo = mid;
else hi = mid;
}
const { cost, count } = solve((lo + hi) / 2);
return cost - k * ((lo + hi) / 2);
}
// Example: Minimum cost to divide array into k subarrays,
// cost of subarray = (last - first)^2
// solve(lambda): DP with penalty lambda per subarray
// dp[i] = min cost for arr[0..i] with any number of subarrays + lambda each
// dp[i] = min over j<=i of (dp[j-1] + (arr[i]-arr[j])^2 + lambda)
// Can be solved in O(n log n) with convex hull trickWorked Problems
bot
Aliens trick applicability: dp[k] must be convex — meaning the marginal benefit of each additional "item" (segment, group, etc.) is non-increasing.
Steps:
1. Define f(λ) = optimal cost when adding λ per item
2. Binary search for λ* where f uses exactly k items
3. Answer = f(λ*) - k × λ*
Why it works: Lagrangian relaxation — adding penalty λ per item selects the Pareto-optimal trade-off between cost and count. Convexity ensures each λ corresponds to a unique optimal count.
Complexity: If unconstrained DP is O(n log n) (via CHT), total = O(n log n × log(RANGE)) ≈ O(n log² n).
Steps:
1. Define f(λ) = optimal cost when adding λ per item
2. Binary search for λ* where f uses exactly k items
3. Answer = f(λ*) - k × λ*
Why it works: Lagrangian relaxation — adding penalty λ per item selects the Pareto-optimal trade-off between cost and count. Convexity ensures each λ corresponds to a unique optimal count.
Complexity: If unconstrained DP is O(n log n) (via CHT), total = O(n log n × log(RANGE)) ≈ O(n log² n).