Topcoder SRM 149 D2 Q3: Pricing

Question

This following problem is taken from Topcoder's SRM 149. I have no idea how to do this question even after looking at the solution. I've been trying this problem for an hour and half, and starting at the solution for another hour, but I just can't fathom what the heck its doing....

If someone can give me some tip on how this solution works, I will really appreciate it.

Question:http://topcoder.bgcoder.com/print.php?id=250

Solution:http://apps.topcoder.com/forums//?module=Thread&threadID=575120&start=0

TopCoder problem "Pricing" used in SRM 149 (Division II Level Three)

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

0)

{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.) 1)

{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 2)

{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

SOLUTION:
Arrays.sort(price);
   int ret = 0;
   for(int i = 0; i<price.length; i++){
      for(int j = i; j<price.length; j++){
         for(int k = j; k<price.length; k++){
            for(int m = k; m<price.length; m++){
               int rev = 0;
               for(int n = 0; n<price.length; n++){
                  if(price[n]>=price[m]){
                     rev+=price[m];
                  }else if(price[n]>=price[k]){
                     rev+=price[k];
                  }else if(price[n]>=price[j]){
                     rev+=price[j];
                  }else if(price[n]>=price[i]){
                     rev+=price[i];
                  }
               }
               ret=Math.max(ret,rev);
            }
         }
      }
   }
   return ret;

Answer 1

I thought I'd share my solution, despite the fact it's a painful and obfuscated brute force (as Beta suggested). I make use of itertools to get pricing combinations instead of nesting loops - this felt more logical as I explicitly specified possible group sizes (see range(0, MAX_GROUPS)).

Note I have only tested this on basic test cases in Topcoder Arena, and not the all test cases from SRM 149. The final trimming code is hacky.

import itertools

MAX_GROUPS = 4

# price ~ (int, int, ...)
def maxSales(price):

    # Returns from given sales combination
    def _ret(grp):
        return sum([len(g) * g[0] for g in grp])

    if len(price) <= MAX_GROUPS:
        return sum(price)

    # Sort price listing ascending, and then split into 1-4 groups
    price = sorted(price)
    grp_max_ret, grp = -1, []
    for i in range(0, MAX_GROUPS):
        for splits in itertools.combinations(range(1, len(price)), i):
            result = []
            prev = None
            for split in itertools.chain(splits, [None]):
                result.append(list(price[prev:split]))
                prev = split
            result_ret = _ret(result)
            # Keep track of top performer
            if result_ret > grp_max_ret:
                grp_max_ret, grp = result_ret, result

    # Trim first group, which effectively gives freebies
    pre_trim_grp = grp[:]
    for _ in range(len(pre_trim_grp[0])-1):
        trim_grp = pre_trim_grp[:]
        trim_grp[0].pop(0)
        grp_max_ret = max(grp_max_ret, _ret(trim_grp))

    return grp_max_ret

Answer 2

It's brute force.

Each set of {i,j,k,m} is a choice of prices for the four groups. The n loop counts up the revenue for that choice, and ret tracks the maximum revenue.

(This solution is O(N⁵). I think O(N) is possible.)