Re: Programming Contest

[Tucker Taft <stt@avercom.net>]

Al Christians wrote:

> 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.

Dynamic programming does not generally require that the optimal
solution for N is always part of the optimal solution for N+1.  However,
it is certainly the case that *some* solution for N is part of the optimal
solution for N+1.  The challenge is to retain as few solutions as possible
from the "N" level to still guarantee that the optimal solution for
the N+1, N+2, ... levels can be composed from it.

In this case, the trick is to throw away some of the N solutions because
they are so obviously "bad" that they couldn't possible appear in
an optimal solution for more than N areas.

For what it is worth, my initial attempt is not selective enough.  Although
I can get up to eight areas in a minute or so, I have yet to get past there.

>
>
> 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

-Tucker Taft stt@avercom.net