Is there any way to check this testcase? I use codechef ide, and there’s no way such a huge testcase is gonna be pasted in input.
Logical AND with every number in the given array. For different values of X ( whose binary representation must contain K 1 bits)
when you are computing v[i] * =power overflow occurs. Suppose n=10^5 and all the elements has 30th bit as 1 then v[30]=10^5. At i=30 your power value is 2^30 which is approximately 10^9. When you multiply v[i]* power your value will be stored as long long int because your power variable type is “long long int” but when you are assigning this long long value to v[i] which is of type “int” you are getting overflow. So change the type of vector ‘v’ to long long.
All those who looked at the code and wondering about 50-i. I was too lazy to write comparator so i used this trick.
Note that i have no comparator function like you.
isnt this question almost same as The Maximum number from Hackerearth June circuit. ??
why -50 in solution?
accepted solution in python3 with comments .
hope this help to all those who yet did not solved this:
just let me know if anything is unclear.
happy coding
To sort the vector i used a different approach and my code is giving partial correct ans.
Can someone please tell me why only subtask 2 is getting accepted.
Thanks in advance.
+1
Hey Debugger ! my code only passing first testcase, Please help me with your debugging skills.It gives WA for subtask 2.
#include <bits/stdc++.h>
#define ll long long int
#define f(i,a,n) for(ll i=a;i<n;i++)
#define fast() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define test() ll tc;cin>>tc;while(tc–)
using namespace std;
ll power(ll x, ll y)
{
ll temp;
if (y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
{
if (y > 0)
return x * temp * temp;
else
return (temp * temp) / x;
}
}
int main()
{
fast();
test()
{
ll n, k;
cin >> n >> k;
ll a[n];
f(i, 0, n)
{
cin >> a[i];
}
ll bits[32];
f(i, 0, 32)
{
bits[i] = 0;
}
f(i, 0, n)
{
f(j, 1, 32)
{
if (a[i] & (1 << (j - 1)))
{
bits[j] += power(2, j - 1);
}
}
}
ll maxx = 0, set = 0, ans = 0;
f(i, 0, k)
{
maxx = 0;
f(j, 0, 32)
{
if (bits[j] > maxx)
{
maxx = bits[j];
set = j;
}
}
if (bits[set] != -1)
{
bits[set] = -1;
ans = (ans | (1 << (set - 1)));
}
}
cout << ans << endl;
}
}
Do consider the case where K is larger than the max. possible number of set bits that can be present in a given sequence of As. Some might get struck in second subset acceptance because of these type of cases.
1 Like
It would be very helpfull
please can someone see my code i am also following the same approach
my code---->
https://www.codechef.com/viewsolution/35109239
can anyone give me hints as how to solve the bonus question in this
my approach is to calculate the cost using the no of unset bits
and the rest logic will be same as the original question
am i right?
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool sortby(pair<ll,ll> &a,pair<ll,ll> &b)
{
if(a.first!=b.first)
{
return a.first>b.first;
}
else
return b.second>a.second;
}
int main() {
// your code goes here
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
ll hash[65]={0};
for(ll i=0;i<n;i++)
{
bitset<64> bit1(a[i]);
for(ll j=0;j<64;j++)
{
if(bit1[j]==1)
{
hash[j]++;
}
}
}
vector<pair<ll,ll>> v;
for(ll i=0;i<64;i++)
{
if(hash[i]!=0)
{
ll x=hash[i]*pow(2,i);
v.push_back(make_pair(x,i));
}
}
sort(v.begin(),v.end(),sortby);
ll sum=0;
ll index=0;
while(k--)
{
sum=sum+pow(2,v[index].second);
index++;
}
cout<<sum<<"\n";
}
return 0;
}
I am Passing the first subtask but not second can anyone let me know the problem
Video Explanation->Codechef June Lunchtime 2020 || Maximum AND || MAXAND18 (Interesting Problem with clear explanation) - YouTube
Hey Man, I was solving this question today and I was also using the same approach of taking bitwise “or” of all Input numbers first, but our approach is wrong, take this case for example.
n = 4, k = 2, arr = [3,4,5,1]
Our answer would be 6 but the correct answer is 5, because 3 bits of ‘1’ at 2^0 base would be greater than 1 bit of ‘1’ at 2^1 base.
why in setter’s solution, (50-i) is paired instead of i.
also, during calculating ans, power[50-v[i].second] is used. therefore, it will be power[50-(50-i)]=power[i]… so what is the sense of using (50-i).
@dean_student
plz clarify this.
@chemthan
@taran_1407
https://www.codechef.com/viewsolution/38317357
above given is my solution link, if anyone can please let me know why my code only passes partial test cases and where its failing at. Thanks in advanced