Aliens Trick / WQS

Why Aliens Trick / WQS Matters

Dynamic programming problems frequently require optimizing an objective function subject to a strict cardinality constraint $K$—such as selecting exactly $K$ non-overlapping intervals, partitioning a sequence into $K$ contiguous subarrays, or constructing a spanning tree with $K$ special edges. A naive 2D dynamic programming approach maintains the number of items chosen as an explicit state variable, yielding time complexities of $O(N \cdot K)$ or $O(N^2 \cdot K)$. When $N$ and $K$ scale to $10^5$ or larger, such algorithms fail due to excessive time and memory consumption.

The Aliens Trick (also known as WQS Binary Search after Wang, Qing, and Song, or Lagrangian Relaxation) eliminates the constraint dimension entirely. By introducing a fixed penalty (or cost) $C$ for every resource or item selected, the problem transforms into an unconstrained 1D optimization problem solved in $O(N)$ time. By binary searching over the penalty $C$, we find an exact slope where the unconstrained optimum naturally chooses $K$ items. This reduces the total time complexity from $O(N \cdot K)$ to $O(N \log(\text{Range}))$, turning intractable constrained DP problems into near-linear time operations.

The Aliens Trick applies Lagrangian relaxation to constrained dynamic programming: by charging a penalty $C$ per unit of resource consumed, it converts a $K$-constrained optimization problem $\max_{k=K} g(k)$ into an unconstrained problem $\max_k (g(k) - C \cdot k)$. Provided the objective function $g(k)$ is concave (or convex for minimization), binary searching for the penalty $C$ yields the exact constrained optimum in $O(N \log(\text{Range}))$ time and $O(N)$ space.

Core Concepts and Terminology

Understanding the Aliens Trick requires viewing the constrained optimization problem geometrically. Let $g(k)$ denote the maximum objective value achievable using exactly $k$ resources. Evaluating $g(k)$ directly for all $k$ requires $O(N \cdot K)$ time. However, if $g(k)$ exhibits concavity (i.e., diminishing marginal returns where $g(k+1) - g(k) \le g(k) - g(k-1)$), the sequence of points $(k, g(k))$ forms an upper convex hull.

When we introduce a penalty $C$ per resource, the unconstrained optimization problem computes $f(C) = \max_k (g(k) - C \cdot k)$. Geometrically, $g(k) - C \cdot k$ represents the $y$-intercept of a line passing through $(k, g(k))$ with slope $C$. Maximizing this $y$-intercept finds the point $(k, g(k))$ where a line of slope $C$ is tangent to the upper envelope of $g(k)$.

Term	Definition	Role in Aliens Trick / WQS
Constraint $K$	The target number of resources, segments, or choices required by the problem.	Defines the exact cardinality constraint to eliminate from 2D DP.
Penalty $C$	A scalar cost deducted from the objective for every unit of resource chosen.	Converts the constrained problem into an unconstrained 1D DP.
Objective $g(k)$	The optimal answer as a function of the resource count $k$.	Must be concave (for max) or convex (for min) for the trick to hold.
Unconstrained DP	An $O(N)$ DP that computes $\max_k (g(k) - C \cdot k)$ and tracks $cnt(C)$.	Evaluates the tangent line intercept for a candidate penalty slope $C$.
Choice Count $cnt(C)$	The optimal number of resources chosen by the unconstrained DP under penalty $C$.	Monotonically decreases as penalty $C$ increases; guides binary search.
Lagrange Multiplier	The optimal penalty $C^*$ where the supporting hyperplane touches $k = K$.	Reconstructs exact answer: $g(K) = \text{DP}(C^) + K \cdot C^$.

How Aliens Trick / WQS Works, Step by Step

The algorithm searches for the optimal penalty slope $C^*$ using binary search. Because $g(k)$ is concave, increasing the penalty $C$ monotonically decreases (or non-increases) the number of resources $cnt(C)$ selected by the unconstrained DP.

The control flow follows a standard binary search loop over the penalty value:

Aliens Trick / WQS control flow

flowchart TD
A[Start: Target K, Input Array] --> B[Initialize Penalty Bounds L, R]
B --> C{L <= R?}
C -- Yes --> D[Mid Penalty C = L + R / 2]
D --> E[Run O N Unconstrained DP with Penalty C]
E --> F[Get DP Value & Choice Count cnt]
F --> G{cnt >= K?}
G -- Yes --> H[Record Candidate C & DP Value; Set L = C + 1]
G -- No --> I[Set R = C - 1]
H --> C
I --> C
C -- No --> J[Reconstruct Answer = Best DP Value + K * Best C]
J --> K[End: Return Exact Maximum]

