xviii. Aliens Trick

Also called WQS binary search or Lagrangian relaxation (IOI 2016 “Aliens”). If $g(k)$ = best cost using exactly $k$ groups/operations is convex in $k$, drop the $k$ dimension: charge a penalty $\lambda$ per group, solve the unconstrained problem $f(\lambda )={\min }_t(g(t)+\lambda t)$, and binary search $\lambda$ so that the optimum uses $k$ groups. Then $g(k)=f(\lambda )-\lambda k$. Cost: (unconstrained solve) × $O(\log C)$.

// solve(lambda) -> {min over t of g(t) + lambda * t, the LARGEST t attaining it}
template<class S> ll aliens(int k, ll lo, ll hi, S solve) {   // g convex, minimisation
    ll ans = LLONG_MAX;
    while (lo <= hi) {
        ll mid = lo + (hi - lo) / 2;
        auto [val, cnt] = solve(mid);
        if (cnt >= k) ans = val - mid * k, lo = mid + 1;       // penalty can still grow
        else hi = mid - 1;
    }
    return ans;
}

The search range must contain the slope $g(k-1)-g(k)$, which is negative when adding groups makes things worse (penalty becomes a reward); with integer costs, integer $\lambda$ suffices. For maximisation of a concave $g$, subtract the penalty instead (or negate everything).

Proof: why the largest feasible $\lambda$ gives $g(k)$

$t$ minimises $g(t)+\lambda t$ iff $-\lambda$ is a subgradient of $g$ at $t$, i.e. $g(t)-g(t+1)\le \lambda \le g(t-1)-g(t)$ (convexity makes these intervals consecutive and nonincreasing in $t$). Let $t^{\ast }(\lambda )$ be the largest minimiser; it is nonincreasing in $\lambda$, and $t^{\ast }(\lambda )\ge k$ iff $\lambda \le {\lambda }_k:=g(k-1)-g(k)$. So the binary search ends at $\lambda ={\lambda }_k$ (an integer when costs are integers), where $k$ itself is a minimiser because $g(k)-g(k+1)\le {\lambda }_k\le g(k-1)-g(k)$. Therefore $f({\lambda }_k)=g(k)+{\lambda }_{k}k$. The answer is correct even if the solver reports some other $t$ at that $\lambda$, which is why ties must be broken consistently (largest $t$ here) but exactness is never required.

Recognising convexity

• Exactly $k$ segments of an array with a Monge segment cost (QI): $g$ is convex. This covers $(\text{sum}{)}^2$, equal-pair counts, 1D $k$-medians/$k$-means on a line.
• Exactly $k$ disjoint intervals / subarrays maximising total value: concave (min-cost-flow argument: each extra interval is an augmenting path of nonincreasing gain).
• Anything that is a min-cost flow with $k$ units of flow: the cost is convex in $k$ (successive shortest paths have nondecreasing lengths).
• Spanning tree with exactly $k$ special edges (parametric MST): add $\lambda$ to every special edge’s weight and run Kruskal, binary searching $\lambda$ until exactly $k$ special edges are picked; ties broken toward special edges (matroid exchange gives convexity) (Kruskal).
• When unsure, brute-force $g(t)$ for small inputs and check $g(t-1)-2g(t)+g(t+1)\ge 0$.

Proof sketch: Monge segment costs give convex $g$

Write $g(k)=\min$ over $k$-paths from $0$ to $n$ in the DAG with edge weights $C(i,j)$. Take an optimal $(k-1)$-path $P$ and $(k+1)$-path $Q$. Walking both from left to right, there must be a position where $Q$ “overtakes”: an edge $(a,d)$ of $P$ and an edge $(b,c)$ of $Q$ with $a\le b<c\le d$ such that $P$‘s prefix up to $a$ and $Q$‘s prefix up to $b$ use $s$ and $s+1$ edges respectively. Swap the tails: $P^{\prime }=P[\mathrm{0..}a]+(a,c)+Q[c..n]$ and $Q^{\prime }=Q[\mathrm{0..}b]+(b,d)+P[d..n]$ both have exactly $k$ edges, and QI gives $C(a,c)+C(b,d)\le C(a,d)+C(b,c)$, so $w(P^{\prime })+w(Q^{\prime })\le w(P)+w(Q)$. Hence $2g(k)\le g(k-1)+g(k+1)$.

Example: exactly $k$ segments, cost $(\text{sum}+c{)}^2$

The unconstrained solve with penalty $\lambda$ is $d{p}_i={\min }_{j}d{p}_j+(S_i-S_j+c{)}^2+\lambda$ (plus a segment counter), done with a monotone CHT in $O(n)$; total $O(n\log C)$. Track the count alongside the value and compare pairs $(\text{value},-\text{count})$ so ties prefer more segments.

auto solve = [&](ll lambda) {                              // O(n^2) reference version of the inner DP
    vector<pair<ll, int>> dp(n + 1, {LLONG_MAX, 0}); dp[0] = {0, 0};
    for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) {
        ll s = S[i] - S[j] + c; pair<ll, int> cand{dp[j].first + s * s + lambda, dp[j].second + 1};
        if (cand.first < dp[i].first || (cand.first == dp[i].first && cand.second > dp[i].second)) dp[i] = cand;
    }
    return dp[n];
};
ll best = aliens(k, -(ll)4e12, (ll)4e12, solve);           // slopes can be negative: more segments may cost more

Notes

• At most $k$: if the unconstrained optimum ($\lambda =0$) already uses $\le k$ groups, that’s the answer.
• Nested Aliens (two “exactly” constraints) works when the 2D function is jointly convex (L♮-convex); rare.
• Recovering a solution with exactly $k$ groups at the final $\lambda$: the solver’s solution may use another count with the same penalised cost; adjust by exchanging segments along the tie (problem-specific), or reconstruct from a DP that tracks both min and max counts.
• Aliens is the only standard technique whose complexity doesn’t depend on $k$; for small $k$, divide and conquer optimisation is simpler (D&C Optimization).
• The famous instance of “at most $k$ non-overlapping intervals maximising value” is the stock-trading-with-at-most-$k$-transactions problem (Classic DP), where $k$ up to $10^9$ makes the plain $O(nk)$ DP infeasible and forces exactly this trick.