1434. Number of Ways to Wear Different Hats to Each Other

SourceBiweekly Contest 25 Q4DifficultyHardRating2273

Description

There are n people and 40 types of hats labeled from 1 to 40.

Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the i^th person.

Return the number of ways that n people can wear different hats from each other.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person chooses hat 3, Second person chooses hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats:
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

Solutions

Solution 1: Dynamic Programming

Thinking

There are \(n\le 10\) people and at most \(40\) hats. Assigning hats per person is awkward to compress. Enumerate hats instead and bit-mask who already wears one.

\(f[i][j]\) is the number of ways using the first \(i\) hats with assigned set \(j\). Hat \(i\) may be unused or given to a person \(k\) who likes it and is still free. The answer is \(f[m][2^n-1]\).

We notice that \(n\) is not greater than \(10\), so we consider using DP with state compression to solve this problem.

We define \(f[i][j]\) as the number of ways to assign the first \(i\) hats to the people whose state is \(j\). Here \(j\) is a binary number, which represents a set of people. We have \(f[0][0]=1\) at the beginning, and the answer is \(f[m][2^n - 1]\), where \(m\) is the maximum number of hats and \(n\) is the number of people.

Consider \(f[i][j]\). If we don't assign the \(i\)-th hat to anyone, then \(f[i][j]=f[i-1][j]\); if we assign the \(i\)-th hat to the person \(k\) who likes it, then \(f[i][j]=f[i-1][j \oplus 2^k]\). Here \(\oplus\) denotes the XOR operation. Therefore, we can get the state transition equation:

\[ f[i][j]=f[i-1][j]+ \sum_{k \in like[i]} f[i-1][j \oplus 2^k] \]

where \(like[i]\) denotes the set of people who like the \(i\)-th hat.

The final answer is \(f[m][2^n - 1]\), and the answer may be very large, so we need to take it modulo \(10^9 + 7\).

Time complexity \(O(m \times 2^n \times n)\), space complexity \(O(m \times 2^n)\). Here \(m\) is the maximum number of hats, which is no more than \(40\) in this problem; and \(n\) is the number of people, which is no more than \(10\) in this problem.

Python3JavaC++GoTypeScript

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        g = defaultdict(list)
        for i, h in enumerate(hats):
            for v in h:
                g[v].append(i)
        mod = 10**9 + 7
        n = len(hats)
        m = max(max(h) for h in hats)
        f = [[0] * (1 << n) for _ in range(m + 1)]
        f[0][0] = 1
        for i in range(1, m + 1):
            for j in range(1 << n):
                f[i][j] = f[i - 1][j]
                for k in g[i]:
                    if j >> k & 1:
                        f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod
        return f[m][-1]

class Solution {
    public int numberWays(List<List<Integer>> hats) {
        int n = hats.size();
        int m = 0;
        for (var h : hats) {
            for (int v : h) {
                m = Math.max(m, v);
            }
        }
        List<Integer>[] g = new List[m + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 0; i < n; ++i) {
            for (int v : hats.get(i)) {
                g[v].add(i);
            }
        }
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[m + 1][1 << n];
        f[0][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k : g[i]) {
                    if ((j >> k & 1) == 1) {
                        f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
                    }
                }
            }
        }
        return f[m][(1 << n) - 1];
    }
}

class Solution {
public:
    int numberWays(vector<vector<int>>& hats) {
        int n = hats.size();
        int m = 0;
        for (auto& h : hats) {
            m = max(m, *max_element(h.begin(), h.end()));
        }
        vector<vector<int>> g(m + 1);
        for (int i = 0; i < n; ++i) {
            for (int& v : hats[i]) {
                g[v].push_back(i);
            }
        }
        const int mod = 1e9 + 7;
        int f[m + 1][1 << n];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k : g[i]) {
                    if (j >> k & 1) {
                        f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
                    }
                }
            }
        }
        return f[m][(1 << n) - 1];
    }
};

func numberWays(hats [][]int) int {
    n := len(hats)
    m := 0
    for _, h := range hats {
        m = max(m, slices.Max(h))
    }
    g := make([][]int, m+1)
    for i, h := range hats {
        for _, v := range h {
            g[v] = append(g[v], i)
        }
    }
    const mod = 1e9 + 7
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, 1<<n)
    }
    f[0][0] = 1
    for i := 1; i <= m; i++ {
        for j := 0; j < 1<<n; j++ {
            f[i][j] = f[i-1][j]
            for _, k := range g[i] {
                if j>>k&1 == 1 {
                    f[i][j] = (f[i][j] + f[i-1][j^(1<<k)]) % mod
                }
            }
        }
    }
    return f[m][(1<<n)-1]
}

function numberWays(hats: number[][]): number {
    const n = hats.length;
    const m = Math.max(...hats.flat());
    const g: number[][] = Array.from({ length: m + 1 }, () => []);
    for (let i = 0; i < n; ++i) {
        for (const v of hats[i]) {
            g[v].push(i);
        }
    }
    const f: number[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: 1 << n }, () => 0),
    );
    f[0][0] = 1;
    const mod = 1e9 + 7;
    for (let i = 1; i <= m; ++i) {
        for (let j = 0; j < 1 << n; ++j) {
            f[i][j] = f[i - 1][j];
            for (const k of g[i]) {
                if (((j >> k) & 1) === 1) {
                    f[i][j] = (f[i][j] + f[i - 1][j ^ (1 << k)]) % mod;
                }
            }
        }
    }
    return f[m][(1 << n) - 1];
}

1434. Number of Ways to Wear Different Hats to Each Other

Description

Solutions

Solution 1: Dynamic Programming

Comments