Adam Shelly
2/5/2006 10:27:00 PM
On 2/5/06, Luke Blanshard <luke@blanshard.us> wrote:
> My submission is attached. The key insight: if you start with the
> largest values you can divide the loot one gang member at a time without
> fear of getting wrongly stuck.
...
> Technically, this is not so much an insight as an intuition. It might
> not be true in all cases. But using it as a heuristic, we can cut the
> solution down to O(n^3).
>
I thought I had a similar speedy solution, but then I found a few
places it fails:
Try splitting [4, 6, 8, 9, 18, 26, 34, 36, 39, 40, 43, 50, 55, 66, 67,
76, 82, 83, 86, 91, 96] into 5 parts.
The top-down approach fails to find an even division, but it is possible:
0: 82 66 55
1: 86 67 50
2: 91 76 36
3: 96 83 18 6
4: 43 40 39 34 26 9 8 4
I used the following to generate a bunch of test cases (not all of
which are solvable):
r = []
n=rand(8)+2
20.times{|e| r<< rand(100); }
r << n-r.sum%n i #make sure it's divisible
p n,r
-Adam