Results 1 to 3 of 3

Math Help - please solve it.

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    1

    Post please solve it.

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by turfyjackson View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    I think a part of the proof will be like this

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

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

    a_i > a_j
     a_i < a_j
    a_i = a_j

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

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

    Consider the products

    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
    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, n,m > 0, the top product is smaller. In this case keep the a's and 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 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. need to solve summation equation to solve sum(x2)
    Posted in the Statistics Forum
    Replies: 2
    Last Post: July 16th 2010, 10:29 PM
  2. Replies: 1
    Last Post: June 9th 2009, 10:37 PM
  3. how do I solve this?
    Posted in the Calculus Forum
    Replies: 5
    Last Post: January 22nd 2009, 06:21 PM
  4. How could i solve?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 2nd 2009, 02:18 PM
  5. Solve for x
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: January 1st 2009, 12:33 PM

Search Tags


/mathhelpforum @mathhelpforum