This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
The Travelling Salesman Problem
Sounds not very hard at first, but it is an NP-hard problem, so bruteforce is impossible. What we are going to use are heuristic algorithms, which don't find the optimal solution but a solution close to the best.
There is a puzzle about the TSP on this website already, which features one heuristic algorithm called "Nearest neighbor".
- You win if your output is correct!
- You lose if your output isn't correct!
Warning: the validation tests used to compute the final score are not the same as the ones used during the event. Harcoded solutions will not score highly.
Line 1: an integer N, the number of input points
N lines: two integers X and Y, the coordinates of a given point
Allotted response time to output is ≤
0 0 // This is point 0
0 2 // This is point 1
2 0 // This is point 2
2 2 // This is point 3
The shortest path from start point 0 to all other points and back to 0 is 0 - 1 - 3 - 2 - 0, therefore we output 0 1 3 2 0
Also 0 1 2 3 0 would be valid, but it doesn't get scored that high, since it has a higher cost
A higher resolution is required to access the IDE