Tanjiro vs Demons

Author : manorath13

Required Knowledge : Bit Mask, DP

Time Complexity : $O(M \cdot 2^N)$

Editorialist : manorath13

Approach:

The idea is using $bitmask$ $dp$.

Since there are only $12$ or less demons we can store them as a bitmask.

Ex: Say the demons $1,3,4,12$ can be represented as bitmask - $100000001101$.

Let, $c$ be the cost array of the katanas and $d$ be the array consisting bitmask of demons that can be slayed by ${i^{th}}$ katana.

Now, let $dp[i][b]$ be the minimum cost to to slay demons which are set in the mask b at the ${i^{th}}$ katana.

initial state - $dp[0][0] = 0$ and $dp[0][d[0]] = c[0]$

Lets find $dp[i][b]$

if the ${i^{th}}$ katana is not chosen at bit b:

$dp[i][b] = min(dp[i-1][b],dp[i][b])$

if the ${i^{th}}$ katana is chosen at bit b:

$dp[i][(b|d[i])] = min(dp[i][(b|d[i])],c[i]+dp[i][b])$

Code using Tabulation:

// Author: Manorath
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long
#define MOD 1000000007
#define cy cout << "YES\n"
#define cn cout << "NO\n"
#define pb push_back
#define ss second
#define ff first
#define sz(x) (int)(x).size()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define fr(i, a, b) for (ll i = (a); i < (ll)(b); ++i)
#define frr(i, a, b) for (ll i = (a); i >= (ll)(b); --i)
#define setbits(x) __builtin_popcountll(x)
#define minel(a) *min_element(all(a))
#define maxel(a) *max_element(all(a))
#define sumall(a) accumulate(all(a), 0ll)

////////////////////////////////////

template <class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &x : a)
        is >> x;
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    for (const auto &x : a)
        os << x << ' ';
    return os;
}

template <class T> 
void _print(T t) { 
    cerr << t << " "; 
}

template <class T> 
void _print(vector<T> v) { 
    cerr << "[ "; 
    for (T i : v) {
        _print(i); 
        cerr << " ";
    } 
    cerr << "]" << nl;
}

//////////////////////////////////////////

const int N = (int)1e5 + 1, INF = (int)1e9+1;


void solve() {
    int n,m;
    cin>>n>>m;
    vector<int> c(m),d(m);
    for(int i=0;i<m;++i){
        cin>>c[i];
        int ki,di=0;
        cin>>ki;
        for(int j=0;j<ki;++j){
            int dj;
            cin>>dj;
            dj--;
            di|= (1ll<<dj);
        }
        d[i] = di;
    }
    
    vector<vector<int>> dp(m,vector<int>((1ll<<n),INF));
    dp[0][0] = 0;
    dp[0][d[0]] = c[0];
    for(int i=1;i<m;++i){
        for(int b=0;b<(1ll<<n);++b){
            dp[i][b] = min(dp[i-1][b],dp[i][b]);
            dp[i][(b|d[i])] = min(dp[i][(b|d[i])],c[i]+dp[i][b]);
        }
    }
    if(dp[m-1][(1ll<<n)-1]==INF){
        cout<<-1;
    }
    else{
        cout<<dp[m-1][(1ll<<n)-1];
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Code using Recursion and Memoization

// Author: Manorath
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
#define MOD 1000000007
#define cy cout << "YES\n"
#define cn cout << "NO\n"
#define pb push_back
#define ss second
#define ff first
#define sz(x) (int)(x).size()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define fr(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define frr(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define setbits(x) __builtin_popcountll(x)
#define minel(a) *min_element(all(a))
#define maxel(a) *max_element(all(a))
#define sumall(a) accumulate(all(a), 0ll)

////////////////////////////////////

template <class T>
istream &operator>>(istream &is, vector<T> &a)
{
  for (auto &x : a)
    is >> x;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a)
{
  for (const auto &x : a)
    os << x << ' ';
  return os;
}
template <class T> void _print(T t){cerr << t <<" ";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]"<<nl;}
//////////////////////////////////////////

const int N = (int)1e3 + 1, INF = (int)1e9, S = (1<<12);
int n,m,b;
// b = (1<<n)-1
vi c,d;

int dp[N][S];

int helper(int i, int bt){
  if(i==m){
    if(bt==b){
      return 0;
    }
    return INF;
  }
  if(dp[i][bt]!=-1) return dp[i][bt];
  int ans = INF;
  ans = min(ans,helper(i+1,bt));
  int t = bt;
  t|= d[i];
  ans = min(ans,c[i]+helper(i+1,t));

  return dp[i][bt] =  ans;
}

void solve() {
  cin>>n>>m;
  c = vi(m);
  d = vi(m);
  b = (1<<n)-1;
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<m;++i){
        cin>>c[i];
        int ki,di=0;
        cin>>ki;
        for(int j=0;j<ki;++j){
            int dj;
            cin>>dj;
            dj--;
            di|= (1ll<<dj);
        }
        d[i] = di;
    }
  int ans = helper(0,0);
  if(ans>=INF) ans = -1;

  cout<<ans;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1, x = 1;;
  // cin >> T;
  while (T--) {
    // cout << "Case #" << x << ": " ; x++;
    solve();
  }
  return 0;
}