Problem Statement

A bookstore offers a promotion where, for every three books purchased, the cheapest book in the group is free. Customers can group books strategically to minimize the total cost. The task is to calculate the minimum price a customer has to pay given the prices of the books. Each group can have between 1 and 3 books.

Bounded conditions

The first line of input contains the integer N (1<N<100 000), the number of books the customer bought. Each of the following N lines contains a single integer C_i (1<C_i<100 000), the price of each book.

My question

My idea is to sort the price in decreasing order first and then always add the first two prices in the group of 3 to my sum price. I think this idea is somewhat correct, but the algorithm I use to sort an is Bubble sort, which is O(N^2). Seems that this will cause Time Limit Exceed.

I am not sure whether O(N^2) sorting algorithm is suitable or not in this question. Can someoen help me. My code is written in C. Assume that the not-standard input/output functions work fine.

void swap(long a[], long src, long tar)
{
  long temp = a[src];
  a[src] = a[tar];
  a[tar] = temp;
}

void bubble_pass(size_t last, long a[]) {
  for (size_t i = 0; i < last; i += 1) {
    if (a[i] < a[i+1]) {
      swap(a, i, i+1);
    }
  }
}

void bubble_sort(size_t n, long a[n]) {
  for (size_t last = n - 1; last > 0; last -= 1) {
    bubble_pass(last, a);
  }
}

long calc_min_price(size_t n, long a[n])
{
  size_t cur = 0;
  long price = 0;
  for (size_t i = 0; i < n; i += 1)
  {
    if (i % 3 != 2)
    {
      price += a[i];
    }
  }
  return price;
}    

int main()
{
  size_t n = cs1010_read_size_t();
  long *price = cs1010_read_long_array(n);
  if (price == NULL)
  {
    return 1;
  }
  bubble_sort(n, price);
  long min_price = calc_min_price(n, price);
  cs1010_println_long(min_price);
  free(price);
}

I tried the O(N^2) sorting algorithm, but got TLE. Don't know if the problem lies in the efficiency of the sorting algorithm or somewhere else.

Solution

I agree the O(N^2) algorithm is main reason of TLE. You get at most 100000 numbers in range 0..100000, it could be solved using any O(N log N) algorithm such as Heapsort or Mergesort, or even using linear-time algorithm such as Countingsort or Radixsort.

I am certain that test data in informatics contests are designed the way that forces solvers to use the algorithm with best possible asymptotic complexity.