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.
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.
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?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];