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?

notes: you can find the problem here