Once upon a time, there was a kingdom where math was always a big problem. When the post of the royal treasurer needed to be filled, applicants were presented with the following problem:

"We have two arrays of integers, A and B. A and B each contain exactly N elements. Let's define a function S over A and B:

S = A0*B0 + ...... + AN-1*BN-1
Rearrange the numbers in A in such a way that the value of S is as small as possible. You are not allowed to rearrange the numbers in B.?

The problem writers need a program to check the correctness of the applicants' answers. Given int[]s A and B, return the rearranged array A for smallest sum.

Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each element of A will be between 0 and 100, inclusive.
- Each element of B will be between 0 and 100, inclusive.

2. Originally Posted by turfyjackson
Once upon a time, there was a kingdom where math was always a big problem. When the post of the royal treasurer needed to be filled, applicants were presented with the following problem:

"We have two arrays of integers, A and B. A and B each contain exactly N elements. Let's define a function S over A and B:

S = A0*B0 + ...... + AN-1*BN-1
Rearrange the numbers in A in such a way that the value of S is as small as possible. You are not allowed to rearrange the numbers in B.?

The problem writers need a program to check the correctness of the applicants' answers. Given int[]s A and B, return the rearranged array A for smallest sum.

Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each element of A will be between 0 and 100, inclusive.
- Each element of B will be between 0 and 100, inclusive.
Is this from a competition/competition website? If so I'd like to know which one. I just started SPOJ.

Note that the restriction that we can't rearrange the elements of B doesn't really do anything. All we really care about is bijective map f: A -> B such that the product a * f(a) appears in our sum.

My guess is that the solution is: rearrange B ascending making B', rearrange A descending making A', associate A'_i with B'_i, then rearrange A' such that it corresponds with B instead of B'. Of course B descending and A ascending produces the same effect.

3. I think a part of the proof will be like this

For $\displaystyle i < j$:
Let $\displaystyle a_i$ and $\displaystyle a_j$ be elements of set $\displaystyle A$.
Let $\displaystyle b_i$ and $\displaystyle b_j$ be the associated elements of set $\displaystyle B$.

So as undefined assumed, let the elements of $\displaystyle B$ be arrange in ascending order . Then $\displaystyle b_i < b_j$ and $\displaystyle b_j = b_i+m$ For the $\displaystyle a$'s we have three options:

$\displaystyle a_i > a_j$
$\displaystyle a_i < a_j$
$\displaystyle a_i = a_j$

The third case is trivial since then it does not matter how $\displaystyle a_i$ and $\displaystyle a_j$ are positioned with respect to each other.

So in the first case $\displaystyle a_i = a_j + n$ for some positive integer $\displaystyle n$.

Consider the products

$\displaystyle a_i b_i + a_j b_j = (a_j+n)(b_j-m) + a_j b_j = 2a_j b_j +n b_j -m a_j - m n$
$\displaystyle a_i b_j +a_j b_i = (a_j+n)b_j +a_j(b_j-m) = 2a_j b_j + n b_j - m a_j$

Clearly since, $\displaystyle n,m > 0$, the top product is smaller. In this case keep the $\displaystyle a$'s and $\displaystyle b$'s in their relative positions.

In the other case we would get the opposite.

Since these integers were arbitrary, this procedure will yield the same result every time : it will make the set $\displaystyle A$ more and more descending, i.e. it'll sort it in descending order. This should work with sets of arbitrary finite size and arbitrary elements from the real numbers.