MAXARXOR - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Vichitr Gandas

DIFFICULTY:

SIMPLE

PREREQUISITES:

NONE

PROBLEM:

Value of an array A of length L is defined as the sum of (A_i⊕i) for all 0≤i<L, where denotes bitwise xor operation. Note that array indices start from zero.

You are given an integer N. Then you create an array A consisting of 2^N integers where A_i=i for all 0≤i<2^N.

You can do at most K operations on this array. In one operation, you can choose two indices i and j (0≤i,j<2^N) and swap A_i and A_j.

What is the maximum value of array A you can obtain after at most K operations?

EXPLANATION

Initially A_i = i hence A_i ⊕ i = 0 for all 0 \le i < 2^N. Here we can get max xor A_i ⊕ i = 2^N -1 by setting A_i = i ⊕ (2^N - 1). In one operation we are swapping two elements so we can make two elements equal to 2^N-1. So best way is to swap A_i with A_i ⊕ (2^N-1).

So we just need to find out how many elements we would be able to make equal to 2^N-1 in K moves. In one move, we can make two elements, hence in K moves at most 2 \cdot K. But also there are only 2^N elements hence take the minimum i.e. min(2 \cdot K, 2^N).

After these operations if i^{th} element has become A_i = i ⊕ (2^N-1) then it would contribute 2^N-1 to the value because A_i ⊕ i = i ⊕ (2^N-1) ⊕ i = 2^N-1. And all other elements would contribute 0 as they are not changed. Hence answer is min(2 \cdot K, 2^N) \times (2^N-1).

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n, k; cin >> n >> k;
		int x = 1;
		for (int i = 0; i < n - 1; i++) x *= 2;
		int ans = 2 * min(x, k) * (x * 2 - 1);
		cout << ans << '\n';
	}
	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    long long n, k;
    cin>>n>>k;
    long long temp = pow(2, n);
    long long ans = min(2 * k, temp) * (temp - 1);
    cout<<ans<<"\n";
  }
  return 0;
}
Editorialist's Solution
/*
 * @author: vichitr
 * @date: 24th July 2021
 */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

void solve() {
	int N, K; cin >> N >> K;
	int twoPowerN = 1;
	for (int i = 0; i < N; i++)
		twoPowerN *= 2;
	int ans = min(twoPowerN, K * 2) * (twoPowerN - 1);
	cout << ans << '\n';
}

signed main() {
	fast;

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	int t = 1;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}

VIDEO EDITORIAL:

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

3 Likes

‘’’
#include
#include
using namespace std;
typedef long long int ll;
int main(){
int T;
cin >> T;
while(T–){
ll N, K, sum(0),ran,x,j(0);
cin >> N;
cin >> K;
ran = pow(2,N);
ll a[1000001];
for(ll i = 0; i < ran; i++){
a[i] = i;
}
if(K == 0){
//cout << “0” << ‘\n’;
}
if (K > 0){
while(K–){
ll temp;
temp = a[j];
a[j] = a[ran-1-j];
a[ran-1-j] = temp;
j++;
}

        }
    for(ll i = 0; i < ran; i++){
        
        
        //cout << a[i] << " ";
        //x =  a[i]^i;
        //cout << x << "   "; 
        sum = sum + (a[i]^i);
    }
    cout << sum <<'\n';
}

return 0;

}
‘’’
What’s wrong with this approach ?
It’ s Showing me RE.
Thank You

1 Like

Mostly because you are declaring too much memory. In each test you are declaring an array of size 10^6. Also your solution has a runtime of O(T \cdot 2^N) which is too much. 2^N > 10^9 if N=30.

1 Like

Dhanyavad

1 Like

using ll = long long;
using ld = long double;

void solve() {
ll n,k;
cin >> n>>k;
if (k == 0) {
cout << “0\n”;
}
else {

	ll e = pow(2,n)-1,s = 0;
	unsigned long long ans = 0;
	while (k > 0) {
		ans = ans + (e ^ s);
		e--;
		s++;
		k--;
	}
	cout << ans*2 << '\n';	
	
}

}

