After so many tries, I got stuck on this question.
Your shop sells several different types of dolls. Each doll has a suggested price, and no two types of doll have the same price. You would like to fix an actual selling price for each doll so that dolls of different types are as different in price as possible. Due to some government regulations, you can only modify the suggested price within a fixed band of ±K—in other words, if the suggested price is p, you can pick any selling price in the range { p−K,p−K+1,..,p+K−1,p+Kp−K,p−K+1,..,p+K−1,p+K }. Of course, the selling price must always be non-negative.
For instance, suppose there are four types of dolls with suggested prices 130, 210, 70 and 90 and you are allowed to modify prices within a band of 20. Then, you can adjust the prices to 150, 210, 50 and 100, respectively, so that the minimum difference in price between any two types of dolls is 50. (For the second doll, you could have picked any price between 200 and 230.) You can check that this is the largest separation that you can achieve given the constraint.
In each of the cases below, you are given a sequence of prices and the value of K. You have to determine the maximum separation that you can achieve between all pairs in the sequence if you are allowed to modify each price by upto ±K.
(a) K = 13. Sequence: 144, 152, 214, 72, 256, 3, 39, 117, 238, 280.
(b) K = 10. Sequence: 10, 48, 57, 32, 61, 74, 33, 45, 99, 81, 19, 24, 101.