TopCoder problem "RoyalTreasurer" used in SRM 433 (Division II Level One)



Problem Statement

    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 smallest possible value for S.
 

Definition

    
Class:RoyalTreasurer
Method:minimalArrangement
Parameters:int[], int[]
Returns:int
Method signature:int minimalArrangement(int[] A, int[] B)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{1,1,3}
{10,30,20}
Returns: 80
If you move the number 3 to the beginning of A, you get the minimal possible sum.
1)
    
{1,1,1,6,0}
{2,7,8,3,1}
Returns: 18
The best option would be to rearrange the numbers in A this way: {1,1,0,1,6}.
2)
    
{5,15,100,31,39,0,0,3,26}
{11,12,13,2,3,4,5,9,1}
Returns: 528

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10007

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13695&pm=10007

Writer:

gojira_tc

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simple Search, Iteration, Sorting