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