Or_ion's blog

solution to this problem
By Or_ion, 22 months ago, In English

following images shows the problem statement

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
22 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Simple submask dp problem.

Let's count dp[mask]. mask is an integer and it's i-th bit is gonna representate whether i-th skill is owned by Alice. dp[mask] will be equal to mininimum cost of books we need to use to get skill set mask. N <= 15 so mask <= 2^N < 33000.

Let's say binary mask of the initial set of Alice's skills is initMask. Then at start we set dp[initMask] = 0. All other dp values are gonna be equal to +INF. To calculate the dp, we are going to iterate through all the books i and all the masks mask. Then if bookMask[i] represents binary mask of i-th book, formula would be something like: dp[mask | bookMask[i]] = min(dp[mask | bookMask[i]], dp[mask] + bookCost[i]), where | is binary OR. After all the dp's are calculated the answer is the smallest dp[mask] within all masks that contain the set of skills we need to get. If the answer is greater or equal to infinity, that means that Alice can't get such set of skills.

The time complexity is smth like O(2^N * M)

→ Reply