894. The k Smallest Pair Sums
Two lists A and B are given, each already sorted in non-decreasing order.
Form the pair (a, b) for every a in A and every b in B, so there
are n * m pairs counting positions separately.
Print the k pairs with the smallest sums, ordered by increasing sum, then by
increasing a, then by increasing b. One pair per line, as two integers.
``` A = [1 7 11], B = [2 4 6], k = 4 -> 1 2 1 4 1 6 7 2
A = [1 2 3], B = [4 5 6], k = 9 -> every pair, in order A = [0], B = [-3 -2 -1 5], k = 3 -> 0 -3 / 0 -2 / 0 -1 ```
The sums in the first example are 3, 5, 7 from a = 1, then 9, 11, 13
from a = 7. The four smallest are the three from a = 1 and then 7 2.
## What most people try first
**Building all n * m pairs and sorting them.** With n and m both
10^5 that is 10^10 pairs. Neither the time nor the memory exists.
Binary searching the answer. Problem 783 does exactly that for a closely
related question, and it is the right method THERE. The difference is what is
being asked for. Counting how many pair sums are at most x is easy and
monotone, so binary search finds the kth SUM. But counting cannot list the
pairs, and this problem wants the pairs themselves, in order. A count tells
you where the boundary is, not what is inside it.
## The frontier
Every row of the implied grid is already sorted: for a fixed a = A[i], the
sums A[i] + B[0] <= A[i] + B[1] <= ... increase with j. So this is a
merge of n sorted sequences, exactly like problem 887, and the same
candidate argument applies: the next smallest pair is always the front of some
row.
h = min-heap ordered by (a + b, a, b)
for i from 0 to min(n, k) - 1:
push (A[i] + B[0], A[i], B[0], i, 0)
repeat k times:
pop the smallest, print its a and b
if j + 1 < m: push (A[i] + B[j+1], A[i], B[j+1], i, j+1)
## Why only the first k rows are seeded
The smallest sum in row i is A[i] + B[0], and A is sorted, so those row
minimums increase with i. Row k therefore has at least k pairs ahead of
it, one from each earlier row, and it cannot contribute to the answer. Seeding
min(n, k) rows keeps the heap from becoming huge when n is 10^5 and
k is 1.
## Why the pops come out in exactly the required order
The heap key is the full ordering key (sum, a, b), not just the sum. Within
one row, j increasing gives non-decreasing sums and, when sums tie,
non-decreasing b, so row order IS key order. The heap always holds the
smallest unpopped key of every seeded row, so its minimum is the global
smallest unpopped key. Popping k times therefore yields the k smallest
keys in order, with no sorting pass afterwards.
Ordering the heap on the sum alone would still give sums in the right order while leaving tied pairs in an arbitrary sequence, which fails a byte-for-byte judge.
## The boundary that breaks a careless implementation
Pushing both `(i, j+1)` and `(i+1, j)`. That is the other common frontier
expansion, and it reaches the same pairs by more than one route, so it needs a
visited set or it emits duplicates. Seeding every row once and expanding only
along j reaches each pair exactly once with no set at all.
Running off the end of `B`. The expansion must check j + 1 < m. A row
that is exhausted simply stops contributing.
Duplicate values. A = [2 2] and B = [1 1 3 3] has four pairs summing
to 3 and they are four separate answers, printed as four identical lines. A
program that de-duplicates by value loses three of them.
## What is NOT an overflow here
A sum is at most 2 * 10^9 in magnitude. It is worth stating the exact
comparison, because this is the most mis-remembered bound in the topic: the
largest signed 32-bit integer is 2147483647, and 2000000000 is smaller,
so the sum FITS. There is no overflow in this problem. The place to be careful
is problem 783, where the same pair sums are searched over a much wider range.
## Related problems
Problem 887 is this merge without the second dimension. Problem 783 asks for
the kth pair TOTAL inside a single array and solves it by counting, and
comparing the two is the lesson: counting finds a ranked value, a heap
enumerates ranked items.
## Cost
Time O(min(n, k) + k log min(n, k)). Space O(min(n, k)).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 100000` - `1 ≤ k ≤ 100000` - `k ≤ n * m` - `-1000000000 ≤ value ≤ 1000000000`
Input
The first line contains three integers n, m and k.
The second line contains n integers in non-decreasing order, the list A.
The third line contains m integers in non-decreasing order, the list B.
Output
Print k lines, one per pair, each being two integers separated by a single space: the value from A then the value from B, ordered by increasing sum then increasing first value then increasing second value.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.