Array Destruction -- CF 1474C

Difficulty: 1700 * Techniques: greedy, constructive, enumeration, multiset Problem Link

Quick Revisit

• PROBLEM: Pair up 2n elements so each pair sums to x, with x decreasing as the max of each pair
• KEY INSIGHT: The largest element must be in the first pair, so x = a_max + a_j for only O(n) candidates
• TECHNIQUES: greedy (forced pairing), candidate enumeration, multiset
• TRANSFER: When a process is monotone (only decreases), the largest element pins the first move -- enumerate partners

First Read

We have $2n$ integers. We pick some initial value $x$. Each step, we choose two elements that sum to the current $x$, remove them, and the larger of the pair becomes the new $x$. Repeat until the array is empty -- or declare it impossible.

The constraint $n\le 1000$ means $2n\le 2000$. And we need to output the sequence of pairs. Feels constructive.

The Greedy Trap

My first thought: "Sort the array, greedily pair the largest unused element with whatever sums to $x$." This is actually part of the solution, but I was stuck on: how do I choose $x$?

If I just try random values of $x$, there are too many. Or are there?

The Key Constraint

The largest element in the array must be used in the very first step (because after that, $x$ can only decrease -- the new $x$ is the max of the pair, which is at most the current $x$ minus something positive). So the largest element is always paired first.

That means $x=a_{max}+a_j$ for some other element $a_j$. There are only $2n-1$ choices for $a_j$. For each candidate $x$, we simulate the greedy process:

1. Sort descending. The largest unused element must pair with $x-\text{largest}$ (look it up).
2. Remove both. New $x$ = largest element just used.
3. Repeat.

If at any point the partner doesn't exist, this $x$ fails. Try the next candidate.

Why Greedy Works Once x Is Fixed

Once $x$ is fixed, the largest remaining element must be in the current pair. Here is the one-line proof: at every step the new target equals the larger element of the pair just removed, which is at most the previous target. So the target value is monotonically non-increasing across steps. If we tried to defer the current largest remaining element to a later step, the future target would already be smaller than that element, leaving no partner with a non-negative value to pair against. Hence the greedy choice is forced, not heuristic.

Complexity

$O(n)$ candidates for $x$. Each simulation is $O(n\log n)$ using a multiset for lookups and deletions. Total: $O(n^2\log n)$. With $n\le 1000$, that's around ${10}^7$ -- fine.

Implementation Notes

• Use a multiset so you can handle duplicate values. erase(find(val)) removes exactly one copy.
• When pairing, be careful: if $x-a_{max}=a_{max}$, you need two copies of that value in the multiset.
• Store the pairs as you go so you can output them if the simulation succeeds.
• Presentation nit: tryX returns {} on failure, and n = 0 would also produce {}. The constraint guarantees $n\ge 1$, so it works here. In a more general setting, return optional<vector<pair<int,int>>> (or a bool plus the vector) so success and emptiness are distinguishable.

The Code

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

void solve() {
    int n; cin >> n;
    vector<int> a(2 * n);
    for (auto& x : a) cin >> x;
    sort(a.rbegin(), a.rend());

    auto tryX = [&](int x) -> vector<pair<int,int>> {
        multiset<int> ms(a.begin(), a.end());
        vector<pair<int,int>> res;
        int cur = x;
        for (int step = 0; step < n; step++) {
            int big = *ms.rbegin();
            ms.erase(ms.find(big));
            int need = cur - big;
            auto it = ms.find(need);
            if (it == ms.end()) return {};
            ms.erase(it);
            res.push_back({big, need});
            cur = big;
        }
        return res;
    };

    for (int i = 1; i < 2 * n; i++) {
        int x = a[0] + a[i];
        auto res = tryX(x);
        if (!res.empty()) {
            cout << "YES\n" << x << "\n";
            for (auto [a, b] : res) cout << a << " " << b << "\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

• "The largest element is forced" -- when a process is monotone (values only decrease), the biggest element pins down the first move, massively reducing the search space.
• Enumerate a small set of candidates, simulate each -- a powerful pattern when brute force over all possibilities is too much, but fixing one decision makes the rest forced.
• Multiset for pairing problems -- erase(find(...)) to remove one copy, rbegin() for the current max. Clean and fast.

---

See also: Greedy | Constructive Algorithms | Set and Multiset | Pattern Recognition Guide | Practice Ladder 1400-1700