I realized one simple way to find a solution is to find any space-filling curve to enumerate all cells of the grid such that consecutive cells in the enumeration are adjacent cells on the grid. Then as you enumerate cells, when you visit a marked cell, you start the path, until you visit the next marked cell, where you end the path. you basically pair these two marked cells and continue with the enumeration to pair up next marked cells.
one simple space filling curve would be:
1 2 3 4 8 7 6 5 9 10 ...
or you can go by columns, or spiral, etc.
this way you can pair them up in O(n) while ignoring all the weights. (you get some points still)
Improvements: I also marked the cells I visited to pair two points, and ran dijkstra hoping to find a longer path (dijkstra cannot find the longest path but it may find a better path). I also tried both by column and by row and picked the best. but couldn’t go above 36 points.
what ideas did you guys use?
my solution: https://www.codechef.com/viewsolution/22480725