Editorialist: Raj Shah
DIFFICULTY: Easy  Medium
PREREQUISITES: Binary Search
Problem Statement: ZIO 2013 Problem 3
PROBLEM:
Each doll has a suggested price, and no two types of dolls have the same price. You have to fix an actual selling price for each doll so that dolls of different types are as different in price as possible. 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+ K}.The selling price must always be nonnegative.
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. You can check that this is the largest separation that you can achieve given the constraint.
QUICK EXPLANATION:

Sort the numbers in ascending order. The minimum difference’s maximum value lies between the current minimum difference and current minimum difference + 2K.

Use binary search. Decide a value X exactly between the minimum difference (call it left) and minimum difference + 2K (call it right). Try to make every consecutive difference >= X.

Let A1, A2 … AN is the sorted array and B1, B2…… BN is the final array with a minimum difference >= X. We try to construct B1, B2 … BN as follows:
B1 = max(0, A1K) B2 = max(A2K, B1+X) B3 = max(A3K, B2+X) … and so on.

If BiAi > K for any i, it is not possible.

If it is not possible, do a binary search from left to X  1. If it is possible, do a binary search from X+1 to right.

Stop the binary search when left > right.

The final answer is the last successful binary search, i.e., where B1, B2… BN can be successfully constructed.
SOLUTIONS:
Task 1:

Sorted Sequence :
 3 39 72 117 144 152 214 238 256 280
 Minimum Difference (i.e. MD) = 8
 Maximum possible MD = MD + 2*K = 8+26 = 34

Binary Search Parameters :
 Left = 8
 Right = 34
 Mid = (Left + Right)/2 = 21

Binary Search iterations :
Left  Right  Mid  Array  Possible for this mid 

8  34  21  0 26 59 104 131 152 201 225 246 267  YES 
22  34  28  0 28 59 104 132 160 201 229 257 285  YES 
29  34  31  0 31 62 104 135 166 201 232 263 294  NO 
29  30  29  0 29 59 104 133 162 201 230 259 288  YES 
30  30  30  0 30 60 104 134 164 201 231 261 291  YES 
Final Answer = 30
Task 2:

Sorted Sequence :
 10 19 24 32 33 45 48 57 61 74 81 99 101
 Minimum Difference (i.e. MD) = 1
 Maximum possible MD = MD + 2*K = 1+20 = 21

Binary Search Parameters :
 Left = 1
 Right = 21
 Mid = (Left + Right)/2 = 11

Binary Search iterations :
Left  Right  Mid  Array  Possible for this mid 

1  21  11  0 11 22 33 44 55 66 77 88 99 110 121 132  NO 
1  10  5  0 9 14 22 27 35 40 47 52 64 71 89 94  YES 
6  10  8  0 9 17 25 33 41 49 57 65 73 81 89 97  YES 
9  10  9  0 9 18 27 36 45 54 63 72 81 90 99 108  NO 
Final Answer = 8
Task 3:

Sorted Sequence :
 10 19 39 54 67 83 99 110 124 139 154 170
 Minimum Difference (i.e. MD) = 9
 Maximum possible MD = MD + 2*K = 9+40 = 49

Binary Search Parameters :
 Left = 9
 Right = 49
 Mid = (Left + Right)/2 = 29

Binary Search iterations :
Left  Right  Mid  Array  Possible for this mid 

9  49  29  0 29 58 87 116 145 174 203 232 261 290 319  NO 
9  28  18  0 18 36 54 72 90 108 126 144 162 180 198  NO 
9  17  13  0 13 26 39 52 65 79 92 105 119 134 150  YES 
14  17  15  0 15 30 45 60 75 90 105 120 135 150 165  YES 
16  17  16  0 16 32 48 64 80 96 112 128 144 160 176  YES 
17  17  17  0 17 34 51 68 85 102 119 136 153 170 187  YES 
Final Answer = 17