Hard
Minimum Incompatibility — C++
Full explanation · Time O(max(n * 2^n, 3^n)) · Space O(2^n)
// Time: O(max(n * 2^n, 3^n))
// Space: O(2^n)
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
const vector<int> candidates = findCandidates(nums, k); // Time: O(n * 2^n)
const int total = (1 << size(nums)) - 1;
vector<int> dp(total + 1, numeric_limits<int>::max());
dp[0] = 0;
for (int mask = 0; mask <= total; ++mask) { // Time: O(3^n)
if (__builtin_popcount(mask) % (size(nums) / k) != 0) {
continue;
}
// submask enumeration:
// => sum(nCr(n, k) * 2^k for k in xrange(n+1)) = (1 + 2)^n = 3^n
// => Time: O(3^n), see https://cp-algorithms.com/algebra/all-submasks.html
for (int submask = mask; submask; submask = (submask - 1) & mask) {
if (candidates[submask] == numeric_limits<int>::max() ||
dp[mask - submask] == numeric_limits<int>::max()) {
continue;
}
dp[mask] = min(dp[mask], dp[mask - submask] + candidates[submask]);
}
}
return dp.back() != numeric_limits<int>::max() ? dp.back() : -1;
}
private:
vector<int> findCandidates(const vector<int>& nums, int k) {
const int total = (1 << size(nums)) - 1;
vector<int> result(total + 1, numeric_limits<int>::max());
for (int mask = 0; mask <= total; ++mask) {
if (__builtin_popcount(mask) != size(nums) / k) {
continue;
}
int lookup = 0;
int mx = 0, mn = numeric_limits<int>::max();
bool duplicated = false;
for (int i = 0; i < size(nums); ++i) {
if ((mask & (1 << i)) == 0) {
continue;
}
if (lookup & (1 << nums[i])) {
duplicated = true;
break;
}
lookup |= (1 << nums[i]);
mx = max(mx, nums[i]);
mn = min(mn, nums[i]);
}
if (duplicated) {
continue;
}
result[mask] = mx - mn;
}
return result;
}
};
// Time: O(sum(i*d * nCr(i*d, d) * nCr(n, i*d) for i in xrange(1, k+1))) < O(sum(n * 2^m * nCr(n, m) for m in xrange(n+1))) = O(n * 3^n)
// Space: O(n * k)
class Solution_TLE {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
unordered_map<string, int> lookup;
int result = backtracking(nums, size(nums) / k, &lookup);
return result != numeric_limits<int>::max() ? result : -1;
}
private:
int backtracking(const vector<int>& nums, int d, unordered_map<string, int> *lookup) {
if (empty(nums)) {
return 0;
}
string k = key(nums);
if (!lookup->count(k)) {
int ret = numeric_limits<int>::max();
combinations(size(nums), d,
[this, &nums, &d, &lookup, &ret](const vector<int>& idxs) {
unordered_set<int> new_nums_set;
for (const auto& idx : idxs) {
new_nums_set.emplace(nums[idx]);
}
if (size(new_nums_set) < d) {
return;
}
int mx = *max_element(cbegin(new_nums_set), cend(new_nums_set));
int mn = *min_element(cbegin(new_nums_set), cend(new_nums_set));
vector<int> left;
for (const auto& num : nums) {
if (new_nums_set.count(num)) {
new_nums_set.erase(num);
continue;
}
left.emplace_back(num);
}
int result = backtracking(left, d, lookup);
if (result != numeric_limits<int>::max()) {
ret = min(ret, mx - mn + result);
}
});
(*lookup)[k] = ret;
}
return (*lookup)[k];
}
string key(const vector<int>& nums) {
string result;
for (const auto& num : nums) {
result += to_string(num);
result.push_back(',');
}
return result;
}
void combinations(int n, int k, const function<void (const vector<int>&)>& callback) {
static const auto& next_pos =
[](const auto& n, const auto& k, const auto& idxs) {
int i = k - 1;
for (; i >= 0; --i) {
if (idxs[i] != i + n - k) {
break;
}
}
return i;
};
vector<int> idxs(k);
iota(begin(idxs), end(idxs), 0);
callback(idxs);
for (int i; (i = next_pos(n, k, idxs)) >= 0;) {
++idxs[i];
for (int j = i + 1; j < k; ++j) {
idxs[j] = idxs[j - 1] + 1;
}
callback(idxs);
}
}
};
// Time: O(nlogn)
// Space: O(n)
// wrong with greedy solution
// nums = [15, 9, 7, 10, 15, 14, 12, 2, 10, 8, 10, 13, 4, 11, 2]
// k = 5
// greedy => [[2, 4, 7], [2, 8, 9], [10, 11, 12], [10, 13, 15], [10, 14, 15]] => 24
// correct => [[2, 4, 7], [2, 8, 10], [9, 10, 11], [10, 12, 15], [13, 14, 15]] => 22
// optimized from Solution_Wrong_Greedy
class Solution_Wrong_Greedy_Map {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
return min(greedy<less<int>>(nums, k), greedy<greater<int>>(nums, k)); // two possible minimas
}
private:
template<typename T>
int greedy(const vector<int>& nums, int k) {
map<int, int, T> count;
for (const auto& num : nums) {
++count[num];
}
unordered_map<int, list<int>> freq_to_nodes;
unordered_map<int, list<int>::iterator> key_to_nodeit;
for (const auto& [x, cnt] : count) {
freq_to_nodes[cnt].emplace_back(x);
key_to_nodeit[x] = prev(end(freq_to_nodes[cnt]));
if (cnt > k) {
return -1;
}
}
vector<vector<int>> stks(k);
int curr = 0;
while (!empty(count)) { // the while loop runs O(k) times
if (freq_to_nodes.count(size(stks) - curr)) { // fill the deterministic elements into the remaining subsets
for (const auto& x : freq_to_nodes[size(stks) - curr]) { // total time = O(n)
for (int i = curr; i < size(stks); ++i) {
stks[i].emplace_back(x);
}
key_to_nodeit.erase(x);
count.erase(x);
}
freq_to_nodes.erase(size(stks) - curr);
}
// greedily fill the contiguous ordered elements into the first vacant subset until it is full,
// otherwise, the result sum would get larger => in fact, this is wrong
vector<int> to_delete;
for (auto& [x, cnt] : count) {
stks[curr].emplace_back(x);
freq_to_nodes[cnt].erase(key_to_nodeit[x]);
if (empty(freq_to_nodes[cnt])) {
freq_to_nodes.erase(cnt);
}
--cnt; // total time = O(n)
if (!cnt) {
key_to_nodeit.erase(x);
to_delete.emplace_back(x);
} else {
freq_to_nodes[cnt].emplace_back(x);
key_to_nodeit[x] = prev(end(freq_to_nodes[cnt]));
}
if (size(stks[curr]) == size(nums) / k) {
++curr;
break;
}
}
for (const auto& x : to_delete) {
count.erase(x); // total time = O(nlogn)
}
}
return accumulate(cbegin(stks), cend(stks), 0,
[](const auto& a, const auto& b) {
return a + (*max_element(cbegin(b), cend(b)) - *min_element(cbegin(b), cend(b)));
});
}
};
// Time: O(nlogn + k * n)
// Space: O(n)
// wrong with greedy solution
// nums = [15, 9, 7, 10, 15, 14, 12, 2, 10, 8, 10, 13, 4, 11, 2]
// k = 5
// greedy => [[2, 4, 7], [2, 8, 9], [10, 11, 12], [10, 13, 15], [10, 14, 15]] => 24
// correct => [[2, 4, 7], [2, 8, 10], [9, 10, 11], [10, 12, 15], [13, 14, 15]] => 22
class Solution_Wrong_Greedy {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
return min(greedy<less<int>>(nums, k), greedy<greater<int>>(nums, k)); // two possible minimas
}
private:
template<typename T>
int greedy(const vector<int>& nums, int k) {
map<int, int, T> count;
for (const auto& num : nums) {
++count[num];
}
for (const auto& [_, cnt] : count) {
if (cnt > k) {
return -1;
}
}
vector<vector<int>> stks(k);
int curr = 0;
int remain = size(nums);
while (remain) { // the while loop runs O(k) times, and the inner loops runs O(n) times
for (auto& [x, cnt] : count) { // fill the deterministic elements into the remaining subsets
if (cnt != size(stks) - curr) {
continue;
}
for (int i = curr; i < size(stks); ++i) {
stks[i].emplace_back(x);
}
remain -= cnt;
cnt = 0;
}
// greedily fill the contiguous ordered elements into the first vacant subset until it is full,
// otherwise, the result sum would get larger => in fact, this is wrong
for (auto& [x, cnt] : count) {
if (!cnt) {
continue;
}
stks[curr].emplace_back(x);
--remain;
--cnt;
if (size(stks[curr]) == size(nums) / k) {
++curr;
break;
}
}
}
return accumulate(cbegin(stks), cend(stks), 0,
[](const auto& a, const auto& b) {
return a + (*max_element(cbegin(b), cend(b)) - *min_element(cbegin(b), cend(b)));
});
}
};