Krammer's blog

https://leetcode.com/problems/minimum-incompatibility/ from Microsoft

Thinking process:

This is a DP problem. We can use a bit map to represent the minimum incompatibility for a set of elements. We first precompute a map which separates the bit map based on how many bits they have.

Then, we compute the incompatibility for all the base subsets. With that, we can growth our solution based on that.

Here is the code.

 1class Solution {
 2public:
 3    int N;
 4    int bits(int x) {
 5        int ret = 0;
 6        while (x) {
 7            ret += (x&1);
 8            x = x >> 1;
 9        }
10        return ret;
11    }
12    bool check(int x, vector<int>& nums) {
13        bool seen[17] = {};
14        for (int i=0; i<N; i++) {
15            if ((1<<i) & x) {
16                if (seen[nums[i]]) return false;
17                seen[nums[i]] = true;
18            }
19        }
20        return true;
21    }
22    
23    int calculate(int x, vector<int>& nums) {
24        int Max = 1, Min = 16;
25        for (int i=0; i<N; i++) {
26            if ((1<<i) & x) {
27                Max = max(Max, nums[i]);
28                Min = min(Min, nums[i]);
29            }
30        }
31        return Max - Min;
32    }
33    
34    int minimumIncompatibility(vector<int>& nums, int K) {
35        N = nums.size();
36        vector<int> dp(1<<N, INT_MAX);
37        unordered_map<int, vector<int>> mp;
38        int k = N / K;
39        if (k == 1) return 0;
40        
41        for (int i=1; i<(1<<N); i++) {
42            int b = bits(i);
43            if ((b % k) == 0 and (b != k or check(i, nums))) {
44                mp[b].push_back(i);
45            }
46        }
47        
48        for (auto x : mp[k]) {
49            dp[x] = calculate(x, nums);
50        }
51        
52        int cur = k;
53        while (cur < N) {
54            for (auto x : mp[cur]) {
55                if (dp[x] == INT_MAX) continue;
56                for (auto y : mp[k]) {
57                    if ((x&y) == 0) {
58                        dp[x|y] = min(dp[x|y], dp[x] + dp[y]);
59                    }
60                }
61            }
62            cur += k;
63        }
64        return dp[(1<<N)-1] == INT_MAX ? -1 : dp[(1<<N)-1];
65    }
66};

Editorial: LeetCode 1681 Minimum Incompatibility