Two-Phase Sorting

When One Sort Isn't Enough

The previous two lessons sorted everything by a single comparator. Some problems have a richer structure: two groups of items that need different sort orders.

The exchange argument still applies — but you apply it twice, independently to each group. And before even proving the sort order, you need to prove that one group should always come entirely before the other.

This three-step structure is the signature of two-phase sorting: 1. Prove group A comes before group B 2. Prove the sort order within group A 3. Prove the sort order within group B

The Problem That Requires Two Phases

CF1203F1 — Complete the Projects: A freelancer has rating \(r\). There are \(n\) projects. Project \(i\) requires minimum rating \(a_i\) to start, and changes the rating by \(b_i\) after completion (\(b_i\) can be negative). You must complete ALL projects. Can you find an ordering where the rating is never negative at any point?

The Greedy Choice: Do all positive projects first (sorted by requirement ascending), then all negative projects (sorted by \(a_i + b_i\) descending). Two groups, two sort orders.

The twist: some projects increase your rating (\(b_i \geq 0\)) and some decrease it (\(b_i < 0\)). These two groups need completely different sort strategies.

Step 1: Why Positive Projects Come First

Rating trajectory: positive projects raise the rating, then negative projects spend it — must stay non-negative

Claim: do all projects with \(b_i \geq 0\) before all projects with \(b_i < 0\).

Proof by exchange: Suppose in some ordering, a negative project N (\(b_N < 0\)) comes before a positive project P (\(b_P \geq 0\)). Consider swapping them.

Let the rating before N be \(r\).

Current (N before P):
Start N: need \(r \geq a_N\). After N: \(r + b_N\). Need \(r + b_N \geq 0\).
Start P: need \(r + b_N \geq a_P\). After P: \(r + b_N + b_P\).
After swap (P before N):
Start P: need \(r \geq a_P\). After P: \(r + b_P\).
Start N: need \(r + b_P \geq a_N\). After N: \(r + b_P + b_N = r + b_N + b_P\) (same final rating).

The final rating is identical. But is the swap safer? Since \(b_P \geq 0\): - \(r + b_P \geq r\) — the rating before N is now higher, making \(r + b_P \geq a_N\) easier to satisfy than \(r + b_N \geq a_P\) (since \(r + b_N \leq r\)).

If the current order was feasible, the swapped order is also feasible. And in some cases the swap makes an infeasible order feasible. So doing all positive projects first is weakly better — never worse.

Step 2: Sort Within Positive Projects

Among projects with \(b_i \geq 0\), which order is best?

Claim: sort by \(a_i\) ascending (lowest requirement first).

Exchange proof: Two adjacent positive projects \(i\) and \(j\) with \(a_i > a_j\) (but \(i\) comes first). Let \(r\) be the rating before them.

Current (\(i\) before \(j\)):
Need \(r \geq a_i\). After \(i\): \(r + b_i\). Need \(r + b_i \geq a_j\).
After swap (\(j\) before \(i\)):
Need \(r \geq a_j\). After \(j\): \(r + b_j\). Need \(r + b_j \geq a_i\).

Since \(a_i > a_j\): the swapped order requires less rating to start (\(a_j < a_i\)), and \(r + b_j \geq r \geq a_i\) (since \(b_j \geq 0\) and if \(r \geq a_i > a_j\)).

More carefully: if the current order is feasible (\(r \geq a_i\) and \(r + b_i \geq a_j\)), is the swap also feasible? Yes: \(r \geq a_i > a_j\) ✓, and \(r + b_j \geq r \geq a_i\) ✓ (since \(b_j \geq 0\)).

Sorting easier (lower requirement) positive projects first is always safe and never blocks feasibility.

Step 3: Sort Within Negative Projects

Among projects with \(b_i < 0\), which order is best?

Claim: sort by \(a_i + b_i\) descending.

