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
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];
/******************************************************************************
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;
}
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, …]
If a is an even number, then a^(a+1) = 1 (because a and a+1 differ in only 0th bit)
1 ^ (a+2) = a+3 (because a+2 is even and we turn on the 0th bit)
(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
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.
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;
}
}