D. Doubles Horseback Wrestling

Updated May 21, 2026

Track ICPC

Year 2024

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 4 seconds

The Nomadic Games Exploratory Committee (NGEC) is floating the idea of a doubles horseback wrestling tournament with pairs of riders astride single horses. They have advertised a pilot tournament, and n eager riders have signed up to compete! So now the NGEC needs to pair the riders in order to make the tournament both fair and exciting. The Central Asian Audaryspak League (CAAL) maintains a list of all horseback wrestlers and their ratings. From their previous expe- rience with ordinary horseback wrestling, the NGEC has decided that the pairs are best balanced if the ratings of their two riders add up to a particular integer, s. For obscure licensing reasons, the CAAL refuses to release the exact rating of each rider. But the NGEC has some good estimates, knowing that any rider i’s true rating ri lies in an interval [li , ui ]. So the NGEC would consider pairing two riders i and j if there are ratings ri ∈ [li , ui ] and rj ∈ [lj , uj ] such that ri + rj = s. Horseback wrestling in Kyrgyzstan by Theklan The NGEC wants to form as many non-intersecting pairs of riders as Wikimedia Commons, CC BY-SA 4.0

possible. You need to help them.

Input

The first line contains two integers n and s (2 ≤ n ≤ 2 · 105 , 1 ≤ s ≤ 109 ), denoting the number of riders and the desired sum of ratings of riders in a pair. Riders are numbered 1 to n. This is followed by n lines, where the ith line contains two integers li and ui (1 ≤ li ≤ ui ≤ 109 ), denoting the rating range of the ith rider.

Output

Output k, the maximum number of riding pairs that can be formed, followed by k pairs of integers, denoting the numbers of the riders forming each pair. If there are multiple ways to pair off the riders, output any one.

Sample Tests

Sample 1

Sample Input

Sample Output

2
6 2
3 4

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

Sort riders by increasing $l$.
For a fixed rider $i$, any partner $j$ with smaller or equal $l$ must satisfy $l_j \le s - l_i$ and $u_j \ge s - u_i$.
If we process riders from large $l$ down to small $l$, then when rider $i$ is current, every still unprocessed rider with $l_j \le s - l_i$ is already known and can be placed in a pool.
Among feasible partners in that pool, it is optimal to use the one with the smallest possible $u$. A larger $u$ can only help future riders more than a smaller $u$ can.
If rider $i$ cannot be matched when it is processed, then it can never be matched later: all later riders have even smaller $l$, so rider $i$ would still need a partner from the same pool, and the lower bound on $u_j$ would only get harder to satisfy for rider $i$ itself.

Algorithm

Sort riders by increasing $l$.
Scan the sorted list from right to left.
Maintain a multiset of still-unmatched riders to the left of the current position whose lower bound already satisfies $l_j \le s - l_i$. Store them ordered by $u_j$.
For the current rider $i$, find in the multiset the rider with smallest $u_j \ge s - u_i$.
If such a rider exists, match them and remove that rider from the multiset. Otherwise leave $i$ unmatched forever.

Correctness Proof

We prove that the algorithm outputs a maximum matching.

Lemma 1.

When rider $i$ is processed, the multiset contains exactly the unmatched riders $j$ to the left of $i$ such that $l_j \le s - l_i$.

Proof.

We scan riders in decreasing order of $l_i$. A pointer grows over the left prefix and inserts every rider whose $l_j$ has become small enough to satisfy $l_j \le s - l_i$. Since $s - l_i$ only increases during the scan, every such rider is inserted exactly once. We remove riders only when they are matched or when a former pool rider becomes the current rider itself. Therefore the multiset contains exactly the still-unmatched eligible riders to the left. □

Lemma 2.

If rider $i$ is matched, choosing among all feasible partners the one with minimum $u_j$ cannot decrease the size of an optimal completion.

Proof.

Let $j$ be the feasible partner with minimum $u_j$, and suppose some optimal solution matches $i$ with another feasible rider $k$. Since both are feasible for $i$, we have \[ u_j \le u_k, \qquad l_j \le s - l_i, \qquad u_j \ge s - u_i. \] Replace pair $(i,k)$ by $(i,j)$. Any other rider that could be matched with $j$ in the optimal solution also has lower-bound requirement at most the requirement used for $i$ at this moment, and using the smaller $u_j$ instead of $u_k$ only frees the larger $u_k$ for later riders. So we can swap $j$ into $i$'s pair and use $k$ wherever $j$ was used, or leave $k$ unmatched if $j$ was unused. The number of pairs does not decrease. □

