Connection Status:
Competition Arena > StockSales

StockSales

SRM 202 · 2004-07-07 · by dgoodman

SRM 202 · 2004-07-07 · by dgoodman · Advanced Math
Class Name: StockSales
Return Type: int[]
Method Name: getAmounts
Arg Types: (vector<int>)
Problem Statement

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.

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)
{84,23,46}
Returns: { -3,  1,  5 }

Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StockSales with a public method vector<int> getAmounts(vector<int> values) · 24 test cases · 2 s / 256 MB per case

Submitting as anonymous