CRDFLP - Editorial

pankhil77 · August 30, 2021, 6:11am

Can anyone tell me where i am wrong
#include<bits/stdc++.h>
using namespace std;
#define ff #define ss #define int #define pb #define mp #define pii #define vi #define mii #define pqb #define pqs #define setbits(x) #define zrobits(x) #define mod #define inf #define ps(x,y) #define mk(arr,n,type) #define w(x) mt19937 rng(chrono::steady_clock::now().time_since const int M = 3e5+ 7, N = 500;
int fact[1001];
int power(int x, int y){
int res = 1;
x = x % mod;
if (x == 0) return 0;
while (y > 0){
if (y & 1)
res = (resx) % mod;
y = y>>1;
x = (x*x) % mod;
}
return res;
}
int ad(int a, int b){
return((a % mod + b % mod) % mod);
}
int sub(int a, int b){
return((a % mod - b % mod + mod) % mod);
}
int mul(int a, int b){
return(((a % mod) * (b % mod)) % mod);
}
int divi(int a, int b){
return(mul(a, power(b, mod - 2)) % mod);
} first
second
long long
push_back
make_pair
pair<int,int>
vector
map<int,int>
priority_queue
priority_queue<int,vi,greater >
__builtin_popcountll(x)
__builtin_ctzll(x)
1000000007
1e18
fixed<<setprecision(y)<<x
type arr=new type[n];
int x; cin>>x; while(x–)
_epoch().count());

int ncr(int n, int r){
if(r > n)
return 0;
return divi(fact[n], mul(fact[n - r], fact[r]));
}
void c_p_c(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen(“input.txt”, “r”, stdin);
// freopen(“output.txt”, “w”, stdout);
// #endif
}
int po(int n,int exp){
if(exp==0)return 1%mod;
int n2=po(n,(exp>>1))%mod;
return (exp&1)==0?(n2n2)%mod:(nn2n2)%mod;
}
vi primeNum;
bool prime[10000000];
unordered_sets;
void Sieve(){
int N=10000000;
for(int i=4;i<N;i+=2)prime[i]=true;
primeNum.push_back(2);
s.insert(2);
for(int i=3;i<N;i++){
if(!prime[i]){
s.insert(i);
primeNum.push_back(i);
for(int j=ii;j<N;j+=2*i){
prime[j]=true;
}
}
}
return;
}
void solve(){
int n;
cin>>n;
vectora(n);
for(int i=0;i<n;i++)
cin>>a[i];
vectorb(n);
for(int i=0;i<n;i++)
cin>>b[i];
vectorc;
int flips=0;
for(int j=31;j>=0;j–){
int flip1=0;
vectord;
for(int i=0;i<n;i++){
int temp=((a[i]>>j)&1),temp1=((b[i]>>j)&1);
if(temp==1)
d.push_back(a[i]);
else if(temp1==1){
d.push_back(b[i]);
flip1++;
}
}
int t=d.size();
if(t==n){
c=d;
flips=flip1;
break;
}
}
int maxend=INT_MAX;
// for(int j=31;j>=0;j–){
// bool flag=false;
// for(int i=0;i<c.size();i++){
// int temp=((c[i]>>j)&1);
// if(temp==0){
// flag=true;
// break;
// }
// }
// if(!flag&&c.size()>0)
// maxend+=1<<j;
// }
for(int i=0;i<c.size();i++)
maxend=(maxend&(c[i]));
if(c.size()==0){
cout<<“0”<<" “<<“0”<<endl;
return;
}
cout<<maxend<<” "<<flips<<endl;
}
int32_t main(){
c_p_c();
//Sieve();
// fact[0]=1;
// for(int i = 1; i < 1001; i++){
// fact[i] = (fact[i - 1] * i)%mod;
// }
// prime[10000000]={false};
w(x)
solve();
return 0;
}

torizfan · August 30, 2021, 6:20am

I believe people don’t want a conversational editorial(though i understand you wanting to help).
We come across editorials only when you know we are fed up or we want a direction. So if you can change your structure of editorial like giving Hints initially, someone like me would prefer hints first over reading all this in one go.
Though I gave a 4 I mean it wasn’t bad it was a decent editorial.

arpit92_8 · August 30, 2021, 6:48am

Can please someone tell me whats the meaning of this line in the editorialist’s solution

int ans = (1<<30)-1

pankhil77 · August 30, 2021, 6:59am

if you are not able to understand above code

raksha1906 · August 30, 2021, 7:20am

Hi,
I am getting answer as
1073741823 0
1073741823 0
1073741823 0
even with the additional condition you suggested.
I think there is some error in the bits while calculating && or so, but am not able to figure out,

raksha1906 · August 30, 2021, 7:23am

Hi,
This could be written as (2^30) - 1
<< is a left shift operator used for shifting the bits by one in each iteration where
1 << no_of_iterations ===> so 30 is no of iterations here.
You could read more about left shift operators

infinitepro · August 30, 2021, 7:37am

Thank you for your feedback! I shall keep this in mind the next time I write editorials

jha_rishi · August 30, 2021, 8:00am

Could you elaborate your approach in detail. It will be helpful for us

rishabgt · August 30, 2021, 8:13am

You are using Arrays.fill to set the wrong array I believe. It should set the state array instead of array a, which has the input.

naveen_hacker · August 30, 2021, 8:18am

Can anyone tell me what is wrong with my code, I am not able to figure what’s wrong in this code.
Thank you in advance.

#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long ll;

void solve()
{
int t; cin >> t;
while (t–) {
int n; cin >> n;
vector a(n), b(n);

      for (ll & i : a)
           cin >> i;
      for (ll & i : b)
           cin >> i;

      vector<bool> vis(n, true);

      int ans = 0;
      for (int i = 31; i >= 0; i--) {
           bool flag = true;
           for (int j = 0; j < n; j++) {
                if (a[j] & (1 << i) && b[j] & (1 << i)) {
                     continue;
                } else if (a[j] & (1 << i) && vis[j]) {
                     continue;
                } else if (b[j] & (1 << i) && vis[j]) {
                     continue;
                } else {
                     flag = false; break;
                }
           }
           if (flag) {
                for (int j = 0; j < n; j++) {
                     if (a[j] & (1 << i) && b[j] & (1 << i)) {
                          continue;
                     } else if (a[j] & (1 << i) && vis[j]) {
                          continue;
                     } else {
                          if (vis[j]) {
                               vis[j] = false;
                               ans++;
                          }
                     }
                }
           }
      }
      ll ramp;
      for (int i = 0; i < n; i++) {
           if (i == 0) {
                if (vis[i]) ramp = a[i];
                else ramp = b[i];
           } else {
                if (vis[i]) ramp &= a[i];
                else ramp &= b[i];
           }
      }

      cout << ramp << " " << ans << "\n";
 }

}

int main() {
fastio();
solve();
}

raksha1906 · August 30, 2021, 8:54am

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

newbixo · August 30, 2021, 12:48pm

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();

}

pewpiyu · August 30, 2021, 4:26pm

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

pegasus_97 · August 30, 2021, 5:17pm

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

humourously_69 · August 30, 2021, 5:48pm

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;
}

infinitepro · August 30, 2021, 7:59pm

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)

messi_code · August 31, 2021, 11:23am

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";

arpit92_8 · August 31, 2021, 1:05pm

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

ishan301 · September 1, 2021, 6:28pm

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;

}

ishan301 · September 1, 2021, 6:30pm

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;
}