CRDFLP - Editorial

Ohh yess, but now it gives me
0 0
0 0
0 0
as output

We can even just directly iterate from maximum possible set bit we can get from two arrays , This way our time complexity will be (O(maxmsb(a,b))*n)

My code :
// Note i have used one indexing for bits 
#include<bits/stdc++.h>
using namespace std;
int setbitk(int n , int k){
	return (n&(1<<(k)))>>k;
}
int msb(int n){
	return 1 + log2(n);
}

void solve(){
	int n;
	cin >> n;
	vector <int> a(n) , b(n);
	for(auto &x : a) cin >> x;
	for(auto &x : b) cin >> x;

	vector <int> canflip(n,true);
	int maxmsb = 0;
	for(int i=0;i<n;i++){
		maxmsb = max({maxmsb,msb(a[i]),msb(b[i])});
	}
	int flips = 0;
	for(int k=maxmsb;k>=0;k--){

		bool canset = true;
		vector <int> noMoreFlips;
		vector <int> needsSwap;
		vector <int> pos;
		for(int i=0;i<n;i++){
			int x = setbitk(a[i],k);
			int y = setbitk(b[i],k);
			if(x==1){
				if(y==0){
					noMoreFlips.push_back(i);
				}
				// else u may flip
			}
			else{
				if(y==0 or !canflip[i]){
					canset = false;
					break;
				}
				else{
					needsSwap.push_back(i);
					noMoreFlips.push_back(i); // no more flips		
				}
			}

		}

		if(canset){
		
			for(auto i : noMoreFlips){
				canflip[i] = false;
			}
			for(auto i : needsSwap){
				swap(a[i],b[i]);
				flips++;
			}
		}

	}

	int ans = a[0];
	for(int i=1;i<n;i++){
		ans &= a[i];
		
	}
	cout << ans << " " << flips << "\n";
}
int main(){
	int t;
	cin >> t;
	while(t-->0) solve();

}
1 Like

I have spent so much time building this solution , and i dont know what is wrong with my approach.
please do look at my solution and help me .
thanks in advance.
link :- sol

Can some one please explain the logic used for the loop for the solution linked to the editorial.
Why is it for(int msb = (1<<29); msb > 0; msb /= 2) Can we use msb - - ?
Why are we dividing it by 2 every time?
Thanks

Can anyone please review my code, it is passing sample test but failing on submission…
And what about N==1 case?

void solve(){
    int n;
    cin>>n;
    vector<int>arr(n),b(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    if(n==1){
        cout<<arr[0]<<" "<<0<<endl;
        return;
    }
    vector<int>res(n,-1);
    int count=0;
    for(int i=30;i>=0;i--){
        int j=0,flag=0;
        for(;j<n;j++){
            if(arr[j]&(1<<i)) continue;
            else if(b[j]&(1<<i)){
                res[j]=b[j]; flag=1;
            }else break;
        }
        if(flag && j==n){
            for(int i=0;i<n;i++){
                if(not (res[i]==-1) && not(arr[i]==res[i])){
                    arr[i]=res[i];
                    count++;
                }
            }
        }
        res.clear();
        res.resize(n,-1);
    }
    int ans=arr[0]&arr[1];
    for(int i=2;i<n;i++){
        ans&=arr[i];
    }
    cout<<ans<<" "<<count<<endl;
}

msb refers to the most significant bit (which starts with 1<<29 and ends with 1<<0). The reasoning for this, and not iterating from 29 to 0 (as the editorial states) is ease of implementation, as I don’t have to bit shift every time I want to do an AND operation (lines 34,35,36,43,44 would have ...&msb replacd with ...&(1<<i) which is redundant)

Please help !
Why am I getting WA for Subtask 3.
Have used diff logic.
First checking what can be max allowed by all nums, then checking individually if the max is possible and updating val and count accordingly.

    int n;cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    ll val=a[0]|b[0];
    for(int i=1;i<n;i++)
    {
        val=val&(a[i]|b[i]);
    }
    ll c=0;
    // cout<<val<<" ";
    for(int i=0;i<n;i++)
    {
        ll a1=val&a[i];
        ll b1=val&b[i];
        if(a1!=val)
        {
            if(b1==val||a1<b1)
            {
                val=b1;c++;
            }
            else
            val=a1;
        }
    }
    cout<<val<<" "<<c<<"\n";

Thank you for your reply but I wanted to know what it does in the program like why we have to initialize ans with it

Can anyone please tell me why I am getting wrong answer by this code? I have only given the main code below.

int t;cin>>t;while(t–){

    int n; cin>>n;

    vi a(n),b(n);

    for(int i=0;i<n;i++)

    {

        cin>>a[i];

    }

    for(int i=0;i<n;i++)

    {

        cin>>b[i];

    }

    int flipped=0;

        bool pass=true;

        vi select(n,0);

    for(int i=1<<30;i>0;i>>=1)

    {

        pass=true;

        for(int j=0;j<n;j++)

        {

            if((a[j]&i)!=0)

            {continue;}

            if((b[j]&i)!=0)

            {

                flipped++;

                select[j]=1;

                continue;

            }

            pass=false;

            flipped=0;

            break;

        }

        if(pass)

        {

            break;

        }

        for(int j=0;j<n;j++)

        {

            select[j]=0;

        }

    }

    if(pass)

    {

        int x=(1<<30)-1;

        for(int i=0;i<n;i++)

        {

            if(select[i]==1)

            {

                x&=b[i];

            }

            else{x&=a[i];}

        }

        cout<<x<<" "<<flipped<<endl;

        continue;

    }

    cout<<0<<" "<<0<<endl;

}

return 0;

}

Can you please tell why this code is not working. I have used same logic as per the editorial.

int t;cin>>t;while(t–)
{
int n; cin>>n;
vi a(n),b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
cin>>b[i];
}
int flipped=0;
bool pass=true;
vi select(n,0);
for(int i=1<<30;i>0;i>>=1)
{
pass=true;
for(int j=0;j<n;j++)
{
if((a[j]&i)!=0)
{continue;}
if((b[j]&i)!=0)
{
flipped++;
select[j]=1;
continue;
}
pass=false;
flipped=0;
break;
}
if(pass)
{
break;
}
for(int j=0;j<n;j++)
{
select[j]=0;
}
}
if(pass)
{
int x=(1<<30)-1;
for(int i=0;i<n;i++)
{
if(select[i]==1)
{
x&=b[i];
}
else{x&=a[i];}
}
cout<<x<<" “<<flipped<<endl;
continue;
}
cout<<0<<” "<<0<<endl;
}
return 0;
}

Can somebody explain my why is my solution failing my solution

Can anyone tell me for the case, if to set xth bit to 1 , doing a flip may cause a higher bit set to 0, how are we handling that case?

Once a bit is flipped, it can’t be un-flipped (a boolean vector can be used for this), rest other bits which are flexible till now can only be flipped after that.
This is what I’d missed while solving the problem, but later I got it luckily.

Try solving maximum AND value ques on GFG you will understand it better then.
I have extended that same approach here…

1 Like

Your question is - In the iteration, if we flip a particular card to make the x^{th} bit in the answer 1, how do we know bit i\space(i>x) is still set in the answer?

See step 2 in the editorial. When processing the i^{th} bit, a card is left undecided ONLY if flipping the card doesn’t unset the i^{th} bit. Therefore, if the card is flipped when processing the x^{th} bit, the i^{th} bit is still on.