ESUBXOR Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kanhaiya Mohan
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1620

PREREQUISITES:

Bitwise XOR

PROBLEM:

Given a positive integer N, construct two arrays A and B, each of size N such that:

  • A_i \ne A_j for all (1\le i \lt j \le N).
  • B_i \ne B_j for all (1\le i \lt j \le N).
  • A_i \ne B_j for all (1\le i,j \le N).
  • 1 \leq A_i, B_i \leq 3\cdot 10^5 for all (1\leq i \leq N);
  • \oplus A[1,i] = \oplus B[1,i] for all (1\le i \le N) such that i is even.
    Here \oplus A[L,R] corresponds to the bitwise XOR of all elements of the subarray [L,R] of array A. Similarly, \oplus B[L,R] corresponds to the bitwise XOR of all elements of the subarray [L,R] of array B.

EXPLANATION:

We define our two arrays A and B as follows:

A[i] = 2 \times i + 1, 1 \leq i \leq N \\ B[i] = 2 \times i, 1 \leq i \leq N

Now if we check XOR of first i elements of A and B where i is even, then we would notice that the first bit in the final xor of both A[1..i] and B[1..i] would be 0. This is because none of the elements of B has their first bit set since they are all even and for A since there are even number of set bits in the first bit position so the first bit would be unset in the final xor. Thus the first bit would be same in the final xor of both A and B. Now if we ignore the first bit in A and B, then essentially

A[j] = B[j] ,1 \leq j \leq N

so their corresponding XOR \oplus A[1...j] and \oplus B[1...j] would also be the same(ignoring the first bit) , where 1 \leq j \leq N and since we already saw above that the first bit for \oplus A[1...i] and \oplus B[1...i] is also same, therefore

\oplus A[1...i] = \oplus B[1...i]

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

7 Likes

As length is even so XOR of each consecutive pair in both the arrays is equal. so i take 4 consecutive values starting from 2 and assigned it to both the arrays pair wise. eg for n=6
A=[2,3,6,7,10,11]
B=[4,5,8,9,12,13]

As you can see each pair of A and B have 4 consecutive values. like 0,1 in A=[2,3]
0,1 in B=[4,5];

5 Likes

Why am I getting w/a. My solution is here.
My output for every value of n is :
0 1 2 3…(n-1)
2^17 2^17+1+2^17+2…+2^17+(n-1)

Your code will print A[0] = 0 but ques says Ai>=1

2 Likes

Also A[i] should be less than 3*10^5

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std ;

#define int long long int

bool vowel(char c){
    if(c == 'a' or c == 'e' or c == 'i' or c=='o' or c=='u') return true ;
    else return false ;
}

int32_t main()
{
    int t ;
    cin >> t ;
    while(t--){
        int n ; cin >> n ;
        int base = 1 << 17 ;
        if(n == base){
            for(int i = 2 , j = 1 ; j <= n ; i ++ , j++) cout << i << ' ' ;
            cout << '\n' ;
            for(int i = 2 ; i < base ; i ++) cout << i + base << ' ' ;
            cout << base*2 << ' ' << base*2 + 1 << ' ' ;
            cout << '\n' ;
            continue ;
        }
        for(int i = 1 ; i <= n ; i ++) cout << i << ' ' ;
        cout << '\n' ;
        for(int i = 1 ; i <=n ; i ++) cout << i + base << ' ' ;
        cout << '\n' ;
    }
    return 0;
}

u can refer my code :slightly_smiling_face:

I also did the same thing as you , on submission it is showing 3 AC and 1 WA . I don’t know why?
All the array elements are also within the range[(2*(2^17))<(3*10^5)] and greater than 1.
Here is the link to my solution → here

Alternate construction:
A = [2, 3, 4, …, n+1]
B = [n+3, n+4, n+5, … ] if n is odd
else
B = [n+5, n+6, n+7, …]

Not so formal Proof:
Let A = [a, a+1, a+2, a+3, …]

  1. If a is an even number, then a^(a+1) = 1 (because a and a+1 differ in only 0th bit)
  2. 1 ^ (a+2) = a+3 (because a+2 is even and we turn on the 0th bit)
  3. (a+3) ^ (a+3) = 0

