Minimum Costs Of Subsets

Hard
0/120
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
eBay

Problem statement

You are given an array ARR of ‘N’ Integers and an integer. Your task is to divide this array into ‘K’ subsets satisfying the following constraints-

1. Each element in ARR belongs to exactly one subset.
2. All the elements in a subset are unique.
3. Each subset has a size of ‘N’/ ’K’

Your task is to find the minimum cost of constructing the ‘K’ subset.

Cost of the construction of subsets is calculated as the sum of the maximum - the minimum of a subset. If there is no way to divide ARR into K subsets satisfying the constraints, print -1.

It is guaranteed that ‘K’ is a divisor of ‘N’.

For example :

[1,2,3,1,2,5] k=2
[[1,2,3],[1,2,5]] is a valid subset division. All the elements in each subset are unique and the the cost of construction is (3 - 1) + (5 - 1) = 6
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line and the only line of each test case contain two single space-separated integers, ‘N’ and ‘K’.

The second line of each test case contains N space-separated integers representing the elements of the array ARR.
Output Format : 
For each test case print the minimum cost of construction.
Output for each test case is 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 <= 5
1 <= N <= 12
1 <= K <= N
1<= ARR[i] <= 20    
K is a devisor of the N

Time Limit: 1 sec
Sample Input 1 :
2 
4 2
1 4 5 9
5 5
1 2 3 4 5
Sample Output 1 :
 7
 0
Explanation of Sample Input 1 :
For the first test case [[1,4], [5,9]] is the required distribution.
ANS = ( 4 - 1) + (9 - 5) = 7
[ [1, 5], [9, 4] ] is also the valid distribution but the cost of construction is not minimum. 
For the second test case each subset has exactly one element [ [1], [2], [3], [4], [5] ]
ANS = (1 - 1) + (2 - 2) + (3 - 3) + (4 - 4) + (5 - 5)
Sample Input 2 :
2
6 3 
3 3 3 1 11 4
4 2 
7 11 7 11
Sample Output 2 :
11
8
Hint

Constrains are small, can we use a bitmask to solve this problem?

Approaches (1)
Bitmask DP

The answer depends on the smallest and the largest element in the subset. We will iterate over all the submasks of the array and the last element taken in this mask. Number the set bits in the mask will give the idea about if we are starting a new subset or ending a current subset. We will create a subset from the smallest element to the largest element. 


 

groupSize = size of each group/subset 

 

If we are starting a new group with i’th element then this element will be the smallest element in our new group so we will subtract it 

DP[new_mask][i] = min(dp[new_mask][i],DP[mask][last]-arr[i])

    

If we are ending a group with i’th element then this will be the largest element in our group so we will add it 

DP[new_mask][i]=min(DP[new_mask][i],DP[mask][last]+arr[i])

    

If we are adding the i’th element and it is not starting or ending a group than 

DP[new_mask][i]=min(DP[new_mask][i], DP[mask][last])


 

The algorithm will be :

  1. Calulate number of element in each subset (let groupSize= n/k)
  2. dp[(1<<n)][ n ]

dp[mask][last] represents the minimum cost to group all the elements in the mask and the last element taken is ‘last’

  1. For i in range(n)
    1. dp[1<<i][ i ] = - arr[i]

     Base case here we are starting a new subset having only i’th element 

  1. For mask in range((1<<n))
    1. SETBITS = number of set bits in mask
    2. For CURRENT  in range(n)
      1. For NEXT in range(n)
        1. If CURRENT in mask and NEXT not in mask
        2. If SETBITS%groupSize == 0
          1. Start a new group
        3. If SETBITS%groupSize == groupSize - 1
          1. End the current group
        4. If  0 < SETBITS < groupSize - 1
          1. Add to current group
  2. ANS = infinity
  3. For i in range(n)
    1. ANS = min(ANS, dp[(1<<n) - 1][ i ] )
  4. If ANS == infinity
    1. ANS =- 1
  5. Return ANS
Time Complexity

O(2^n * n^2 ), where n is the size of arr.

 

We are iterating over all the submask and for every last element, we are trying the new next element.

Space Complexity

O(n* 2^n), where n is the size of arr.

 

Storing the minimum cost for all the submasks and last values.

Code Solution
(100% EXP penalty)
Minimum Costs Of Subsets
Full screen
Console