XORED - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Sandeep V
Tester: Manan Grover
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy

PREREQUISITES:

Bitwise Xor

PROBLEM:

Given two positive integers N and X, construct an array A of N elements such that:

  • For each i (1 \leq i \leq N), 0 \leq A_i \leq 5 \cdot 10^5.
  • All the elements in the array A are pairwise distinct.
  • Bitwise Xor of all the N elements of the array is X.

QUICK EXPLANATION:

  • For N = 1, the first and only element of the array is X.
  • For N>1, Set the array as A_i = i (0 \leq i < N). Let Y be the bitwise xor of the first N-1 values. Then, the last element of the array will be Z = YβŠ•X.
  • If Z lies outside the given range or matches with one of the first N-1 elements, toggle its 19^{th} bit.
  • To maintain the bitwise xor of the whole array as X, toggle the 19^{th} bit of one other element.

EXPLANATION:

Easier Version - One duplicate possible

For an easier version, let us think of constructing an array having atmost 1 duplicate and satisfying all other conditions.

Solution

Let A_i = i for 0 \leq i < N-1, and Y denote the bitwise xor of the first N-1 values of this array. We can set the last element of the array as YβŠ•X. This way,

  • The bitwise xor of all the elements of the array = Y (bitwise xor of first N-1 elements) βŠ• (YβŠ•X) (last element) = (YβŠ•Y)βŠ•X = X.
  • Since the first N-1 elements are pairwise distinct, regardless of the value of the last element, there can only be 1 duplicate at maximum.

Based the idea of the easier version, let us set A_i = i for 0 \leq i < N-1. Let Y denote the bitwise xor of the first N-1 values of this array. To make the bitwise xor of the whole array X, the last element should be Z = YβŠ•X.

We can categorise the possible values of Z as:

  • Category 1: (N-1 \leq Z \leq 5 \cdot 10^5) - Since the value of Z is within the bounds, it is a possible candidate. Also, Z is greater than all other elements in the array, therefore, ensuring that all the elements are pairwise distinct. We can simply set the last element as Z.
  • Category 2: (Z < N-1) - The maximum value of N is 10^5. This means that all bits beyond the 18^{th} bit of Z must be unset. We can set the 19^{th} bit of Z to transform Z into the first category and place it as the last element.
  • Category 3: (Z > 5 \cdot 10^5) - Let us look at the maximum value Z can take. We know that Z = YβŠ•X. This implies that the maximum number of set bits in Z would be less than or equal to that of X and Y. Since the maximum out of these is X and X \leq 5 \cdot 10^5 which takes 19 bits at maximum, we can say that Z<2^{19}.
    Thus, the updated range of Z is (5 \cdot 10^5 \leq Z < 2^{19}). This means that the 19^{th} bit of Z is set. Turning off the 19^{th} bit of Z would transform it into one of the first two categories. We can then place it as the last element.

Note that while transforming Z (category two and three), we toggle the 19^{th} bit of Z. Thus, the bitwise xor of the array becomes (XβŠ•2^{18}). To revert this effect, we can set the 19^{th} bit of one other element. Based on the value of current Z, we have to make sure that all the elements are pairwise distinct.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
def firstXOR(n):
    if n % 4 == 0 :
        return n
    if n % 4 == 1 :
        return 1
    if n % 4 == 2 :
        return n + 1
    return 0
t=int(input())
from random import *
for _ in range(t):
    
    n,x=map(int,input().split())
    if(n==1):
        print(x)
        continue
    ans=[]
    if(x<=10**5):
        c=firstXOR(n-2)
        if(firstXOR(n-2)==x):
            for i in range(0,n-2):
                ans.append(i)
            c=firstXOR(n-3)
            ans.append(2*(10**5))
            ans.append(c^(2*(10**5))^x)
        else:
            for i in range(1,n-1):
                ans.append(i)
            ans.append(2*(10**5))
            ans.append(c^(2*(10**5))^x)
    else:
        c=firstXOR(n-1)
        if(c==0):
            for i in range(1,n):
                ans.append(i)
            ans.append(x)
        elif(c==1):
            ans.append(0)
            for i in range(2,n):
                ans.append(i)
            ans.append(x)
        elif(c==n-1):
            for i in range(0,n-1):
                ans.append(i)
            ans.append(x)
        else:
            ans.append(0)
            if(x==(5*10**5)):
                for i in range(2,n-1):
                    ans.append(i)
                ans.append(368928)
                ans.append(368928^x)
            else:
                for i in range(1,n-1):
                    ans.append(i)
                ans.append(1^x)                           
    print(*ans)
