The Aliens Trick (WQS Binary Search)

Quick Revisit

• USE WHEN: DP with "exactly $k$ items" constraint where $f(k)$ is convex — trade the $k$ dimension for binary search on a per-item penalty $\lambda$
• INVARIANT: $g(\lambda )=\underset{k}{min}[f(k)+\lambda k]$ is the Lagrangian dual; answer is $g({\lambda }^{\ast })-{\lambda }^{\ast }k$ where $k({\lambda }^{\ast })=k$
• TIME: O(n log C · T) where T = inner DP cost, C = cost range | SPACE: same as inner DP
• CLASSIC BUG: Not handling the flat region of $g(\lambda )$ where multiple $k$ values share the same slope (tie-breaking in cnt)
• PRACTICE: 04-ladder-dp

You need to choose exactly $k$ items to minimize cost, but the DP is $O(n\cdot k)$. The Aliens trick removes the "$k$ items" constraint by adding a per-item penalty $\lambda$, solves the unconstrained problem in $O(n)$ or $O(n\log n)$, then binary searches on $\lambda$ to land on exactly $k$ items. The whole thing runs in $O(n\log n\cdot T)$ where $T$ is the cost of the inner DP.

Difficulty: [Advanced]Prerequisites: DP -- 1D Introduction, Binary SearchCF Rating Range: 2200-2600+

---

Origin Story

IOI 2016, problem "Aliens." Contestants needed to cover certain cells in a grid using exactly $k$ squares, minimizing total area minus overlaps. The 2D DP was $O(n^{2}k)$. The intended solution: penalize each square by $\lambda$, solve the unconstrained DP, and binary search on $\lambda$.

The trick has been independently discovered many times: Lagrangian relaxation in optimization, WQS binary search (named after the Chinese competitive programmer 王钦石), and lambda optimization in the ICPC community.

The Mathematical Setup

You want to compute:

$$f(k)=\underset{\text{choose exactly }k}{min}\text{Cost}(S)$$

Key assumption: $f(k)$ is convex -- meaning the marginal benefit of adding one more item decreases. Formally, $f(k)-f(k-1)\ge f(k+1)-f(k)$.

The trick: instead of enforcing "exactly $k$," define:

$$g(\lambda )=\underset{\text{any number of items}}{min}(\text{Cost}(S)+\lambda \cdot |S|)$$

This is the Lagrangian dual. For each $\lambda$, the optimal $|S|$ (call it $k(\lambda )$) decreases as $\lambda$ increases -- because items become more expensive. By binary searching on $\lambda$, you find the ${\lambda }^{\ast }$ where $k({\lambda }^{\ast })=k$.

  f(k):  cost vs number of items (convex curve)

  cost
   |  *
   | * *
   |*   *         The tangent line with slope -lambda
   |     *        touches the curve at exactly one k.
   |      * *
   |         *
   +-----------> k

  g(lambda) = min_k [ f(k) + lambda*k ]
            = value where tangent with slope -lambda touches f

The answer is $f(k)=g({\lambda }^{\ast })-{\lambda }^{\ast }\cdot k$.

Algorithm Skeleton

  1. Binary search on lambda in [lo, hi]:
       lo = 0, hi = max possible cost per item
  2. For each lambda, solve the UNCONSTRAINED DP:
       dp[i] = min cost of covering positions 1..i
               where each "item used" adds penalty lambda
       Track cnt[i] = number of items used in optimal solution for dp[i]
  3. If cnt[n] <= k: decrease lambda (items too expensive, using too few)
     If cnt[n] > k: increase lambda
  4. When binary search converges: answer = dp[n] - lambda * k

Implementation Skeleton

#include <bits/stdc++.h>
using namespace std;

int n, K;
// problem-specific data

pair<long long, int> solveDP(long long lam) {
    // dp[i] = {min cost, item count} for positions 0..i
    // with penalty lam per item
    vector<long long> dp(n + 1, 1e18);
    vector<int> cnt(n + 1, 0);
    dp[0] = 0; cnt[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            long long cost = dp[j] + C(j + 1, i) + lam;  // +lam = one more item
            if (cost < dp[i] || (cost == dp[i] && cnt[j] + 1 < cnt[i])) {
                dp[i] = cost;
                cnt[i] = cnt[j] + 1;
            }
        }
    }
    return {dp[n], cnt[n]};
}

int main() {
    // read n, K, problem data
    long long lo = 0, hi = 1e18;
    long long ans = 0;
    // Binary search on lambda (integer or real)
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        auto [cost, items] = solveDP(mid);
        if (items <= K) {
            ans = cost - mid * K;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
}

The inner DP should be accelerated -- typically with CHT, D&C optimization, or Li Chao tree -- to bring it from $O(n^2)$ to $O(n\log n)$ or $O(n)$. The binary search adds another $O(\log V)$ factor.

Recognizing the Pattern

Reach for the Aliens trick when you see:

1. "Exactly $k$ items/groups/segments" in the constraint.
2. The cost function is convex in $k$ -- adding more items has diminishing (or increasing, for max problems) returns.
3. Removing the "exactly $k$" constraint makes the DP simpler -- drops one dimension.

Classic signals: "partition into exactly $k$ groups," "choose exactly $k$ edges," "use exactly $k$ operations."

Convexity check: if you can argue that $f(k+1)-f(k)\ge f(k+2)-f(k+1)$ (for minimization), the trick applies. Often this follows from the structure of the cost function (e.g., squared costs, optimal substructure).

Pitfalls

• Non-convex $f(k)$? The trick simply doesn't work. If you can't prove convexity, don't use it -- you'll get WA.
• Integer vs. real binary search. If costs are integers, binary search on integer $\lambda$ and handle ties in item count carefully. If costs are real, use a fixed number of iterations (60-80) with floating point.
• Tie-breaking in the inner DP. When two transitions give the same cost, prefer the one using fewer (or more) items. This ensures $k(\lambda )$ is monotone.
• Large penalty range. Set the binary search bounds wide enough. $\lambda$ can range from $0$ to $max(\text{single item cost})$.
• Off-by-one in counting items. Make sure each "item" in the DP correctly increments the counter.

Practice Problems

#	Problem	Difficulty	Notes
1	IOI 2016 -- Aliens	IOI Gold	The original problem; DP + CHT + Aliens trick
2	CF 739E -- Gosha is Hunting	2800	Two types of balls, exactly $k$ of one type
3	CF 1279F -- New Year and Handle Change	2600	Exactly $k$ operations, convex cost
4	APIO 2014 -- Sequence	--	Partition into $k$ parts, product cost

Further Reading

• DP -- Convex Hull Trick -- often used to accelerate the inner DP
• DP -- D&C Optimization -- another common inner DP accelerator
• Binary Search -- the outer loop
• CF blog: WQS Binary Search -- community explanation with examples

---