Worked Example with a Full Trace

Consider selecting $K = 2$ non-overlapping subsegments from the array $A = [3, -1, 4, -2, 5]$ to maximize the total sum.

Without constraints, we could pick $3$ subsegments ($[3]$, $[4]$, and $[5]$) for a total sum of $12$. With $K = 2$, the optimal choice selects $[3, -1, 4]$ (sum $6$) and $[5]$ (sum $5$), giving an optimal sum of $11$.

Let's trace how the Aliens Trick binary searches for penalty $C$ across the range $[0, 20]$:

Worked Example

Trace It by Hand

Question: Given array $A = [3, -1, 4, -2, 5]$, evaluate the unconstrained DP state for penalty $C = 2$. Why does the DP choose $cnt = 2$ segments?

Step 1: Maintain two DP states at each index $i$:

dp0: Max sum up to index $i$ while not actively inside a segment.
dp1: Max sum up to index $i$ while actively inside a segment (having paid penalty $C$).

Step 2: Trace transitions for $C = 2$:

$i=0 \, (A[0]=3)$: Start segment $\to dp1 = 3 - 2 = 1 \, (cnt=1)$. Close or skip $\to dp0 = 1 \, (cnt=1)$.
$i=1 \, (A[1]=-1)$: Continue $dp1 = 1 - 1 = 0$; Start new $dp1 = 1 - 1 - 2 = -2$. Best $dp1 = 0 \, (cnt=1)$. Best $dp0 = 1 \, (cnt=1)$.
$i=2 \, (A[2]=4)$: Continue $dp1 = 0 + 4 = 4 \, (cnt=1)$; Start new $dp1 = 1 + 4 - 2 = 3 \, (cnt=2)$. Best $dp1 = 4 \, (cnt=1)$. Best $dp0 = 4 \, (cnt=1)$.
$i=3 \, (A[3]=-2)$: Continue $dp1 = 4 - 2 = 2 \, (cnt=1)$. Best $dp0 = 4 \, (cnt=1)$.
$i=4 \, (A[4]=5)$: Continue active segment $dp1 = 2 + 5 = 7 \, (cnt=1)$; Start new segment from $dp0$: $4 + 5 - 2 = 7 \, (cnt=2)$.
Tie-break: Both choices yield value $7$. By preferring the larger segment count on ties, $dp1$ adopts $cnt = 2$.

Final Result: $f(2) = 7$ with $cnt = 2$. Adding back $K \cdot C = 2 \cdot 2 = 4$ yields $11$.

Implementation in Python, C++, and Java

The following code implements the Aliens Trick for finding the maximum sum of at most $K$ non-overlapping subsegments in an array. All three implementations feature identical DP state transitions, tie-breaking logic, binary search bounds, and sample output formatting.

def run_dp(arr, C):
    # dp0: max sum, not currently in a segment (and segment count)
    # dp1: max sum, currently in an active segment (and segment count)
    dp0, cnt0 = 0, 0
    dp1, cnt1 = -10**18, 0

    for x in arr:
        # Option to start a new segment vs continue existing active segment
        v_start, c_start = dp0 + x - C, cnt0 + 1
        v_cont, c_cont = dp1 + x, cnt1

        if v_start > v_cont or (v_start == v_cont and c_start > c_cont):
            next_dp1, next_cnt1 = v_start, c_start
        else:
            next_dp1, next_cnt1 = v_cont, c_cont

        # Option to stay out of segment vs close active segment
        if next_dp1 > dp0 or (next_dp1 == dp0 and next_cnt1 > cnt0):
            next_dp0, next_cnt0 = next_dp1, next_cnt1
        else:
            next_dp0, next_cnt0 = dp0, cnt0

        dp0, cnt0 = next_dp0, next_cnt0
        dp1, cnt1 = next_dp1, next_cnt1

    return dp0, cnt0

def solve_aliens_trick(arr, K):
    print(f"Array: {arr}")
    print(f"Target K: {K}\n")
    print("Binary Search Trace:")

    L, R = 0, 20
    best_C = 0
    best_dp = 0

    while L <= R:
        mid_C = (L + R) // 2
        val, cnt = run_dp(arr, mid_C)
        print(f"Penalty C = {mid_C} -> DP Value = {val}, Segments = {cnt}")

        if cnt >= K:
            best_C = mid_C
            best_dp = val
            L = mid_C + 1
        else:
            R = mid_C - 1

    max_sum = best_dp + K * best_C
    print(f"\nOptimal Penalty C = {best_C}")
    print(f"Max Sum for K = {K} subsegments: {max_sum}")
    return max_sum

