PERMOR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

1196

PREREQUISITES:

Familiarity with bitwise OR

PROBLEM:

Given N, find a permutation P of \{1, 2, 3, \ldots, N\} such that for each i \geq 3, P_i \neq P_{i-1} \mid P_{i-2}.
\mid denotes bitwise OR.

EXPLANATION:

For any two integers x and y, note that (x\mid y) \geq x (and so (x\mid y) \geq y as well).

In particular, if we want an integer z such that z \neq (x\mid y), the easiest way is to just ensure that z \lt x and z \lt y: this way, nothing else needs to be checked!

In context of our task, that just means if we’re able to ensure that P_i is strictly less than both P_{i-1} and P_{i-2}, the condition will be satisfied.
That’s pretty easy to do: arrange everything in descending order!
That is, one valid solution is to just print [N, N-1, N-2, \ldots, 3, 2, 1].

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <iostream>
using namespace std;

int main() {
	int t = 0;
	cin >> t;
	while(t--){
	     int n;
	     cin >> n;
	     for(int i = n; i>=1; i--) cout << i <<' ';
	     cout << endl;
	}
	return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    print(*reversed(list(range(1, n+1))))
1 Like
2

I had a different approach for this problem. Since, there is no restriction on the order of the elements or uniqueness of the array, I had the following approach

Let’s choose the first 2 elements as ‘2’ and ‘3’, so the next element can be any even number(let’s say 4).

odd | even ! = even
even | even != odd

Now the next element will be an even number and so one. However, I got TLE…I am not sure where it is consuming more time as the overall time complexity is still O(n).

https://www.codechef.com/viewsolution/1029173119

3

There are a couple of issues here.

There is, however, a restriction that you must print a permutation of length N (which as the statement details, means each number from 1 to N should appear exactly once).
Your approach definitely doesn’t adhere to that.

The TLE is a separate problem, and is just because the default input-output methods in Java are extremely slow.
Consider using a faster template, like this one.

1 Like
4

I approached the problem in a bit different way. First, I printed the numbers 1 3 2 and then iterated over the rest of the numbers till n and printed them all in ascending order.
The thought behind this approach was that if we just printed numbers from 4 to n in ascending order, there would be no such instance where Pi​=Pi−1​∣Pi−2​, and thus, we only needed to care about the order of numbers 1, 2, and 3 which I took into consideration in the first hand only.
However, this is giving me an error, and I am unable to understand why. So, I would request that you please elaborate on this.

1029486661

5

This statement is not correct.
5 | 6 = 7
9 | 10 = 11
13 | 14 = 15
17 | 18 = 19
…

I too came up with a similar approach, but I found out that this won’t work using this code :

list_n = [1, 3, 2] + list(range(4, 5000 + 1))
print(*list_n)


for i in range(3, 5000):
    if list_n[i-1] | list_n[i - 2] == list_n[i]:
        print(list_n[i-2], list_n[i-1], list_n[i])

This checks the sequence where n = 5000, and applies your logic

1 Like