PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Sandeep V
Tester: Manan Grover
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy
PREREQUISITES:
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;
}
