Header Ad

HackerEarth Bob and K - Subset problem solution

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


Post a Comment

0 Comments