CodeChef: Practical coding for everyone hope this helps.
Code seems fine on the face of it. Try using a [32] array initialized to 0 to store the bit count/contribution - if it gives AC on both - you can work backwards to find out where your map approach is going wrong.
what changes you did in sorting function please tell
@axel223 I changed the macro pi to pair<long long int, long long int> from pair<int, int>.
That in turn changed my sorting function to be valid for long long int.
Not using long caused me a star 
Here is an easy intuitive greedy approach using bitset.
- Take bitwise-OR of all numbers and store it in binary format using a bitset data structure.
- For all numbers collectively frequency of every bit(0-29) being 1 is stored in an array.
- Iterating from 0-29 using bit frequency generates its value and map it to its index.{weight, index}
- Sort this array using a custom comparator where weight is sorted in descending and index is stored in ascending(for getting the smallest one for multiple sol).
-Iterate over this array ‘k’ times and set ‘1’ to the corresponding position and that’s the required solution.
Take a look at my code…this is my first post hope you like it.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n,k,num,t;
bool comp(pair<ll,ll> a,pair<ll,ll> b){ // < ascending ; > descending
if(a.fi == b.fi) return a.se < b.se;
return a.fi > b.fi;
}
int main()
{
ios
cin>>t;
while(t--){
cin>>n>>k;
vector<ll> freq(30,0);
bitset<30> bs[n];
ll stor=0;
for(int i=0;i<n;i++){
cin>>num;
stor |= num; //Bitwise-or of all nums
bs[i] = bitset<30> (num);//storing n nums in bitwise format
for(int j=0;j<30;j++)
freq[j] += bs[i][j]; //maintaining the count of every bit from 0 to 29 position
}
bitset<30> temp(stor);//Binary representation of bitwise-OR of all nums
vector<pair<ll,ll>> v;
for(int i=0;i<30;i++){
bitset<64> samp;samp[i] = 1;//frequency of every bit is weighted
v.pb({(ll)((ll)(samp.to_ullong()) * freq[i]),i});
}
sort(v.begin(),v.end(),comp);
bitset<30> ans;
for(int i=0;i<k;i++)
ans[v[i].se] = 1;
cout<<(int)(ans.to_ulong())<<endl;
}
return 0;
}
@chemthan @dean_student
Since so many guys are having issue in passing the first sub-task, can you please share that particular test case here?
Hey, getting right ans on this particular testcase, but still not able to clear first sub-task. Can you have a look at my sol please?
https://www.codechef.com/viewsolution/34827909
Where the code fails is a completely random case and too large to be posted here.
1 Like
I guess the particular case which is causing problems is one where n is large and some of the most significant bits are turned on in most or all the numbers.
A sample case would be n = 10^5, k = 1, each Ai = 671088640.
The answer
The ans should be 536870912
29 1
1 2 4 8 1 2 4 8 1 2 4 1 2 4 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1
Answer should be 1
Long long is needed you are storing contribution of each bit which can be 10^5*2^30
let`s say
count[i] * x == > 8 4 4
i ===========> 2 1 0
after sorting
count[i] * x___i
4_____________0
4_____________1
8_____________2
(select last 2 value of k after sorting) ie 1th bit and 2nd bit
and k = 2 that means we need to select 2 bits in such a way that sum will be maximum and number formed (i.e… X) is minimum
so in this case bits selected will be 2 and 1 so, number formed is 6 and sum will be 8 + 4 = 12
but this is not minimum X as we can form another X with same sum ie… by selecting bits 2 and 0, therefore X will be 5 and sum will be same ie 8+4 = 12
due to this reason when we do sorting of that pairs we will subtract it from 50
count[i] * x == > 8 4 4
50 - i ==> 48 49 50
after sorting
count[i] * x__50 - i__i
4____________49____1
4____________50____0
8____________48____2
(select last 2 value of k after sorting) ie 0th bit and 2nd bit
hope it is clear now…
#include <bits/stdc++.h>
using namespace std;
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << ‘'’ << x << ‘'’; }
void __print(const char *x) { cerr << ‘"’ << x << ‘"’; }
void __print(const string &x) { cerr << ‘"’ << x << ‘"’; }
void __print(bool x) { cerr << (x ? “true” : “false”); }
template <typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << ‘{’;
__print(x.first);
cerr << ‘,’;
__print(x.second);
cerr << ‘}’;
}
template
void __print(const T &x)
{
int f = 0;
cerr << ‘{’;
for (auto &i : x)
cerr << (f++ ? “,” : “”), __print(i);
cerr << “}”;
}
void _print() { cerr << “]\n”; }
template <typename T, typename… V>
void _print(T t, V… v)
{
__print(t);
if (sizeof…(v))
cerr << ", ";
_print(v…);
}
#ifndef ONLINE_JUDGE
#define dbg(x…)
cerr << “[” << #x << “] = [”;
_print(x)
#else
#define dbg(x…)
#endif
#define endl “\n”
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define ROF(i, a, n) for (ll i = a; i >= n; i–)
#define all(x) (x).begin(), (x).end()
#define dline cout << “///REACHED///\n”;
typedef long long ll;
const ll MOD = 1e+9 + 7;
const ll INF = 0x7f7f7f7f7f7f7f7f;
const int INFi = 0x7f7f7f7f;
const ll MAXN = 4e+5 + 7;
ll n, k;
vector counts(64, 0);
void decToBinary(ll n)
{
ll binaryNum[64] = {0};
ll i = 0;
while (n > 0)
{
binaryNum[i] = n % 2;
n = n / 2;
i++;
}
FOR(i, 0, 64)
{
counts[i] += binaryNum[i];
}
}
void solve()
{
cin >> n >> k;
ll num;
FOR(i, 0, n)
{
cin >> num;
decToBinary(num);
}
vector ans(64, 0);
map<ll, set> m;
FOR(i, 0, 64)
{
counts[i] = (1LL << i) * counts[i];
if (counts[i] > 0)
{
m[counts[i]].insert(i);
}
}
sort(all(counts));
ROF(i, 64, 0)
{
for (auto x : m[counts[i]])
{
// dbg(x);
if (k)
{
assert(x < 64);
ans[x] = 1;
k--;
}
}
}
// dbg(ans);
// dbg(m[counts[64]]);
ll ansnum = 0;
FOR(i, 0, 64)
{
if (ans[i])
{
ansnum += (1LL << i);
}
}
cout << ansnum << endl;
fill(all(counts), 0);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
/*
Approach-> counts stores the number of set bits in position i in the given integers
After that,count is modified as (2^i)(i=>position) * count[i](gives value for me to sort and greedily pick the indices to set)
ans is the binary array version of answer
idk why, but my solution only gets 50 points
*/
Can anyone help me the solution satisfies only subtask 1 may i know where i am going wrong??
Link->CodeChef: Practical coding for everyone
I think it should be res = res | (1 << (v[i].first)) in place of res += (1 << (v[i].first)) , if everything else is fine it should work.
And, for subtask 1, use long long int.
(For, long long int (1LL << m) in place of (1 << m) .
1 Like
@taran_1407 bro from where you get the knowledge of implementing comparator in java. In such a classical manner.
#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!!!
what is wrong with my code ? Solution link:- Link
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int comp(const pair<long long int, long long int> &a, const pair<int, long long int> &b){
return a.second > b.second;
}
int main() {
long long int t;
cin>>t;
while (t--) {
long long int n,k;
cin>>n>>k;
long long int a;
vector< pair<int, long long int> > sum;
long long int x=0;
for (long long int i=0;i<32;i++){
sum.push_back(make_pair(i,0));
}
for (long long int i=0;i<n;i++) {
cin>>a;
for (long long int i=31;i>=0;i--) {
sum[i].second += (a&(1<<i));
}
}
sort(sum.begin(),sum.end(), comp);
// for(int i=0;i<sum.size();i++) {
// cout<<sum[i].first<<" "<<sum[i].second<<endl;
// }
for(auto itr = sum.begin(); itr != sum.end(); ++itr) {
if (k>0 && (itr->second)!=0) {
// cout<<(itr->first)<<" "<<(itr->second)<<" "<<endl;
x |= (1<<(itr->first));
k--;
}else {
break;
}
}
if(k!=0) {
for (long long int i=0;i<32;i++){
if(k>0 && (x&(1<<i)) == 0){
x|= (1<<i);
k--;
}
}
}
cout<<x<<endl;
}
return 0;
}
i m not able to understand the editorial pls can anyone explain me ?