The Alien’s Trick

The Constraint You Wish You Could Drop

You have a DP that runs in \(O(n)\) or \(O(n \log n)\) — fast, clean, no issues. Then the problem adds four words: "using exactly K items." Suddenly your state space gains an extra dimension, the DP becomes \(O(n \cdot K)\), and for large \(K\) this is too slow.

WQS Binary Search lets you drop that constraint.

The Greedy Choice: Instead of enforcing "exactly \(K\) items," impose a penalty \(\lambda\) per item. Binary search on \(\lambda\) until the unconstrained solver naturally picks exactly \(K\).

Named after Wang Qinshi from a 2012 Chinese Team Selection Test, this technique became globally famous after IOI 2016 Problem "Aliens." The idea: convert a constrained optimization problem into an unconstrained one via a penalty parameter, then binary search on that penalty.

The Brute Force Bottleneck

Consider the array [10, 3, 8, 7, 2, 9]. Pick exactly \(K=2\) non-adjacent elements to maximize the sum.

Without the \(K\) constraint, you'd run a standard \(O(n)\) DP: at each position, either pick it (add value, skip the previous) or don't. Done.

With "exactly \(K=2\)," you need to track how many you've picked. The DP becomes dp[i][j] = best sum considering the first \(i\) elements, having picked exactly \(j\). That's \(O(n \cdot K)\) states. For \(n = 500{,}000\) and \(K = 250{,}000\), this is far too slow.

Core Idea: Penalize Each Pick

Instead of forcing exactly \(K\) items, impose a penalty of \(\lambda\) for each item picked. Define:

\[g(\lambda) = \max_k \left\{ h(k) - \lambda \cdot k \right\}\]

where \(h(k) =\) best value achievable using exactly \(k\) items.

For a fixed \(\lambda\), this is an unconstrained problem — pick however many items you want, but each one costs \(\lambda\). The inner solver finds the best tradeoff.

Why does this help? The unconstrained problem is the easy \(O(n)\) DP you started with. Each item's effective value is \(a[i] - \lambda\) instead of \(a[i]\). Pick it if it helps, skip it if it doesn't. No count tracking needed.

The Key Requirement: Concavity

This trick only works when \(h(k)\) is concave — the marginal gain of each additional item is non-increasing:

\[h(k+1) - h(k) \geq h(k+2) - h(k+1) \quad \text{for all } k\]

In other words: the first item you pick is the most valuable, the second is slightly less valuable, the third even less. Diminishing returns.

Why does this matter? Because if \(h\) is concave, you can recover \(h(K)\) exactly from the penalty formulation. If \(h\) has "dents" (non-concavity), some values of \(K\) are unreachable by any tangent line, and WQS fails.

Many natural problems have concavity: picking non-adjacent elements, placing facilities to minimize distance, selecting edges in a spanning structure. Each additional pick helps, but less than the last.

The Geometric View

Plot \(h(k)\) as points: x-axis is \(k\) (number of items), y-axis is \(h(k)\) (best value). Since \(h\) is concave, these points form an upside-down bowl shape.

Plot of h(k) as a concave curve with points for k=0,1,2,3 — the curve bends downward, and a tangent line with slope lambda touches the curve at exactly k=K

Now consider \(g(\lambda) = \max_k \{ h(k) - \lambda \cdot k \}\). We're looking for the point \((k, h(k))\) that maximizes \(h(k) - \lambda \cdot k\), which is the y-intercept of a line with slope \(\lambda\) passing through that point.

If you know calculus, this is the discrete Legendre transform. If you don't, think of it as sliding a ruler against a curve: the angle of the ruler is \(\lambda\), and where it touches the curve gives you the optimal \(k\).

For a specific target \(K\), we want the tangent line that touches the curve at \(k = K\). The slope of that tangent is the optimal \(\lambda^*\). Finding it by binary search gives us the recovery formula:

\[h(K) = g(\lambda^*) + \lambda^* \cdot K\]

As \(\lambda\) increases (steeper tangent line), the touching point slides left (fewer items picked). As \(\lambda\) decreases, it slides right (more items). This monotonicity is what makes binary search work.

Tracing on a Small Example

Problem: Array [10, 3, 8, 7, 2, 9]. Pick exactly \(K=2\) non-adjacent elements to maximize sum.

First, compute \(h(k)\) by brute force to verify concavity:

\(k\)	Best non-adjacent subset	\(h(k)\)	Marginal gain \(h(k)-h(k-1)\)
0	{}	0	—
1	{10}	10	10
2	{10, 9} (indices 0,5)	19	9
3	{10, 7, 9} (indices 0,3,5)	26	7

