Programming Praxis

Today’s exercise comes to us from the practice round of Google Code Jam 2008.

You are given two vectors v₁=(x₁,x₂,…,x_n) and v₂=(y₁,y₂,…,y_n). The scalar product of these vectors is a single number, calculated as x₁y₁+x₂y₂+…+x_ny_n.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Google gives two examples: the minimum scalar product of the two vectors (1 3 -5) and (-2 4 1) is -25, and the minimum scalar product of the two vectors (1 2 3 4 5) and (1 0 1 0 1) is 6.

Your task is to write a program that finds the minimum scalar product of two vectors. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2