if __name__ == "__main__":
    arr = [3, -1, 4, -2, 5]
    K = 2
    solve_aliens_trick(arr, K)

#include <iostream>
#include <vector>
#include <algorithm>

const long long INF = 1e18;

struct DPResult {
    long long val;
    int cnt;
};

DPResult run_dp(const std::vector<long long>& arr, long long C) {
    long long dp0 = 0;
    int cnt0 = 0;
    long long dp1 = -INF;
    int cnt1 = 0;

    for (long long x : arr) {
        long long v_start = dp0 + x - C;
        int c_start = cnt0 + 1;
        long long v_cont = dp1 + x;
        int c_cont = cnt1;

        long long next_dp1;
        int next_cnt1;
        if (v_start > v_cont || (v_start == v_cont && c_start > c_cont)) {
            next_dp1 = v_start;
            next_cnt1 = c_start;
        } else {
            next_dp1 = v_cont;
            next_cnt1 = c_cont;
        }

        long long next_dp0;
        int next_cnt0;
        if (next_dp1 > dp0 || (next_dp1 == dp0 && next_cnt1 > cnt0)) {
            next_dp0 = next_dp1;
            next_cnt0 = next_cnt1;
        } else {
            next_dp0 = dp0;
            next_cnt0 = cnt0;
        }

        dp0 = next_dp0;
        cnt0 = next_cnt0;
        dp1 = next_dp1;
        cnt1 = next_cnt1;
    }

    return {dp0, cnt0};
}

long long solve_aliens_trick(const std::vector<long long>& arr, int K) {
    std::cout << "Array: [";
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << (i + 1 < arr.size() ? ", " : "");
    }
    std::cout << "]\nTarget K: " << K << "\n\nBinary Search Trace:\n";

    long long L = 0, R = 20;
    long long best_C = 0;
    long long best_dp = 0;

    while (L <= R) {
        long long mid_C = L + (R - L) / 2;
        DPResult res = run_dp(arr, mid_C);
        std::cout << "Penalty C = " << mid_C << " -> DP Value = " << res.val
                  << ", Segments = " << res.cnt << "\n";

        if (res.cnt >= K) {
            best_C = mid_C;
            best_dp = res.val;
            L = mid_C + 1;
        } else {
            R = mid_C - 1;
        }
    }

    long long max_sum = best_dp + (long long)K * best_C;
    std::cout << "\nOptimal Penalty C = " << best_C << "\n";
    std::cout << "Max Sum for K = " << K << " subsegments: " << max_sum << "\n";
    return max_sum;
}

int main() {
    std::vector<long long> arr = {3, -1, 4, -2, 5};
    int K = 2;
    solve_aliens_trick(arr, K);
    return 0;
}

import java.util.Arrays;

public class Main {
    private static final long INF = (long) 1e18;

    static class DPResult {
        long val;
        int cnt;

        DPResult(long val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
    }

    private static DPResult runDp(long[] arr, long C) {
        long dp0 = 0;
        int cnt0 = 0;
        long dp1 = -INF;
        int cnt1 = 0;

        for (long x : arr) {
            long vStart = dp0 + x - C;
            int cStart = cnt0 + 1;
            long vCont = dp1 + x;
            int cCont = cnt1;

            long nextDp1;
            int nextCnt1;
            if (vStart > vCont || (vStart == vCont && cStart > cCont)) {
                nextDp1 = vStart;
                nextCnt1 = cStart;
            } else {
                nextDp1 = vCont;
                nextCnt1 = cCont;
            }

            long nextDp0;
            int nextCnt0;
            if (nextDp1 > dp0 || (nextDp1 == dp0 && nextCnt1 > cnt0)) {
                nextDp0 = nextDp1;
                nextCnt0 = nextCnt0 = nextCnt1;
            } else {
                nextDp0 = dp0;
                nextCnt0 = cnt0;
            }

            dp0 = nextDp0;
            cnt0 = nextCnt0;
            dp1 = nextDp1;
            cnt1 = nextCnt1;
        }

        return new DPResult(dp0, cnt0);
    }

