Two countries each send N cyclists to ride tandem bicycles, and every bike's speed is decided by "the faster of its two riders". The question: pair them so the total speed of all N bikes is as small as possible — or as large as possible. CCC 2016 J5/S2 Tandem Bicycle looks like it requires comparing all N! pairings. What it really tests is one greedy line: sort first, then pair. Once sorted, "same-order pairing minimizes, opposite-order pairing maximizes" can be proved by a single exchange argument — one of the most common greedy shapes in contests.

Where This Fits in the CCC DSA Map

• Level: Junior J5 ≡ Senior S2 (the same problem serves both levels)
• Pattern: Sorting + Greedy Pairing
• Prerequisite: sorting lists, loops, max(), Big-O basics (Python basics: input, operators, and conditions, Python Lists: append() vs +)
• What this teaches: prove a greedy rule with an "one exchange tells the direction" argument, reducing N! pairings to one scan after sorting
• Where it appears again: the greedy topic (planned), the same-week DSA-025 Time on Task greedy proof (python-notes), CPW-026 Time on Task (planned)

What to Study Next

• Related CP Weekly problems: CCC 2013 J4 Time on Task (coming soon — greedy counting under a budget), and "Why Does Greedy Sorting Always Work? The Exchange Argument with Time on Task" (Python Notes, same week)
• Related Python / C++ foundations: Python Basics: Input, Operators, and Conditions, Python Lists: append() vs +
• Related DSA roadmap article: Greedy and Binary Search Patterns (planned)

What the Problem Is Asking

The first line gives q: q=1 asks for the minimum total speed, q=2 for the maximum. The second line gives N (1 ≤ N ≤ 100), the third the N speeds of Dmojistan, the fourth the N speeds of Pegland (each between 1 and 10⁶). Each tandem bike pairs one rider from each country, and its speed is the larger of the two riders' speeds. Output one integer: the requested total speed.

Official sample 1 (q=1): Dmoj [5 1 4], Peg [6 2 4] → pair 5-6, 1-2, 4-4, total 6+2+4 = 12.

Official sample 2 (q=2): same data, maximize → pair 5-2, 1-6, 4-4, total 5+6+4 = 15.

Official sample 3 (q=2, N=5): Dmoj [202 177 189 589 102], Peg [17 78 1 496 540] → 2016.

Where Beginners Often Get Stuck

• Enumerating pairings for real: N! pairings sounds hopeless. After sorting, the answer is uniquely determined — there is nothing to "choose".
• Adding both riders' speeds: the bike speed is decided by the faster rider — it is max(a, b); computing a+b (which gives 22 on the sample) solves the wrong objective.
• Forgetting to reverse for the maximum: q=2 needs one list ascending and the other descending; skipping the reverse still computes the minimum's shape.
• Reversing both lists: reversing both preserves the original pairs and does nothing for the maximum — if you want speed, reverse exactly one.
• Worrying about the proof: "same-order minimizes" feels like a guess. The exchange argument below shows it holds for all data, not by luck.

Core Algorithm Idea

Do the arithmetic of two bikes first. Take any two Dmoj riders a ≤ b and any two Peg riders c ≤ d. Only two pairings exist:

same-order: max(a, c) + max(b, d)
crossed:    max(a, d) + max(b, c)

As shown under "Why the Algorithm Is Correct", for every a ≤ b and c ≤ d, same-order ≤ crossed. So every time a "crossed" pair is swapped back into same order, the total does not increase — pairing both ascending by index minimizes the total. The maximizer is the mirror image: one list ascending, the other descending.

This also explains why summing first kills the greedy: if the bike speed were a+b, every pairing would give the same total, and greedy reasoning would have nothing to hold onto. Reading the objective — max or sum — is step one of this problem family.

State / Data Structure Design

• q: objective type, 1 = minimum total, 2 = maximum total.
• n: riders per country, i.e., the number of tandem bikes.
• dmoj, peg: the two speed lists, sorted (and possibly reversed), then paired by index.
• total: the sum of max(dmoj[i], peg[i]) over all pairs.

No need to record "who paired with whom" — the pairing is uniquely decided by the sorted order.

Algorithm Steps

1. Read q, n, and the two speed lists of length n each.
2. Sort both lists in ascending order.
3. If q=2, reverse peg (exactly one list).
4. Walk the indices, adding max(dmoj[i], peg[i]) into total.
5. Print total.

