Problem 3 - Shopping Spree

Here, we will discuss the solution to Shopping Spree from AIO 2024.

Summary

Pair Mart sells N items where N is even, and you want to buy all of them. At Pair Mart, you can only buy items in pairs, and you pay the cost of the more expensive item. Additionally, you have K coupons, which allow you to buy two items for the cost of the cheaper item.

What is the minimum cost to buy all N items?

Note that the prices are given in ascending order, meaning that item 1 with a cost of C₁ is the cheapest item and item N with a cost of C_N is the most expensive item.

Solution

Subtask 1: K = 0 and N ≤ 1000

The crux of this subtask is deciding how to optimally pair up the items when we have no coupons.

Consider the most expensive item (item N):

• When we buy this item, we will buy it together with another item and we will pay C_N.
• Essentially, we get the second (cheaper) item for free.
• Intuitively, it feels like a good idea to pair it with the second most expensive item (item N-1).
• We can prove that this is the best possible choice:
  • Consider a solution that does not pair item N with N-1. Instead, item N is paired with item i and item N-1 is paired with item j.
  • The cost of buying these two pairs is C_N + C_N-1.
  • If we instead paired N with N-1 and i with j, this would cost C_N + max(C_i, C_j).
  • Because max(C_i, C_j) ≤ C_N-1, this second pairing is equal to or cheaper than the first pairing. Therefore, it is always best to pair the most expensive item with the second most expensive item.
  • This type of proof is called an exchange argument. Exchange arguments typically come about when you are trying to reason if a greedy algorithm will work for a problem.

Using a similar argument, it is best to pair the third most expensive item with the fourth most expensive item and continue this until all the items have been paired up. This gives us a greedy algorithm that successfully solves this subtask.

Consider an example with N = 8, K = 0, and items with prices 1, 2, 3, 4, 5, 6, 7, 8:

• Make pairs: (1, 2), (3, 4), (5, 6), (7, 8).
• This costs 2+4+6+8 = 20 dollars.
• In other words, we pay for every second item.

This algorithm has a time complexity of O(N), however, slower algorithms with a time complexity of O(N²) will also pass this subtask.

Subtask 2: K = N/2 and N ≤ 1000

The crux of this subtask is deciding how to optimally pair up the items when we have enough coupons to use on every pair.

We will use a greedy algorithm, similar to subtask 1. This time, consider the cheapest item (item 1):

• When we buy this item, we will buy it together with another item and we will pay C₁.
• Essentially, we get the second (more expensive) item for free.
• Intuitively, it feels like a good idea to pair it with the most expensive item (item N).
• We can prove that this is the best possible choice using another exchange argument:
  • Consider a solution that does not pair item 1 with N. Instead, item 1 is paired with item i and item N is paired with item j.
  • The cost of buying these two pairs (using coupons) is C₁ + C_j.
  • If we instead paired 1 with N and i with j, this would cost C₁ + min(C_i, C_j).
  • Because min(C_i, C_j) ≤ C_j, this second pairing is equal to or cheaper than the first pairing. Therefore, it is always best to pair the cheapest item with the most expensive item.

Using a similar argument, it is best to pair the second cheapest item with the second most expensive item and continue this until all the items have been paired up.

Consider an example with N = 8, K = 4, and items with prices 1, 2, 3, 4, 5, 6, 7, 8:

• Make pairs: (1, 8), (2, 7), (3, 6), (4, 5).
• This costs 1+2+3+4 = 10 dollars.
• In other words, we pay for the cheapest N/2 items, and get the more expensive items for free.

This algorithm has a time complexity of O(N), however, slower algorithms with a time complexity of O(N²) will also pass this subtask.

Full Solution

We can combine our solutions for the first two subtasks:

• We use the K coupons to pair the K cheapest items with the K most expensive items, just like in the subtask 2 solution.
• We pair the remaining N-2K items using the strategy from subtask 1.

Consider an example with N = 8, K = 2, and items with prices 1, 2, 3, 4, 5, 6, 7, 8:

• Use the 2 coupons to buy (1, 8) and (2, 7) for 1+2 = 3 dollars.
• Four items remain, with prices 3, 4, 5, 6.
• Pair these like in subtask 1, buying (3, 4) and (5, 6) for 4+6 = 10 dollars.
• The overall cost is 3+10 = 13 dollars.

This algorithm has a time complexity of O(N) which is fast enough to score 100 in this problem.

Code

Below you can see the full solution written in Python and C++. I suggest trying to code the solution yourself, look at our code after you finish or if you get stuck.

• Python 3
• C++

# Open the input and output files.
input_file = open("shopin.txt", "r")
output_file = open("shopout.txt", "w")

# Read the value of N and the string of characters from the input file.
input_line = input_file.readline().strip()
N, K = map(int, input_line.split())
input_line = input_file.readline().strip()
costs = list(map(int, input_line.split()))

answer = 0

# First, use the coupons to buy the K cheapest and most expensive items
# We just pay the cost of the cheapest K items
for i in range(K):
   answer += costs[i]

# We now buy the remaining items, paying the cost of every second item
for i in range(K+1, N-K, 2):
   answer += costs[i]

# Write the answer to the output file.
output_file.write("%d\n" % (answer))

# Finally, close the input/output files.
input_file.close()
output_file.close()

#include <cstdio>
int N, K, costs[200005];
int main(void) {
   /* Open the input and output files. */
   FILE *input_file = fopen("shopin.txt", "r");
   FILE *output_file = fopen("shopout.txt", "w");

   /* Read the value of N and the string of characters from the input file. */
   fscanf(input_file, "%d%d", &N, &K);
   for (int i = 0; i < N; i++) {
       fscanf(input_file, "%d", &costs[i]);
   }

   int answer = 0;

   // First, use the coupons to buy the K cheapest and most expensive items
   // We just pay the cost of the cheapest K items
   for (int i = 0; i < K; i++) {
       answer += costs[i];
   }

   // We now buy the remaining items, paying the cost of every second item
   for (int i = K+1; i < N-K; i += 2) {
       answer += costs[i];
   }

   /* Write the answer to the output file. */
   fprintf(output_file, "%d\n", answer);

   /* Finally, close the input/output files. */
   fclose(input_file);
   fclose(output_file);
}

Click here to go back.