Marginal gains: 10, 9, 7. Strictly decreasing — \(h\) is concave.

Target \(K=2\), so \(h(2)=19\). Binary search on \(\lambda\):

Iter	lo	hi	\(\lambda\)	Effective values	Best non-adj	cnt	Action	Recovery
1	0	20	10	\([0,-7,-2,-3,-8,-1]\)	\(\{0\}\) or \(\{\}\), val=0	0-1	cnt \(< 2\), hi=9	—
2	0	9	4	\([6,-1,4,3,-2,5]\)	\(\{6,4,5\}\) idx 0,2,5, val=15	3	cnt \(\geq 2\), lo=5	\(15+4 \cdot 2=23\)
3	5	9	7	\([3,-4,1,0,-5,2]\)	\(\{3,2\}\) idx 0,5, val=5	2	cnt \(\geq 2\), lo=8	\(5+7 \cdot 2=19\)
4	8	9	8	\([2,-5,0,-1,-6,1]\)	\(\{2,1\}\) idx 0,5, val=3	2	cnt \(\geq 2\), lo=9	\(3+8 \cdot 2=19\)
5	9	9	9	\([1,-6,-1,-2,-7,0]\)	\(\{1\}\) idx 0, val=1	1	cnt \(< 2\), hi=8	—
6	9	8	—	loop ends				ans\(=19\)

Answer: 19. Verified: indices 0 and 5, giving \(10+9=19\).

Why does \(\lambda=8\) work? Each pick "costs" 8. The first pick's marginal gain was 10 (worth it: \(10-8=2\) profit). The second pick's marginal gain was 9 (worth it: \(9-8=1\) profit). The third pick's marginal gain would be 7 (not worth it: \(7-8=-1\) loss). So exactly 2 items get picked.

The Algorithm

1. Binary search on lambda in [lo, hi]
2. For each lambda:
   a. Run inner solver: maximize (value - lambda * count)
   b. Inner solver returns (adjustedValue, elementsPicked)
3. If elementsPicked >= K: lambda is too low, increase it
   If elementsPicked < K: lambda is too high, decrease it
4. At convergence: answer = g(lambda*) + lambda* * K

The Bug Factory: tie-breaking. When \(\lambda\) hits a value where the marginal gain of the next item equals \(\lambda\) exactly (a "flat" segment on the concave curve), the inner solver faces a tie: picking that item or not gives the same adjusted value. If the solver alternates unpredictably between picking 2 items and picking 4 items at the same \(\lambda\), the binary search oscillates forever.

The fix: the inner solver must consistently prefer fewer items (or consistently prefer more items) when tied. The code below uses >= in the DP comparisons, which on tie prefers the "skip" branch (fewer items). This ensures convergence.

Complexity Analysis

Let \(T(n)\) be the time for the inner solver. WQS adds a binary search wrapper:

\[\text{Total: } O(T(n) \cdot \log V)\]

where \(V\) is the range of possible \(\lambda\) values. For integer problems, \(\log V\) is typically 30-60.

Problem	Without WQS	Inner solver	Total with WQS
Non-adjacent \(K\) picks	\(O(N \cdot K)\)	\(O(N)\)	\(O(N \cdot \log V)\)
General DP with count dim	\(O(N \cdot K \cdot T)\)	\(O(N \cdot T)\)	\(O(N \cdot T \cdot \log V)\)

The savings come from removing the \(K\) dimension from the inner DP.

