Editorial for CPC '19 Contest 1 P1 - Distance

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

For the first subtask, you can just brute force all possible ways you can visit all the houses and output any that matches the constraints of the problem.

Time Complexity: $\mathcal{O}(N! \cdot N)$ $O (N! \cdot N)$

Subtask 2

The trick here is to start from $1$ $1$ , then go to $N$ $N$ , then back to $2$ $2$ , then go to $N-1$ $N - 1$ , then back to $3$ $3$ , etc. If you look at the sequence here, you'll notice the absolute difference between adjacent values is constantly decreasing:

$\displaystyle 1,N,2,N-1,3,N-2,\dots$ $1, N, 2, N - 1, 3, N - 2, \dots$

Absolute Value of Differences:

$\displaystyle N-1,N-2,N-3,N-4,N-5,\dots$ $N - 1, N - 2, N - 3, N - 4, N - 5, \dots$

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.