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: O(N!N)

Subtask 2

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

1,N,2,N1,3,N2,

Absolute Value of Differences:

N1,N2,N3,N4,N5,

Time Complexity: O(N)


Comments

There are no comments at the moment.