In this HackerEarth Bob and K - Subset problem solution You are given an array of size n consisting of integers. Now, you need to find the number of distinct integers x, such that there exists a sequence of distinct indices i1 < i2 < ... < im, 1 <= m <= k and a[i1] or a[i2] or ... or a[im] = x


HackerEarth Bob and K - Subset problem solution


HackerEarth Bob and K - Subset problem solution.

#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define mp make_pair
#define infile() freopen("samplein.txt","r",stdin);
#define output() freopen("sampleout.txt","w",stdout);
#define ll long long
#define sc(t); scanf("%d",&t);
#define scl(t); scanf("%lld",&t);
#define sc2(n,m); scanf("%d%d",&n,&m);
#define scl2(n,m); scanf("%lld%lld",&n,&m);
#define debug(); printf("tushar\n");
#define N 200005
#define mod 1000000007
#define printi(n) printf("%d",n);
#define inf ((1<<29)-1)
#define linf ((1LL<<60)-1)
const double eps = 1e-9;
set < ll > s ;
set  < int > si ;
set < ll > :: iterator it ; 
vector < ll > v ;
vector < int > vi ;

int n,m,q,k ;
int a[N] ;
int hs[22][10001] = {0} ; 
void func(int x)
{
  for(int i=0;i<=2048;i++)
  hs[x][i]=hs[x-1][i] ; 
  
  for(int i=1;i<=n;i++)
  {
    int y = a[i] ; 
    for(int j=0;j<=6;j++)
    {
      //printf("x = %d y = %d hs[x-1][j] = %d j = %d\n",x,y,hs[x-1][j],j);
      if(hs[x-1][j])
      {
        int tmp = (y|j) ; 
        //printf("tmp = %d\n",tmp)
        if(tmp >2048 )
        {
        //  printf("we are getting tmp as tmp = %d y = %d j = %d\n",tmp,y,j) ;
          assert(0);
        }
        hs[x][tmp]++ ; 
      }
    }
  }
return  ;
}
int main()
{

int i , j , t ;

sc2(n,k) ; 
if(n < 1 || n > 1000 || k  <  1 || k > 20)
{
  printf("n or k out of bounds\n") ; 
  assert(0) ; 
}
hs[0][0]++ ; 
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]) ;
if(a[i] > 1024 ){
printf("a[i] is oout of bounds\n");assert(0) ; }
}

for(i=1;i<=k;i++)
func(i) ; 

for(i=1;i<=5000;i++)
{
  if(hs[k][i])
  s.insert(i) ; 
}
printf("%d\n",s.size());
return 0 ;
}


Second solution

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 4e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

int main() {
  #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);      
    #endif
    int n,k;
    cin>>n>>k;
    assert(n>=1 && n<=10000);
    assert(k>=1 && k<=20);
    set<int>ss;
    int a[n];
    for(int i=0;i<n;i++) {
      cin>>a[i];
      assert(a[i]>=1 && a[i]<=1200);
      ss.insert(a[i]);
    }  
    int ans=(int)ss.size();
    set<int>::iterator it;
    for(int p=2;p<=k;p++) {
      set<int>temp;
      for(int i=0;i<n;i++) {
        for(it=ss.begin();it!=ss.end();it++) {
          int x=((*it)|a[i]);
          temp.insert(x);
        }
      }
      ss.clear();
      ss=temp;
      ans=max(ans,(int)ss.size());
    }
    cout<<ans<<endl;

  return 0;
}