Python 3: TC O(2**n) SC O(2**n): DFS + Caching, Three States: Unknown, Good, Bad
Intuition\n\nThis is a tricky problem because\n1. it\'s a complicated logic puzzle\n2. the problem is a bit poorly worded, perhaps on purpose (see next)\n3. the
# Intuition\n\nThis is a tricky problem because\n1. it\'s a complicated logic puzzle\n2. the problem is a bit poorly worded, perhaps on purpose (see next)\n3. there are really three states for each person as you solve: good / bad / unknown\n\n**If a person is good, all of their statements are true (or there\'s a contradiction)**\n\n**If a person is bad, each of their statements INDIVIDUALLY may be true OR false**\n\n## Insight 1: There are THREE States\n\nIt\'s tempting to look at the problem and think: everyone is either good or bad.\n\nBut really there are three:\n* good\n* bad\n* unknown\n\nThis is important because at the beginning we haven\'t determined if anyone is good or bad yet.\n\nIt matters because if we look at person `i`:\n* if they\'re good, we must trust their statements (or return -inf because we found a contradiction)\n* if they\'re bad, their statements are meaningless (see below) and we move on\n* if unknown then we need to decide if they\'re good (if that doesn\'t lead to a contradiction) or bad and proceed in both cases\n\n**Technically:** there are maybe actually FIVE states:\n* for people `j > i` we haven\'t visited yet in DFS (see below): good/bad/unknown\n* for people we already visited `j <= i`: they\'re either good or bad\n\n## Insight 2: Bad == Ignore Statements\n\nIf someone is bad then each statement individually can be true or false. If a choice would lead to a contradiction then pick the other value.\n\nWe might think that iterating over all non-contradictory good/bad choices for each person `j` a bad person `i` made statements about helps.\n\nBut it turns out that it does not, because we would be taking the maximum over all patterns. Therefore we\'ll explore all valid arrangements anyway regardless of what we choose right now.\n\nAnother way to think about it is that all people in every solution are either good or bad, there\'s no third state. Therefore the fact that a bad person made statements about them doesn\'t change that fact. The bad person\'s statements also don\'t tell us which of the two choices are true or even if one is more likely than the other. Therefore the fact that a bad person makes statement (0/1) or not (2) doesn\'t matter!\n\n## Insight 3: DFS + Backtracking -> DFS + Caching\n\nThe last thing to note is that\n* for a solution we must decide if each person is good or bad: implies we need to iterate over `i=0..n-1`\n* we need to know who we know is good so far: a bit set\n* we also need to know who is bad so far: another bit set\n\n**The most obvious approach is DFS+backtracking.** It\'s what the sample problem explanations are doing, and `n=15` comports with that. For each person `i` we can\n* tentatively accept them as good, but only if doing so doesn\'t conflict with prior good/bad determinations we\'ve made\n* tentatively accept them as bad, but only if doing so doesn\'t conflict with deciding they were good earlier (indirectly via trusting another person who said they\'re good)\n\n**Optimization:** with the logic above we can see that if we made a series of choices for `0..i-1` so far that results in some `g` and `b` bit sets, then the specific pattern of choices doesn\'t matter. All that matters is the tentative statuses of each person as good, bad, or unknown. Therefore we might have some repeated subproblems where different choices made on the first few people result in the same decisions being made about later people (or perhaps the same lack of decisions). **Therefore we can use DFS + backtracking.**\n\n# Approach\n\nUse bit sets to track whether each person thus far has been tentatively determined to be good, bad, or neither.\n* good: the `g` bit set\n* bad: the `b` bit set\n* neither: any bits that are neither in good nor bad\n\nTo make sure we check each person\'s choices we iterate through `i=0..n-1`. For each person we\n* if good or neither: consider them good, check for conflicts, proceed with them as good\n* if bad or neither: consider them bad, check for conflict, proceed with them as bad\n\nTo speed up this process of checking for conflicts I made `good` and `bad`, bit sets where e.g. `good[i]` has a bit set for each person `i` said was good.\n\nThis way if we take `i` as being good, then we can check for conflicts with `good[i] & b > 0`. If it\'s above zero that means a person we already determined was bad (encoded by `b`) is also someone that `i` said was good: `good[i]`. This is a contradiction so we must discard this choice.\n\n# Further Optimizations\n\nWe should probably sort by the number of statements made. If we process a bunch of people early that don\'t make many statements then there are probably a lot of combinations that work until we get deep into the DFS tree. But if we make decisions about very opinionated people early then it reduces branching and more quickly leads to contradictions.\n\nI also suspect that we can further achieve early pruning as follows. When we tentatively accept someone as good, some of their statements will be that another person is good. Therefore we should check those other people\'s statements about who is good and bad right now to see if any of them conflict with the `b` and `g` bit sets thus far. This way we can more quickly prune situations where e.g. `i < j` says `j` is good, and we accept `i` as good, but then much later we discover that `j` says `i` is bad. So being more aggressive with conflict checks can help us a lot by reducing branching.\n\nSpeaking of the `i`, `j` pairs: situations such as `i` states `j` is good, but `j` states `i` is bad. Here we know that `i` and `j` are not independent choices because if we choose `i` as good, then we will get a conflict. Therefore we know `i` can never be good, and therefore `i` must be bad. Therefore anyone that says `i` is good must be lying and thus bad.\n\nDetecting basic patterns like this early and simplifying accordingly, perhaps by setting the corresponding bits in the starting value of `b`, would also reduce the amount of time we spend. Every removed choice like this reduces time and memory by 2x.\n\n# Complexity\n- Time complexity: `O(2**n)`. For each person we have at most two choices: we can tentatively decide they are good or bad and proceed. The checks we do are `O(1)` for each choice because we use bit sets for `O(1)` conflict checks and updates to `b` and `g`.\n\n- Space complexity: `O(2**n)` because there are the same `2**n` choices at most, at worst they all result in different patterns of `b` and `g`, and thus we need to cache the answer and `O(1)` memory used by the arguments\n\n# Code\n```python3 []\nclass Solution:\n    def maximumGood(self, statements: List[List[int]]) -> int:\n        # statements[i][j] means i said j is\n        #   0: bad\n        #   1: good\n        #   2: didn\'t say anything\n\n        # some people always tell the truth\n        # others lie at least once\n\n        # return maximum people that can be good\n\n        n = len(statements)\n        \n        # suppose we assume everyone is telling the truth: all good\n        # if we find a statement by a good person i that says j is bad, but then we called j good, we have a conflict\n        \n        # suppose we take i as good\n        #     can only do this if it doesn\'t conflict with our existing choices\n        #     anyone they say is bad we toggle off\n        # or we take i as bad: no information content, continue\n\n        # suppose we trust person i:\n        #    anyone they say is good must be good\n        #    anyone they say is bad must be bad\n        #\n        # suppose we\'ve made decisions, resulting in bit sets of people known to be good or bad thus far\n\n        # then if bad[i] & good we have a conflict: can\'t choose this person\n        #      if good[i] & bad then we also have a conflict\n\n        good = [0]*n\n        bad = [0]*n\n        for i, row in enumerate(statements):\n            for j, s in enumerate(row):\n                if s == 0: bad[i] |= 1 << j\n                elif s == 1: good[i] |= 1 << j\n\n        ALL = (1 << n) - 1\n\n        # we decide if each person is good or bad\n        #    good: always tells the truth\n        #    bad: may tell the truth, or may be lying, in each statement\n\n        @cache\n        def maxGood(i: int, g: int, b: int) -> float:\n            \n            if i == n:\n                return int.bit_count(g) # good people\n\n            bit = 1 << i\n\n            # if bit & g: already decided on good\n            # if bit & b: already decided on bad\n            # else: can choose either\n\n            ans = -math.inf\n\n            maybeGood = (g & bit) or not (b & bit)\n            maybeBad = (b & bit) or not (g & bit)\n            \n\n            if maybeGood and good[i] & b == 0 and bad[i] & g == 0:\n                # good and telling the truth\n                ans = max(ans, maxGood(i+1, g | good[i] | bit, b | bad[i]))\n\n            if maybeBad:\n                # bad, each statement may be true or not independently so there\'s no information given by their answers\n                ans = max(ans, maxGood(i+1, g, b | bit))\n\n            return ans\n\n        return maxGood(0, 0, 0) # start with person 0, nobody known to be good or bad yet\n```
['Python3']