Advertisement
DeepRest

Maximum Good People Based on Statements

Jan 23rd, 2022 (edited)
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.62 KB | None | 0 0
  1. #Backtracking(pruning branches and thus less than 2^n possible cases are checked.)
  2. class Solution:
  3.     def maximumGood(self, statements: List[List[int]]) -> int:
  4.         n = len(statements)
  5.         self.res = 0
  6.        
  7.         def solve(i, mask):
  8.             if i == n:
  9.                 self.res = max(self.res, mask.count(1)+mask.count(2))
  10.                 return  
  11.            
  12.             temp = mask[:]
  13.             flag = True
  14.             for j in range(n):
  15.                 if statements[i][j] == 2:
  16.                     continue
  17.                 if statements[i][j]+temp[j] == 1:
  18.                     flag = False
  19.                     break
  20.                 temp[j] = statements[i][j]
  21.             if flag==True:
  22.                 solve(i+1, temp)
  23.            
  24.             if mask[i] == 1:
  25.                 return
  26.             mask[i] = 0  
  27.             solve(i+1, mask)
  28.            
  29.        
  30.         solve(0, [2]*n)
  31.         return self.res
  32.  
  33. #Brute Force
  34. class Solution:
  35.     def maximumGood(self, statements: List[List[int]]) -> int:
  36.         n = len(statements)
  37.        
  38.         def isValid(mask):
  39.             for i in range(n):
  40.                 if mask&(1<<i):
  41.                     for j in range(n):
  42.                         if statements[i][j] + ((mask>>j)&1) == 1:
  43.                             return False
  44.             return True
  45.    
  46.         best = 0
  47.         for i in range(1<<n):
  48.             mask = i  
  49.             if isValid(mask):
  50.                 tmp = 0
  51.                 for j in range(n):
  52.                     tmp += (mask>>j)&1
  53.                 best = max(best, tmp)
  54.         return best
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement