Sort, Priority Queue, Binary Search
Given two arrays A[1..K], B[1..K], deal with Q queries of finding the n-th smallest pair sum in all K^2 pair sums (A[i] + B[j]).
A brute force enumeration can give us an O(K^2 logK) - O(1) algorithm: just simply store all possible sums and use the some sorting algorithm such as quick sort. And then, for each query, return the n-th number of the stored sorted array. This brute force algortihm’s time complexity is O(K^2 + Q). Also, it needs O(K^2) space. Both time and memory are exceeded.
There are 2 ways to improve this brute force algorithm. The common key point to improve this brute force algorithm is as following: Suppose A and B are sorted ascendingly, A[i] + B[j] is smaller than or equal to any A[i] + B[k] if k > j.
For instance, we use quick sort to sort A and B in O(K logK) time. And then, 2 possible solutions are here.
The first solution is that we can find the smallest sum among at most K candidates (one for each A[i]) and remove it. After n removes, the n-th smallest sum is found. More specifically, we can maintain K pointers for each A[i]. Let’s say ptr[1..K] (equals 1 initially). First, we can use a binary heap (or other priority queues, balanced binary search trees, etc...) to find the smallest sum among A[i] + B[ptr[i]]. Second, suppose the smallest is A[p] + B[ptr[p]]. We remove it from the heap, then increase the pointer ptr[p] by 1 and insert a new element A[p] + B[ptr[p]] if it exists. Repeat this process n times, the n-th smallest sum is got. This algorithm’s time complexity is O(n log K) for each query, and thus O(K logK + Q n logK) in total.
The second solution is more tricky and useful. Consider the dual problem: given a number X, find how many pair sums are smaller than or equal to X (The answer of the original problem is that the smallest X such that there are at least n pair sums smaller than or equal to X). To solve the dual problem, based on the previous observation, there exists limit[i] such that A[i] + B[1..limit[i]] are all smaller than or equal to X while A[i] + B[limit[i] + 1 … K] are all greater than X. Furthermore, limit[i] >= limit[i + 1] since A[i] <= A[i + 1]. Using these two properties, we can simply get the rank of X in O(K) time. Through binary search, we can get the answer of original problem in O(K logAnswer), and thus O(K logK + Q K logAnswer) in total.
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
I solved this after the contest and used a very simple approach. First sort both the arrays. Since the limit on q is 10000, this can be done with the following code.
This will ensure that atleast the first 10000 sums will be stored in v. Then we just have to sort the vector v and print the answer of every query.
answered 21 Nov '13, 02:08
can anybody please explain me the first approach? not getting it :(
answered 12 Dec '13, 10:24
though editorial has been provided for this problem but still i am not able to understand it. it would be great if someone explain me the correct approach to solve this problem..........
answered 28 Dec '13, 14:40
Hmm, I tried both approach in the contest. However, only the first one get AC (http://www.codechef.com/viewsolution/2998337 ). The second solution gave me TLE (http://www.codechef.com/viewsolution/2997409 ). Is the time limit too strict for the second solution or it is just me that didn't implement the algorithm efficiently?