LawlietYagami's blog

By LawlietYagami, history, 7 years ago, In English

I was going through this question which uses DP + Bitmask. But the editorial is too brief to understand and the author assumes everyone's familiarity with DP + Bitmask.

In my understanding,

    for (int i = 1 ; i <= n ; i ++) {
    	for (int k = 1 ; k < 60 ; k ++) {
    		int x = (~fact[k]) & ((1 << 17) - 1);
    		for (int s = x ; ; s = (s - 1) & x) {
                if (dp[i - 1][s] + abs(a[i] - k) < dp[i][s | fact[k]]){
                    dp[i][s | fact[k]] = dp[i-1][s] + abs(a[i]-k);
                }
    		if (s == 0) break;
            }
    	}
    }

We iterate through all the possible values of k , ORing it every time which includes the prime factors in the answer. But why do we add abs(a[i] - k) in the dp, how does it help in identifying the answer? And once the dp matrix is set how do we retrieve the answer? Any help on the problem is appreciated.

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

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

This problem is very well explained in this blog.
To retrieve the answer for any state of your dp you should remember k which you changed a[i] to.
You can see my code for this problem to understand better.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, now I understand better. Just a last question, for the last row in dp array, the answer is the minimum column which gives the answer, and then you negate the primes marked by bitmask by pos &= (~pr[come[i][pos]]); since the n-1 th answer should have disjoint set of primes, then you retrive the minimum answer for that set of primes from dp array. Is it right or am I missing something?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. dp[n][mask] means that we changed all numbers, used primes from mask and abs(a[1] — b[1]) + ... + abs(a[n] — b[n]) = dp[n][mask]. Our goal is to minimize this value so we choose the mask with minimal dp[n][mask]. And then we retrieve the answer negating primes used in current b[i];