PERMAND Editorial

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

1 Like

Solution: 66964476 | CodeChef , why is this code working can someone explain??

why this solution is wrong
>here

What is wrong with this implementation?
It is working well locally(cross-checked using checker function).
https://www.codechef.com/viewsolution/66965341

It will be great if write comments in codes of editorial.

1 Like

how did 400+ solutions got accepted for this problem which seems quite tough to get intuition while contest. Accepted solutions should be approximately around <200 during live contest !!

How can we prove that we can always find unique pairs (a,b) in a permutation such that their is sum is of the form 2^x-1?

1 Like

Everything in my code is almost similar to the editorial, yet it is providing WA. Can anyone please check it here : https://www.codechef.com/viewsolution/67765411
I’ve used XOR to find the other element as compared to method in observation 3 , please do check !