PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Tejas Pandey
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
2197
PREREQUISITES:
Bitwise Operations
PROBLEM:
Chef’s last task in his internship requires him to construct 2 permutations, each having length N, such that the bitwise AND of each pair of elements at every index is the same.
Formally, if the permutations are A and B, then, the value A_i \& B_i must be constant over all 1\le i \le N.
Help Chef by providing him 2 such permutations. If it is not possible to construct such permutations, print -1 instead.
EXPLANATION:
In case N = 1, A = [1] and B = [1].
Now let’s discuss for N \geq 2.
Observation 1: The only constant value possible is 0.
Any number greater than 1, say c would not be possible since then no number can be paired with 1 to give their AND as c. If we select the constant as 1, then also no number can be paired 2 to get their AND as 1. Thus by elimination of choice, only 0 is a viable candidate.
Observation 2: It is not possible if N is odd(and greater than 1).
Say for N = 2k + 1. There would be k+1 odd numbers and k even numbers. Since each odd number has their first bit set and to unset it we would need an even number but since the number of odd numbers is more than that of even numbers, therefore it won’t be possible to make such pairs.
Observation 3: if there are two numbers say, a and b, then if
sum of a and b is of the form 2^x - 1, then their AND is 0.
Thus when N is even, we can find all such possible pairs by going from N to 1, and for each number i(not already included in a pair), we can find its pair k by subtracting i from p where p is formed by setting all unset bits(right of MSB) of i.
This way after finding all the pairs, we can construct our two permutations.
TIME COMPLEXITY:
O(N), for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution