C++, GDB Lecture and Valid Subsets Problem

February 04, 2021

Introduction to C++ and GDB
Chickens and Zombies problem
Include the standard template library (STL)
```
 #include <bits/stdc++.h>
```
Include these 2 lines for fast input and output
```
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
```
Instead of using vector<bool>, you can use vector<char>

Geppetto
Method 1: Bitmask (\(O(2^{n}m) = O(2^{n}n^{2})\))

 int main() {
     int n, m, a, b;
     cin >> n >> m;
     unordered_set<int> masks;
     for (int i = 0; i < m; i++) {
         cin >> a >> b;
         a--; b--;
         masks.insert((1 << a) | (1 << b));
     }

     int count = 0;
     for (int i = 0; i < (1 << n); i++) {
         bool ok = true;
         for (auto m : masks) {
             if ((i & m) == m) {
                 ok = false;
                 break;
             }
         }

         if (ok)
             count++;
     }

     cout << count;
     return 0;
 }

Method 2: Backtracking (\(O(2^{n}n)\))
Choose or not choose. If choose, then don’t put the ingredients that conflict

 int n, m;
 bool adj[maxn][maxn];
 int cnt_out[maxn];
 int res = 0;
    
 void go(int idx)
 {
     if(idx == n+1)
     {
         ++res;
         return;
     }
     // do not choose this
     go(idx + 1);
     // try to choose this
     if(cnt_out[idx] == 0)
     {
         for(int j = idx + 1; j <= n; ++j)
         {
             if( adj[idx][j] )
             {
                 cnt_out[j] += 1;
             }
         }
         go(idx + 1);
         // undo
         for(int j = idx + 1; j <= n; ++j)
         {
             if( adj[idx][j] )
             {
                 cnt_out[j] -= 1;
             }
         }
     }
 }
    
 int main()
 {
     cin >> n >> m;
     int u, v;
     for(int i = 0; i < m; ++i)
     {
         cin >> u >> v;
         adj[u][v] = adj[v][u] = true;
     }
     go(1);
     cout << res;
     return 0;
 }