Minimum Scalar Product

[gavinksong]

Here's a fairly easy one for you thinkers.

 

It's very possible that the coders among you have seen the coding version of this challenge before. It is from the Google CodeJam Round 1A 2008 and is listed as a practice problem on their homepage.

 

The Problem

 

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.

 

Each round there is a small input file and a large input file. The method of testing every possible permutation will work on the small input file, but it is impractical to use the same method for the large input. Solving the large input requires a key mathematical insight (or perhaps just a good hunch).

 

What is this insight? Prove it.

Edited March 7, 2015 by gavinksong

[bonanova]

You'd want to avoid multiplying pairs of large numbers. if the x values were say 1 and 100 and the y values were 2 and 101 the two inner products are 10,002 and 301. Clearly multiplying 100x101 is a bad idea. So my first guess would be to put x in increasing order and y in decreasing order.

[Rainman]

Suppose we have found an optimal permutation, v

₁ = (x₁, x₂, ..., x_n) and v₂ = (y₁, y₂, ..., y_n). Choose the index a so that no x_i is larger than x_a. Choose the index b so that no y_i is smaller than y_b. Consider switching x_a with x_b. We would have x_by_a+x_ay_b instead of the original x_ay_a+x_by_b. The difference is x_by_a+x_ay_b-x_ay_a-x_by_b = x_b(y_a-y_b)+x_a(y_b-y_a) = x_b(y_a-y_b)-x_a(y_a-y_b) = (x_b-x_a)(y_a-y_b), which is guaranteed to be non-negative by our choice of indices. So either a=b from the start or we have a new permutation which is also optimal, and we know that the largest x is "paired" with the smallest y. Now put the largest x and the smallest y aside, and consider the rest of the vector. This vector is also optimally permuted, and follows the same rules. So we can guarantee that this vector also has the largest x paired with the smallest y. Hence the second largest x and the second smallest y of the original vector are paired. And so on. So if we arrange the x_i in ascending order, the y_i will be in descending order.

[gavinksong]

Suppose we have found an optimal permutation, v

₁ = (x₁, x₂, ..., x_n) and v₂ = (y₁, y₂, ..., y_n). Choose the index a so that no x_i is larger than x_a. Choose the index b so that no y_i is smaller than y_b. Consider switching x_a with x_b. We would have x_by_a+x_ay_b instead of the original x_ay_a+x_by_b. The difference is x_by_a+x_ay_b-x_ay_a-x_by_b = x_b(y_a-y_b)+x_a(y_b-y_a) = x_b(y_a-y_b)-x_a(y_a-y_b) = (x_b-x_a)(y_a-y_b), which is guaranteed to be non-negative by our choice of indices. So either a=b from the start or we have a new permutation which is also optimal, and we know that the largest x is "paired" with the smallest y. Now put the largest x and the smallest y aside, and consider the rest of the vector. This vector is also optimally permuted, and follows the same rules. So we can guarantee that this vector also has the largest x paired with the smallest y. Hence the second largest x and the second smallest y of the original vector are paired. And so on. So if we arrange the x_i in ascending order, the y_i will be in descending order.

 

The explanation is a bit longer and awkward than it needs to be, but it is correct.

As sharp as ever, Rainman.

 

If you consider swapping any two elements, it decreases the scalar product iff (x

_by_a+x_ay_b)-(x_ay_a+x_by_b)= (x_b-x_a)(y_a-y_b) < 0. In other words, if one vector has monotonically increasing elements and the other has monotonically decreasing elements, swapping any two elements does not decrease the scalar product. Thus, it is optimal.

Edited March 8, 2015 by gavinksong