Hi, I am currently attempting the Maximum Independent Set in the Bitmask DP section of gold. However, I am unable to solve the problem and find editorials online related to the problem. I attempted to use bitmask DP and meet in the middle technique to solve the problem (Code below). Could anyone give me some hints or a link to an editorial that I can take a peek at so I can continue?
My current code:
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxN = 20+2;
void testIO(){
freopen("../test.in","r",stdin);
return;
}
vector<int> adj[2*maxN];
set<int> f[1<<maxN]; //f[i] = set of points that can't be in the independent set i
set<int> f2[1<<maxN]; //f2[i] = set of points in f[i]
set<int> g[1<<maxN]; //g[i] = set of points that can't be in the independent set i
set<int> g2[1<<maxN]; //g2[i] = set of points in g[i]
set<int> h[1<<maxN]; //h[i] = maximum independent set given set of points i
int N,M;
inline void addAll(set<int> &a, set<int> b){ //add all of b to a
auto x = b.begin();
while(x != b.end()){
a.insert(*x);
x++;
}
return;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
testIO();
cin >> N >> M;
for(int i = 1; i <= M; ++i){
int a,b; cin >> a >> b; ++a; ++b;
adj[a].pb(b);
adj[b].pb(a);
}
//f[i]
for(int i = 0; i < (1<<(N/2)); ++i){
for(int j = 1; j <= (N/2); ++j){
if((i&(1<<(j-1))) != 0)continue; //j is already chosen
addAll(f2[i|(1<<(j-1))],f2[i]); f2[i|(1<<(j-1))].insert(j);
if(f[i].count(j) != 0)continue; //including j makes it not independent
if(f[i].size() == 0 && i != 0)continue; //i is not a valid independent set
addAll(f[i|(1<<(j-1))],f[i]);
for(int k = 0; k < adj[j].size(); ++k)f[i|(1<<(j-1))].insert(adj[j][k]);
}
}
//g[i]
for(int i = 0; i < (1<<(N/2+1)); ++i){
for(int j = N/2+1; j <= N; ++j){
if((i&(1<<(j-N/2-1))) != 0)continue; //j is already chosen
addAll(g2[i|(1<<(j-N/2-1))],g2[i]); g2[i|(1<<(j-N/2-1))].insert(j);
if(g[i].count(j) != 0)continue; //including j makes it not independent
if(g[i].size() == 0 && i != 0)continue; //i is not a valid independent set
addAll(g[i|(1<<(j-N/2-1))],g[i]);
for(int k = 0; k < adj[j].size(); ++k)g[i|(1<<(j-N/2-1))].insert(adj[j][k]);
}
}
//h[i]
for(int i = 0; i < (1<<(N/2+1)); ++i){
for(int j = N/2+1; j <= N; ++j){
if(h[i|(1<<(j-N/2-1))].size() < h[i].size()){
h[i|(1<<(j-N/2-1))].clear();
addAll(h[i|(1<<(j-N/2-1))],h[i]);
}
if(g[i].size() == 0)continue; //i is not a valid independent set
if(__builtin_popcount(i) <= h[i].size())continue;
h[i].clear();
addAll(h[i],g[i]);
}
}
//Calculate Answer
int res = 0;
set<int> ans;
for(int i = 0; i < 1<<(N/2); ++i){
int j = (1<<(N/2+1)) - 1;
if(f[i].size() == 0)continue; //i is not a valid independent set
auto x = f[i].begin();
while(x != f[i].end()){
if(*x > N/2){
int k = *x;
j = j & (~(1<<(k-N/2-1)));
}
x++;
}
if(__builtin_popcount(i) + h[j].size() > res){
res = __builtin_popcount(i) + h[j].size();
ans.clear();
addAll(ans,f2[i]);
addAll(ans,h[j]);
}
}
cout << res << '\n';
auto x = ans.begin();
while(x != ans.end()){
cout << *x << '\n';
x++;
}
return 0;
}
Thanks in Advance !