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_{1}=(x_{1},x_{2},...,x_{n}) and v_{2}=(y_{1},y_{2},...,y_{n}). The scalar product of these vectors is a single number, calculated as x_{1}y_{1}+x_{2}y_{2}+...+x_{n}y_{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).

## Question

## 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.

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

## Join the conversation

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