PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This problem brought a very close race into this contest. With only two hours to go, it was still unclear who would win.
Even though a lot of coders are finishing the contest with 6 points, the difference in their approaches is quite significant – that is, even with 6 points it’s still very difficult to climb up the rankings to the very top places. For example, a score of at least 0.997 could be achieved by the following very simple approach. First, fill all the empty cells with the same number, say, 25 (so that it’s close to the average of the possible values). Then take any cell, try to change its value into some other value (usually just adding or subtracting 1) and see if this action improves the score (if it doesn’t, undo the change); do this until there are no more cells which can be improved.
Simulated annealing is a better approach, as it allows changes which actually make the score worse with some probability – and the earlier is the moment we try to perform such a change the higher is the probability. For more information on this approach, Wikipedia may help (or some other resource which I don’t know or don’t remember).
The biggest drawback of the mentioned approaches is their locality – that is, sometimes changing the value of a cell doesn’t help unless we change the values of a whole bunch of cells. So, it might be worth taking an “area” of equal values and trying to change all the values in the area (except the cells which weren’t empty from the start). Trying to improve a particular row or column may also help.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.