Aliens Trick

Remove a “exactly $k$ groups” constraint from a DP by turning it into a penalty, then binary searching the penalty. Named after the IOI 2016 problem Aliens; also called Lagrangian relaxation or the WQS binary search.

The setup

You can solve
$f(\lambda )={\min }_{\text{any number of groups }t}(\mathrm{cost}+\lambda t)$
in $O(n)$ or $O(n\log n)$, but the problem demands exactly $k$ groups, and adding a $k$ dimension costs a factor of $k$.

The idea

Let $g(t)$ be the optimal cost using exactly $t$ groups. If $g$ is convex in $t$, then:

• Adding a penalty $\lambda$ per group and minimising freely selects the $t$ where the marginal gain of another group equals $\lambda$.
• Increasing $\lambda$ makes the optimiser use fewer groups — monotonically.
• So binary search $\lambda$ until the unconstrained solve happens to use exactly $k$ groups.
• Recover the answer as $g(k)=f(\lambda )-\lambda k$.

Geometrically: $\lambda$ is the slope of a supporting line to the convex curve $g$, and you are searching for the slope that touches it at $t=k$.

The template

// solve(lambda) returns {cost + lambda * groups, groups_used}
pair<long long,int> solve(long long lambda);
 
long long aliens(int k, long long lo, long long hi) {
    long long best = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        auto [cost, cnt] = solve(mid);
        if (cnt >= k) { best = cost - mid * k; lo = mid + 1; }   // penalty too small
        else hi = mid - 1;
    }
    return best;
}

Search over integer $\lambda$ when costs are integers — the optimum is attained at an integer slope, and integer search avoids all floating-point trouble.

The two requirements

1. Convexity of $g(t)$. This is the real condition, and it must be argued or tested. Verify empirically: brute-force $g(t)$ for small $n$ and check that the second differences $g(t+1)-2g(t)+g(t-1)$ are all $\ge 0$.
2. A fast unconstrained solver. Usually $O(n)$ or $O(n\log n)$ with CHT or a monotone queue.

Total: $O(\text{solve}\times \log (\text{cost range}))$.

The tie-breaking problem

The hardest part

At the optimal $\lambda$, several group counts often achieve the same penalised cost — so the solver may return $t\ne k$ even though $\lambda$ is correct. Two standard fixes:

1. Track a second criterion. Among equal costs, make the solver prefer the maximum (or minimum) group count, consistently. Then binary search on that count.
2. Do not require exactness. Binary search for the largest $\lambda$ with $t\ge k$, and return $f(\lambda )-\lambda k$. Convexity guarantees this is $g(k)$ even when the solver never reports exactly $k$.

The second is more robust and is what the template above does.

When to reach for it

Signal
”exactly $k$ segments / groups / operations”	✔
$k$ is large ($10^5$), so an $O(nk)$ DP is too slow	✔
The unconstrained version is easy	✔
The cost-vs-$k$ curve is convex	required
$k$ is small	use plain D&C DP — simpler

Typical problems

• Partition an array into exactly $k$ segments minimising the sum of segment costs
• Choose exactly $k$ non-overlapping intervals maximising total value
• Buy and sell a stock at most $k$ times (the LeetCode classic, at $k=10^9$)
• Build exactly $k$ facilities minimising total distance
• Select exactly $k$ edges of a spanning tree with a colour constraint (parametric MST — same idea, applied to Kruskal)

The parametric MST version is worth noting: to find a spanning tree with exactly $k$ white edges, add $\lambda$ to every white edge’s weight and binary search $\lambda$ until Kruskal picks exactly $k$ of them.

Relationship to other techniques

	Keeps the $k$ dimension	Time
Plain DP	yes	$O(nk)$
D&C DP	yes	$O(nk\log n)$
Aliens trick	no	$O(n\log C)$ or $O(n\log n\log C)$

Aliens is the only one whose complexity is independent of $k$ — which is exactly why it exists.

See also: D&C DP · Convex Hull Trick · Binary Search