PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: S. Manuj Nanthan
Tester: Harris Leung
Editorialist: Nishank Suresh
DIFFICULTY:
1057
PREREQUISITES:
None
PROBLEM:
Given N, construct a permutation of the integers \{1, 2, \ldots, N\} that minimizes LCM(1+A_1, 2+A_2, \ldots, N+A_N).
EXPLANATION:
The answer is the permutation [N, N-1, \ldots, 2, 1].
Proof
First, note that N+A_N \geq N+1, so no matter what the permutation is, the given LCM is definitely going to be \geq N+1. If we are able to achieve an LCM of N+1, it is clearly the minimum possible.
If we set A_i = N+1-i, then A_i + i = N+1 for every i. So, the LCM we compute simply becomes LCM(N+1, N+1, \ldots, N+1), which is N+1 and we are done.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print(*reversed(range(1, n+1)))