CRDFLP - Editorial

[infinitepro]

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

EASY

PREREQUISITES:

Bitwise Operations, Greedy

PROBLEM:

You are given two arrays A and B, of size N. In one move, you are allowed to swap the values of A_i and B_i for any i. Determine the maximum possible bitwise AND of array A, and the minimum number of moves needed to achieve it.

EXPLANATION:

Observation: The x^{th} bit (in the binary representation) of the final answer is 1 if and only if, the x^{th} bit is 1 in each of the upward facing numbers.
(The proof is a direction application of the definition of bitwise AND)

Define an array S such that, s_i is

• 0, if in the final answer, card i should have number A_i upwards,
• 1, if in the final answer, card i should have number B_i upwards,
• -1, if the side of the card to be facing up is undecided (the default state of the card in this case is number A_i upwards).

initially, all s_i is -1.

Let us tackle the problem one bit at a time. Since we are concerned with maximising the answer, we seek the most significant bit to be as large as possible.
Iterate over the bit range in descending order - from 29 to 0 (largest and smallest possible bits that can be set in the answer, respectively). Let the current bit we are processing be x.

Step 1: Determine if it possible to flip a subset of the undecided cards (those with s_i = -1) such that every number facing upwards has the x^{th} bit set.

Why? How?

By the definition of s_i, it is clear that, the only cards we can flip are those whose state is undecided. To determine if it is possible to have all upward facing numbers with the x^{th} bit set:

• check if the x^{th} bit is set in the upward facing number of each decided card.
• check if the x^{th} bit is set in either A_i or B_i of each undecided card.

This can be accomplished easily using bit manipulation (the x^{th} bit is set in number a only if a\&2^x \ne 0).

Step 2: If possible, flip the bare minimum number of undecided cards to achieve the same.

How?

By the definition of bitwise AND, it is clear that each upward facing number must have the x^{th} bit set. Thus, iterate over each of the N cards,

• skipping the cards whose state is already decided.
• skipping undecided cards with both A_i and B_i having the x^{th} bit set.
• setting the final state of the remaining cards such that, in the upward facing number, the x^{th} bit is set. Also, update the values of s_i appropriately.

At the end, the maximum possible answer is the bitwise AND of all upward facing numbers (use the number A_i if s_i equals -1) and the minimum number of cards to flip is equal to the number of cards with s_i=1.

TIME COMPLEXITY:

For each valid bit, we iterate over the N cards twice (once per step). We also iterate over the N cards one last time to determine the answer. The total time complexity is then:

O(d*(N+N)+N) \approx O(d*N)

where d, the bit range, is 30.

SOLUTIONS:

Editorialist’s solution can be found here

---

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

[sumit_king]

Why wouldn’t dp work for this problem?
let dp[i][0/1] denote the max AND in the prefix of I when I have take 0th(A[i]) or 1th(B[i]) element at ith position.

code

[chor123]

That is shameful!

[infinitepro]

Can someone please explain why the editorial has gotten only 2.95 rating? I would be grateful if someone pointed out the ambiguous sections in the explanation.

[tejas10p]

Consider a small test case like -

1
3
2 3 1
1 3 1

You will see why max AND at some prefix may lead to sub optimal solutions later on.

[deepakpra]

Why my solution is not working, My approach is:

1. for every bit if the ith bit in a[i] is set take this otherwise take b[i] (if the ith bit is set ) and increase the fliped count, if in both ith bit is not set, go for the next bit.
2. take bitwise and of all selected numbers if ith bit set in all of them.

my wrong solution

[raksha1906]

My soln doesn’t work for java. Please suggest possible changes required.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner s = new Scanner(System.in);
		int t = s.nextInt();
		while (t-- > 0){
		    int n = s.nextInt();
		    int[] a = new int[n];
		    int[] b = new int[n];
		    
		    for (int i = 0; i < n; i++) a[i] = s.nextInt();
		    for (int i = 0; i < n; i++) b[i] = s.nextInt();
		    
		    flipmagical(a,b);
		}
	}
	
	public static void flipmagical(int[] a, int[] b){
	    
	    
	    int[] state = new int[a.length];
	    Arrays.fill(a,-1);
	    //-1 => unset bit
	    // 0 => a wala bit taken
	    // 1 => b se flipped bit
	    
	    // MSB to LSB
	    for (long bit = 1 << 29; bit > 0 ; bit >>=1){
	        boolean possible = false;
	        for (int i = 0; i < a.length ; i++){
	            // 
	            if (state[i] == 0 && (a[i]&bit) != 1) possible = false;
	            else if (state[i] == 1 && (b[i]&bit) != 1) possible = false;
	            else if ((a[i]&bit) != 1 && (b[i]&bit) != 1) possible = false;
	        }
	        
	        if (!possible) continue;
	        //long ans = 1<<30;
	        for (int i = 0; i < a.length ; i++){
	            // 
	            if (state[i] != -1) continue;  // already fixed its bit
	            if ((a[i]&bit) != 1) state[i] = 1;
	            else if ((b[i]&bit) != 1) state[i] = 0;
	        }
	    }
	    
	    // maxflips = no of 1s
	    long minflips = 0;
	    long maxbiteiseans = (1 << 30)- 1;
	    for (int i = 0; i < a.length; i++){
	        if (state[i] == 1) minflips++;
	        
	        if (state[i] == 1) maxbiteiseans = maxbiteiseans & b[i];
	        else maxbiteiseans = maxbiteiseans & a[i];
	    }
	    
	    System.out.println(maxbiteiseans +" "+ minflips);
	}
}

