Minimum Dot Product
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3:Greedy Algorithms, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
The dot product of two sequences a(1) , a(2) , . . . , a(n) and b(1) , b(2) , . . . , b(n) of the same length is equal to a(1) b(1) + a(2) b(2) + · · · + a(n) b(n)
Problem Description
Task: The goal is, given two sequences a(1) , a(2) , . . . , a(n) and b(1) , b(2) , . . . , b(n) , find a permutation π of the second sequence such that the dot product of a(1) , a(2) , . . . , a(n) and b(π 1) , b(π 2) , . . . , b(π n) is minimum.
Input Format: The first line contains an integer n, the second one contains a sequence of integers a(1) , a(2) , . . . , a(n) , the third one contains a sequence of integers b(1) , b(2) , . . . , b(n) .
Constraints: 1 ≤ n ≤ 10^3 ; −10^5 ≤ a(i) , b(i) ≤ 10^5 for all 1 ≤ i ≤ n.
Output Format: Output the minimum possible dot product.
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb
Sample 1
Input:
1
23
39
Output:
897
Explanation:
In this case, 897 is just the only possible dot product.
Sample 2
Input:
3
1 3 -5
-2 4 1
Output:
-25
Explanation:
−25 = 1 · 1 + 3 · (−2) + (−5) · 4.
What To Do
The first thing to note is that the problem can be restated as follows: partition two input sequences a = (a(1) , a(2) , . . . , a(n)) and b = (b(1) , b(2) , . . . , b(n) ) into n pairs of the form (a(i) , b(j) ) such that the sum of their products is minimum.
We claim that it is safe to multiply a maximum element of a by a minimum element of b. We illustrate this by a toy example. Assume that n = 4 and that a(2) = max{a(1) , a(2) , a(3) , a(4) } and b(1) = min{b(1) , b(2) , b(3) , b(4) }.
Consider a candidate solution:
a(1) b(3) + a(2) b(4) + a(3) b(1) + a(4) b(2)
Here, a(2) is multiplied by b(4) and b(1) is multiplied by a(3) . Let’s show that if we “swap” these two pairs, then the total value can only decrease. Indeed, the difference between dot products of these two solutions is equal
to (a(1) b(3) + a(2) b(4) + a(3) b(1) + a(4) b(2) ) − (a(1) b(3) + a(2) b(1) + a(3) b(4) + a(4) b(2) ) = a(2) b(4) + a(3) b(1) − a(2) b(1) − a(3) b(4) = (a(2) − a(3) )(b(4) − b(1) ) .
It is non-negative, since a(2) ≥ a(3) and b(4) ≥ b(1)
My Solution:
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
