Aliens Trick / Lagrangian Relaxation
Replace a hard limit on the number of chosen groups with a penalty and binary search that penalty.
Aliens Trick / Lagrangian Relaxation
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Aliens trick is the competitive-programming name for a small Lagrangian-relaxation pattern: if the hard part of a DP is ``use at most \(K\) groups / segments / chosen objects,'' add a penalty \(\lambda\) per chosen group, solve the relaxed problem quickly, and binary search \(\lambda\).
When to Use It
Use it when:
the original DP has an extra dimension counting how many segments or objects were used,
fixing a penalty per chosen unit collapses that dimension,
the number of chosen units in the optimal relaxed solution changes monotonically with the penalty.
Core Idea
Turn \[ \text{maximize } \texttt{gain} \quad \text{subject to } \texttt{count} \le K \] into \[ \text{maximize } \texttt{gain} - \lambda \cdot \texttt{count}. \]
For one fixed \(\lambda\), compute both:
the best penalized value,
how many groups that optimum used.
Then binary search \(\lambda\) until the chosen-count crosses \(K\), and undo the penalty at the end.
Key Insight
The penalty parameter acts like a shadow price for opening a new group. If opening too many groups is the only thing that makes the DP expensive, charging for each group can remove the explicit count dimension entirely.
Worked Problem
Problem.
Given an array of profits, choose at most \(K\) pairwise disjoint non-empty subarrays with maximum total sum.
Why the trick fits.
The natural DP has a dimension for ``how many subarrays have been started so far.'' If starting a new subarray costs a penalty \(\lambda\), the DP becomes linear:
either extend the current chosen segment,
or start a new segment and pay \(\lambda\).
Correctness Intuition
As \(\lambda\) increases, starting a new group becomes less attractive, so the optimal group count does not increase. That monotonicity makes the penalty searchable. After finding the largest \(\lambda\) that still uses at least \(K\) groups, adding back \(\lambda K\) recovers the original objective value.
Complexity Analysis
If the relaxed solver costs \(T\), the total cost is \(O(T \log A)\), where \(A\) is the searched penalty range.
Implementation
The code below solves the ``at most \(K\) disjoint subarrays'' problem. The relaxed solver returns a pair:
penalized score,
number of used segments.
Common Pitfalls
Applying the trick without monotonicity of the chosen count in \(\lambda\).
Forgetting to define how ties compare; the segment count on equal penalized score matters.
Using it when the relaxed DP is still too slow, which means the trick removed no real bottleneck.
Variants / Extensions
Partition DPs with a penalty per segment.
Resource-limited problems where one capacity is turned into a multiplier.
Combining the relaxed solver with convex hull or divide-and-conquer optimization.
Practice Problems
Maximize profit using at most \(K\) disjoint segments.
Minimize cost using at most \(K\) groups after adding a per-group penalty.
DP problems where one count dimension is the only reason the state explodes.
References
Code
Contest-ready reference implementation for the idea explained above.
struct State {
long long value;
int count;
};
State better(State a, State b) {
if (a.value != b.value) return (a.value > b.value ? a : b);
return (a.count > b.count ? a : b);
}
State add(State base, long long delta_value, int delta_count) {
return {base.value + delta_value, base.count + delta_count};
}
State solve_with_penalty(const vector<long long>& a, long long penalty) {
const long long NEG = -(1LL << 60);
State best_total{0, 0};
State best_end{NEG, -(int)1e9};
for (long long x : a) {
best_end = better(
add(best_end, x, 0),
add(best_total, x - penalty, 1)
);
best_total = better(best_total, best_end);
}
return best_total;
}
long long max_sum_of_at_most_k_disjoint_subarrays(const vector<long long>& a, int k) {
long long lo = -(1LL << 40), hi = (1LL << 40);
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (solve_with_penalty(a, mid).count >= k) {
lo = mid;
} else {
hi = mid - 1;
}
}
State result = solve_with_penalty(a, lo);
return result.value + lo * k;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.