Tameshk's blog

Problem On Sets
By Tameshk, history, 4 years ago, In English

Consider 16 non-empty sets each containing up to 2^16 numbers, which are between 0 to 2^16-1 inclusive and each number may appear in more than one sets, obviously. The goal is to find minimum number of numbers which we have at least one number from each set. I tried greedy approach, clearly is wrong, also have found general form of this problem which is np-complete. link Any comments would be highly appreciated.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tameshk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tameshk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Tameshk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I think we can use dynamic programming. Let $$$dp[mask]$$$ be the minimum count of numbers such that if $$$j$$$'th bit is on, then the $$$j$$$'th set has a number among chosen numbers. Obviously $$$dp[0]$$$ is zero. Also let $$$S[mask]$$$ be true iff there is a number such that appears in all the corresponding sets in the $$$mask$$$. To fill $$$S$$$ we can find the $$$mask$$$ for all values from 0 to 2^16 — 1 that $$$j$$$'th bit is on iff the $$$j$$$th set has this number, then for all $$$submasks$$$ of $$$mask$$$ we set the value of $$$S[submask]$$$ equal to true. To solve for $$$dp[mask]$$$ check for every submask of $$$mask$$$ and if $$$S[submask]$$$ is true then you can minimize $$$dp[mask] = min(dp[mask], 1 + dp[mask \oplus submask])$$$. The answer is $$$dp[2^n - 1]$$$ and time complexity is $$$O(3^{16})$$$.

→ Reply