Pattern Guide
Aliens Trick (WQS Binary Search)
"DP with "exactly k" constraint → binary search on cost penalty λ."
The Aliens trick (WQS binary search / lambda optimization) solves "minimize cost with exactly k groups/items" by adding a per-group penalty λ and binary searching on λ. If the unconstrained DP (with penalty) is efficiently solvable, we can find the optimal λ such that the optimal solution uses exactly k groups. Reduces O(n²k) DP to O(n log n × log(answer)).
Problems you can solve with this pattern
3 problems · click any to start solving
// 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 trickProblem: 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).
// 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 trickSteps:
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).