# 1681. Minimum Incompatibility¶

• Time: $O(3^n)$
• Space: $O(2^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 class Solution { public: int minimumIncompatibility(vector& nums, int k) { constexpr int kMaxCompatibility = (16 - 1) * (16 / 2); const int n = nums.size(); const int subsetSize = n / k; const int maxMask = 1 << n; const vector incompatibilities = getIncompatibilities(nums, subsetSize); // dp[i] := the minimum possible sum of incompatibilities of the subset // of numbers represented by the bitmask i vector dp(maxMask, kMaxCompatibility); dp[0] = 0; for (unsigned mask = 1; mask < maxMask; ++mask) { // The number of 1s in mask isn't a multiple of subsetSize. if (popcount(mask) % subsetSize != 0) continue; // https://cp-algorithms.com/algebra/all-submasks.html for (int submask = mask; submask > 0; submask = (submask - 1) & mask) if (incompatibilities[submask] != -1) // valid subset dp[mask] = min(dp[mask], dp[mask - submask] + incompatibilities[submask]); } return dp.back() == kMaxCompatibility ? -1 : dp.back(); } private: static constexpr int kMaxNum = 16; // Returns an incompatibilities array where // * incompatibilities[i] := the incompatibility of the subset of numbers // represented by the bitmask i // * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not // subsetSize vector getIncompatibilities(const vector& nums, int subsetSize) { const int maxMask = 1 << nums.size(); vector incompatibilities(maxMask, -1); for (unsigned mask = 0; mask < maxMask; ++mask) if (popcount(mask) == subsetSize && isUnique(nums, mask, subsetSize)) incompatibilities[mask] = getIncompatibility(nums, mask); return incompatibilities; } // Returns true if the numbers selected by mask are unique. // // e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), used variable // will be 0b1, which only has one 1 (less than subsetSize). In this case, // we should return false. bool isUnique(const vector& nums, int mask, int subsetSize) { unsigned used = 0; for (int i = 0; i < nums.size(); ++i) if (mask >> i & 1) used |= 1 << nums[i]; return popcount(used) == subsetSize; } // Returns the incompatibility of the selected numbers represented by the // mask. int getIncompatibility(const vector& nums, int mask) { int mn = kMaxNum; int mx = 0; for (int i = 0; i < nums.size(); ++i) if (mask >> i & 1) { mx = max(mx, nums[i]); mn = min(mn, nums[i]); } return mx - mn; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class Solution { public int minimumIncompatibility(int[] nums, int k) { final int kMaxCompatibility = (16 - 1) * (16 / 2); final int n = nums.length; final int subsetSize = n / k; final int maxMask = 1 << n; final int[] incompatibilities = getIncompatibilities(nums, subsetSize); // dp[i] := the minimum possible sum of incompatibilities of the subset // of numbers represented by the bitmask i int[] dp = new int[maxMask]; Arrays.fill(dp, kMaxCompatibility); dp[0] = 0; for (int mask = 1; mask < maxMask; ++mask) { // The number of 1s in mask isn't a multiple of subsetSize. if (Integer.bitCount(mask) % subsetSize != 0) continue; // https://cp-algorithms.com/algebra/all-submasks.html for (int submask = mask; submask > 0; submask = (submask - 1) & mask) if (incompatibilities[submask] != -1) // valid submask dp[mask] = Math.min(dp[mask], dp[mask - submask] + incompatibilities[submask]); } return dp[maxMask - 1] == kMaxCompatibility ? -1 : dp[maxMask - 1]; } private static final int kMaxNum = 16; // Returns an incompatibilities array where // * incompatibilities[i] := the incompatibility of the subset of numbers // represented by the bitmask i // * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not // subsetSize private int[] getIncompatibilities(int[] nums, int subsetSize) { final int maxMask = 1 << nums.length; int[] incompatibilities = new int[maxMask]; Arrays.fill(incompatibilities, -1); for (int mask = 0; mask < maxMask; ++mask) if (Integer.bitCount(mask) == subsetSize && isUnique(nums, mask, subsetSize)) incompatibilities[mask] = getIncompatibility(nums, mask); return incompatibilities; } // Returns true if the numbers selected by mask are unique. // // e.g. If we call isUnique(0b1010, 2, [1, 2, 1, 4]), used variable // will be 0b1, which only has one 1 (less than subsetSize). In this case, // we should return false. private boolean isUnique(int[] nums, int mask, int subsetSize) { int used = 0; for (int i = 0; i < nums.length; ++i) if ((mask >> i & 1) == 1) used |= 1 << nums[i]; return Integer.bitCount(used) == subsetSize; } // Returns the incompatibility of the selected numbers represented by the // mask. private int getIncompatibility(int[] nums, int mask) { int mn = kMaxNum; int mx = 0; for (int i = 0; i < nums.length; ++i) if ((mask >> i & 1) == 1) { mx = Math.max(mx, nums[i]); mn = Math.min(mn, nums[i]); } return mx - mn; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 class Solution: def __init__(self): self.kMaxNum = 16 def minimumIncompatibility(self, nums: List[int], k: int) -> int: kMaxCompatibility = (16 - 1) * (16 // 2) n = len(nums) subsetSize = n // k maxMask = 1 << n incompatibilities = self._getIncompatibilities(nums, subsetSize) # dp[i] := the minimum possible sum of incompatibilities of the subset # of numbers represented by the bitmask i dp = [kMaxCompatibility] * maxMask dp[0] = 0 for mask in range(1, maxMask): # The number of 1s in mask isn't a multiple of subsetSize. if mask.bit_count() % subsetSize != 0: continue # https://cp-algorithms.com/algebra/all-submasks.html submask = mask while submask > 0: if incompatibilities[submask] != -1: # valid submask dp[mask] = min(dp[mask], dp[mask - submask] + incompatibilities[submask]) submask = (submask - 1) & mask return dp[-1] if dp[-1] != kMaxCompatibility else -1 def _getIncompatibilities(self, nums: List[int], subsetSize: int) -> List[int]: """ Returns an incompatibilities array where * incompatibilities[i] := the incompatibility of the subset of numbers represented by the bitmask i * incompatibilities[i] := -1 if the number of 1s in the bitmask i is not subsetSize """ maxMask = 1 << len(nums) incompatibilities = [-1] * maxMask for mask in range(maxMask): if mask.bit_count() == subsetSize and self._isUnique(nums, mask, subsetSize): incompatibilities[mask] = self._getIncompatibility(nums, mask) return incompatibilities def _isUnique(self, nums: List[int], mask: int, subsetSize: int) -> bool: """Returns True if the numbers selected by mask are unique.""" used = 0 for i, num in enumerate(nums): if mask >> i & 1: used |= 1 << num return used.bit_count() == subsetSize def _getIncompatibility(self, nums: List[int], mask: int) -> int: """ Returns the incompatibility of the selected numbers represented by the mask. """ mn = self.kMaxNum mx = 0 for i, num in enumerate(nums): if mask >> i & 1: mx = max(mx, num) mn = min(mn, num) return mx - mn