You are given 2 arrays A, B sorted in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m*n. You need to fine the kth largest sum(a+b) possible where a \in A, and b \in B.
Hint: i like this problem, a possible solution is by induction and the complexity is O(n+m).
This problem is intriguing, and very related to open problems in computational geometry (as far as I know).
ReplyDeleteI found something I think is optimal but can't prove it yet (not based on induction and not elegant).
So... didn't find the solution yet.
Keep up posting these interesting games!
Maurizio (from Cagliari)