Tester's Editorial
#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);
        }
    }
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t = readInt(1, 200000, '\n');
  int temp = 1 << 18;
  int ns = 0;
  while(t--){
    int n, x;
    n = readInt(1, 100000, ' ');
    x = readInt(1, 500000, '\n');
    ns += n;
    assert(ns <= 300000);
    if(n == 1){
      cout<<x<<"\n";
      continue;
    }
    int ans[n];
    for(int i = 0; i < n - 1; i++){
      x ^= i;
      ans[i] = i;
    }
    if(x >= n && x <= 500000){
      ans[n - 1] = x;
    }else{
      if(x > 500000){
        ans[n - 1] = x - temp;
      }else{
        ans[n - 1] = x + temp;
      }
      if(ans[n - 1] == n - 2 + temp){
        ans[0] = temp;
      }else{
        ans[n - 2] += temp;
      }
    }
    for(int i = 0; i < n; i++){
      cout<<ans[i]<<" ";
    }
    cout<<"\n";
  }
  return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, x;

void solve()
{
    cin>>n>>x;

    if(n==1){
        cout<<x;
        return;
    }

    int y = 0;
    int ans[n];
    for(int i = 0; i<n-1; i++){
        ans[i] = i;
        y ^= i;
    }

    int z = y^x;
    int temp = 1<<18;

    if(z>=n-1 && z<=500000){
        ans[n-1] = z;
    }
    else{
        ans[n-1] = z^temp;
        if((ans[n-2] ^ temp) == ans[n-1]){
            ans[0] ^= temp;
        }
        else{
            ans[n-2] ^= temp;
        }
    }
    for(int i = 0; i<n; i++){
        cout<<ans[i]<<' ';
    }
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
9 Likes

Editorial Solution
(ans[n-2] ^ temp) == ans[n-1]

How we will know: ans[i]^temp==ans[n-1]

Please can anyone elaborate

3 Likes

I followed a seemingly different approach for the problem.
a) The basic idea used if we take bitwise xor of four numbers of the type 4N , 4N+1,4N+2,4N+3 it will always turn out to be zero.

b) we can represent a set of four elements by a number i as 4i, 4i+1, 4i+2,4i+3

c) for any number a , floor(a/4 )(conventional division in c++) is bound to form that 4 element set which contains the number a. We will not take this number in our set of i’s as we simply have sufficiently possible i’s to sufficiently fill the array.

So one can look at the array of size N in the following way:

  1. if N%4==1 , we simply fill the first element of the array with X and for starting from i =0 we store all possible i’s 0,1,2… b such that size of this set is n/4 (not including X/4);

  2. if N%4==2 then always 0,X is the possible pair to include . form a n/4 sized set of i’s which do not include 0,X/4;

Now the tricky part of N%4==3 and ==0 comes.
find the binary representation of X. All possible values of X can be represented in 19 bit size.

1 Like
  1. if N%4 == 3
    we need to find three numbers a,b,c such that a^b^c = X.
    3 cases arise:
    i) 3 or more set bits:
    a = 2**(i1) , b = 2**(i2) , c = X-a-b where i1,i2 are the 1st and 2nd bit position which are set.
    ii) 2 bits are set:
    a = 0 , b = 2**(i1) , c = 2**(i2) where i1,i2 are 1st,2nd set bits.
    iii) only 1 bit is set:
    if we take a = 0, b =0 , c = 2**(i1) duplicity arises. Two remove this we simply find j1 and j2 which are the 1st and 2nd bit positions not being set. we can modify a,b,c as:
    a = 2**(j1) , b = 2**(j2) , c = 2**(i1)+a+b , j1 and j2 bit positions appear 2 times there contribution during bitwise xor becomes 0.

