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

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

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 _{1}* is the cheapest item and item

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*max_{N}+*(C*._{i}, C_{j}) - Because max
*(C*, 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._{i}, C_{j}) ≤ C_{N-1} - 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.

- Consider a solution that does not pair item

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 ^{2})* will also pass this subtask.

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*._{1} - 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*._{1}+ C_{j} - If we instead paired 1 with
*N*and*i*with*j*, this would cost*C*min_{1}+*(C*._{i}, C_{j}) - Because min
*(C*, 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._{i}, C_{j}) ≤ C_{j}

- Consider a solution that does not pair item 1 with

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 ^{2})* will also pass this subtask.

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.

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.

```
# 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);
}
```