Beast Bullies

This problem gives us a list of animals, defines a protocol in which they either chase eachother off, or don't, and asks us if they act optimally, which is the number of animals guaranteed to remain.

In problems such as this, it makes sense to think iteratively. Consider

• The strongest animal will always remain
• If it is only the final two animals, only the strongest will remain, so the second strongest will always prefer to keep others around
• If it is only the final three animals, and the sum of the weakest two is LESS than the strongest, then only the strongest will remain, so they will prefer to keep others around
  • In general, if the remaining non-strongest animals sum to less than the strongest, they will prefer to keep others around
• If of the final three, the sum of the weakest two is GREATER than the strongest, they will always remain
  • Furthermore, since these final will remain, and will always be on the "attack" side, we can treat them as a single animal with respect to the remaining

This leads to the algorithm:

1. Sort the animals in reverse strength order
2. Iterate starting at the third animal, tracking the sum of the remaining "non-strongest" animals
3. When this sum surpasses the strongest animals, create a new "strongest animal" encompassing all remaining animals, and reset the sum
4. Continue iteration at the next-strongest animal