On problem of COCI 2022-2023 #contest5 task Diskurs, the official editorial gave an solution on bitmask DP. I have questions on how it works.↵
↵
The problem goes: given a sequence ${a_n}$, you should find $a_j$ for each i that $a_i, a_j$ shares the greatest hamming distance. (hamming distance is the least step to turn one bitmask to another with changing a bit each time.)↵
↵
The solution says that `hamming(x, y) = popcount(x) + popcount(y) − 2 popcount(x & y)`, so let `DP(mask)=max_{x\in a}(popcount(x) − 2 popcount(x & mask^c))` ($x^c$ is the binarial flip of $x$)↵
↵
And there goes the std:↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int BITS = 20;↵
↵
int a[1 << BITS];↵
int dpUp[1 << BITS];↵
int dpDown[1 << BITS];↵
int exists[1 << BITS];↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
int n, m; cin >> n >> m;↵
↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
exists[a[i]] = 1;↵
}↵
↵
for (int mask = 0; mask < (1 << BITS); ++mask) {↵
dpUp[mask] = -BITS;↵
if (exists[mask]) dpUp[mask] = __builtin_popcount(mask);↵
↵
for (int i = 0; i < BITS; ++i) {↵
if ((1 << i) & mask) {↵
dpUp[mask] = max(dpUp[mask], dpUp[mask ^ (1 << i)]);↵
}↵
}↵
}↵
↵
for (int mask = (1 << BITS) - 1; mask >= 0; --mask) {↵
↵
dpDown[mask] = dpUp[mask];↵
↵
for (int i = 0; i < BITS; ++i) {↵
if ((1 << i) & mask) continue;↵
dpDown[mask] = max(dpDown[mask], dpDown[mask | (1 << i)] - 2);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
int complement = ((1 << BITS) - 1) ^ a[i];↵
cout << __builtin_popcount(a[i]) + dpDown[complement];↵
↵
cout << (i == n - 1 ? '\n' : ' ');↵
}↵
}↵
~~~~~↵
↵
It is really confusing that what's dpUP and dpDOWN doing here. Also, it's really confusing why the solution is doing so.↵
↵
Therefore, I think I need the explanation of the solution. Do you guys have some articles on that kinds of bitmask DP?↵
↵
Thank you so much.↵
↵
notes: you can find the problem [here](https://hsin.hr/coci/archive/2022_2023/)
↵
The problem goes: given a sequence ${a_n}$, you should find $a_j$ for each i that $a_i, a_j$ shares the greatest hamming distance. (hamming distance is the least step to turn one bitmask to another with changing a bit each time.)↵
↵
The solution says that `hamming(x, y) = popcount(x) + popcount(y) − 2 popcount(x & y)`, so let `DP(mask)=max_{x\in a}(popcount(x) − 2 popcount(x & mask^c))` ($x^c$ is the binarial flip of $x$)↵
↵
And there goes the std:↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int BITS = 20;↵
↵
int a[1 << BITS];↵
int dpUp[1 << BITS];↵
int dpDown[1 << BITS];↵
int exists[1 << BITS];↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(0);↵
int n, m; cin >> n >> m;↵
↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
exists[a[i]] = 1;↵
}↵
↵
for (int mask = 0; mask < (1 << BITS); ++mask) {↵
dpUp[mask] = -BITS;↵
if (exists[mask]) dpUp[mask] = __builtin_popcount(mask);↵
↵
for (int i = 0; i < BITS; ++i) {↵
if ((1 << i) & mask) {↵
dpUp[mask] = max(dpUp[mask], dpUp[mask ^ (1 << i)]);↵
}↵
}↵
}↵
↵
for (int mask = (1 << BITS) - 1; mask >= 0; --mask) {↵
↵
dpDown[mask] = dpUp[mask];↵
↵
for (int i = 0; i < BITS; ++i) {↵
if ((1 << i) & mask) continue;↵
dpDown[mask] = max(dpDown[mask], dpDown[mask | (1 << i)] - 2);↵
}↵
}↵
↵
for (int i = 0; i < n; ++i) {↵
int complement = ((1 << BITS) - 1) ^ a[i];↵
cout << __builtin_popcount(a[i]) + dpDown[complement];↵
↵
cout << (i == n - 1 ? '\n' : ' ');↵
}↵
}↵
~~~~~↵
↵
It is really confusing that what's dpUP and dpDOWN doing here. Also, it's really confusing why the solution is doing so.↵
↵
Therefore, I think I need the explanation of the solution. Do you guys have some articles on that kinds of bitmask DP?↵
↵
Thank you so much.↵
↵
notes: you can find the problem [here](https://hsin.hr/coci/archive/2022_2023/)