now simply omit a/4 , b/4 , and c/4 from the set of i’s of size N/4.

  1. finally N%4==0 :
    we need a,b,c,d 4 numbers gosh! but still it isn’t tough if properly thought of.
    cases:
    i) if X has 4 or more set bits:
    simply a,b,c become 2 to powers i1,i2,i3 ; d = X-a-b-c
    ii) 3 set bits:
    a = 0, b,c,d are 2 raised to powes i1,i2,i3 respectively.
    iii) 2 set bits:
    we find j1,j2 as described in case N%4==3 and a = 2**(j1), b = 2**(j2) , c= a+2**(i1), d = b+2**(i2)
    iv) only 1 set bit:
    find j1,j2,j3 3 non-set bit positions and now a,b,c,d become:
    a= 2**(j1) , b = 2**(j2) , c = 2**(j3) , d = 2**(i1) +a+b+c;

in this case we need i’s set of size N/4 -1 with no i equal to a/4,b/4,c/4 or d/4.

Finally for all possible values of i include the four element set in the array and you have your answer

1 Like

https://www.codechef.com/viewsolution/56199402
can anyone check why it’s partially correct?

yes bro i used the same approach but got wrong answer. Can anyone please verify the code from @codechef team.

#include

using namespace std;

int main()
{
// your code goes here
long int T;
cin>>T;
while(T–){
long long int x,n;
cin>>n>>x;
if(n>4)
{
long long int l=n;
for(long long int i=4;i<l;i=i+4){
if(i!=(x-x%4))
cout<<i<<" β€œ<<i+1<<” β€œ<<i+2<<” β€œ<<i+3<<” β€œ;
else l=l+4;
}
}
if(n%4 == 0) cout<<1<<” β€œ<<2<<” β€œ<<3<<” β€œ<<x<<”\n";
else if(n%4 == 1) cout<<x<<"\n";
else if(n%4 == 2) cout<<0<<" β€œ<<x<<”\n";
else if(n%4 == 3) {
long long int h=x-x%4;
if(h !=x)
cout<<h<<" β€œ;
if(h+1 != x)
cout<<h+1<<” β€œ;
if(h+2 != x)
cout<<h+2<<” β€œ;
if(h+3 != x)
cout<<h+3<<” β€œ;
cout<<”\n";
}

}
return 0;
}

In your code if X is less than n then X is surely repeated in your array. First find the elements of n%4 which xor to X and then sets of four which do not include the elements calculated for n%4;

1 Like

if(i!=(x-x%4))
cout<<i<<" β€œ<<i+1<<” β€œ<<i+2<<” β€œ<<i+3<<” β€œ;
else l=l+4;

I have used this code if(i!=(x-x%4)) not to repeat the x in array.

at x = 500000 , if you print h+i , i = {1,2,3} it is going to exceed the limit of 0<=a<=500000 where a is an element of the array.

1 Like

Thanks

But my code is not also showing partialy correct one (30% result) where x can be max 10^5 .

please tell me the second and third condition in this

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

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, x;

void solve()
{
cin>>n>>x;

if(n==1){
    cout<<x;
    return;
}

int y = 0;
int ans[n];
for(int i = 0; i<n-1; i++){
    ans[i] = i;
    y ^= i;
}

int z = y^x;
int temp = 1<<18;

if(z>=n-1 && z<=500000){
    ans[n-1] = z;
}
else{
    ans[n-1] = z^temp;
    if((ans[n-2] ^ temp) == ans[n-1]){
        ans[0] ^= temp;
    }
    else{
        ans[n-2] ^= temp;
    }
}
for(int i = 0; i<n; i++){
    cout<<ans[i]<<' ';
}

}

int32_t main()
{

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

sync;
int t = 1;
cin>>t;
while(t--){
    solve();
    cout<<"\n";
}
return 0;

}

Isn’t it funny that the logic conclusively was just x^x=0

I used the exact same approach of video editorial but in c++14 it is giving some WA
While same code on c++17 passed, What could be the reason?

#include <iostream>
using namespace std;

void print_arr(int ar[], int n)
{
    for(int i=0;i<n;i++)
        cout<<ar[i]<<" ";
    cout<<endl;
}