and so on
Let first element of A be an even number 2
Then for the sequence A = [2, 3, 4, 5, 6, 7, 8, 9, 10, …]
The prefix xor array will be = […, 1, …, 0, …, 1, …, 0, …] and so on (alternating 0 ans 1s on even index)
That’s why the construction works
Submission

3 Likes

Yes, now I got your point.
Thank you.

My code is giving answer less than 3*10^10

i also thought the same but i could not consider even , odd.

Thank you

Similar approach but starting with 2 rather than 0 this time passed all the test cases.
Here is the solution. When I started iteration from 1 it passed 3 test cases. But I think the solution is correct.

This approach is based on the fact that:
For any even number e, (e) XOR (e+1) = 1
Its more intuitive to reach to this solution. Well Done!

Instead of same nos with diff just in LSB, I wote code with same no.s just diff in MSB but it is failing the third test case. If only I could know what the third test case is…

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

int main()
{
       int t;
       cin>>t;
       while(t--)
       {
           int n;
           cin>>n;
           long bits;
           bits=ceil(log2(2*n+1));
           long x=pow(2,bits-1);
           vector<long> a;
           vector<long> b;
           for(int i=1;i<=n;i++)
           a.push_back(i);
           for(int i=x+1;i<=n+x;i++)
           b.push_back(i);
           for(auto i:a)
           cout<<i<<" ";
           cout<<endl;
            for(auto i:b)
           cout<<i<<" ";
           cout<<endl;
       }
}

why am i getting wrong ans on test case 3

                        

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

#define endl              "\n"
#define ll                long long 
#define mod               1000000007
#define all(x)            x.begin(),x.end()
#define rall(x)           (x).rbegin(),(x).rend()
#define ff                first
#define ss                second         
#define pb                push_back
#define ppb               pop_back
#define yes               cout<<"YES"<<endl;
#define no                cout<<"NO"<<endl;
#define mem(a)            memset(a,-1,sizeof(a))
#define sz(x)             (x).size()
#define rep(i,n)          for(ll i=0;i<n;i++)
#define repi(i,l,n)       for(ll i=l;i<=n;i++)
#define repr(i,a,b)       for(ll i=a;i>=b;i--)
#define ppcll             __builtin_popcountll

#ifndef ONLINE_JUDGE
        #include "debug.hpp"
    #else
        #define debug(...)
#endif

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll __pow(ll x, ll y, int M) {ll res = 1;while(y>0){if(y&1) res = (res*x)%M; y>>=1; x = (x*x)%M;}return res%M;}
ll __pow(ll x, ll y) {ll res = 1;while(y>0){if(y&1) res = (res*x); y>>=1; x = (x*x);}return res;}
int mi(int x, int M) {return __pow(x, M-2, M);}
ll gcd(ll a, ll b) {if(b==0) return a; return gcd(b, a % b);}
ll lcm(ll a,ll b) {return(a*(b/gcd(a,b)));}
int add(int a, int b, int M) {return (a+b) % M;}
int mul(int a, int b, int M) {return (a*b) % M;}
int sub(int a, int b, int M) {return (a-b+M) % M;}

const long long inf=(long long)1e18;
const long double PI=3.14159265358979;

void solve(){
    ll n;
    cin>>n;
    vector<ll>a,b;
    ll x=4,y=7,k=0,ft=4,sd=8;
    while(sz(b)<n){
        if(x>y){
            ft*=2*1ll,sd*=2*1ll;
            x=ft;y=sd-1;
        }
        if(k%2==0){
            // cout<<x<<" "<<y<<" ";
            a.pb(x);a.pb(y);x++;y--;k++;
        }
        else if(k%2==1){
            b.pb(x);b.pb(y);x++;y--;k++;
        }
    }
    rep(i,n){
        cout<<a[i]<<" ";
    }    
    cout<<endl;
    rep(i,n){
        cout<<b[i]<<" ";
    }
     cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc=1;
    cin>>tc;
    while(tc--){
        solve();
    }
    return 0;
}  

Sure, you can know! It is N = 2^{17}.

1 Like

Yes, now I got your point..