I did this…used greedy…@dean_student can you please find the bug.
I am getting all the right outputs with this code but still couldn’t pass the second sub-task.
Thanks in advance.
Link :- CodeChef: Practical coding for everyone
Same as editorial says, just find the contribution of each bit, same I did in the code, just run the loop for the each bit i => [0…30], then for each bit calculate the its weightage in each A[j], j => [0…n-1], then store it into the vector of pair<long long, long long> .
Now, just sort the vector in decreasing first by weightage, if weight is same then sort it increasing by bit position.
After that just pick the first k bits according to the sorted vector.
Check the updated code of yours.
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 1000000
#define ll long long int
const double pi = 3.14159265358979323846;
int main(){
int t;
cin>>t;
while(t–){
ll n,sum1=0,sum2=0,k,maxi=0;
cin>>n>>k;
ll a[n];
for(int i=0; i<n; i++)
cin>>a[i];
priority_queue< pair<ll,pair<ll,ll> > >p;
///Run this loop <31 rather than =31, because 0 - 31, total 32 bits ate making an overflow
for(ll i=0; i<31; i++){
ll x=1<<i;
int c=0;
for(int j=0; j<n; j++){
if(x&a[j])
c++;
}
p.push(make_pair(c*x,make_pair(-x,x)));
}
ll ans=0;
while(k--){
ll y=p.top().second.second;
ans+=y;
p.pop();
}
cout<<ans<<endl;
}
}
I too am getting 1, in the above posted code of mine
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