Jump to content
BrainDen.com - Brain Teasers
  • 0

Minimum Scalar Product


gavinksong
 Share

Question

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 v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

 

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 by gavinksong
Link to comment
Share on other sites

3 answers to this question

Recommended Posts

  • 0

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.
Link to comment
Share on other sites

  • 0

Suppose we have found an optimal permutation, v

1 = (x1, x2, ..., xn) and v2 = (y1, y2, ..., yn). Choose the index a so that no xi is larger than xa. Choose the index b so that no yi is smaller than yb. Consider switching xa with xb. We would have xbya+xayb instead of the original xaya+xbyb. The difference is xbya+xayb-xaya-xbyb = xb(ya-yb)+xa(yb-ya) = xb(ya-yb)-xa(ya-yb) = (xb-xa)(ya-yb), 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 xi in ascending order, the yi will be in descending order.

Link to comment
Share on other sites

  • 0

Suppose we have found an optimal permutation, v

1 = (x1, x2, ..., xn) and v2 = (y1, y2, ..., yn). Choose the index a so that no xi is larger than xa. Choose the index b so that no yi is smaller than yb. Consider switching xa with xb. We would have xbya+xayb instead of the original xaya+xbyb. The difference is xbya+xayb-xaya-xbyb = xb(ya-yb)+xa(yb-ya) = xb(ya-yb)-xa(ya-yb) = (xb-xa)(ya-yb), 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 xi in ascending order, the yi 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

bya+xayb)-(xaya+xbyb)= (xb-xa)(ya-yb) < 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 by gavinksong
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...