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-29 12:56:00 PST Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsxfer.eecs.umich.edu!news.bu.edu!inmet!not-for-mail From: Tucker Taft Newsgroups: comp.lang.ada Subject: Re: Programming Contest Date: Sun, 29 Jul 2001 15:57:05 -0400 Organization: AverStar Message-ID: <3B646A90.F41F4181@avercom.net> References: <3B5AFD7F.9C7D24D1@PublicPropertySoftware.com> <3B5B7D4F.BCACD2BC@avercom.net> <3B5BBE63.3534BD78@PublicPropertySoftware.com> NNTP-Posting-Host: 209.6.249.6 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353" Content-Transfer-Encoding: 7bit X-Trace: inmet2.burl.averstar.com 996436550 10901 209.6.249.6 (29 Jul 2001 19:55:50 GMT) X-Complaints-To: usenet@inmet2.burl.averstar.com NNTP-Posting-Date: 29 Jul 2001 19:55:50 GMT X-Mailer: Mozilla 4.75C-CCK-MCD {C-UDP; EBM-APPLE} (Macintosh; U; PPC) X-Accept-Language: en Xref: archiver1.google.com comp.lang.ada:10696 Date: 2001-07-29T19:55:50+00:00 List-Id: 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