simp1eton's blog

Programming Problem
By simp1eton, 15 years ago, In English
Hi all,

I was trying to do this question, but got stuck, so I wonder if you guys can give me some help. Thanks :)

https://www.spoj.pl/problems/SHOOTING/

My idea was to split the numbers up into two groups, positive and negative. Then I sort the negative numbers and pair them up. The two biggest (in terms of absolute value) will be paired, the 3rd and 4th biggest will be paired, and so on. I want to do this because I want to maximise my value, so I want to remove all my negative numbers while at the same time increasing the values of the numbers.

After I changed all numbers to positive, then I think I can use a greedy solution. I sort all the numbers in descending order and multiply the first X elements together such that there are M-1 or more elements left. The remaining elements will be distributed among the remaining targets while the first X elements are multiplied together to get the huge score.

However, I got into many difficulties trying to implement it, because pairing does not always works (there might be odd number of negative numbers), and there are weird cases and 1s and 0s (multiplying the first X elements by 1 does not increase the value. Also, I might want to pair a negative number with 0 so that it will not bring down my score).

Can someone help me? Thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone please help me? :( Any ideas?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Try to the following algorithm (I haven't implemented it yet):

    1) Let us have two lists on numbers: (a[0], a[1], ..., a[n-1]) and (b[0], b[1], ..., b[m-1]). Initially the first list contains the given numbers sorted in non-increasing order, the second one is empty.

    2) While two last numbers in the first list are negative or zeros, do the following step.

    3) Take two last numbers from a and put their product to the end of b. Note that numbers in b will be in non-increasing order too. 

    4) Each time you do that try to update the answer by the sum of M-1 smallest numbers from two lists + the product of the others. Use binary search to find the prefixes (a[0], ..., a[i-1]), (b[0], ..., b[j-1]) of the largest numbers in two sorted lists, that should be multiplied.

    5) You have to use BigIntegers to implement ariphmetic operations. But they are necessary only for multiplication of some prefixes. So you can calculate partial products p[i] = a[0] * a[1] * ... * a[i-1] (and the same way for b) and add a new product with a new element of the list. 
    → Reply