Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #Backtracking(pruning branches and thus less than 2^n possible cases are checked.)
- class Solution:
- def maximumGood(self, statements: List[List[int]]) -> int:
- n = len(statements)
- self.res = 0
- def solve(i, mask):
- if i == n:
- self.res = max(self.res, mask.count(1)+mask.count(2))
- return
- temp = mask[:]
- flag = True
- for j in range(n):
- if statements[i][j] == 2:
- continue
- if statements[i][j]+temp[j] == 1:
- flag = False
- break
- temp[j] = statements[i][j]
- if flag==True:
- solve(i+1, temp)
- if mask[i] == 1:
- return
- mask[i] = 0
- solve(i+1, mask)
- solve(0, [2]*n)
- return self.res
- #Brute Force
- class Solution:
- def maximumGood(self, statements: List[List[int]]) -> int:
- n = len(statements)
- def isValid(mask):
- for i in range(n):
- if mask&(1<<i):
- for j in range(n):
- if statements[i][j] + ((mask>>j)&1) == 1:
- return False
- return True
- best = 0
- for i in range(1<<n):
- mask = i
- if isValid(mask):
- tmp = 0
- for j in range(n):
- tmp += (mask>>j)&1
- best = max(best, tmp)
- return best
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement