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