“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

I only finished the first three questions in the competition, and there was more than an hour left for the last one. I wrote and drew on the draft, feeling confused for a while, and finally gave up the treatment. I saw that the top guys in the list solved this problem in less than three minutes, which is the gap between me and the big guys. This is the fourth question in Weekly Contest 277. It’s Hard. For me, it’s really Hard. The test is DFS.

describe

There are two types of persons:

  • The good person: The person who always tells the truth.
  • The bad person: The person who might tell the truth and might lie.

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:

  • 0 which represents a statement made by person i that person j is a bad person.
  • 1 which represents a statement made by person i that person j is a good person.
  • 2 represents that no statement is made by person i about person j.

Additionally, no person ever makes a statement about themselves. Formally, we have that statements[i][i] = 2 for all 0 <= i < n.

Return the maximum number of people who can be good based on the statements made by the n people.

Example 1:

Input: statements = [[2,1,2],[1,2],[2,0,2]] Output: 2 Explanation: Each person makes a single statement. - Person 0 states that person 1 is good. - Person 1 states that person 0 is good. - Person 2 states that person 1 is bad. Let's take person 2 as the key. - Assuming that person 2 is a good person: - Based on the statement made by person 2, person 1 is a bad person. - Now we know for sure that person 1 is bad and person 2 is good. - Based on the statement made by person 1, and since person 1 is bad, they could be: - telling the truth. There will be a contradiction in this case and this assumption is invalid. - lying. In this case, person 0 is also a bad person and lied in their statement. - Following that person 2 is a good person, there will be only one good person in the group. - Assuming that person 2 is a bad person: - Based on the statement made by person 2, and since person 2 is bad, they could be: - telling the truth. Following this scenario, person 0 and 1 are both bad as explained before. - Following that person 2 is bad but told the truth, there will be no good persons in the group. - lying. In this case person 1 is a good person. - Since person 1 is a good person, person 0 is also a good person. - Following that person 2 is bad and lied, there will be two good persons in the group. We can see that at most 2 persons are good in the best case, so we return 2. Note that there is more than one way to arrive at this conclusion.Copy the code

Note:

n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] is either 0, 1, or 2.
statements[i][i] == 2
Copy the code

parsing

There are two kinds of people nowadays: good people definitely tell the truth. A bad man may tell the truth and may lie. Given an array of 2D integer statements with a 0 index, size n x n, representing statements made by n individuals to each other. Statements [I][j] can be one of the following:

  • Zero means the ith person says the JTH person is bad
  • The 1 is the ith person saying the JTH person is a good guy
  • 2 means that person I does not make any statement about person J

Besides, no one will say anything about themselves. Based on the statements of n people, there could be at most a few good people returned.

Finish see this problem statement and examples of a text I knew, this isn’t a good topic (to me), when did this problem is to think, according to the direction of figure because of possible statement between each other, but after watching the above example a multifarious feel good, if a bad guy, so will put a lot of related statements are overturned, I don’t think this is the right direction. Later, I tried to find out if there was any rule, but I couldn’t find it. And finally, recursion, because the constraint is n is at most 15, and by recursing through different situations, it’s possible to find the most people, but how to design recursion is a problem.

Saw a big man’s answer just suddenly realized, really is such as enlightened, a language wake up dreamers. There are n possible combinations of good guys and bad guys in the recursion (DFS) for persons. Each time a good person is added to Persons, or a bad person is added to Persons, the recursion is repeated on a different branch, and the recursion stops when the length of the new list is n. In this recursive function, we are constantly updating the maximum number of possible good people, which we have defined with the function hasmaobject, to determine if there is a conflict between persons and statements in the current recursion branch. If there is no conflict, it means that the combination of good and bad people on this branch is in line with the meaning of the question. We compare the current number of good people with the result and update the result with a larger value.

Since there are n people, each of whom has two different roles, there are 2^N possibilities, each of which will require a two-layer loop in the hasmaodelling function. Therefore, the time complexity of this algorithm is O(2^ n * n ^2), and thanks to the restriction, n is at most 15, Otherwise I’m running out of time. The space complexity is order N, and there’s nothing to say about that.

Here is the big guy’s code, is really clear thinking, code introduction, admire.

answer

class Solution: def maximumGood(self, statements: List[List[int]]) -> int: BAD, GOOD, NO_STATEMENT = 0, 1, 2 N = len(statements) def hasContradiction(persons): for i in range(N): for j in range(N): if statements[i][j] == NO_STATEMENT: continue if persons[i] == GOOD: if statements[i][j] ! = persons[j]: return True return False ans = 0 def dfs(persons): nonlocal ans if len(persons) == N: if not hasContradiction(persons): ans = max(ans, persons.count(GOOD)) else: dfs(persons+[GOOD]) dfs(persons+[BAD]) dfs([]) return ansCopy the code

The results

91/91 Test cases passed. Status: Accepted Runtime: 4252 MS Memory Usage: 14.3 MBCopy the code

The original link

Leetcode.com/contest/wee…

Your support is my biggest motivation