TopCoder Statistics - Problem Statement

Problem Statement

Market differentiation in its simplest form is a system of charging different prices to different customers for the same product. To maximize the total sales revenue, we would like to charge each customer individually, charging the highest price that that customer would be willing to pay. Usually we have to divide the customers into a few groups, and charge the same price to everyone in a group (e.g. business class, economy class, etc.).

We have a list of all the potential customers for our product and the most that each customer is willing to pay. We have decided to differentiate them into four or fewer (non-overlapping) groups. Everyone within each group will be offered the same price. Our goal is to choose the groups and prices optimally to maximize our total sales revenue.

Create a class Pricing that contains a method maxSales that takes a int[] price containing the highest price that each potential customer is willing to pay, and returns the maximum sales revenue we can generate by differentiating our customers into four or fewer groups.

Definition

Class:: Pricing
Method:: maxSales
Parameters:: int[]
Returns:: int
Method signature:: int maxSales(int[] price)
(be sure your method is public)

Constraints

price must contain between 1 and 50 elements inclusive
each element of price must be between 0 and 1000 inclusive

Examples

{9,1,5,5,5,5,4,8,80}

Returns: 120

Charge 80 to the one customer willing to pay 80. Charge 8 to the 2 customers willing to pay 8 or 9. Charge 5 to the 4 customers willing to pay 5. Charge 4 to the one customer willing to pay 4. Total sales revenue = 1*80 + 2*8 + 4*5 + 1*4. (We can put the customer who is willing to pay 1 into any of these groups since he will not buy anything at these prices.)
{17,50,2}

Returns: 69

We use just three groups, each containing one customer. We charge each customer the most she is willing to pay. Total sales revenue = 1*17 + 1*50 + 1*2
{3,4,5,0,0,0,0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,1,90,6}

Returns: 267
{9,1,9,1,9,1,9,1,9,1,9,1,9,1,9,1}

Returns: 80
{1000}

Returns: 1000
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}

Returns: 1040
{1,1,1,1,1,1,1,1,1,1,9,19,1,1,1,1,1,1,1,1,1,1,46,47,48,1000,1,1,1,1,1,1,1,1,1,1}

Returns: 1188
{1,1,1,1,1,1,1,1,1,1,6,9,18,1,1,1,1,1,1,1,1,1,1,46,47,48,1000,1,1,1,1,1,1,1,1,1,1}

Returns: 1188
{1,1,1,1,1,1,1,1,1,1,7,9,18,1,1,1,1,1,1,1,1,1,1,46,47,48,1000,1,1,1,1,1,1,1,1,1,1}

Returns: 1189
{130,110,90,17,6,5,4,3}

Returns: 347
{130,110,90,13,6,5,4,3,0}

Returns: 346

Charge each of the 4 customers willing to pay between 4 and 13 a price of 4, thereby getting a total of 16 from them. Then charge the most we can to each of the three customers who are willing to pay a lot. 4*4 + 90 + 110 + 130 = 346
{130,110,90,4,6,5,4,3}

Returns: 346
{18,0,20,0,1,0}

Returns: 39
{0,0}

Returns: 0
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1000}

Returns: 1000
{19,99,34,78,67,75,77,36,23,3,3,9,66,34,34,34,34,34,34,66}

Returns: 808
{ 111, 22 }

Returns: 133
{ 130, 110, 90, 13, 6, 5, 4, 3, 0, 130, 110, 90, 15, 15, 15, 13, 6, 5, 4, 3, 0, 130, 110, 90, 13, 6, 5, 4, 3, 0, 130, 110, 90, 13, 6, 5, 4, 3, 0 }

Returns: 1411
{ 130, 110, 90, 13, 6, 5, 4, 3, 0 }

Returns: 346
{ 1, 1, 1 }

Returns: 3
{ 1, 1, 3, 3, 3, 4, 4, 5, 6, 1000, 1, 1, 3, 3, 3, 4, 4, 5, 6, 1000, 1, 1, 3, 3, 3, 4, 4, 5, 6, 1000, 1, 1, 3, 3, 3, 4, 4, 5, 6, 1000, 1, 1, 3, 3, 3, 4, 4, 5, 6, 1000 }

Returns: 5135

Statistics

Problem Statement for "Pricing"

Problem Statement

Definition

Constraints

Examples