int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        int N, X;
        cin>>N>>X;
        
        if(N == 1)
        {
            cout<<X<<endl;
            continue;
        }
        int ans[N];
        int temp_xor = 0;
        for(int i=0;i<=N-2;i++)
        {
            ans[i] = i;
            temp_xor = temp_xor ^ i ;
        }
        int last = temp_xor ^ X;
        int setbit_18 = (1LL<<18) ;
        
        
        if(last >= N-1 && last <= 500000)
            ans[N-1] = last;
        else
        {
            ans[N-1] = last ^ setbit_18 ;
            if(ans[N-1] == (ans[0]^setbit_18))
                ans[1] = ans[1] ^ setbit_18;
            else
                ans[0] = ans[0] ^ setbit_18;
        }
        print_arr(ans, N);
    }
	return 0;
}

I think binary representation of 5*105 will have 19 bits in binary representation not 18. @notsoloud

Please link to the WA C++14 submission and the AC C++17 submission :slight_smile:

Edit:

If it’s this vs this, note that the code is not the same (the former gives this honking great warning:

[simon@simon-laptop][16:32:05]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling lredoc-XORED-wa.cpp
Executing command:
  g++ -std=c++17 lredoc-XORED-wa.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
lredoc-XORED-wa.cpp: In function β€˜int main()’:
lredoc-XORED-wa.cpp:41:25: warning: suggest parentheses around comparison in operand of β€˜^’ [-Wparentheses]
   41 |             if(ans[N-1] == ans[0]^setbit_18)
      |                ~~~~~~~~~^~~~~~~~~
Successful

)

Got it. Thanks for the effort.

1 Like

@ssjgz Can you please confirm the mistake in the editorial.

Thanks a lot for pointing out! Hope it is fine now!

2 Likes

Thanks for updating the editorial. However, there is one more point. Z will still be less than 219, since the maximum number we can get with 19 bits is 219 - 1. @notsoloud

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


signed main() {
    IOS;
    int t; cin >> t;
    const int M = 32;
    int even = 4e5, odd = 4e5+1, zero = 0;
    int even_two = 400000, odd_two = 400002;
    int inf = 5e5+1;
    while(t--) {
        int n, x; cin >> n >> x;
        cout << n << " " << x << "\n";
        if(n == 1) {
            cout << x << "\n";
        } else if(n == 2) {
            cout << 0 << " " << x << "\n";
        } else {
            set<int> ans;
            int till = 0;
            for(int i=1;i<=n-1;i++) {
                // ans.insert(i);
                till = till ^ i;
            } 
            // n - 1 elements filled till here [1, 2, 3, ... n - 1]
            int last = x ^ till;
            // last ^ till = x; last = x ^ till;
            // if last belongs to [1, 2, 3, ... n - 1] 
            if((last > 0) && (last < n)) {
                auto it = ans.find(last);
                if(last == 1) {
                    // don't want 1 in the array as [2 ^ 3 ^ ... ^ n - 1] = X
                    // erase 1 and 2
                    ans.erase(it);
                    // till = till ^ 1;
                    // till = till ^ 2;
                    // add three unique elements such that 
                    ans.insert(even_two);
                    ans.insert(odd_two);
                    ans.insert(zero);
                    // till = till ^ even_two;
                    // till = till ^ odd_two;
                    // till = till ^ zero;
                } else {
                    // don't want some number which is greater than one
                    ans.erase(it);
                    ans.erase(ans.begin());
                    // till = till ^ last;
                    // till = till ^ 1;
                    ans.insert(even);
                    ans.insert(odd);
                    ans.insert(zero);
                    // till = till ^ even;
                    // till = till ^ odd;
                    // till = till ^ zero;
                }
            } else {
                if(last < inf) {
                    ans.insert(last);
                    till = till ^ last;
                } else {
                    auto it = ans.upper_bound(last);

                }
            }

            // int i = 0;
            // cout << "SIZE: " << ans.size() << "\n";
            // for(auto num : ans) {
            //     cout << i + 1 << " " << num << "\n";
            //     i += 1;
            // }
            // till = 0;
            // for(auto num : ans) {
            //     till = till ^ num;
            // }
            cout << "XOR: " << till << "\n";
            
            // assert(ans.size() == n);
            assert(till == x);
            
            // for(auto num : ans) {
            //     cout << num << " ";
            // }
            // cout << "\n";
        }
    }
}

It passes all the test cases for the first subtask but fails on every test case of the second subtask. I tried to debug for a very long time but couldn’t figure out the problem. What am i missing here?