PROBLEM LINK:
Author: Suthirth V
Tester: Suthirth V
Editorialist: Suthirth V
DIFFICULTY:
EASY
PREREQUISITES:
None.
PROBLEM:
Yann LeCun is buying GPUs for his workstation PC. Three of his friends have shops that sell GPUs of different memory size configurations. He wishes to buy at least one card from all his friends’ shops.
To make memory management easy, it is best that LeCun buys the GPUs such that they have as similar memory sizes as possible (smallest range). Given the various memory sizes (in GB) that each of the shops has available, select the range of memory sizes that he must buy.
For example,
Shop 1: [4, 16, 24, 28]
Shop 2: [5, 12, 22, 30]
Shop 3: [20, 42, 64, 96]
The best memory range here would be [20, 24] as he can buy 24 from shop 1, 22 from shop 2, and 20 from shop 3.
Input
First line: x y where x is number of shops and y is the number of card configurations each shop has.
2nd to (x+1)th line: a b c d … (y entries)
All configuration sizes are integer values
Output
m n where m is the lower limit and n is higher limit (both inclusive)
QUICK EXPLANATION:
There are k lists of sorted integers. Make a min heap of size k containing 1 element from each list. Keep track of min and max element and calculate the range.
In min heap, minimum element is at top. Delete the minimum element and another element instead of that from the same list to which minimum element belong. Repeat the process till any one of the k list gets empty.
Keep track of minimum range.
For eg.
List 1: [4, 10, 15, 24, 26]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
Min heap of size 3. containing 1 element of each list
Heap [0, 4, 5]
Range - 6
Remove 0 and add 9
Heap [4, 9, 5]
Range - 6
Remove 4 and add 10
Heap [5, 9, 10]
Range - 6
and so on…
EXPLANATION:
After getting the input, sort the arrays. Once sorted, the above explanation can be implemented in Python as below:
mindata = np.amin(data,1)
min_range = np.amax(mindata)-np.amin(mindata)
md = np.copy(mindata)
counters = [0 for i in xrange(0,x)]
while 1:
loc = np.argmin(md)
counters[loc] = counters[loc] + 1
if counters[loc] >= n:
break;
md[loc] = data[loc][counters[loc]]
mrange = np.amax(md)-np.amin(md)
if mrange < min_range:
min_range = mrange
mindata = np.copy(md)
Your required outputs will be in min and max of mindata
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.