Chapter 116: Alien Trick and Parametric Search

Prerequisites

• Binary search on real/integer domains
• Dynamic programming with constraints
• Lagrange multipliers (conceptual understanding)

Interview Frequency: ★★

The alien trick (Lagrangian relaxation with WQS binary search) sits at the hard end of the optimization spectrum and shows up at Google, Amazon, and Meta mainly in senior or research-leaning loops. It is rarely the intended first solution; interviewers use it to see whether you can turn a “choose exactly k items” constraint into an unconstrained problem with a penalty term, then binary-search the penalty.

116.1 What Is the Alien Trick?

The Alien Trick (also called Parametric Search or WQS Binary Search) is an optimization technique that converts a constrained optimization problem into an unconstrained one by introducing a penalty parameter λ (lambda).

Core Idea: If you need to optimize some cost function f(x) subject to using exactly (or at most) K segments/items, you can instead minimize:

f(x) + λ · g(x)

where g(x) counts the number of segments used. By binary-searching on λ, you find the value that makes the unconstrained optimum use exactly K segments.

When Does It Apply?

The Alien Trick works when the cost vs. number-of-segments curve is convex. This means:

• Adding one more segment always helps, but with diminishing returns
• The marginal gain of each additional segment is non-increasing

If the curve is convex, the Lagrangian relaxation has a unique optimal point for each λ, and binary search on λ maps cleanly to the number of segments.

116.2 Motivating Example

Problem: Given an array of n positive integers, partition it into exactly K contiguous subarrays to minimize the maximum subarray sum.

Without the Alien Trick, this requires a DP with states (position, partitions_used) → O(n² · K) time.

With the Alien Trick, we reduce it to O(n log C) where C is the range of answers.

Why is this faster? We eliminate one dimension of the DP by absorbing the partition count into the objective function via a penalty.

116.3 Intuition: The Lagrangian Relaxation

In optimization theory, a constrained problem:

minimize f(x)    subject to g(x) = K

can be relaxed to:

minimize f(x) + λ · g(x)    (no constraint on g(x))

For each value of λ, the unconstrained problem has some optimal solution with a particular value of g(x). As λ increases, we penalize using more segments, so the optimal g(x) decreases. As λ decreases (becomes negative), we reward using more segments, so g(x) increases.

By binary-searching λ, we find the exact value where g(x) = K.

Geometric Picture

Plot the “number of segments” on the x-axis and “cost” on the y-axis. The set of achievable (segments, cost) pairs forms a convex hull. The Alien Trick finds the point on this convex hull where segments = K.

Cost
  |  .
  |    .
  |      .         ← Convex hull of achievable points
  |        .
  |          .
  |            .
  +---------------- Segments

A line with slope -λ is tangent to this convex hull. Moving λ slides the tangent point along the hull.

116.4 Formal Algorithm

Given:

• A function solve(λ) that returns (optimal_cost, num_segments) for penalty λ
• A target number of segments K

Algorithm:

1. Binary search on λ (integer or real-valued)
2. For each mid = λ, call solve(λ) to get (cost, segments)
3. If segments >= K: increase λ (penalize segments more)
4. If segments < K: decrease λ (encourage more segments)
5. At the boundary, compute the true answer: answer = cost - λ * K

Key Insight: The true answer is f(x*) + λ · g(x*) - λ · K, where (x*, g(x*)) is the solution returned by solve(λ).

116.5 Detailed Example: Partition Array to Minimize Maximum Sum

Problem Statement: Given arr = [1, 3, 2, 4, 1, 5, 2] and K = 3, partition into 3 contiguous subarrays to minimize the maximum subarray sum.

Step-by-step with Alien Trick:

1. The penalty λ represents “cost per partition.”
2. For a given λ, solve the unconstrained problem: partition freely to minimize (max subarray sum) + λ · (number of partitions).
3. The unconstrained problem can be solved greedily: keep adding elements to the current subarray unless starting a new subarray (cost λ) would be better.

Walkthrough with λ = 2:

arr = [1, 3, 2, 4, 1, 5, 2]

Start new partition at arr[0] = 1, current_sum = 1, partitions = 1
Add arr[1] = 3 → current_sum = 4. Starting new costs λ=2, extending costs 3. Extend.
Add arr[2] = 2 → current_sum = 6. Starting new costs 2, extending costs 2. Either works; extend.
Add arr[3] = 4 → current_sum = 10. Starting new costs 2, extending costs 4. Start new partition.
  → partitions = 2, current_sum = 4
Add arr[4] = 1 → current_sum = 5. Extend.
Add arr[5] = 5 → current_sum = 10. Starting new costs 2, extending costs 5. Start new partition.
  → partitions = 3, current_sum = 5
Add arr[6] = 2 → current_sum = 7. Extend.

Partitions: [1,3,2], [4,1], [5,2] → max sum = 6, partitions = 3
Objective = 6 + 2·3 = 12

Since partitions = 3 = K, we found the answer!
True answer = 12 - 2·3 = 6

Verification: Can we do better than max sum = 6? With 3 partitions on [1,3,2,4,1,5,2]:

• [1,3,2,4], [1,5], [2] → max = 10
• [1,3], [2,4,1], [5,2] → max = 7
• [1,3,2], [4,1], [5,2] → max = 6 ✓

116.6 Implementation in C++

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

struct Result {
    long long cost;
    int partitions;
};

