Sponsored
Sponsored
This approach involves using backtracking to try all possible assignments of hats by recursively assigning hats to people.
We use memoization to store already computed results to avoid redundant calculations, improving efficiency.
Time Complexity: O(2^n * 40) where `n` is the number of people.
Space Complexity: O(2^n * 40) due to memoization storage.
1MOD = 10**9 + 7
2
3def number_ways(hats):
4 n = len(hats)
5 all_mask = (1 << n) - 1
6 dp = {}
7 hat_to_people = [[] for _ in range(41)]
8 for person, hat_list in enumerate(hats):
9 for hat in hat_list:
10 hat_to_people[hat].append(person)
11
12 def ways(hat, mask):
13 if mask == all_mask:
14 return 1
15 if hat > 40:
16 return 0
17 if (hat, mask) in dp:
18 return dp[(hat, mask)]
19 ans = ways(hat + 1, mask)
20 for person in hat_to_people[hat]:
21 if mask & (1 << person) == 0:
22 ans += ways(hat + 1, mask | (1 << person))
23 ans %= MOD
24 dp[(hat, mask)] = ans
25 return ans
26
27 return ways(1,0)We implemented a `ways` function that checks each hat number iteratively and recursively assigns it to available people.
Using a bit mask helps track which people have already been assigned hats.
Memoization is employed to cache results of previously computed states.
We use dynamic programming and bitmasking to efficiently calculate the number of distinct hat placements.
Each state is represented by a bitmask indicating which people have been assigned hats.
Transition between states occurs by considering each hat for each person who prefers it.
Time Complexity: O(2^n * 40)
Space Complexity: O(2^n * 40)
1import java.util.*;
2
3
This Java solution uses bitmasking and memoization, implementing a depth-first search while protecting against over-counting by storing results in a map.