Editorial for A Good Deal

The team can only ever buy from at most $\lfloor\frac{n-1}{2}\rfloor$ stalls. Why?

By definition, every stall that is "a good deal" must lie strictly between two stalls that are not "a good deal" (and the first and last stalls can never be one), so no two good deals can be adjacent.

If we know that we can buy from at most $\lfloor\frac{n-1}{2}\rfloor$ stalls, which $\lfloor\frac{n-1}{2}\rfloor$ stalls are the easiest to make "a good deal"?

The $\lfloor\frac{n-1}{2}\rfloor$ cheapest stalls are the best candidates. Let's place them at every second position along the street (positions $2, 4, 6, \ldots$ when counting from 1).

We've placed our candidates for "a good deal" already - so now, how should we place the remaining stalls in order to maximise the number of purchases?

This may be easier to think about in the case where all prices are distinct first.

As covered by the hints, the smallest prices should be placed at every second spot along the street. Let's place them like this, where 1 represents the smallest price, 2 the second smallest, and so on:

_ 1 _ 2 _ 3 _ 4 _ ...

Now, how should we place the rest of the stalls? Well, if all prices are distinct, it doesn't matter: all of our candidates will be "a good deal". But what if there are duplicates? Then some of our largest candidates might not be "a good deal", because a neighbour has the same price. So we should place the largest remaining prices towards the end of the street, next to the largest candidates, to give our at-risk candidates the best chance of being "a good deal".

There are other valid strategies, however. Since the only candidates that can fail are those equal to the largest candidate price, any placement that puts the non-candidate copies of that price as far left as possible is also optimal.

In either case, the configuration can be computed efficiently by sorting the prices first.