// Solve unconstrained problem with penalty lambda per partition
Result solve(const std::vector<int>& arr, long long lambda) {
    int n = arr.size();
    long long currentSum = 0;
    long long maxInCurrent = 0;
    int partitions = 1;  // Always start with at least one partition

    for (int x : arr) {
        // If extending would make currentSum > lambda + maxInCurrent, start new partition
        if (currentSum + x > maxInCurrent + lambda) {
            partitions++;
            currentSum = x;
            maxInCurrent = x;
        } else {
            currentSum += x;
            maxInCurrent = std::max(maxInCurrent, currentSum);
        }
    }

    return {maxInCurrent + lambda * partitions, partitions};
}

long long aliensTrick(const std::vector<int>& arr, int k) {
    // Binary search on lambda
    long long lo = -1e15, hi = 1e15;
    long long answer = 0;

    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        auto result = solve(arr, mid);
        if (result.partitions >= k) {
            answer = result.cost - mid * k;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return answer;
}

int main() {
    std::vector<int> arr = {1, 3, 2, 4, 1, 5, 2};
    int k = 3;
    std::cout << "Min max-subarray with " << k << " partitions: "
              << aliensTrick(arr, k) << "\n";
    return 0;
}

116.7 Implementation in Python

def solve(arr, lam):
    """Solve unconstrained problem with penalty `lam` per partition."""
    n = len(arr)
    current_sum = 0
    max_in_current = 0
    partitions = 0

    for x in arr:
        if partitions > 0 and current_sum + x > max_in_current + lam:
            # Start new partition
            partitions += 1
            current_sum = x
            max_in_current = x
        else:
            current_sum += x
            max_in_current = max(max_in_current, current_sum)

    if partitions == 0:
        partitions = 1

    return max_in_current + lam * partitions, partitions


def aliens_trick(arr, k):
    """Find minimum max-subarray-sum when partitioning into exactly k parts."""
    lo, hi = -10**15, 10**15
    answer = 0

    while lo <= hi:
        mid = (lo + hi) // 2
        cost, partitions = solve(arr, mid)
        if partitions >= k:
            answer = cost - mid * k
            lo = mid + 1
        else:
            hi = mid - 1

    return answer


# Example
arr = [1, 3, 2, 4, 1, 5, 2]
k = 3
print(f"Min max-subarray with {k} partitions: {aliens_trick(arr, k)}")
# Output: Min max-subarray with 3 partitions: 6

116.8 Implementation in Java

public class AlienTrick {

    static class Result {
        long cost;
        int partitions;
        Result(long cost, int partitions) {
            this.cost = cost;
            this.partitions = partitions;
        }
    }

    static Result solve(int[] arr, long lambda) {
        long currentSum = 0;
        long maxInCurrent = 0;
        int partitions = 0;

        for (int x : arr) {
            if (partitions > 0 && currentSum + x > maxInCurrent + lambda) {
                partitions++;
                currentSum = x;
                maxInCurrent = x;
            } else {
                currentSum += x;
                maxInCurrent = Math.max(maxInCurrent, currentSum);
            }
        }
        if (partitions == 0) partitions = 1;

        return new Result(maxInCurrent + lambda * partitions, partitions);
    }

    static long aliensTrick(int[] arr, int k) {
        long lo = -1_000_000_000_000_000L;
        long hi = 1_000_000_000_000_000L;
        long answer = 0;

        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            Result result = solve(arr, mid);
            if (result.partitions >= k) {
                answer = result.cost - mid * k;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 1, 5, 2};
        int k = 3;
        System.out.println("Min max-subarray with " + k + " partitions: "
                           + aliensTrick(arr, k));
    }
}

116.9 Complexity Analysis

Where C is the range of possible λ values (typically 10^15 for 64-bit integers).

Comparison with standard DP:

• Standard DP: O(n² · K) time, O(n · K) space
• Alien Trick: O(n · log C) time, O(1) space

The Alien Trick is dramatically faster when n and K are large.

116.10 Common Pitfalls

1. Non-convex cost curve: If the cost vs. segments curve is not convex, the trick fails. The binary search may oscillate or find a wrong answer.

2. Tie-breaking: When multiple solutions have the same cost but different segment counts, you need consistent tie-breaking. The standard approach is to prefer more segments (or fewer) consistently.

3. Off-by-one in λ: The binary search must handle the case where the exact K is achievable but λ lands between two integers.

4. Integer vs. real λ: For problems where the cost function involves integers, integer λ suffices. For real-valued costs, you may need real-valued λ with sufficient precision.

116.11 Practice Problems

1. Partition array into K subarrays minimizing max sum (the example above)
2. IOI 2016 — Railroad: Minimize cost with exactly K rail segments
3. AtCoder DP Contest — X: Partition with penalty per segment
4. Codeforces 739E — Gosha is hunting: Two types of “balls” with constraints
5. USACO — Balanced Teams: Group students into exactly K teams

116.12 Interview Questions

1. Q: When can you apply the Alien Trick? A: When the cost vs. number-of-segments curve is convex. This means each additional segment provides diminishing returns.

2. Q: What is the time complexity improvement over standard DP? A: From O(n² · K) to O(n · log C), where C is the answer range. The Alien Trick eliminates one DP dimension.

3. Q: How do you handle the case where no valid partition exists? A: Return a sentinel value or check feasibility before applying the trick.

4. Q: Can the Alien Trick be used for maximization problems? A: Yes, with appropriate sign changes. The penalty λ encourages or discourages more segments depending on the optimization direction.

116.13 Dry Run: Full Trace

Input: arr = [7, 2, 5, 10, 8], K = 2

Binary search on λ:

Final answer: 18 (partition [7,2,5] and [10,8], max sum = max(14, 18) = 18)

116.14 Related Techniques

Summary

Key Takeaway: The Alien Trick trades a dimension of DP for a binary search, dramatically improving time complexity for constrained partitioning problems.