Problem statement

https://binarysearch.com/problems/Polyglot-Contest/

Solution

First of all, number of languages can be upto 32, so the is not way we can check all masks for languages. So, instead we will check masks for persons. We have state dp(idx, mask), where idx is the index of language and mask is mask of persons we covered, which know at least one language so-far. Then we have two options:

  1. Either add new language to group of languages we choose, then we can update our mask as mask & ~d2[idx]: here we do difference of sets: d2[idx] is mask for persons indexes who know this language.
  2. Or do not add new language.

Complexity

It is O(2^n * l), where n = len(A) and l is total number of languages.

Code

class Solution:
    def solve(self, A):
        skills = list(set(chain(*A)))
        d = {s:i for i, s in enumerate(skills)}
        d2 = Counter()  #language: persons
        for i, row in enumerate(A):
            for lang in row:
                d2[d[lang]] += 1<<i

        l, n = len(d2), len(A)

        @lru_cache(None)
        def dp(idx, mask):
            if not mask: return 0
            if idx == l: return float("inf")
            return min(dp(idx + 1, mask), 1 + dp(idx + 1, mask & ~d2[idx]))
            
        return dp(0, (1<<n) - 1)