AVDSQUARPLZ - Editorial

editorial
,
1

PROBLEM LINK:

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

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

DIFFICULTY:

960

PREREQUISITES:

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))
2

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

3

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.

4

Thanks for the info. I didn’t know about this before.