PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given N, find a set of at most 10 permutations of the integers \{1, 2, \ldots, N\} such that the following condition holds:
- For each pair (x, y) with 1 \leq x, y \leq N and x \neq y, there exists a permutation where x appears before y.
EXPLANATION:
Two permutations are enough: simply take
[1, 2, \ldots, N-1, N] \hspace{20pt} \text{ and } \hspace{20pt} [N, N-1, \ldots, 2, 1]
This way,
- If x \lt y, x appears before y in the first permutation.
- If x \gt y, x appears before y in the second permutation.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
n = int(input())
print(2)
print(*list(range(1, n+1)))
print(*list(reversed(range(1, n+1))))