Minimum Dot Product — aadimator

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:

Minimum Dot Product — aadimator

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.