    public static long solveAliensTrick(long[] arr, int K) {
        System.out.println("Array: " + Arrays.toString(arr));
        System.out.println("Target K: " + K + "\n");
        System.out.println("Binary Search Trace:");

        long L = 0, R = 20;
        long bestC = 0;
        long bestDp = 0;

        while (L <= R) {
            long midC = L + (R - L) / 2;
            DPResult res = runDp(arr, midC);
            System.out.println("Penalty C = " + midC + " -> DP Value = " + res.val
                    + ", Segments = " + res.cnt);

            if (res.cnt >= K) {
                bestC = midC;
                bestDp = res.val;
                L = midC + 1;
            } else {
                R = midC - 1;
            }
        }

        long maxSum = bestDp + (long) K * bestC;
        System.out.println("\nOptimal Penalty C = " + bestC);
        System.out.println("Max Sum for K = " + K + " subsegments: " + maxSum);
        return maxSum;
    }

    public static void main(String[] args) {
        long[] arr = {3, -1, 4, -2, 5};
        int K = 2;
        solveAliensTrick(arr, K);
    }
}

Complexity, Correctness, and Invariants

The efficiency of the Aliens Trick stems from reducing the 2D DP table dimension from $O(N \cdot K)$ to $O(N)$ per binary search step.

Algorithm / Paradigm	Time Complexity	Auxiliary Space	Key Assumptions / Constraints
Naive 2D Dynamic Programming	$O(N \cdot K)$	$O(N \cdot K)$ or $O(N)$	Works for any arbitrary non-concave DP functions.
Aliens Trick / WQS Binary Search	$O(N \log(\text{Range}))$	$O(N)$ or $O(1)$	Requires $g(k)$ to be strictly concave / convex.
Min-Cost Max-Flow (MCMF)	$O(V \cdot E + F \cdot E \log V)$	$O(V + E)$	Requires graph modeling; much slower constant factors.
Divide & Conquer / Slope Trick	$O(N \log N)$	$O(N)$	Requires explicit monotonicity of decision boundaries.

Correctness Invariant & Proof Idea: By Lagrangian Duality, if $g(k)$ is a concave function defined over discrete integers, its upper boundary is equal to the lower envelope of its supporting hyperplanes: $g(K) = \min_C (\max_k (g(k) - C \cdot k) + C \cdot K)$. Because $f(C) = \max_k (g(k) - C \cdot k)$ is convex in $C$ and $cnt(C)$ is monotonically decreasing with respect to $C$, binary search guarantees finding a slope $C^*$ such that $g(K) = f(C^*) + K \cdot C^*$.

Variants, Pitfalls, and Optimizations

The most critical requirement of the Aliens Trick is that $g(k)$ must be concave (for maximization) or convex (for minimization). If $g(k)$ is not concave—for instance, if there is a "gap" where no linear slope $C$ touches $(K, g(K))$—the binary search will fail to hit $K$.

Common Implementation Pitfalls:

Collinear Points (Multiple $k$ for same $C$): When $g(k)$ contains flat segments, a single penalty $C$ may yield multiple valid choice counts $[k_{min}, k_{max}]$. Always tie-break DP states to maximize (or minimize) $cnt$ consistently, and check whether $K \in [k_{min}, k_{max}]$.
Floating-Point Precision: When binary searching continuous penalties $C \in \mathbb{R}$, use a fixed iteration count (e.g., $60$ to $80$ iterations) rather than while (R - L > EPS) to prevent infinite loops caused by precision limitations.
Incorrect Sign on Penalty Adjustment: In maximization problems, a larger penalty $C$ reduces resource usage. Therefore, if $cnt \lt K$, you must decrease penalty $C$ (or adjust bounds accordingly).

Practice Problems and Real-World Use

The Aliens Trick appears in competitive programming and production systems that optimize resource allocation under hard capacity bounds.

Problem / System	Core Idea / Application	Difficulty
IOI 2016 - Aliens	Original problem. Binary search photo penalty $C$ to place at most $K$ square photos covering grid points.	Hard
LeetCode 188 - Stock IV	Maximize profit with at most $K$ transactions. Penalty $C$ charged per transaction.	Medium-Hard
Codeforces 739E - Gosu	Catch Pokemon using $A$ Ultra Balls and $B$ Great Balls. Requires 2D Aliens Trick with two penalties $(C_1, C_2)$.	Very Hard
Tree Partitioning into $K$ Components	Partition a weighted tree into $K$ connected components by penalizing edge cuts.	Hard
Cloud Resource Scheduler	Allocate workloads across $K$ fixed server clusters while minimizing latency penalties.	Real-World System
Signal Processing $K$-Segment Fit	Approximate continuous time-series data using $K$ linear segments by charging penalty $C$ per segment split.	Real-World System

Cookie Consent