Maximize the average working ratio

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
eBayVisa

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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

Sample input 1:

2
4 3
1 2
2 4
3 4
1 1
3 2
1 2
2 4
4 8

Sample output 1:

0.77500
0.58889

Explanation of sample input 1:

Test Case 1:
‘N = 4’, ‘EXTRA = 3’
‘BULBS = [ [1, 2], [2, 4], [3, 4], [1, 1] ]’

To get the maximum average working ratio, assign one bulb to shop ‘1’ and two bulbs to shop ‘3’. So, the average working ratio will be equal to ‘(3/4 + 3/5 + 3/4 + 1/1) / 4 = 0.77500’.

Test Case 2:
‘N = 3’, ‘EXTRA = 2’
‘BULBS = [ [1, 2], [2, 4], [4, 8] ]’

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 ‘(2/3 + 3/5 + 4/8) / 3 = 0.58889’.

Sample input 2:

2
3 3
1 2
2 3
3 4
3 5
1 1
2 2
3 3

Sample output 2:

0.75000
1.00000
Hint

Greedily assign each extra blub to the best current choice.

Approaches (2)
Greedy approach

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’.
    • 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.
Time Complexity

O(N*EXTRA), where ‘N’ is the number of shops, and ‘EXTRA’ is the number of extra bulbs.

 

Creating the ‘PROFITS’ array takes ‘O(N)’ time. To assign one bulb, we find the maximum value in ‘PROFITS’ in ‘O(N)’, and there are ‘O(EXTRA)’ extra bulbs. So, the overall time complexity is ‘O(N*EXTRA)’.

Space Complexity

O(N), where ‘N’ is the number of shops.

 

As there are ‘N’ shops, the size of the array ‘PROFITS’ is ‘O(N)’.

Code Solution
(100% EXP penalty)
Maximize the average working ratio
Full screen
Console