2151. Maximum Good People Based on Statements Hard

1/**
2 * [2151] Maximum Good People Based on Statements
3 *
4 * There are two types of persons:
5 * 
6 * 	The good person: The person who always tells the truth.
7 * 	The bad person: The person who might tell the truth and might lie.
8 * 
9 * You are given a 0-indexed 2D integer array statements of size n x n that represents the statements made by n people about each other. More specifically, statements[i][j] could be one of the following:
10 * 
11 * 	0 which represents a statement made by person i that person j is a bad person.
12 * 	1 which represents a statement made by person i that person j is a good person.
13 * 	2 represents that no statement is made by person i about person j.
14 * 
15 * Additionally, no person ever makes a statement about themselves. Formally, we have that statements[i][i] = 2 for all 0 <= i < n.
16 * Return the maximum number of people who can be good based on the statements made by the n people.
17 *  
18 * Example 1:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2022/01/15/logic1.jpg" style="width: 600px; height: 262px;" />
20 * Input: statements = [[2,1,2],[1,2,2],[2,0,2]]
21 * Output: 2
22 * Explanation: Each person makes a single statement.
23 * - Person 0 states that person 1 is good.
24 * - Person 1 states that person 0 is good.
25 * - Person 2 states that person 1 is bad.
26 * Let's take person 2 as the key.
27 * - Assuming that person 2 is a good person:
28 *     - Based on the statement made by person 2, person 1 is a bad person.
29 *     - Now we know for sure that person 1 is bad and person 2 is good.
30 *     - Based on the statement made by person 1, and since person 1 is bad, they could be:
31 *         - telling the truth. There will be a contradiction in this case and this assumption is invalid.
32 *         - lying. In this case, person 0 is also a bad person and lied in their statement.
33 *     - Following that person 2 is a good person, there will be only one good person in the group.
34 * - Assuming that person 2 is a bad person:
35 *     - Based on the statement made by person 2, and since person 2 is bad, they could be:
36 *         - telling the truth. Following this scenario, person 0 and 1 are both bad as explained before.
37 *             - Following that person 2 is bad but told the truth, there will be no good persons in the group.
38 *         - lying. In this case person 1 is a good person.
39 *             - Since person 1 is a good person, person 0 is also a good person.
40 *             - Following that person 2 is bad and lied, there will be two good persons in the group.
41 * We can see that at most 2 persons are good in the best case, so we return 2.
42 * Note that there is more than one way to arrive at this conclusion.
43 * 
44 * Example 2:
45 * <img alt="" src="https://assets.leetcode.com/uploads/2022/01/15/logic2.jpg" style="width: 600px; height: 262px;" />
46 * Input: statements = [[2,0],[0,2]]
47 * Output: 1
48 * Explanation: Each person makes a single statement.
49 * - Person 0 states that person 1 is bad.
50 * - Person 1 states that person 0 is bad.
51 * Let's take person 0 as the key.
52 * - Assuming that person 0 is a good person:
53 *     - Based on the statement made by person 0, person 1 is a bad person and was lying.
54 *     - Following that person 0 is a good person, there will be only one good person in the group.
55 * - Assuming that person 0 is a bad person:
56 *     - Based on the statement made by person 0, and since person 0 is bad, they could be:
57 *         - telling the truth. Following this scenario, person 0 and 1 are both bad.
58 *             - Following that person 0 is bad but told the truth, there will be no good persons in the group.
59 *         - lying. In this case person 1 is a good person.
60 *             - Following that person 0 is bad and lied, there will be only one good person in the group.
61 * We can see that at most, one person is good in the best case, so we return 1.
62 * Note that there is more than one way to arrive at this conclusion.
63 * 
64 *  
65 * Constraints:
66 * 
67 * 	n == statements.length == statements[i].length
68 * 	2 <= n <= 15
69 * 	statements[i][j] is either 0, 1, or 2.
70 * 	statements[i][i] == 2
71 * 
72 */
73pub struct Solution {}
74
75// problem: https://leetcode.com/problems/maximum-good-people-based-on-statements/
76// discuss: https://leetcode.com/problems/maximum-good-people-based-on-statements/discuss/?currentPage=1&orderBy=most_votes&query=
77
78// submission codes start here
79
80impl Solution {
81    pub fn maximum_good(statements: Vec<Vec<i32>>) -> i32 {
82        0
83    }
84}
85
86// submission codes end
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_2151() {
94    }
95}
96