PERMCREATE - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: Jeevan Jyot Singh
Tester: Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

1323

PREREQUISITES:

None

PROBLEM:

Given N, construct a permutation of \{1, 2, \ldots, N\} such that any two adjacent elements differ by 2, or say that no such permutation exists.

EXPLANATION:

If N = 2 or N = 3, no valid permutation exists. Otherwise, a required permutation always exists.

There are many constructions, one simple one is as follows:

  • First, print all the even numbers till N. That is, 2, 4, 6, \ldots with the last element being either N-1 (if N is odd) or N (if N is even).
  • Then, print all the odd numbers.

For example, if N = 7 this results in [2, 4, 6, 1, 3, 5, 7] and if N = 10 this results in [2, 4, 6, 8, 10, 1, 3, 5, 7, 9].

Adjacent odd numbers and adjacent even numbers differ by exactly 2, and as long as N \geq 4, 1 will be adjacent to an number that is at least 4, so this construction works for all N\geq 4.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    if n <= 3:
        print(-1)
        continue
    print(*range(2, n+1, 2), *range(1, n+1, 2))
1 Like