Formatted question description: https://leetcode.ca/all/1681.html

1681. Minimum Incompatibility (Hard)

You are given an integer array nums​​​ and an integer k. You are asked to distribute this array into k subsets of equal size such that there are no two equal elements in the same subset.

A subset's incompatibility is the difference between the maximum and minimum elements in that array.

Return the minimum possible sum of incompatibilities of the k subsets after distributing the array optimally, or return -1 if it is not possible.

A subset is a group integers that appear in the array with no particular order.

 

Example 1:

Input: nums = [1,2,1,4], k = 2
Output: 4
Explanation: The optimal distribution of subsets is [1,2] and [1,4].
The incompatibility is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.

Example 2:

Input: nums = [6,3,8,1,3,1,2,2], k = 4
Output: 6
Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].
The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: nums = [5,3,3,6,3,3], k = 3
Output: -1
Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.

 

Constraints:

  • 1 <= k <= nums.length <= 16
  • nums.length is divisible by k
  • 1 <= nums[i] <= nums.length

Related Topics:
Backtracking, Greedy

Solution 1. Bitmask DP

Preprocess

  • Sort A in asending order
  • Handle special cases where k = 1 and k = N.

State Definition

Let dp[mask][pre] be the minimum incompatibility we can get with:

  • mask: If the ith bit is 0, then ith number is used. Otherwise, ith number is available.
  • pre: the index of the number selected in the previous choice.

State Transition

We allocate the subsets one by one. For each subset, we allocate the numbers in ascending order.

We can use the number of 1 bits in mask, i.e. __builtin_popcount(mask), to know how many numbers are available.

If __builtin_popcount(mask) is not divisible by sz, then in the current choice we need to consider pre. To avoid duplicate numbers in the same subset, we must choose a number that is greater than A[pre]. Assume we chose A[p], then we added A[p] - A[pre] into the incompatibility.

          pre  p
           v   v
A:       1 2 2 3 4 4 5 5 6 
subset:  1 2   3

delta
incompa-   3 - 2 = 1
tibility

Transition formula:

dp[mask][pre] = min( dp[mask - (1 << p)][p] + A[p] - A[pre] | pre < p < N && A[p] > A[pre] && (mask & (1 << p)) != 0 )

If __builtin_popcount(mask) is divisible by sz, then we are allocating for a new subset. Now pre doesn’t matter. We just need to pick the first available number.

dp[mask][0] = ... = dp[mask][N - 1] = min( dp[mask - (1 << p)][p] | 0 < p < N && (mask & (1 << p)) != 0 )
// OJ: https://leetcode.com/problems/minimum-incompatibility/

// Time: O(2^N * N^2)
// Space: O(2^N * N)
// Ref: https://leetcode-cn.com/problems/minimum-incompatibility/solution/lao-tao-lu-zhuang-tai-ya-suo-dp-by-newha-j58b/
class Solution {
public:
    int minimumIncompatibility(vector<int>& A, int k) {
        int N = A.size(), M = 1 << N, sz = N / k;
        if (k == 1) {
            set<int> s(begin(A), end(A));
            return s.size() == A.size() ? *s.rbegin() - *s.begin() : -1;
        }
        if (k == N) return 0;
        sort(begin(A), end(A));
        int dp[M][N];
        memset(dp, 0x3f, sizeof(dp)); // infinity
        memset(dp[0], 0, sizeof(dp[0]));
        for (int mask = 1; mask < M; ++mask) {
            if (__builtin_popcount(mask) % sz) {
                for (int pre = 0; pre < N; ++pre) {
                    for (int p = pre + 1; p < N; ++p) {
                        if ((mask & (1 << p)) && A[p] > A[pre]) {
                            dp[mask][pre] = min(dp[mask][pre], dp[mask - (1 << p)][p] + A[p] - A[pre]);
                        }
                    }
                }
            } else {
                for (int p = 0; p < N; ++p) {
                    if (mask & (1 << p)) dp[mask][0] = min(dp[mask][0], dp[mask - (1 << p)][p]);
                }
                for (int i = 1; i < N; ++i) dp[mask][i] = dp[mask][0];
            }
        }
        return dp[M - 1][0] > 10000 ? -1 : dp[M - 1][0];
    }
};

Java

class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        int length = nums.length;
        int[] value = new int[1 << length];
        Arrays.fill(value, -1);
        int[] freq = new int[length + 1];
        for (int i = 0; i < 1 << length; i++) {
            if (Integer.bitCount(i) == length / k) {
                for (int j = 0; j < length; j++) {
                    if ((i & (1 << j)) != 0)
                        freq[nums[j]]++;
                }
                boolean flag = true;
                for (int j = 1; j <= length; j++) {
                    if (freq[j] > 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
                    for (int j = 1; j <= length; ++j) {
                        if (freq[j] > 0) {
                            low = Math.min(low, j);
                            high = Math.max(high, j);
                        }
                    }
                    value[i] = high - low;
                }
                for (int j = 0; j < length; ++j) {
                    if ((i & (1 << j)) != 0) {
                        --freq[nums[j]];
                    }
                }
            }
        }
        int[] dp = new int[1 << length];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i < 1 << length; i++) {
            if (Integer.bitCount(i) % (length / k) == 0) {
                for (int j = i; j != 0; j = (j - 1) & i) {
                    if (value[j] != -1 && dp[i ^ j] != -1) {
                        if (dp[i] == -1)
                            dp[i] = dp[i ^ j] + value[j];
                        else
                            dp[i] = Math.min(dp[i], dp[i ^ j] + value[j]);
                    }
                }
            }
        }
        return dp[(1 << length) - 1];
    }
}

All Problems

All Solutions