Problem on Bitmask DP for help

Правка en3, от zhutiance, 2023-12-16 12:49:22

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский zhutiance 2023-12-16 12:49:32 0 (published)
en3 Английский zhutiance 2023-12-16 12:49:22 34 Tiny change: 'sk DP?\n\nnotes:' -> 'sk DP?\n\nThank you so much.\n\nnotes:'
en2 Английский zhutiance 2023-12-16 12:45:20 1897
en1 Английский zhutiance 2023-12-16 08:06:47 262 Initial revision (saved to drafts)