Posts tagged as “bitmask”

花花酱 LeetCode 1723. Find Minimum Time to Finish All Jobs

By zxi on January 10, 2021

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the i^th job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 10⁷

Solution 1: All subsets

dp[i][t] := min of max working time by assigning a subset of jobs s to the first i workers.

dp[i][t] = min{max(dp[i – 1][s], cost[s ^ t])} where s is a subset of t.

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

C++

// Author: Huahua

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

const int n = jobs.size();

int dp[13][4096];

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

dp[0][0] = 0;

vector<int> cost(1 << n);

for (int t = 0; t < 1 << n; ++t) {

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

if (t >> j & 1) cost[t] += jobs[j];

dp[1][t] = cost[t]; // do jobs t by one worker

}

for (int i = 2; i <= k; ++i)

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

for (int s = t; s; s = (s - 1) & t)

dp[i][t] = min(dp[i][t], max(dp[i - 1][s], cost[t ^ s]));

return dp[k][(1 << n) - 1];

}

};

Solution 2: Search + Pruning

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

C++

class Solution {

public:

int minimumTimeRequired(vector<int>& jobs, int k) {

vector<int> times(k);

int ans = INT_MAX;

function<void(int, int)> dfs = [&](int i, int cur) {

if (cur >= ans) return;

if (i == jobs.size()) {

ans = cur;

return;

}

unordered_set<int> seen;

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

if (!seen.insert(times[j]).second) continue;

times[j] += jobs[i];

dfs(i + 1, max(cur, times[j]));

times[j] -= jobs[i];

}

};

sort(rbegin(jobs), rend(jobs));

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1681. Minimum Incompatibility

By zxi on December 6, 2020

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;

}

};

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th customer gets are all equal, and
Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

for (int x : nums) ++m[x];

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

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

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

vector<vector<int>> dp(1 << m, vector<int>(n + 1));

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

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

dp[mask][i + 1] |= dp[mask][i];

for (int cur = mask; cur; cur = (cur - 1) & mask)

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

dp[mask][i + 1] = 1;

}

return dp[(1 << m) - 1][n];

}

};

花花酱 LeetCode 1595. Minimum Cost to Connect Two Groups of Points

By zxi on September 23, 2020

You are given two groups of points where the first group has size₁ points, the second group has size₂ points, and size₁ >= size₂.

The cost of the connection between any two points are given in an size₁ x size₂ matrix where cost[i][j] is the cost of connecting point i of the first group and point j of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.

Return the minimum cost it takes to connect the two groups.

Example 1:

Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.

Example 2:

Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.

Example 3:

Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10

Constraints:

size₁ == cost.length
size₂ == cost[i].length
1 <= size₁, size₂ <= 12
size₁ >= size₂
0 <= cost[i][j] <= 100

Solution 1: Bistmask DP

dp[i][s] := min cost to connect first i (1-based) points in group1 and a set of points (represented by a bitmask s) in group2.

ans = dp[m][1 << n – 1]

dp[i][s | (1 << j)] := min(dp[i][s] + cost[i][j], dp[i-1][s] + cost[i][j])

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

C++/Bottom up

class Solution {

public:

int connectTwoGroups(vector<vector<int>>& cost) {

constexpr int kInf = 1e9;

const int m = cost.size();

const int n = cost[0].size();

// dp[i][s] := min cost to connect first i points in group1

// and points (bitmask s) in group2.

vector<vector<int>> dp(m + 1, vector<int>(1 << n, kInf));

dp[0][0] = 0;

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

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

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

dp[i + 1][s | (1 << j)] = min({dp[i + 1][s | (1 << j)],

dp[i + 1][s] + cost[i][j],

dp[i][s] + cost[i][j]});

return dp[m].back();

}

};

花花酱 LeetCode 1542. Find Longest Awesome Substring

By zxi on August 10, 2020

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

Time complexity: O(n)
Space complexity: O(2^10) = O(1)

C++

class Solution {

public:

int longestAwesome(string s) {

constexpr int kInf = 1e9;

vector<int> idx(1024, kInf);

idx[0] = -1;

int mask = 0; // prefix's state 0:even, 1:odd

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

mask ^= (1 << (s[i] - '0'));

ans = max(ans, i - idx[mask]);

// One digit with odd count is allowed.

for (int j = 0; j < 10; ++j)

ans = max(ans, i - idx[mask ^ (1 << j)]);

idx[mask] = min(idx[mask], i);

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int longestAwesome(String s) {

final int n = s.length();

int[] idx = new int[1024];

Arrays.fill(idx, n);

idx[0] = -1;

int mask = 0;

int ans = 0;

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

mask ^= (1 << (s.charAt(i) - '0'));

ans = Math.max(ans, i - idx[mask]);

for (int j = 0; j < 10; ++j)

ans = Math.max(ans,

i - idx[mask ^ (1 << j)]);

idx[mask] = Math.min(idx[mask], i);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def longestAwesome(self, s: str) -> int:

idx = [-1] + [len(s)] * 1023

ans, mask = 0, 0

for i, c in enumerate(s):

mask ^= 1 << (ord(c) - ord('0'))

ans = max([ans, i - idx[mask]]

+ [i - idx[mask ^ (1 << j)] for j in range(10)])

idx[mask] = min(idx[mask], i)

return ans