# AVDSQUARPLZ - Editorial

Author: Satyam
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh

960

None

# PROBLEM:

Given N, find a permutation of \{1, 2, 3, \ldots, N\} such that the product of any two adjacent elements is not a square.

# EXPLANATION:

The solution is simple: print 1 \ 2 \ 3 \ \ldots \ N.

Proof

In the given permutation, products are of the form i\times (i+1) for some positive integer.

Such a product can never be a square, because:

• i^2 \lt i\times (i+1) \lt (i+1)^2
• There is no perfect square between i^2 and (i+1)^2 since they’re already adjacent squares.

# TIME COMPLEXITY

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

# CODE:

Code (Python)
for _ in range(int(input())):
print(*range(1, int(input())+1))


All the questions of this contest were unclear. Explanations of the test cases were also quite unclear. Though solutions were easy.

If you feel like something about a problem is unclear during the contest, you can ask a clarification: the contest admin or problemsetter will generally reply quite quickly.