int main() {

int t;
cin >> t;
while (t--) {
	solve();
}

}

I was getting a TLE in this solution. Can someone point out the errors.
Thanks :slight_smile:

Note::
I am taking the rightmost and the left most number and then XORing them K times moving towards the middle of the the sequence. Then adding all the XORed elements. I am a complete beginner I think I am doing somthing really silly here.

Blockquote

The constraints in this case for k are:
0 ≤ K ≤ 10^9
When the time limit is 1 second.
O(N) solution works fine for when n <= 10^6 ~ 10^7.
When n>=10^7, you need to find a better solution.

Can someone explain how do we get maximum XOR

by swapping maximum numbers to minimum numbers k number of times.
let the array is 0 1 2 3 4 5 , k=1, we swap 0 and 5

sorry i am not understanding what you wrote. The thing i did to solve the question is by xorring odd with even integer.
like ; let an array be
0 1 2 3 4 5 6 7 and k==8
we will do
7 6 5 4 3 2 1 0
now every individual xor result will be 7. you do 7 xor 0 =7, 6 xor 1 =7 and so on. and we do the operation L times ( L= 2^n/2). if k=L ans= 2*(a[2L-1])L and if k<L ans= 2(a[2L-1])k;
here a[2
L-1] refers biggest element in the array. You can refer to my code if you still have any doubt

:sweat_smile: thanks

O(1)solution
int n, k; cin >> n >> k; int maxi = (1ll << n); maxi -= 1; int cur = maxi; int ans = 0; int z = (maxi + 1) / 2; ans += maxi * min(k, z); cout << 2 * ans << endl;

Hey, isn’t this a bad practice?

Haha it is. But well I often use this to avoid any overflow issues. I mostly forget about the range hence I prefer to use this to not care about overflow.

1 Like

If it helps, since i⊕(2^N - 1 - i) = 2^N - 1
We can at most do 2^(N-1) swaps to maximise the value of an array A of length 2^N by swapping ith element with (2^N - 1 - i)th element. Hence K <= 2^(N-1) and with one swap the value of the array increases by 2*(2^N -1)

why isn’t my solution working? I mean it looks similar to the editorial solution but still giving WA, can anyone pls point out the difference between the two.
my solution
AC solution

I understand the solution and the maths behind it, my only doubt is with this line of code common to the setter’s and tester’s solutions:

ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

What does it do?

Thanks mate didn’t knew this thing . :grinning_face_with_smiling_eyes:

This is for fast input/output. Basically IO buffer flushes after each use of cin/cout. After putting this, it does not flush. Read more about it here.

Got it, thanks a lot!

This can be solved in O(1) per test case.as n<=30 we can use bitwise operator for calculating maxm value.
1)first calculate maximum value as 2^(n)-1.because here elements are from 0 to (2^n)-1.and maxm value we will get only when we are making xor of first and last value again second and second last value and so on.for k we can rearrange 2*k numbers.

2)as there are 2^n numbers.we can swap maxm 2^(n-1).if k is greater than 2^(n-1) or 2*k>2^n then for k value there are insufficient numbers with different indexes.because we are only calculating maxm value and for that we are making xor of first with last,xor of second with second last and so on.

3)if k>2^(n-1) then maxm value will be (2^n)-1.let’s take example.for 0 to 7 maxm value we can get by making xor of 2 elements is 7.because here all the bits are 1 and that’s the maxm value.
so,if k>2^(n-1) the maxm value of sum of array is (2^(n))*((2^n)-1).

4)if k<=2^(n-1) or 2k<=2^n then maxm value of sum of array will be (2^(n)-1)(2*k).

we can calculate power of 2 usinng bitwise otherwise we can store the power of 2 in an array with the maxm constraint value of n.because to avoid multiple operations.

        long long p=((long long)1<<n);
    long long maxm=p-1;
    if(2*k<=p)
    {
    cout<<(((long long)(maxm)*(2*k)))<<'\n';
    }
    else
    {
        cout<<(maxm)*(p)<<'\n';
    }

here’s the algorithm.

This is O(1) per test case.
bitwise uses constant operations.

Thanks.

1 Like