Problem Introduction
The dot product of two sequences \(a_1,a_2,\cdots,a_n\) and \(b_1,b_2,\cdots,b_n\) of the same length is equal to \(\sum\limits_{i=1}^na_ib_i=a_1b_1+a_2b_2+\cdots+a_nb_n\)
Problem Description
Task.The goal is,given two sequences $a_1,a_2,\cdots,a_n $ and \(b_1,b_2,\cdots,b_n\) find a permutation \(\pi\) of the second sequence such that the dot product of \(a_1,a_2,\cdots,a_n\) and \(b_{{\large{\pi}}_1}, b_{{\large{\pi}}_2}, \cdots, b_{{\large{\pi}}_n}\) is minumum.
Input Format.
Constraints.$1 \leq n \leq 10^3; -10^5 \leq a_i, b_i \leq 10^5; $ for all \(1 \leq i \leq n\).
Output Format.Out put the minimum possible product.
Sample 1.
Input:
1
23
39
Output:
897
Sample 2.
Input:
3
1 3 -5
-2 4 1
Output:
-25
Solution
#Uses python3
import sys
def min_dot_product(a, b):
res = 0
a = sorted(a)
b = sorted(b, reverse=True)
for idx in range(len(a)):
res += a[idx] * b[idx]
return res
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
n = data[0]
a = data[1:(n + 1)]
b = data[(n + 1):]
print(min_dot_product(a, b))