-
Notifications
You must be signed in to change notification settings - Fork 11
/
bitmask.py
90 lines (58 loc) · 2.67 KB
/
bitmask.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from collections import defaultdict
class AssignCap:
# Initialize variables
def __init__(self):
self.allmask = 0
self.total_caps = 100
self.caps = defaultdict(list)
# Mask is the set of persons, i is the current cap number.
def countWaysUtil(self,dp, mask, cap_no):
# If all persons are wearing a cap so we
# are done and this is one way so return 1
if mask == self.allmask:
return 1
# If not everyone is wearing a cap and also there are no more
# caps left to process, so there is no way, thus return 0;
if cap_no > self.total_caps:
return 0
# If we have already solved this subproblem, return the answer.
if dp[mask][cap_no]!= -1 :
return dp[mask][cap_no]
# Ways, when we don't include this cap in our arrangement
# or solution set
ways = self.countWaysUtil(dp, mask, cap_no + 1)
# assign ith cap one by one to all the possible persons
# and recur for remaining caps.
if cap_no in self.caps:
for ppl in self.caps[cap_no]:
# if person 'ppl' is already wearing a cap then continue
if mask & (1 << ppl) : continue
# Else assign him this cap and recur for remaining caps with
# new updated mask vector
ways += self.countWaysUtil(dp, mask | (1 << ppl), cap_no + 1)
ways = ways % (10**9 + 7)
# Save the result and return it
dp[mask][cap_no] = ways
return dp[mask][cap_no]
def countWays(self,N):
# Reads n lines from standard input for current test case
# create dictionary for cap. cap[i] = list of person having
# cap no i
for ppl in range(N):
cap_possessed_by_person = map(int, raw_input().strip().split())
for i in cap_possessed_by_person:
self.caps[i].append(ppl)
# allmask is used to check if all persons
# are included or not, set all n bits as 1
self.allmask = (1 << N) -1
# Initialize all entries in dp as -1
dp = [[-1 for j in range(self.total_caps + 1)] for i in range(2 ** N)]
# Call recursive function countWaysUtil
# result will be in dp[0][1]
print self.countWaysUtil(dp, 0, 1,)
#Driver Program
def main():
No_of_people = input() # number of persons in every test case
AssignCap().countWays(No_of_people)
if __name__ == '__main__':
main()