When WQS Applies (and When It Doesn't)

WQS works when: - \(h(k)\) is concave (or convex for minimization — just negate) - Marginal gains are non-increasing - The inner unconstrained problem is significantly faster than the constrained one

WQS fails when: - \(h(k)\) is not concave (e.g., the 2-item knapsack from Lesson 2.4) - The inner solver doesn't simplify without the count constraint - Tie-breaking is pathological (rarely an issue in practice)

How to check concavity in practice: If each additional item picked is "weaker" than the last — because the best items are grabbed first and leftovers are worse — you almost certainly have concavity. If adding an item can sometimes help MORE than the previous addition (synergy effects, threshold bonuses), concavity likely fails.

The Code

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

pair<long long, int> solveUnconstrained(const vector<int>& arrayElements, long long penaltyLambda) {
    int numElements = arrayElements.size();
    vector<array<long long, 2>> maxAdjustedValue(numElements, {0, 0});
    vector<array<int, 2>> elementsPicked(numElements, {0, 0});

    maxAdjustedValue[0][0] = 0;
    elementsPicked[0][0] = 0;
    maxAdjustedValue[0][1] = arrayElements[0] - penaltyLambda;
    elementsPicked[0][1] = 1;

    for (int i = 1; i < numElements; i++) {
        if (maxAdjustedValue[i-1][0] >= maxAdjustedValue[i-1][1]) {
            maxAdjustedValue[i][0] = maxAdjustedValue[i-1][0];
            elementsPicked[i][0] = elementsPicked[i-1][0];
        } else {
            maxAdjustedValue[i][0] = maxAdjustedValue[i-1][1];
            elementsPicked[i][0] = elementsPicked[i-1][1];
        }

        long long baseValue = (i >= 2) ? max(maxAdjustedValue[i-2][0], maxAdjustedValue[i-2][1]) : 0;
        int baseCount = 0;
        if (i >= 2) {
            baseCount = (maxAdjustedValue[i-2][0] >= maxAdjustedValue[i-2][1]) ? elementsPicked[i-2][0] : elementsPicked[i-2][1];
        }

        maxAdjustedValue[i][1] = baseValue + arrayElements[i] - penaltyLambda;
        elementsPicked[i][1] = baseCount + 1;
    }

    if (maxAdjustedValue[numElements-1][0] >= maxAdjustedValue[numElements-1][1]) {
        return {maxAdjustedValue[numElements-1][0], elementsPicked[numElements-1][0]};
    } else {
        return {maxAdjustedValue[numElements-1][1], elementsPicked[numElements-1][1]};
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numElements, targetCount;
    cin >> numElements >> targetCount;

    vector<int> arrayElements(numElements);
    for (int i = 0; i < numElements; i++) {
        cin >> arrayElements[i];
    }

    long long lowPenalty = 0, highPenalty = 2e9;
    long long finalAnswer = 0;

    while (lowPenalty <= highPenalty) {
        long long penaltyLambda = lowPenalty + (highPenalty - lowPenalty) / 2;
        auto [adjustedValue, elementsPicked] = solveUnconstrained(arrayElements, penaltyLambda);

        if (elementsPicked >= targetCount) {
            finalAnswer = adjustedValue + penaltyLambda * targetCount;
            lowPenalty = penaltyLambda + 1;
        } else {
            highPenalty = penaltyLambda - 1;
        }
    }

    cout << finalAnswer << "\n";
    return 0;
}

Try It

Test case 1: Non-adjacent, pick exactly 2.

Input:
6 2
10 3 8 7 2 9
Output: 19

Before running, predict: what value of \(\lambda\) will make the inner solver pick exactly 2 items? Hint: it's between the marginal gain of the 2nd item (9) and the 3rd item (7).

Test case 2: Pick exactly 1.

Input:
4 1
3 7 2 5
Output: 7

What would happen if \(\lambda = 0\)? The inner solver picks everything profitable. What if \(\lambda = 6\)? Only items with value \(> 6\) survive.

Test case 3: Pick exactly 3.

Input:
7 3
5 1 8 1 5 1 8
Output: 21

Trace: indices 0, 2, 6 → \(5+8+8=21\). Check non-adjacency: 0 and 2 differ by 2, 2 and 6 differ by 4. Valid.

Challenge: What if two different \(k\) values give the same \(h(k)\)? (A "flat" segment in the concave curve.) The tangent line touches the curve along an entire segment, not at a single point. How does the binary search handle this? What tie-breaking rule in the inner solver ensures we still get the right answer?

Historical Note: IOI 2016 — Aliens. The problem that made WQS globally famous. You place square photos on an \(N \times N\) grid to cover \(M\) points of interest, minimizing total cost using exactly \(K\) photos. Without WQS, the DP is \(O(M^2 \cdot K)\). With WQS, you drop the \(K\) constraint, penalize each photo by \(\lambda\), and the inner DP becomes \(O(M \log M)\) using the Convex Hull Trick. Total: \(O(M \log M \cdot \log V)\). Out of 300+ IOI 2016 finalists, only one scored full marks during the contest — cementing WQS as one of the most powerful (and feared) techniques in competitive programming.

Problems

Problem	Link	Difficulty
IOI 2016 — Aliens	oj.uz/problem/view/IOI16_aliens	IOI Hard
CF 739E — Gosha is Hunting	codeforces.com/problemset/problem/739/E	2600
CF 958E2 — Guard Duty (Hard)	codeforces.com/problemset/problem/958/E2	2700
APIO 2014 — Sequence	oj.uz/problem/view/APIO14_sequence	Hard
JOI 2019 — Candies (with fixed K)	oj.uz/problem/view/JOI19_candies	Hard