TopCoder problem "StockSales" used in SRM 202 (Division I Level Three)



Problem Statement

     For tax purposes I need to trade some stock, generating as small a positive amount of revenue as possible. I can buy or sell any integer quantity of each stock (I can "sell short", which means that I can sell more of a stock than I have).

Create a class StockSales that contains a method getAmounts that is given a int[] values, the prices of the stocks I am willing to trade, and that returns the amounts of each stock that I should buy or sell. In the return, positive amounts represent amounts to sell, while negatives represent amounts to buy.

To make the answer unique, choose the amounts in order. Choose each amount to have the smallest possible absolute value (considering all the earlier choices). If both the negative and positive amount is available, choose the positive amount.

 

Definition

    
Class:StockSales
Method:getAmounts
Parameters:int[]
Returns:int[]
Method signature:int[] getAmounts(int[] values)
(be sure your method is public)
    
 

Constraints

-values contains between 1 and 50 elements inclusive.
-Each element in values is between 1 and 1,000,000 inclusive.
 

Examples

0)
    
{6,12,17}
Returns: { 0,  -7,  5 }
The smallest positive revenue is 1. We can trade 0 of the first stock and still achieve this. Choose -7 for the second stock since -7 is the smallest (absolute value) coefficient of 12 that allows us to get revenue of 1: 0*6 + -7*12 + 5*17 = 1.
1)
    
{10,4}
Returns: { 1,  -2 }
The smallest positive revenue is 2. Both {1,-2} and {-1,3} achieve this. {1,-2} is chosen by the tie breaking rule that says to choose the positive amount in preference to the same negative amount. 1*10 + -2*4 = 2, the minimum revenue possible.
2)
    
{79}
Returns: { 1 }
3)
    
{60,60,60,60,60,60,60}
Returns: { 0,  0,  0,  0,  0,  0,  1 }
4)
    
{17,19,37,11,22,110}
Returns: { 0,  0,  3,  0,  0,  -1 }
5)
    
{1000000,499999}
Returns: { -249999,  499999 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5848&pm=762

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Advanced Math