Welcome to Subscribe On Youtube
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 <= 16nums.lengthis divisible byk1 <= nums[i] <= nums.length
Related Topics:
Backtracking, Greedy
Solution 1. Bitmask DP
Preprocess
- Sort
Ain asending order - Handle special cases where
k = 1andk = N.
State Definition
Let dp[mask][pre] be the minimum incompatibility we can get with:
mask: If theith bit is0, thenith 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];
}
};
-
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]; } } -
// 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]; } }; -
class Solution: def minimumIncompatibility(self, nums: List[int], k: int) -> int: @cache def dfs(mask): if mask == (1 << n) - 1: return 0 d = {v: i for i, v in enumerate(nums) if (mask >> i & 1) == 0} ans = inf if len(d) < m: return ans for vs in combinations(d.keys(), m): nxt = mask for v in vs: nxt |= 1 << d[v] ans = min(ans, max(vs) - min(vs) + dfs(nxt)) return ans n = len(nums) m = n // k ans = dfs(0) dfs.cache_clear() return ans if ans < inf else -1