#include <bits/stdc++.h>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
#define MOD 1000000007
#define INF 10000000000000000
// find_by_order(), order_of_key()
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FORI(i,j,n) for(int i=j; i<n; i++)
#define FOR(i, n) FORI(i, 0, n)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define vi vector<int>
#define ss second
#define pb push_back
#define ff first
#define pii pair<int,int>
#define vii vector<pii>
#define pq priority_queue<int>
#define pdq priority_queue<int, vi, greater<int> >
#define gethash(l, r) (MOD-(h[r+1]*p_pow[r-l+1])%MOD+h[l])%MOD;
using namespace __gnu_pbds;
using namespace std;
const int N = 5e5+4;
int arr[N];
int freq[32];
bool compare(pii p, pii q){
if(p.ff!=q.ff) return p.ff>q.ff;
else if(p.ff==q.ff && p.ss!=q.ss) return p.ss<q.ss;
}
void solve(int test){
int n, k;
cin>>n>>k;
memset(freq, 0, sizeof(freq));
FOR(i, n){
cin>>arr[i];
int j = 0;
while(j<32){
if(arr[i]&(1<<j)) freq[j]++;
j++;
}
}
int sum[32]={0};
vector<pii> pp(32);
FOR(i, 32) {
sum[i] = freq[i]*pow(2,i);
pp[i] = {sum[i], i};
}
sort(all(pp), compare);
int ans = 0;
FOR(i, k){
pii curr = pp[i];
ans+=pow(2, curr.ss);
}
cout<<ans<<endl;
}
signed main()
{
fastIO
int t;
cin>>t;
for(int i=0; i<t; i++){
solve(i);
}
return 0;
}DP BASED SIMPLE SOLUTION.
O(N) TIME COMPLEXITY.
#include <bits/stdc++.h>
using namespace std;
long long int b[31];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int a[n];
int i,j;
for(i=0;i<n;i++)
cin>>a[i];
memset(b,0,sizeof(b));
for(i=0;i<n;i++)
{
int x=a[i];
j=30;
while(x)
{
b[j]+=x%2;
x/=2;
j--;
}
}
long long int dp[32][k+1];
long long int ans[32][k+1];
for(i=0;i<32;i++)
{
dp[i][0]=0;
ans[i][0]=0;
}
long long int x=0;
for(i=0;i<=k;i++)
{
dp[0][i]=0;
ans[0][i]=x;
x=2*x+1;
}
for(i=1;i<=31;i++)
{
for(j=1;j<=k;j++)
{
dp[i][j]=0;
long long int xx=b[i-1]+2*dp[i-1][j-1];
dp[i][j]=max(2*dp[i-1][j],xx);
if(dp[i][j]==xx && dp[i][j]==2*dp[i-1][j])
ans[i][j]=min(2*ans[i-1][j],2*ans[i-1][j-1]+1);
else if(dp[i][j]==xx)
ans[i][j]=2*ans[i-1][j-1]+1;
else
ans[i][j]=2*ans[i-1][j];
}
}
cout<<ans[31][k]<<endl;
}
return 0;
}
#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;
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;
}
}
what is wrong with that code?(it is partially accepted)
please help!!!
can i get test case of sub task 1??
i tried using long long as well but didn’t pass subtask 1. CodeChef: Practical coding for everyone
can u tell where i made mistake?
and why is long long needed?
Can someone please help me, my solution got passed only for the 1st test case.
And it is exactly the same as explained in the editorial and I have also used long long.
Here is my link: CodeChef: Practical coding for everyone
Can you explain this code a bit please?
MY CODE isn’t working for the SUBTASK 1 ( K<=2 )
can anyone HELP ?
#include <bits/stdc++.h>
using namespace std; // MACROS
typedef long long int ll;
typedef vector vll;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define fo(i,n) for( i=0; i < n ; i++)
const ll MODA = 1000000007;
ll power(ll a, ll b) { ll res=1; while(b) { if(b&1) res=(resa); a=(aa); b>>=1; } return res; }
bool sortbydesc( pair<int,int> i1, pair<int,int> i2)
{
if (i1.first > i2.first) return true ;
else if( i1.first == i2.first )
{
if( i1.second <= i2.second ) return true ;
else return false;
}
else return false;
}
int main()
{ ios_base::sync_with_stdio(false); cin.tie(0);
ll tc; cin>>tc; while(tc–)
{
ll i,j,n,k,ans=0; cin>>n>>k;
vll a(n);
vector<pair<ll,ll>> pp;
ll b[32]={0};
fo(i,n)
{
cin>>a[i];
for (int j = 0; j < 32; j++)
{ if(a[i] & (1<<j) ) b[j]++; }
}
for (int j = 0; j < 32; j++)
{
b[j] = b[j]*(1<<j);
pp.pb({b[j],j}) ;
}
sort(pp.begin(),pp.end(),sortbydesc);
for (int j = 0; j < k; j++)
ans += power(2 , pp[j].second );
cout<<ans<<"\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool mysort(pair<int, ll> a, pair<int, ll> b){
if(a.second == b.second) return a.first<b.first;
return a.second>b.second;
}
int main(){
int t;
cin>>t;
while(t–){
ll n,k;
cin>>n>>k;
ll a[n] = {};
vector bits(50);
for(int i=0;i<n;i++){
cin>>a[i];
ll x = a[i];
int j=0;
while(x){
if(x&1){
bits[j]++;
}
x = x>>1;
j++;
}
}
ll ans = 0;
vector<pair<int, ll> > pq;
for(int i=0;i<49;i++){
// cout<<bits[i]<<" ";
// cout<<(1<<i)<<endl;
pq.push_back(make_pair(i,(1<<i)*bits[i]));
}
sort(pq.begin(), pq.end(), mysort);
for(int i=0;i<k;i++){
ans += (1<<pq[i].first);
}
cout<<ans<<endl;
}
}
Please someone tell the problem with the code.
I am not getting 50 points in the first case.
even i’m facing the same issue .While debugging my code i found that for the first bit ( 2^0 )
some times a garbage value is stored in place of the contribution( as in the editorial ) of the first bit
( dont know in which cases it stores garbage value and what is the reason behind garbage value )
[Link to my code]CodeChef: Practical coding for everyone
why is iit showing wrong answer and runtime error ???
// regerence geeks for geeks
// Program for Decimal to Binary Conversion - GeeksforGeeks
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f(a, b) for (ll i = a; i < b; i++)
#define test
ll t;
cin >> t;
while (t–)
#define pb push_back
#define pf push_front
#define mp make_pair
#define fast
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using namespace std;
void decToBinary(int n, ll *count)
{
int i = 0;
while (n > 0) {
if(n%2 == 1) count[i]++;
n = n / 2;
i++;
}
}
bool comp(pair<ll, ll> a, pair<ll ,ll > b){
return a.first>b.first;
}
void solve()
{
//freopen(“input.txt”, “r”, stdin);
//freopen(“out.txt”, “w”, stdout);
ll power[32]={0};
power[0] = 1;
f(1,32){
power[i] = 2power[i-1];
}
test{
ll n,k; cin >> n >> k;
ll a[n];
f(0,n){
cin >> a[i];
}
ll count[32]={0};
f(0,n){
decToBinary(a[i],count);
}
vector<pair<ll, ll> > res;
ll x=1;
f(0,n){
res.pb(mp(xcount[i], i));
x *= 2;
}
sort(res.begin(), res.end(), comp);
ll ans = 0;
f(0,k){
ans += power[res[i].second];
}
cout << ans << endl;
}
}
int main()
{
fast;
solve();
return 0;
}
My code gave an AC when using a [32] size array with all bits set to zero, but only passed the first subtask when using maps.
The reason turned out to be: When using maps - I was only adding the powers of 2 which had a positive contribution - but didn’t add them if the contribution was zero.
Make sure your DS contains the contribution of all bits 0-31 even if their contribution is 0.
An example testcase would be:
1
4 3
64 64 64 64
Ans: 67
Even though the contribution of bits 0 and 1 is zero -> they need to be added to the final X since k=3.
1 Like
Can you explain what did you do exactly on video at 3:40.
You said we are doing And With Every Number, but that seems confusing to me.
Hey even I used maps. but got ac on second subtask. my code works fine this case which u stated. Can you help where does my code fail?
@admin the editorial for question 3(div 1) is not opening as well as editorial for question 4 and 5 (div 1) is not available and rating is also not updated.
Please have a look into this.
Why we have made pair of (50-i) in settlers solution instead of simply (i) ??
///Greedy || Priority Queue
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector< ll >v;
int Set(int N,int pos){ return N=N | (1<<pos);}
bool Check(int N,int pos){return (bool)(N & (1<<pos));}
ll solve(int k){
priority_queue < pair < ll , int > > pq;
for(int i=0; i<=31; i++){
ll tot=0;
for(int j=0; j<v.size(); j++){
if(Check(v[j],i))tot+=(1<<(i+1));
}
pq.push({tot,-i});
}
int x=0;
while(! pq.empty() && k--){
int pos=pq.top().second*-1;
x=Set(x,pos);
pq.pop();
}
return x;
}
int main(){
int t,k,n;
cin>>t;
while(t--){
cin>>n>>k;
v.resize(n);
for(auto &i: v)cin>>i;
cout<<solve(k)<<endl;
}
return 0;
}
I am just trying to count no of ones at that position
At one bit by just doing and operation
8 is the maximum value of S
but in answer we have to return X
so X is 100 -> which is 4
and using this X
we get max S = 8
hope it’s clear
if anything is still unclear do let me know
Thanks.