ZIO13003 - Editorial

editorial
, , , , ,
1

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 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. You can check that this is the largest separation that you can achieve given the constraint.

QUICK EXPLANATION:

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

  2. 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.

  3. 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, A1-K)
        B2 = max(A2-K, B1+X)
        B3 = max(A3-K, B2+X)
        … and so on.

  4. If Bi-Ai > K for any i, it is not possible.

  5. 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.

  6. Stop the binary search when left > right.

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

SOLUTIONS:

Task 1:

  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

  2. Binary Search Parameters :

    • Left = 8
    • Right = 34
    • Mid = (Left + Right)/2 = 21

  3. 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:

  1. 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

  2. Binary Search Parameters :

    • Left = 1
    • Right = 21
    • Mid = (Left + Right)/2 = 11

  3. 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:

  1. 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

  2. Binary Search Parameters :

    • Left = 9
    • Right = 49
    • Mid = (Left + Right)/2 = 29

  3. 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

2 Likes