There was this contest problem I was stuck on so I am trying to learn algorithms that would help me solve it. Appreciate if you can give me some input on how you would solve this.



An integer N represents the number of points around your coordinate (0,0) where N is between 1 and 2000. Your job is to calculate the maximum points you can visit with the restriction that you cannot visit the same location on two consecutive visits and that every visit has a distance less than the previous visit. Therefore every visit has a strictly decreasing distance.



At first when I thought about solving this, I thought you simply go to the farthest point from your location everytime but that is not the case so it is essential to search through all combinations. Well atleast I think so. Anyone else have any ideas?

Assuming this is a non-directed weighted graph, given a starting point S, your solution would be to pick a destination point D such that the longest path between S and D yields the maximum amount of edges touched. The longest path algorithm would have to remember the previously added edge and the weight associated with it that way it can choose a new edge to add to the longest path with a lesser weight.

Interesting problem. Longest Path is NP-Hard, which leads me to believe that sicne this is a contest problem there are certain heuristics that can be applied to the algorithm to prune the search tree. I'd be interested to see the full problem, as what you supplied is not enough to adequately solve this.