# Gold Bitmask DP Max Independent Set

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;
}

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;
}
//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
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
}
}
//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
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
}
}
//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();
}
if(g[i].size() == 0)continue; //i is not a valid independent set
if(__builtin_popcount(i) <= h[i].size())continue;
h[i].clear();
}
}
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();
}
}
cout << res << '\n';
auto x = ans.begin();
while(x != ans.end()){
cout << *x << '\n';
x++;
}
return 0;
}

``````

Idk about an editorial, but you can check the AC submissions on that website or the first USACO Guide user solution. Not sure why your solution uses `set`s.