Last Updated: 10 Apr, 2021
Maximize the average working ratio
Moderate
Asked in companies
You are given an array ‘BULBS’ of size ‘N’. There are ‘N’ shops and for each shop ‘i’, ‘BULBS[i] = [WORKS, TOTAL]’, where ‘WORKS’ is the number of working bulbs, and ‘TOTAL’ is the total number of bulbs in the shop ‘i’.
You are also given an integer ‘EXTRA’. These are the number of extra bulbs that are guaranteed to be working. You want to assign the extra bulbs to the shops in a way that maximizes the average working ratio across all the shops.
The working ratio of a shop is defined as ‘WORKS/TOTAL’. The average working ratio is the sum of the working ratios of all the shops divides by ‘N’. Your task is to find the maximum possible average working ratio.
Example:
‘N = 3’, ‘EXTRA = 2’
‘BULBS = [ [2, 3], [3, 5], [2, 2] ]
To get the maximum average working ratio, assign one bulb to shop ‘0’ and one bulb to shop ‘1’. So, the average working ratio will be equal to ‘(3/4 + 4/6 + 2/2) / 3 = 0.80556’.
Note:
1. The answers within ‘10^(-5)’ of the actual answer will be accepted.
2. You do not need to print anything, it has already been taken care of. Just implement the function.
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.
Each test case’s first line contains two integers, ‘N’ and ‘EXTRA’, denoting the number of shops and extra bulbs. Then, ‘n’ lines follow.
Each line contains two integers, ‘WORKS’ and ‘TOTAL’, denoting an element in the array ‘BULBS’.
Output format:
For every test case, return the maximum possible average working ratio. The printed output will be up to ‘5’ decimal places.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N, EXTRA <= 10^3
1 <= WORKS <= TOTAL <= 10^5
Each element of ‘BULBS’ contains exactly two integers.
Where ‘T’ is the number of test cases, ‘N’ is the number of shops, ‘EXTRA’ is the number of extra bulbs, and ‘[WORKS, TOTAL]’ represents an element in the ‘BULBS’ array.
Time limit: 1 second
Approaches
Let ‘PROFIT’ be the difference between the new and previous working ratio. The new working ratio is obtained by adding some extra bulbs to the previous. Observe that the value of ‘PROFIT’ keeps decreasing when you add extra bulbs.
At any instance, the shop which gives the maximum ‘PROFIT’ by taking one extra bulb should be assigned that extra bulb so as to get the maximum sum of working ratios. In each iteration, we search for the shop with maximum ‘PROFIT’, assign one extra bulb to it, and update the ‘PROFIT’ and ‘BULBS’ values for the assigned shop.
Algorithm:
- Create an array ‘PROFITS’ of size ‘N’ to store the ‘PROFIT’ values for each shop.
- Create a function GETPROFIT(‘W’, ‘T’), which calculates the profit value for ‘W’ (i.e., ‘WORKS') and ‘T’ (i.e., ‘TOTAL’). The function description should be:
- Return ‘(W+1)/(T+1) - W/T‘. ‘PROFIT’ gained by adding one extra bulb.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’ to compute the ‘PROFIT’ values for each shop:
- ‘PROFITS[i] = GETPROFIT(BULBS[i][0], BULBS[i][1])’.
- Run a loop where ‘i’ ranges from ‘0’ to ‘EXTRA’ to assign the extra bulbs:
- Set ‘POS = 0’.
- Run a loop where ‘j’ ranges from ‘1’ to ‘N-1’ to find the index with the maximum value in the ‘PROFITS’ array.
- If ‘PROFITS[POS] < PROFITS[j]’, then:
- ‘POS = j’.
- If ‘PROFITS[POS] < PROFITS[j]’, then:
- Assign one extra bulb to shop ‘POS’ and update its ‘BULBS’ and ‘PROFITS’ values.
- ‘BULBS[POS][0] += 1’ and ‘BULBS[POS][1] += 1’.
- ‘PROFITS[POS] = GETPROFIT(BULBS[POS][0], BULBS[POS[1])’.
- Set ‘AVG = 0’. To compute the average working ratio after assigning extra bulbs.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’ to get the sum of working ratios:
- ‘AVG += BULBS[i][0]/BULBS[i][1]’.
- Return ‘AVG/N’ as the answer.
We optimize the previous approach by using a priority queue (in this case, a max-heap) to find the shop that gives the maximum ‘PROFIT’ by taking one extra bulb. In each iteration, we pop the top of the priority queue, which is the shop with maximum ‘PROFIT’, update its ‘PROFIT’ and ‘BULBS’ values, and insert it into the priority queue with the new ‘PROFIT’ value.
Algorithm:
- Create an array ‘PROFITS’ of size ‘N’ to store the ‘PROFIT’ values for each shop.
- Create a function GETPROFIT(‘W’, ‘T’), which calculates the profit value for ‘W’ (i.e., ‘WORKS') and ‘T’ (i.e., ‘TOTAL’). The function description should be:
- Return ‘(W+1)/(T+1) - W/T‘. ‘PROFIT’ gained by adding one extra bulb.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’ to compute the ‘PROFIT’ values for each shop:
- ‘PROFIT = GETPROFIT(BULBS[i][0], BULBS[i][1])’.
- ‘PROFITS[i] = {PROFITS, i}. The profit and index of the current shop.
- Create a priority queue ‘PQ’. Build ‘PQ’ (in this a max-heap) from the ‘PROFITS’ array.
- Run a loop where ‘i’ ranges from ‘0’ to ‘EXTRA’ to assign the extra bulbs:
- ‘(PROFIT, POS) = PQ.pop()’. Get the profit and index of the shop having maximum profit and remove it from ‘PQ’.
- Assign one extra bulb to shop ‘POS’ and update its ‘BULBS’ and ‘PROFIT’ values.
- ‘BULBS[POS][0] += 1’ and ‘BULBS[POS][1] += 1’.
- ‘PROFIT = GETPROFIT(BULBS[POS][0], BULBS[POS[1])’.
- ‘PQ.push({PROFIT, i})’. Insert the new ‘PROFIT’ value into ‘PQ’.
- Set ‘AVG = 0’. To compute the average working ratio after assigning extra bulbs.
- Run a loop where ‘i’ ranges from ‘0’ to ‘N-1’ to get the sum of working ratios:
- ‘AVG += BULBS[i][0]/BULBS[i][1]’.
- Return ‘AVG/N’ as the answer.