PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: S.Manuj Nanthan
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta
DIFFICULTY:
Simple
PREREQUISITES:
PROBLEM:
You are given an integer N. Construct a permutation A of length N which is attractive.
A permutation is called attractive if the bitwise XOR of all absolute differences of adjacent pairs of elements is equal to 0.
Formally, a permutation A = [A_1, A_2, \ldots, A_N] of length N is said to be attractive if:
|A_{1}-A_{2}| \oplus |A_{2}-A_{3}| \oplus \ldots \oplus |A_{N-1} - A_{N}| = 0
where \oplus denotes the bitwise XOR operation.
Output any attractive permutation of length N. If no attractive permutation exists, print -1 instead.
Note: A permutation of length N is an array A = [A_1, A_2, \ldots, A_N] such that every integer from 1 to N occurs exactly once in A. For example, [1, 2, 3] and [2, 3, 1] are permutations of length 3, but [1, 2, 1], [4, 1, 2], and [2, 3, 1, 4] are not.
QUICK EXPLANATION:
If N is odd
In this case, there are total even number of absolute difference terms. If these terms are all equal, their overall XOR will become 0.
Hence, we can have all absolute difference terms to be equal to 1. In simpler words, the permutation \{1, 2, \ldots N\} is a valid permutation.
If N is even
In this case, there are total odd number of absolute difference terms.
We cannot make XOR of 1 term to be 0 (as each term is greater than 0). Let us try to make XOR of first 3 terms to be 0, and follow the above strategy for rest of the terms.
One of the valid permutation is: \{2, 3, 1, 4, 5, 6 \ldots N\}.
Corner Case
N = 2 is a corner case. Since we have only one absolute difference term, and it is non-zero, we cannot have the overall XOR as 0. The answer would be -1 in this case.
EXPLANATION:
There can be many possible constructions. This editorial explains one of the strategies to make a valid permutation.
Let us divide our solution in two parts depending on the parity of N. We will first see a valid construction when N is odd, and then we will use this solution to construct a valid permutation for even values of N. Finally, we will take a look at a corner case.
When N is odd
In this case, we will have even number of absolute difference terms. Now, whenever we deal with overall XOR to be equal to 0, one of the properties of XOR that we should keep in mind is: a \oplus a = 0. Let us extend this property for our case. If we take even number of a's and take their XOR, the result will be equal to 0.
So, if all the absolute terms are equal, we will have a valid permutation. One of the permutation that satisfies this property is \{1, 2, \ldots , N \}
When N is even
In this case, we will have odd number of absolute difference terms. Also, we already have a solution when we have even number of absolute difference terms. Let us think in the direction of breaking these odd number of terms in two parts - one having odd number of terms such that its XOR is 0, and other having even number of terms. Because we can’t have XOR of 1 term as 0 (because each term is greater than 0) , let us focus on 3 terms.
Let the permutation be \{P_1, P_2, \ldots P_N \}. The above parts corresponds to terms from the following two sequences - \{P_1, P_2, P_3, P_4\} and \{P_4, P_5, \ldots P_N\}.
We have already seen that if \{P_4, P_5, \ldots P_N\} = \{4, 5, \ldots , N\}, then we have the XOR of absolute difference terms as 0. Also, this fixes the value of P_4 as 4, and leaves 1, 2 and 3 for P_1, P_2 and P_3.
A little trial and error on paper shows that permutations like \{1, 3, 2, 4\} or \{2, 3, 1, 4\} have their XOR of absolute difference terms as 0.
Hence, one of the valid permutations is \{2, 3, 1, 4, 5, 6 \ldots N\}.
An Important corner case
Note that if N = 2, we have only one absolute difference term, and it is non-zero. So we cannot have the overall XOR as 0. The answer would be -1 in this case.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll ,ll>
using namespace std ;
const ll z = 998244353 ;
int main()
{
int t ;
cin >> t ;
while(t--)
{
int n ;
cin >> n ;
if(n == 2)
{
cout << -1 << endl ;
continue ;
}
if(n%2 == 1)
{
for(int i = 1 ; i <= n ; i++)
cout << i << ' ';
cout << endl ;
}
else
{
cout << 2 << ' ' << 3 << ' ' << 1 << ' ';
for(int i = 4 ; i <= n ; i++)
cout << i << ' ';
cout << endl ;
}
}
return 0;
}
