Editorial for A Good Deal

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Hints

Hint 1
Show Hint The team can only ever buy from at most \lfloor\frac{n-1}{2}\rfloor stalls. Why?
Hint 2
Answer to Previous Hint 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.
Show Hint 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"?
Hint 3
Answer to Previous Hint 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).
Show Hint 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.

Solution

View Solution 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.

Comments

There are no comments at the moment.