MINARRS - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan Jaddouh
Tester: Joud Zouzou
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Observations, bitwise operations and being greedy once again :stuck_out_tongue:

PROBLEM:

Given an array A with N elements, we need to find the minimum value of \sum A_i \oplus X by choosing any value for X.

QUICK EXPLANATION

  • Writing all elements of A_i in binary, Consider each bit separately. Count the number of elements having the current bit set.
  • If there are p elements with bit x set, current bit contributes p*2^x to the total sum which we need to minimize.
  • If p > N-p, we can choose to set the current bit of X on so that p on bits become off bits and N-p off bits become set bits, reducing answer by (p- (N-p))*2^x.

EXPLANATION

Quick explanation nearly explained it all.

In XOR operation, the current bit is independent of the result of XOR operation on lower bits, which allows us to solve this problem separately for each bit and simply add the answers.

W repeat the process for each bit. For bit x, if there are p elements with the current bit on, we get the sum as p*2^x.

In XOR operation, we can choose to leave the current bits as it is by setting the current bit of X as off or flip all of them by setting the current bit of X as on. If we keep it off, the current bit contributes p*2^x to answer. If we keep it on, the current bit contribute (N-p)*2^x to answer. In order to minimize sum, we can simply add min(p*2^x, (N-p)*2^x) to answer for the current bit.

So, minimum sum is \sum_{i =0}^{B-1} min(p_x, N-p_x)*2^i if there are p_x elements with ith bit set in array A and B is the number of bits.

TIME COMPLEXITY

The time complexity is O(N*B) per test case where B is the number of bits.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}

int T;
int n;
int arr[100100];
int sm_n=0;


int main(){
	//freopen("01.txt","r",stdin);
	//freopen("01o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntLn(1,100000);
		sm_n+=n;
		assert(sm_n<=1000000);
		for(int i=0;i<n;i++){
			if(i==n-1){
				arr[i]=readIntLn(1,1000000000);
			} else {
				arr[i]=readIntSp(1,1000000000);
			}
		}
		for(int i=0;i<30;i++){
			int cnt = 0;
			for(int j=0;j<n;j++){
				if(arr[j] & (1<<i)){
					cnt++;
				}
			}
			if( cnt < n - cnt){
				continue;
			}
			for(int j=0;j<n;j++){
				arr[j] ^= 1<<i;
			}
		}
		long long sol=0;
		for(int i=0;i<n;i++){
			sol += arr[i];
		}
		cout<<sol<<endl;
	}
	assert(getchar()==-1);
}
Tester's Solution
// Full Solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
	    char g=getchar();
	    if(g=='-'){
	        assert(fi==-1);
	        is_neg=true;
	        continue;
	    }
	    if('0'<=g && g<='9'){
	        x*=10;
	        x+=g-'0';
	        if(cnt==0){
	            fi=g-'0';
	        }
	        cnt++;
	        assert(fi!=0 || cnt==1);
	        assert(fi!=0 || is_neg==false);

	        assert(!(cnt>19 || ( cnt==19 && fi>1) ));
	    } else if(g==endd){
	        assert(cnt>0);
	        if(is_neg){
	            x= -x;
	        }
	        assert(l<=x && x<=r);
	        return x;
	    } else {
	        assert(false);
	    }
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
	    char g=getchar();
	    assert(g!=-1);
	    if(g==endd){
	        break;
	    }
	    cnt++;
	    ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long a[1000005];
long long num[1000];
int main()
{
	int t = readIntLn(1,1000);
	while(t--)
	{
	    int n = readIntLn(1,100000);
	    for (int i=0;i<=50;i++)num[i]=0;
	    for (int i=1;i<=n;i++)
	    {
	        if (i<n)
	            a[i]=readIntSp(1,1000000000);
	        else
	            a[i]=readIntLn(1,1000000000);
	        for (int j=0;j<=30;j++)
	        {
	            if ((1<<j)&a[i])num[j]++;
	        }
	    }
	    long long ret=0;
	    for (int i=0;i<=30;i++)
	    {
	        long long cur = min(num[i],n-num[i]);
	        ret+=(((1LL)<<i)*cur);
	    }
	    cout<<ret<<endl;
	}
	assert(getchar()==-1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
	//SOLUTION BEGIN
	//This code is not meant for understanding, proceed with caution
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), B = 30;
	    int[] s = new int[B];
	    for(int i = 0; i< n; i++){
	        int x = ni();
	        for(int b = 0; b< B; b++)if(((x>>b)&1)==1)s[b]++;
	    }
	    long ans = 0;
	    for(int b = 0; b< B; b++)ans+= (1l<<b)*Math.min(s[b], n-s[b]);
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long mod = (long)1e9+7, IINF = (long)1e18;
	final int INF = (int)1e9, MX = (int)1e6+1;
	DecimalFormat df = new DecimalFormat("0.0000000");
	double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
	static boolean multipleTC = true, memory = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    int T = (multipleTC)?ni():1;
//        Solution Credits: Taranpreet Singh
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new Main().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}   

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2 Likes

It would be nice if the solutions had syntax coloring

3 Likes

This problem is same as March Long 18 problem, XXOR and Winter code sprint problem, WCSB with L = 1 and R = N. I just modified my last solution and submitted it :grin:

I think typing code for this problem will be faster than that :smile:

3 Likes

Why did you set B = 30? Why 30? Is it just any arbitrary number?

Well, How many number of bits will be required to store a number with limit <=10^9. Just consider those ones.

1 Like

to store 10^9 30 bits are required thats y i took 30.

well, the maximum possible value is 10^9 and to represent that in binary we need 30 bits…how 30…? It’s simple just take log2(max_value)…

1 Like

Can someone tell what is wrong with my Solution?
It is partially correct

Hello , I just solved the problem partially by saving the numbers in Binary and the comparing the columns i.e If one column have more number of 1’s than 0’s then I set the bit for XORing to 1 else leave it as it is. However this solution passes for 50pts but there is a TLE for remaining points.

https://www.codechef.com/viewsolution/24116598

What can I do for it?

can someone help here getting WA.

Need Help understanding the statement from Editorial:
“If we keep it on, the current bit contribute (N−p)∗2x to answer.”

So, lets say there are ‘p’ elements out of n, whose first bit is set. Then while deciding our X, if we decide to keep the first bit off, then the contribution towards sum will be p*2^0, else (n-p)*2^0.

Test cases for first subtask seems really weak ; I actually misinterpreted X to be always a part of the array and got AC on first subtask with that implementation!

can someone explain this solution clearly (not the brute force method :sweat_smile:)