Re: Programming Contest

[Al Christians <alc@PublicPropertySoftware.com>]

Tucker Taft wrote:
> 
> This problem seems like one which just needs a good data structure to > support the dynamic programming solution.  Basically, you start with a > very simple problem,  solve that by a smple search, and then build up > solutions of more complicated problems using results saved away for > solutions to smaller problems.
> 

From my simple testing, this looks like a dead end.  By brute force
search for the optimum solution, I find, for example, that the fourth
lowest board region scores 8 when there are 4 regions, 14 when
there are five regions, 9 when there are 6 regions, and 15 when there
are seven regions, 10 when there are eight regions.  Knowing the answer
for six is not much help for finding the answer to seven, etc.  

Six regions takes about 1 second to figure out, seven takes about 20
seconds to figure out, eight takes about 10 minutes.  So, I don't think
that brute force is going to solve this one up to 25 regions.


Al