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)

Subtask 2

The trick here is to start from 1, then go to N, then back to 2, then go to N-1, then back to 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

Absolute Value of Differences:

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

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.