PERMXORITY - Editorial

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:

Bitwise XOR

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;
}
3 Likes

from where can we practice more xor related problems??

7 Likes

Alternate Approach :
Generate all permutations of the array either using next_permutation (builtin function of c++ )or using recursion then check if it satisfies the condition that is check whether the xor of the difference of adjacent elements is equal to zero if it is print it and then return
Do not generate the rest of the permutations
https://www.codechef.com/viewsolution/59468463

2 Likes

This is not a recommended approach. The time complexity of iterating over all permutations of length N and checking for a valid sequence is O(N!). This can time out for a very small value of N, say 12.

One of the solutions for this problem is to print the 5^{th} lexicographically smallest permutation of integers from 1 to N for a given N (N must be Even). That’s the reason why your submission was accepted.

7 Likes

Yea I know its not a recommended approach actually I wanted to see the pattern between the permutations which satisfy the condition and that’s how I came to this solution and Thanks for telling me why the submission works

1 Like

Hey, you can find more XOR related problems here:

  1. Tags - problems | CodeChef
  2. Tags - problems | CodeChef
1 Like

thanks

I think I am going to ask very silly question:

can’t we just print number from 1 to N because the absolute diff int his condition will be 1 for every pair and XOR of same number will be Zero let’s say we have N=5

1 , 2 , 3 ,4 ,5

2-1=1 , 3-2=1 , 4-3=1 , 5-4=1

1^1^1^1=0

Hey @proxnoob :smiling_face:
You are right but only for the case when (N is odd , since there you only have N-1(even) 1’s so XOR will be 0) but for the case N is even XOR will not be 0 try pen and paper you will get that (also you can see the editorial for the same for N even case).

1 Like