Sample Check with the Official Data

Walk both objectives on the sample data (sort [5 1 4] into [1 4 5], [6 2 4] into [2 4 6]):

Same-order gives 12, matching sample 1; reversed gives 15, matching sample 2. Sample 3's 2016 comes from the same "ascending + descending" pairing. This table is the whole core of greedy pairing: sort once, scan once per objective.

Python Solution

q = int(input())
n = int(input())
dmoj = list(map(int, input().split()))
peg = list(map(int, input().split()))

dmoj.sort()
peg.sort()

if q == 2:
    peg.reverse()

total = 0
for i in range(n):
    total += max(dmoj[i], peg[i])

print(total)

This matches the curriculum notebook (p2006, sorting and greedy reasoning) line for line — sort, reverse when asked, accumulate. total ≤ 100 × 10⁶ = 10⁸, which Python integers handle easily; a 32-bit signed int also just barely fits, though building the long long habit is safer.

C++ Solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int q;
    cin >> q;
    int n;
    cin >> n;
    vector<int> dmoj(n);
    for (int i = 0; i < n; i++) {
        cin >> dmoj[i];
    }
    vector<int> peg(n);
    for (int i = 0; i < n; i++) {
        cin >> peg[i];
    }

    sort(dmoj.begin(), dmoj.end());
    sort(peg.begin(), peg.end());
    if (q == 2) {
        reverse(peg.begin(), peg.end());
    }

    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += max(dmoj[i], peg[i]);
    }

    cout << total << '\n';
    return 0;
}

Mirrors the curriculum pseudocode step by step: sort is O(N log N), the accumulation O(N), and the official limits finish in well under a millisecond. Sorting aux space: Python's sort uses O(N) worst case, C++ introsort O(log N) stack.

Why the Algorithm Is Correct

• Each bike's speed is indeed a max: the statement defines the bike speed as the larger of the two riders' speeds, matching max(dmoj[i], peg[i]).
• Same-order pairing minimizes the total: take any two "crossed" pairs (a,d) and (b,c) with a ≤ b and d ≥ c (as they appear in the sorted lists). Swap them back to (a,c), (b,d). For every a ≤ b and c ≤ d, max(a,c) + max(b,d) ≤ max(a,d) + max(b,c): check the four size cases one by one (for example, when a ≤ c ≤ b ≤ d, the left side is c + d and the right side is d + b, and c ≤ b makes the left ≤ right). Any pairing can be sorted into same order by finitely many such "descent swaps", each never increasing the total, so the same-order pairing is minimal.
• Reversed pairing maximizes the total: swapping the two sides of the same inequality gives max(a,d) + max(b,c) ≥ max(a,c) + max(b,d) — the reversed pairing is the mirror image of the same argument.
• No better pairing is missed: sorting fixes the relative order of both sequences; every index-based pairing corresponds to exactly one "same-order" or "opposite-order" shape, so nothing better is left out.

Therefore the printed total is exactly the requested minimum or maximum total speed.

Complexity Analysis

• Time O(N log N): the two sorts dominate; the pairing pass is O(N). At N=100 this runs in well under a millisecond.
• Space O(N): the two speed lists (see above for sort aux space).
• If N grew to 10⁵, this would still be the standard solution — the proof and the sorting both scale unchanged.

Common Mistakes

1. Summing both riders' speeds — misreading the objective as a+b (the sample would give 22).
2. Forgetting the reverse for q=2 — or reversing both lists (which reverses nothing).
3. Sorting only one list — the unsorted side makes the pairing depend on input order.
4. Memorizing "same-order minimizes" without the proof — under a different objective (like a sum) the greedy dies instantly; be ready to retell the exchange argument.
5. Misreading the input — q, n, then two lines of speeds; line up with the samples row by row.

Review Questions

1. Complete the exchange argument for all four relative orders of a ≤ b and c ≤ d, and explain why same-order pairing is never worse than crossed pairing.
2. If the bike speed were changed to the sum of both riders' speeds, would sort-and-pair still work? Why or why not?
3. Why does reversing both lists fail to maximize the total? Explain with the pairs at indices 0 and N−1.
4. This problem shares one greedy habit with Time on Task (finish as many tasks as possible within a budget). What is that sentence? (Hint: see DSA-025.)
5. With N ≤ 10⁵ and speeds ≤ 10⁹, what are the time and space complexities? Is there a better asymptotic order?