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

Solution: TSP

dp[s][i] := min cost to distribute a set of numbers represented as a binary mask s, the last number in the set is the i-th number.

Init:
1.dp[*][*] = inf
2. dp[1 <<i][i] = 0, cost of selecting a single number is zero.

Transition:
1. dp[s | (1 << j)][j] = dp[s][i] if s % (n / k) == 0, we start a new group, no extra cost.
2. dp[s | (1 << j)][j] = dp[s][i] + nums[j] – nums[i] if nums[j] > nums[i]. In the same group, we require the selected numbers are monotonically increasing. Each cost is nums[j] – nums[i].
e.g. 1, 3, 7, 20, cost is (3 – 1) + (7 – 3) + (20 – 7) = 20 – 1 = 19.

Ans: min(dp[(1 << n) – 1])

Time complexity: O(2^n * n^2)
Space complexity: O(2^n * n)

C++

// Author: Huahua

class Solution {

public:

int minimumIncompatibility(vector<int>& nums, int k) {

const int n = nums.size();

const int c = n / k;

int dp[1 << 16][16];

memset(dp, 0x7f, sizeof(dp));

for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;

for (int s = 0; s < 1 << n; ++s)

for (int i = 0; i < n; ++i) {

if ((s & (1 << i)) == 0) continue;

for (int j = 0; j < n; ++j) {

if ((s & (1 << j))) continue;

const int t = s | (1 << j);

if (__builtin_popcount(s) % c == 0) {

dp[t][j] = min(dp[t][j], dp[s][i]);

} else if (nums[j] > nums[i]) {

dp[t][j] = min(dp[t][j],

dp[s][i] + nums[j] - nums[i]);

}

int ans = *min_element(begin(dp[(1 << n) - 1]),

end(dp[(1 << n) - 1]));

return ans > 1e9 ? - 1 : ans;

}

};

Problem

Given an array A of strings, find any smallest string that contains each string in A as a substring.

We may assume that no string in A is substring of another string in A.

Example 1:

Input: ["alex","loves","leetcode"]
Output: "alexlovesleetcode"
Explanation: All permutations of "alex","loves","leetcode" would also be accepted.

Example 2:

Input: ["catg","ctaagt","gcta","ttca","atgcatc"]
Output: "gctaagttcatgcatc"

Note:

1 <= A.length <= 12
1 <= A[i].length <= 20

Solution 1: Search + Pruning

Try all permutations. Pre-process the cost from word[i] to word[j] and store it in g[i][j].

Time complexity: O(n!)

Space complexity: O(n)

C++

// Author: Huahua, running time: 692 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

g_ = vector<vector<int>>(n, vector<int>(n));

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

g_[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g_[i][j] = A[j].length() - k;

}

vector<int> path(n);

best_len_ = INT_MAX;

dfs(A, 0, 0, 0, path);

string ans = A[best_path_[0]];

for (int k = 1; k < best_path_.size(); ++k) {

int i = best_path_[k - 1];

int j = best_path_[k];

ans += A[j].substr(A[j].length() - g_[i][j]);

}

return ans;

}

private:

vector<vector<int>> g_;

vector<int> best_path_;

int best_len_;

void dfs(const vector<string>& A, int d, int used, int cur_len, vector<int>& path) {

if (cur_len >= best_len_) return;

if (d == A.size()) {

best_len_ = cur_len;

best_path_ = path;

return;

}

for (int i = 0; i < A.size(); ++i) {

if (used & (1 << i)) continue;

path[d] = i;

dfs(A,

d + 1,

used | (1 << i),

d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],

path);

}

};

Java

// Author: Huahua, 439 ms, 35.8MB

class Solution {

private int n;

private int[][] g;

private String[] a;

private int best_len;

private int[] path;

private int[] best_path;

private void dfs(int d, int used, int cur_len) {

if (cur_len >= best_len) return;

if (d == n) {

best_len = cur_len;

best_path = path.clone();

return;

}

for (int i = 0; i < n; ++i) {

if ((used & (1 << i)) != 0) continue;

path[d] = i;

dfs(d + 1,

used | (1 << i),

d == 0 ? a[i].length() : cur_len + g[path[d - 1]][i]);

}

public String shortestSuperstring(String[] A) {

n = A.length;

g = new int[n][n];

a = A;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

g[i][j] = A[j].length();

for (int k = 1; k <= Math.min(A[i].length(), A[j].length()); ++k)

if (A[i].substring(A[i].length() - k).equals(A[j].substring(0, k)))

g[i][j] = A[j].length() - k;

}

path = new int[n];

best_len = Integer.MAX_VALUE;

dfs(0, 0, 0);

String ans = A[best_path[0]];

for (int k = 1; k < n; ++k) {

int i = best_path[k - 1];

int j = best_path[k];

ans += A[j].substring(A[j].length() - g[i][j]);

}

return ans;

}

Solution 2: DP

g[i][j] is the cost of appending word[j] after word[i], or weight of edge[i][j].

We would like find the shortest path to visit each node from 0 to n – 1 once and only once this is called the Travelling sells man’s problem which is NP-Complete.

We can solve it with DP that uses exponential time.

dp[s][i] := min distance to visit nodes (represented as a binary state s) once and only once and the path ends with node i.

e.g. dp[7][1] is the min distance to visit nodes (0, 1, 2) and ends with node 1, the possible paths could be (0, 2, 1), (2, 0, 1).

Time complexity: O(n^2 * 2^n)

Space complexity: O(n * 2^n)

C++

// Author: Huahua, running time: 20 ms

class Solution {

public:

string shortestSuperstring(vector<string>& A) {

const int n = A.size();

vector<vector<int>> g(n, vector<int>(n));

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

g[i][j] = A[j].length();

for (int k = 1; k <= min(A[i].length(), A[j].length()); ++k)

if (A[i].substr(A[i].size() - k) == A[j].substr(0, k))

g[i][j] = A[j].length() - k;

}

vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX / 2));

vector<vector<int>> parent(1 << n, vector<int>(n, -1));

for (int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();

for (int s = 1; s < (1 << n); ++s) {

for (int j = 0; j < n; ++j) {

if (!(s & (1 << j))) continue;

int ps = s & ~(1 << j);

for (int i = 0; i < n; ++i) {

if (dp[ps][i] + g[i][j] < dp[s][j]) {

dp[s][j] = dp[ps][i] + g[i][j];

parent[s][j] = i;

}

auto it = min_element(begin(dp.back()), end(dp.back()));

int j = it - begin(dp.back());

int s = (1 << n) - 1;

string ans;

while (s) {

int i = parent[s][j];

if (i < 0) ans = A[j] + ans;

else ans = A[j].substr(A[j].length() - g[i][j]) + ans;

s &= ~(1 << j);

j = i;

}

return ans;

}

};

Posts tagged as “TSP”

花花酱 LeetCode 1681. Minimum Incompatibility

Solution: TSP

C++

花花酱 LeetCode 943. Find the Shortest Superstring

Problem

Solution 1: Search + Pruning

C++

Java

Solution 2: DP

C++