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=-0.5 required=5.0 tests=BAYES_05 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 23:00:40 PST Path: archiver1.google.com!newsfeed.google.com!sn-xit-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 23:04:19 -0700 Organization: Public Property Software Message-ID: <3B5BBE63.3534BD78@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:10443 Date: 2001-07-22T23:04:19-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 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