Ninja and operations

Posted: 16 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Ninja has been given an array/list ‘COST’ of size ‘N’ and an integer ‘TAR’. Ninja can perform one of the following operations on each element of the ‘COST’ array/list i.e, ‘FLOOR(COST[i])’ or ‘CEIL(COST[i])’.

Ninja has to find if after performing one of these operations on each element of the 'COST', the sum of all elements is equal to ‘TAR’ or not.

If the sum is equal to ‘TAR’ then print the smallest possible value of | opr(‘COST[i]’) - ‘COST[i]’ | from 0 to ‘N’ - 1 up to 3 decimal places where ‘opr(‘COST[i])’ is ‘FLOOR(COST[i])’ or ‘CEIL(COST[i])’. Else print -1.

Note:

FLOOR(2.342) = 2 
CEIL(2.342) = 3
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two integers ‘N’ and ‘TAR’ which denotes the number of elements of ‘COST’ and target sum which has been discussed above.

The next ‘N’ lines contain space-separated real numbers that have exactly 3 decimal places representing the elements of the ‘COST’.
Output Format:
For each test case, print a single line containing a single integer such that If the sum is equal to ‘TAR’ then print the smallest possible value of |opr(‘COST[i]’) - ‘COST[i]’| from 0 to ‘N’ - 1 up to 3 decimal places. Else print -1.


The output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 500
1 <= TAR <= 10000
0 <= COST[i] <= 1000

Where ‘T’ is the number of test cases, 'N' is the size of ‘COST’, the target sum which is discussed above, and ‘COST[i]’ represents the real number present in ‘COST’.

Time limit: 1 sec.
Approach 1

If a number is an integer, then we can only take the floor, not ceil. This is equivalent to a number that cannot be adjusted, otherwise, it is an adjustable number. We put the fractional part of all adjustable numbers into a Priority Queue ‘pq’, and record the size of the ‘pq’.

 

Then we first judge under what circumstances the target cannot be obtained:

 

If the smallest possible sum is taken, then all numbers must be taken on the floor. If this sum is still larger than the target or smaller than the ‘TAR’ - the size of ‘pq’, it means that it is impossible to get the ‘TAR’ anyway. So we return -1.

 

If the above conditions are not met, we must be able to get the sum that meets the conditions of the problem. We need to know how many numbers to adjust, that is, to turn the floor operation into a ceil operation. The number of elements to be adjusted is equal to the ‘TAR’ - the size of ‘pq’.

 

In order to achieve the smallest | opr(‘COST[i]’) - ‘COST[i]’ | for each adjustment operation, we hope that their decimals are as large as possible, which can be obtained from the previous Priority Queue. Take the ceil of that number. Finally, adding all the decimals that do not need to be adjusted is the smallest  | opr(‘COST[i]’) - ‘COST[i]’ |.

 

The steps are as follows:

 

  1. Declare a variable ‘ans’ and a priority queue ‘pq’ as we discussed above.
  2. Run a loop for ‘i’ = 0 to ‘N’:
    • ‘currValue’ = ‘COST[i]’
    • ‘low’ =  ‘FLOOR(COST[i])’.
    • ‘high’ =  ‘CEIL(COST[i])’.
    • If ‘low’ not equal to ‘high’:
      • Add (‘high’ - ‘currValue’) - (‘currValue’ - ‘low’).
    • ‘ans’ = ‘ans’ + ‘currValue’ - ‘low’.
    • ‘TAR’ = ‘TAR’ - ‘low’.
  3. If ‘TAR’ less than 0 or ‘TAR’ is greater than the size of ‘pq’:
    • Return ‘-1’.
  4. While ‘TAR’ greater than 0:
    • ‘ans’ = ‘ans’ + top element of ‘pq’.
  5. Finally, return ‘ans’.
Try Problem