[rishabgt]

Hi,
while setting the state, you might wanna consider adding one more condition:
for(int i = 0;i < n;++i){
if(state[i]!=-1 || (bit&B[i] && bit&A[i]))continue;
if(bit&A[i])state[i]=0;
else if(bit&B[i])state[i]=1;
}
The additional || will prevent locking of state when both bits are set. When it does not matter we pick front or back of the card, we should not lock the state as the upcoming bits might be different, which will need the state to be modified.

[kk_singh]

Much easier solution:

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define pii pair<int, int>
#define vii vector<pii>
#define make make_pair
#define first f
#define second s
#define si unordered_set<int>
#define sll unordered_set<ll>
#define mii unordered_map<int, int>
#define mll unordered_map<ll, ll>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define MOD (int) 1e9+7
#define take(n) int n; cin >> n
void pr(int x) {cout << x;}
void prl(int x) {cout << x << endl;}
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define tc(t) int t; cin >> t; while (t--)
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int max(int a, int b) {if (a > b) return a; else return b;}
int min(int a, int b) {if (a < b) return a; else return b;}
const int dx[4] = { -1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N =  (int)(5 * 1e5 + 10);
vector<vector<int>> divs(N);
void pre(){
    int i, j;
    for1(i, N-1){
        for(int j=i;j<N;j+=i)
            divs[j].pb(i);
    }
}
ll add(ll x, ll y) {ll res=x+y; return res>=MOD ? res-MOD:res;}
ll mul(ll x, ll y) {ll res=x*y; return res>=MOD? res%MOD:res;}
ll sub(ll x, ll y) {ll res=x-y; return res<0? res+MOD:res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){ if (y&1) res=mul(res, x); y >>=1; x=mul(x, x);} return res;}
ll mod_ind(ll x) {return power(x, MOD-2);}

int main(){
//#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//#endif

    tc(t){
        take(n);
        int a[n], b[n];
        for (auto &i:a)
            cin >> i;
        for (auto &j:b)
            cin >> j;
        int ans=0, count=0;
        for (int i=29;i>=0;i--){
            int c=0, flips=0, j;
            vector<int> v;
            int temp=(ans|(1<<i));
            for (j=0;j<n;j++){
                if ((a[j]&temp)==temp)
                c++;
                else if ((b[j]&temp)==temp){
                    v.push_back(j);
                    c++;
                    flips++;
                }
                else
                    break;
            }
            if (c==n){
                ans=temp;
                count+=flips;
                for (auto k:v)
                swap(a[k], b[k]);
            }
        }
        cout << ans << " " << count << "\n";
    }

    return 0;
}

[pankhil77]

Can anyone tell me where i am wrong
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector
#define mii map<int,int>
#define pqb priority_queue
#define pqs priority_queue<int,vi,greater >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type arr=new type[n];
#define w(x) int x; cin>>x; while(x–)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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);
}

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]

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]

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

int ans = (1<<30)-1

[pankhil77]

Coding Blocks IDE

if you are not able to understand above code

[raksha1906]

@rishabgt

Hi,
while setting the state, you might wanna consider adding one more condition:
for(int i = 0;i < n;++i){
if(state[i]!=-1 || (bit&B[i] && bit&A[i]))continue;
if(bit&A[i])state[i]=0;
else if(bit&B[i])state[i]=1;
}
The additional || will prevent locking of state when both bits are set. When it does not matter we pick front or back of the card, we should not lock the state as the upcoming bits might be different, which will need the state to be modified.

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]

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]

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

[jha_rishi]

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

[rishabgt]

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]

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