From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cee6b97ef93f6732 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-07-22 19:18:19 PST Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!sn-xit-01!sn-post-02!sn-post-01!supernews.com!corp.supernews.com!not-for-mail From: Al Christians Newsgroups: comp.lang.ada Subject: Re: Programming Contest Date: Sun, 22 Jul 2001 19:22:11 -0700 Organization: Public Property Software Message-ID: <3B5B8A53.837D8384@PublicPropertySoftware.com> X-Mailer: Mozilla 4.76 [en] (WinNT; U) X-Accept-Language: en MIME-Version: 1.0 References: <3B5AFD7F.9C7D24D1@PublicPropertySoftware.com> <3B5B7D4F.BCACD2BC@avercom.net> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Complaints-To: newsabuse@supernews.com Xref: archiver1.google.com comp.lang.ada:10436 Date: 2001-07-22T19:22:11-07:00 List-Id: 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