Maximum And MAXAND18

help
1 
#include "bits/stdc++.h"
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int

bool sortinrev(const pair<lld,lld> &a,
               const pair<lld,lld> &b)
{
       return (a.first > b.first);
}

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        lld bits[36];
        int n,k;
        cin>>n>>k;
        long arr[100001];
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            for(int j=0;j<=35;j++)
            {
                lld temp=arr[i];
                bits[j]+=(1 & temp>>j);
            }
        }
        vector <pair <lld,lld> > v;
        lld power=1;
        for(int i=0;i<=35;i++)
        {
            v.push_back({bits[i]*power,i});
            power*=2;
        }
        sort(v.begin(),v.end(),sortinrev);
        int mark[36]={0};

        //for(int i=0;i<34;i++)
          //  cout<<v[i].first<<" "<<v[i].second<<"\n";

        int ptr=0;

        set <int> :: iterator it1;
        if(k>0)
        {
            for(int i=0;i<v.size();i++)
            {
                if(k<=0)
                break;
                 set <int> s;
                lld val=v[i].first;
                lld in=v[i].second;
                s.insert(in);
                while(i+1<v.size()&&v[i+1].first==val)
                {
                    i++;
                    s.insert(v[i].second);
                }
                for(it1=s.begin();it1!=s.end();it1++)
                {
                    if(k<=0)
                        break;
                    mark[*it1]=1;
                    k--;
                }
                s.clear();
            }
        }
        lld ans=0;
        power=1;
        for(int i=0;i<=35;i++)
        {
            if(mark[i]==1)
            {
                ans+=power;
            }
            power*=2;
        }
        cout<<ans<<"\n";
    }
}

Two TC are passing and two WA. Why my code fails?
@galencolin @akshitm16

2 
#include <bits/stdc++.h>
#include <fstream>
#define vi vector<int>
#define pi pair<int, int>
#define vs vector<string>
#define mp make_pair
#define mi map<int, int>
#define ull unsigned long long int
#define fo(i, k, n) for(int i = k; i < n; i++)
#define pqi priority_queue<int>
#define ll long long int
#define pb push_back
#define mod 1000000007
#define INF 1e18
#define f first
#define s second

using namespace std;
bool sortcmp(pi a, pi b){
    if(a.f == b.f){
        return a.s < b.s;
    }
    return a.f > b.f;
}
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];
        for(int i = 0; i < n; i++) cin >> a[i];
        vi bcount(31, 0);
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= 30; j++){
                if(a[i] & (1 << j)) bcount[j]++;
            }
        }
        vector<pi> cz(31);
        for(int i = 0; i <= 30; i++){
            cz[i] = mp(pow(2, i)*bcount[i], i);
        }
        sort(cz.begin(), cz.end(), sortcmp);
  
        int ans = 0;
        for(int i = 0; i < k; i++){
            ans = ans|(1 << (cz[i].s));
        }
        cout << ans << "\n";
	}
	return 0;
}

This code passes the second sub-task but fails the first sub-task.
Can someone provide a case where the above solution fails?

3

Did you find where it doesn’t work? I have worse implementation but it passed, curious why this is not passing smaller subtasks…

1 Like
4

Try changing vector<pair<int,int>> cz(31) to vector<pair<ll,ll>> cz(31) , i got WA on first subtask due to that.

1 Like
5

Can you see my code also @prathmesh_99

7

Thanks

1 Like
8

What was the problem?

9

I used int instead of long long int
Just changed that everywhere that mattered and it passed all the testcases

1 Like
10

Hi @sebastian
You were not initializing bits array.
AC Sol

1 Like
11

But, I printed all the values of the vector and saw them. They were 0. Also, 2 tc passed. I know that it is necessary to initialize. But it didn’t take some garbage value when I gave some custom input and ran on ide. So, any reason for this behaviour or it is something like that incident only when array is accessed out of bounds then its value at starting index changes? btw thanks @akshitm16

12

Afaik it is initialized with a garbage value and 0 can be also a garbage value.

13

you have change a little in your function sortinrev as follow
bool sortinrev(const pair<lld,lld> &a,
const pair<lld,lld> &b)
{
if (a.first>b.first) return true;
else if (a.first==b.first) return a.second<b.second;
return false;
}

this is so because if the contribution of two bits is same then we have to select lower bit.
Hope it helps:)

14

That was never the issue in his code. If contribution is same, it already returned the lower bit. The problem was not initializing bits array.

15

Yeah, but I don’t understand that for two cases garbage value is 0 and for other two cases garbage value is some random value (at every submission).

16

It is quite unpredictable but concrete for a particular input. If for input, garbage value is x, then everytime garbage value will be same x for this particular input but this x is unpredictable.

17

Do you mean, garbage value depends on input?

18

kind of…so yeah. On my local system, for same input, garbage values were same everytime. You can try on codechef ide.

19

I found something unusual, when I ran this code

for(int i=0;i<=40;i++)
        {
            lld x=1>>i;
            cout<<x<<" "<<i<<"\n";
        }

It gives 1 for i=32. Also when I just print 1>>32 it gives 0.

20

It’s UB. Thanks @akshitm16

1 Like