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
1 Like
My general strategy was to link up the paths, then spend 4 seconds randomly selecting 2x2 sections and optimizing them. For example:
D . __\ R D
D . / D L
A path that starts at the top left and goes down can be expanded to go right,down,left,down, filling the square. Or the reverse is possible.
Linking up the paths was initially done with a space filling walk, specifically a boustrophedonic one. Boustrophedonic means “as the ox turns”, referring to an ox ploughing a field. It really means going from left to right then right to left, like this:
1 2 3 4
8 7 6 5
9 10 11 12
And the word is as powerful here as it is on the Scrabble board. I mark the endpoints on my grid and proceed boustrophedonically, laying a path if I am between endpoints.
Unfortunately I don’t really want to fill the whole grid up yet. If there are lots of cells with negative weights I want to be able to path around them. Ideally I would like to connect endpoints that are close together, so my optimization algorithm is free to occupy or avoid squares as necessary.
I have two ways to do this. The first is to divide the grid into columns with even numbers of endpoints and path those boustrophedonically, instead of doing the whole grid in one go. The other thing I have is a second pass that shortens the weaving left and right into straight paths.
Having done this, I then start randomly selecting 2x2 sections, seeing if there is a way to change them, and seeing if that change improves my score. For the first second, there is a 1 in 4 chance that a change which lowers my score will be made anyway. This helps my short paths expand and fill the map. The probability of this then drops significantly and I optimize the paths as much as possible in the remaining time.
My solution
1 Like
Great ideas! Thanks for sharing