HackerEarth Bitmask-DP problem

In assignment problem of tutorial ,I didn’t get the logic of dp+bitmasking .please explain.

Ok, Lets start by stating what we are trying to achieve.

We have N jobs to complete and N people to complete it.

Cost[i][j] represents the price we have to pay to get the 'i’th person do the 'j’th task.

Now, our aim is to assign the jobs done in minimum cost such that,

  1. Every Job is assigned to Exactly one person.
  2. One person is assigned exactly one job.

This can be stated as a Linear programming problem,

Subject to constraints:

Xi0 + Xi1 + Xi2 + Xi3 + .... + XiN =  1, for every i in [1,N]

Xij = 1, if ith person does the jth job
      0, Otherwise.

And we have to minimize the function,

Z = Sum [(Cost[i][0] * X[i][0] + Cost[i][1] * X[i][2] + ...... + Cost[i][N] * X[i][N])]  
    for every i in [1,N]

Now, the solution using DP and bitmask:

mask: This is a binary number. if ith bit of mask is 1, then ith job has been assigned.

example : mask = 1100 0001 means that 1st,2nd and 8th jobs has already be assigned.

To check if bit is set and to toggle it we use bitwise operators. Read Here

Now for the dp solution:

answer(mask|(1 << i)) = min(answer(mask|(1 << i)), answer(mask)+cost[k][i])

here mask determines which jobs have assigned.

So, we generate all possible values of mask (0 to 2^N).

Number of people already assigned the job is : k = number of set bits in mask.

i.e People from 0 to k-1 are already assigned jobs.

Now for every job that is not assigned, meaning for every bit that is not set in mask(say bit i):

We find cost if that bit was assigned by:

answer(mask|(1 << i)) = min(answer(mask|(1 << i)), answer(mask)+cost[k][i])

remember here cost[k][i] is assigning the job i to k’th person. and mask|(1 << i)
means that i’th job gets assigned.

Just FYI, there exist a O(n^3) solution for these types of problems, read HERE

4 Likes

"Number of people already assigned the job is k = number of set bits in the mask.

i.e People from 0 to k-1 are already assigned jobs.

In this statement, why are we assigning already assigned k tasks to people from 0 to k-1 only, why not people from k-1 to N?

3 YEARS LATER