Lemma 3.

If rider $i$ has no feasible partner when processed, then there exists an optimal matching in which $i$ is unmatched.

Proof.

By Lemma 1, every possible partner of $i$ among still-unprocessed riders is already in the multiset. If no feasible rider there has $u_j \ge s - u_i$, then no rider to the left can pair with $i$. Riders to the right have already been processed and, in any pair containing $i$, rider $i$ would be the larger-$l$ endpoint. Hence all possible pairings involving $i$ have already been considered, and none is feasible. Therefore $i$ can be left unmatched in some optimal solution. □

Theorem.

The algorithm outputs a maximum-cardinality set of disjoint valid pairs.

Proof.

Consider the riders in the order processed by the algorithm. By Lemma 2, whenever the algorithm matches the current rider, there exists an optimal solution consistent with that choice. By Lemma 3, whenever the algorithm leaves the current rider unmatched, there exists an optimal solution consistent with that choice as well. Inductively, after every step there remains an optimal solution consistent with all choices already made by the algorithm. After the final step, the algorithm itself is such an optimal solution. □

Complexity Analysis

Sorting costs $O(n \log n)$. Every rider is inserted into and removed from the multiset at most once, and every query is one lower_bound, so the total running time is $O(n \log n)$. The memory usage is $O(n)$.

Implementation Notes

The multiset stores pairs $(u_j,\text{position})$ so duplicates in $u_j$ are handled naturally.
A rider may enter the multiset before becoming the current rider later; in that case we remove its own entry before processing it.
The output may list the pairs in any order.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

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

namespace {

struct Rider {
    int l;
    int u;
    int id;
};

void solve() {
    int n;
    int s;
    cin >> n >> s;

    vector<Rider> riders(n);
    for (int i = 0; i < n; ++i) {
        cin >> riders[i].l >> riders[i].u;
        riders[i].id = i + 1;
    }

    sort(riders.begin(), riders.end(), [](const Rider& a, const Rider& b) {
        if (a.l != b.l) {
            return a.l < b.l;
        }
        if (a.u != b.u) {
            return a.u < b.u;
        }
        return a.id < b.id;
    });

    vector<char> matched(n, false);
    vector<char> in_pool(n, false);
    vector<pair<int, int>> answer;
    answer.reserve(n / 2);

    multiset<pair<int, int>> pool;  // (u, position in sorted order)
    int ptr = -1;

    for (int pos = n - 1; pos >= 0; --pos) {
        const Rider& cur = riders[pos];
        if (in_pool[pos]) {
            auto it = pool.find({cur.u, pos});
            if (it != pool.end()) {
                pool.erase(it);
            }
            in_pool[pos] = false;
        }
        if (matched[pos]) {
            continue;
        }

        while (ptr + 1 < pos && riders[ptr + 1].l <= s - cur.l) {
            ++ptr;
            if (!matched[ptr] && !in_pool[ptr]) {
                pool.insert({riders[ptr].u, ptr});
                in_pool[ptr] = true;
            }
        }

        auto it = pool.lower_bound({s - cur.u, -1});
        if (it == pool.end()) {
            continue;
        }

        const int other_pos = it->second;
        pool.erase(it);
        in_pool[other_pos] = false;
        matched[pos] = true;
        matched[other_pos] = true;
        answer.push_back({cur.id, riders[other_pos].id});
    }

    cout << answer.size() << '\n';
    for (const auto& p : answer) {
        cout << p.first << ' ' << p.second << '\n';
    }
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2024/D-doubles-horseback-wrestling/solution.texC++ implementationcompetitive_programming/icpc/2024/D-doubles-horseback-wrestling/solution.cppStatement textcompetitive_programming/icpc/2024/D-doubles-horseback-wrestling/statement.txtStatement PDFcompetitive_programming/icpc/2024/D-doubles-horseback-wrestling/statement.pdfMetadatacompetitive_programming/icpc/2024/D-doubles-horseback-wrestling/meta.jsonYear packetcompetitive_programming/icpc/2024/contest_problems.pdf

D. Doubles Horseback Wrestling

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets