Traveling Salesperson Dadas

Choose the village placed at position $i$ as follows.

• If $i$ is odd, choose the unvisited village with the smallest $Y$-coordinate.
• If $i$ is even, choose the unvisited village with the smallest $X$-coordinate.

This always produces a valid order. Suppose that $i$ is odd. When $P_i$ is chosen, $P_{i+1}$ is still unvisited. Since $$ has the minimum -coordinate among all currently unvisited villages and all -coordinates are distinct, . The even case is identical with in place of . Thus every movement condition is satisfied, so a valid order always exists.

Each coordinate value from $1$ to $N$ occurs exactly once. Store the village having each $X$-coordinate and each $Y$-coordinate. Advance a minimum-coordinate pointer until it refers to an unvisited village. Each of the two pointers advances at most $N$ times, so the total time complexity is $O(N)$ and the space complexity is .

Solution written by GPT5.6