leetcode

commit 6ab4ab94636345f07aaacb244206eeb80aef0efa
parent 05c8686ed873950ead89360be22fbfb967f6ec82
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 16 Jul 2023 18:15:07 +0200

Daily Problem

Diffstat:
A
Problems/1125.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/1125.cpp b/Problems/1125.cpp
@@ -0,0 +1,32 @@
+class Solution {
+public:
+  vector<int> smallestSufficientTeam(vector<string> &req_skills,
+                                     vector<vector<string>> &people) {
+    int n = people.size(), m = req_skills.size();
+    unordered_map<string, int> index;
+    for (int i = 0; i < m; i++) index[req_skills[i]] = i;
+    vector<int> masks(n);
+    for (int i = 0; i < n; i++) {
+      for (string skill : people[i]) masks[i] |= 1 << index[skill];
+    }
+
+    vector<long long> dp(1 << m, (1LL << n) - 1);
+    dp[0] = 0;
+    for (int mask = 1; mask < (1 << m); mask++) {
+      for (int i = 0; i < n; i++) {
+        int smask = mask & ~masks[i];
+        if (smask == mask) continue;
+        long long pmask = dp[smask] | (1LL << i);
+        if (__builtin_popcountll(pmask) < __builtin_popcountll(dp[mask]))
+          dp[mask] = pmask;
+      }
+    }
+
+    long long answerMask = dp[(1 << m) - 1];
+    vector<int> res;
+    for (int i = 0; i < n; i++) {
+      if ((answerMask >> i) & 1) res.push_back(i);
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -425,6 +425,7 @@ for solving problems.
 |  1091  |   Medium   | [Shortest Path in Binary Matrix](Problems/1091.cpp)                                              |
 |  1095  |    Easy    | [Find Numbers with Even Number of Digits](Problems/1095.cpp)                                     |
 |  1099  |    Easy    | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)                        |
+|  1125  |    Hard    | [Smallest Sufficient Team](Problems/1125.cpp)                                                    |
 |  1129  |   Medium   | [Shortest Path with Alternating Colors](Problems/1129.cpp)                                       |
 |  1137  |    Easy    | [N-th Tribonacci Number](Problems/1137.cpp)                                                      |
 |  1140  |   Medium   | [Stone Game II](Problems/1140.cpp)                                                               |