New update is available. Click here to update.

Minimum Costs Of Subsets

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

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

Approach 1

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 :

Calulate number of element in each subset (let groupSize= n/k)
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’

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

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
ANS = infinity
For i in range(n)
1. ANS = min(ANS, dp[(1<<n) - 1][ i ] )
If ANS == infinity
1. ANS =- 1
Return ANS

Try Problem