LeetCode 2151. Maximum Good People Based on Statements

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        int n = statements.size(), ans = 0;
        vector<int> gg(n), bb(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (statements[i][j] == 0) {
                    bb[i] |= (1 << j);
                } else if (statements[i][j] == 1) {
                    gg[i] |= (1 << j);
                }
            }
        }
        function<void(int, int, int)> dfs = [&](int g, int b, int i) {
            if (g & b) return; // conflict.
            if (i == n) {
                ans = max(ans, __builtin_popcount(g));
                return;
            }
            if (n - __builtin_popcount(b) < ans) return; // pruning.
            // 1. say i is good.
            dfs(g | (1 << i) | gg[i], b | bb[i], i + 1);
            // 2. say i is bad.
            dfs(g, b | (1 << i), i + 1);
        };
        dfs(0, 0, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maximumGood(vector<vector<int>> &statements) {
        int n = statements.size(), ans = 0;
        for (int i = 1; i < 1 << n; ++i) { // enumerate each case represented by a bit mask.
            int cnt = 0, valid = true;
            for (int j = 0; j < n && valid; ++j) {
                if ((i >> j) & 1) { // if j is good.
                    for (int k = 0; k < n && valid; ++k) { // check if there is conflict.
                        if (statements[j][k] < 2 && statements[j][k] != ((i >> k) & 1)) {
                            valid = false;
                        }
                    }
                    cnt += valid;
                }
            }
            if (valid) ans = max(ans, cnt);
        }
        return ans;
    }
};