The quantity \(a_i + b_i\) is the minimum rating you'll have AFTER completing project \(i\). If this is high, you "end well" — you're left with more rating for subsequent projects.

Exchange proof: Two adjacent negative projects \(i\) and \(j\). Let \(r\) be the rating before them.

Current (\(i\) before \(j\)):
Need \(r \geq a_i\). After \(i\): \(r + b_i\). Need \(r + b_i \geq a_j\) and \(r + b_i \geq 0\).
Final rating: \(r + b_i + b_j\).
After swap (\(j\) before \(i\)):
Need \(r \geq a_j\). After \(j\): \(r + b_j\). Need \(r + b_j \geq a_i\) and \(r + b_j \geq 0\).
Final rating: \(r + b_j + b_i\) (same).

Put \(i\) before \(j\) when? The critical constraint in the current order is \(r + b_i \geq a_j\), i.e., \(r \geq a_j - b_i\). The critical constraint in the swap is \(r + b_j \geq a_i\), i.e., \(r \geq a_i - b_j\).

Put \(i\) before \(j\) if \(a_j - b_i \leq a_i - b_j\) (the current order's tightest constraint is weaker). Rearranging:

\[a_j + b_j \leq a_i + b_i\]

Put project \(i\) before \(j\) if \(a_i + b_i \geq a_j + b_j\) — sort descending by \(a_i + b_i\).

Tracing the Full Algorithm

Example: r=5, projects: (3, +2), (6, +1), (8, -3), (5, -4).

Split: - Positive: (3, +2), (6, +1) - Negative: (8, -3), (5, -4)

Sort positive by \(a_i\) ascending: (3,+2), (6,+1). Sort negative by \(a_i+b_i\) descending: (8,-3)→5, (5,-4)→1. So (8,-3) first.

Trace:

Step	Project	Rating before	Check	Rating after
1	(a=3, b=+2)	5	5 ≥ 3 ✓	7
2	(a=6, b=+1)	7	7 ≥ 6 ✓	8
3	(a=8, b=-3)	8	8 ≥ 8 ✓	5
4	(a=5, b=-4)	5	5 ≥ 5 ✓	1

1 ≥ 0 ✓. Output: YES.

What if we had done the negative projects in the wrong order — (5,-4) before (8,-3)?

Step	Project	Rating before	Check	Rating after
3'	(a=5, b=-4)	8	8 ≥ 5 ✓	4
4'	(a=8, b=-3)	4	4 ≥ 8 ✗	FAIL

The wrong order fails even though we have enough total rating. The sort order matters.

Example 2: HR Mandragora Forest — A Degenerate Two-Phase Split

Problem: Forest of mandragoras, each with health \(H_i\). Your health starts at 1. For each mandragora, you choose: - Eat it: your health += 1 - Battle it: your EXP += your current health \(\times\) \(H_i\)

Maximize total EXP.

Key insight: You'll eat some prefix and battle the rest. Why a prefix? Because battling gives more EXP when your health is higher. So you want to build up health (by eating) before battling.

Sort mandragoras by \(H_i\) ascending. Eat the first k (smallest \(H_i\)), battle the rest.

Why sort ascending? You want to eat the "weakest" mandragoras (smallest \(H_i\)) — since eating doesn't give EXP, you lose the least potential by eating low-H ones. The battle EXP = health \(\times\) \(H_i\), so you want high \(H_i\) for battling.

Formula: After eating k mandragoras, your health is \(1 + k\). EXP from battling the rest:

\[(1+k) \times \sum_{i=k+1}^{n} H_i\]

Try all split points k = 0, 1, ..., n-1 in O(N) using a suffix sum.

k	Health	suffix_sum	EXP
0	1	all H's	\(1 \times \text{sum(all)}\)
1	2	\(H_1..H_{n-1}\)	\(2 \times \text{sum}(H_1..)\)
...	...	...	...

Take the maximum. This is O(N) after sorting.

Example 3: ABC085D — Katana Thrower (Single Split Point)

Problem: N katanas. You can wield (reusable, \(a_i\) damage) or throw (one-time, \(b_i\) damage, \(b_i \geq a_i\) always). Monster has H HP. Minimize attacks.

Best wield damage: bestWieldDamage = max(a_i).

Two-phase decision: Throw all katanas where \(b_i >\) bestWieldDamage (each is worth more than your best wield). Then wield bestWieldDamage repeatedly for the remaining HP.

Order within throws: doesn't matter (each is independent, one-shot).

int bestWieldDamage = *max_element(wieldDamage.begin(), wieldDamage.end());
sort(throwDamage.rbegin(), throwDamage.rend());

int totalAttacks = 0;
long long remainingHP = monsterHealth;
for (int i = 0; i < totalKatanas && throwDamage[i] > bestWieldDamage && remainingHP > 0; i++) {
    remainingHP -= throwDamage[i];
    totalAttacks++;
}
if (remainingHP > 0) totalAttacks += (remainingHP + bestWieldDamage - 1) / bestWieldDamage;

The Code (Complete Projects)

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

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

    int numProjects, currentRating;
    cin >> numProjects >> currentRating;

    vector<pair<int, int>> positiveProjects, negativeProjects;
    for (int i = 0; i < numProjects; i++) {
        int requirement, ratingChange;
        cin >> requirement >> ratingChange;
        if (ratingChange >= 0) {
            positiveProjects.push_back({requirement, ratingChange});
        } else {
            negativeProjects.push_back({requirement, ratingChange});
        }
    }

    auto positiveCompare = [](const pair<int, int>& x, const pair<int, int>& y) {
        return x.first < y.first;
    };
    sort(positiveProjects.begin(), positiveProjects.end(), positiveCompare);

    auto negativeCompare = [](const pair<int, int>& x, const pair<int, int>& y) {
        return (x.first + x.second) > (y.first + y.second);
    };
    sort(negativeProjects.begin(), negativeProjects.end(), negativeCompare);

    for (const auto& project : positiveProjects) {
        if (currentRating < project.first) {
            cout << "NO\n";
            return 0;
        }
        currentRating += project.second;
    }

    for (const auto& project : negativeProjects) {
        if (currentRating < project.first) {
            cout << "NO\n";
            return 0;
        }
        currentRating += project.second;
        if (currentRating < 0) {
            cout << "NO\n";
            return 0;
        }
    }

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

Try It

Add the two sorting lambdas.

Input:
4 5
3 2
6 1
8 -3
5 -4
Output: YES

Input:
3 10
5 -3
8 -5
4 2
Output: YES

Trace the second case manually: - Positive: (4,+2). Sorted: (4,+2). - Negative: (5,-3) → \(a+b=2\), (8,-5) → \(a+b=3\). Sorted descending: (8,-5), (5,-3). - Start r=10. - (4,+2): r≥4 ✓, r=12. - (8,-5): r≥8 ✓, r=7. - (5,-3): r≥5 ✓, r=4. 4≥0 ✓. YES.

Input:
2 3
5 -2
4 -1
Output: NO

Trace: no positive projects. Negative: (5,-2) → \(a+b=3\), (4,-1) → \(a+b=3\). Both \(a+b=3\), order doesn't matter. - (4,-1): r≥4? 3≥4 ✗. NO.

Challenge: Remove the if (currentRating < 0) check. Does the algorithm still give the right answer? What case requires that check?

Problems

Problem	Link	Difficulty
CF1203F1 — Complete the Projects	codeforces.com/problemset/problem/1203/F1	2100
HR — Mandragora Forest	hackerrank.com/challenges/mandragora	Medium
ABC085D — Katana Thrower	atcoder.jp/contests/abc085/tasks/abc085_d	400pts
ABC160E — Red and Green Apples	atcoder.jp/contests/abc160/tasks/abc160_e	500pts