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 simple search, and then build up 
> solutions of more complicated problems using results saved away for 
> solutions to smaller problems.
> 

That's what I'd hope would work.  But is there any logical reason to 
suggest that hope will actually lead us to a good solutions for this 
particular problem?  If I have an optimal solution for a board with n 
regions, how do I know that there is any similarity between that
solution and an optimal solution for a board with n+1 regions?  My
intuition gives me a strong maybe on that question.

I suppose that for small numbers of regions a complete search is
not beyond possible, and that maybe if we saw similarity of 
successive solutions when the number of regions is small, we could
extrapolate that the similarity continues up to n=25.  

I don't have time for this, but it looks like too much fun to pass
up.


Al