Finished #1, 11054 points.
Until the very last night, I used a single simulated annealing for the whole time. My only mutations were placing an arrow into an empty cell and removing a previously placed arrow, and my scoring function was just the objective function without any modifications. I tried adding more complex modifications and penalties for placing arrows, but none of this seemingly helped. In fact, a more extensive testing – say, running a solution 100 times and averaging the score – would’ve helped me compare ideas to each other and probably move to the right direction. But I was somehow too lazy for that, so what I did was just running a new solution several times and looking if the score “seemingly” improved, so there was quite a lot of noise in my decisions.
I made two noticeable improvements in the last few hours which improved my score by several hundred points:
-
Do the big SA for half of the time. For the remaining half of the time, run several small SA’s to improve the score. I took a random 5x5 square subgrid in my current best solution and spent some fixed number of iterations trying to improve the placement of arrows inside it. It has to be mentioned that I implemented this after being overtaken by eldidou. It probably helped me remember that he used a similar idea in a recent Topcoder Marathon Match and described it at the forums – which I’m grateful for
-
Restrict the set of cells touched by the big SA to empty cells which have a neighboring (in eight directions) arrow or void cell. These cells will most likely contain arrows anyway, while arrows in cells with eight empty neighbors will likely screw my score up – every such arrow prevents several cells here and there from being visited twice, which is essential in test cases with large empty areas. It helped me draw pictures like this, which is inoptimal but still pretty good.
The final quick dirty hack was doing SA for the first 0.1 seconds ignoring cells which only have neighboring arrows but not neighboring voids. It helped me get the score of 850 for the 30th test case almost instantly (which turns out to be the best known score), while if I also included cells with arrow neighbors, my score often was in the 700’s. I imagined it wouldn’t hurt me too much on the other test cases as well.
Thank you for the contest, I enjoyed it!