GCJ – Osmos

Osmos, Round 1B 2013

This was a fun little problem in recursion. We have a mote that wants to eat other smaller motes, and we want to enable our mote to eat all of the others by either removing uneatable motes or adding new, eatable ones. The first thing to notice is that given a set of motes to try to eat, it is always optimal to try to eat the smallest mote. If we can’t eat it, then we know that we also can’t eat any of the larger motes, and if we can eat it, then we’ll only be larger afterwards, able to eat at least as many of the remaining motes as we could before. Secondly, if we want to remove uneatable motes, it’s always optimal to remove the largest motes we can.  If there are any uneatable motes, then the largest must be one of them, and removing it won’t impede our ability to eat any larger motes, if we decide to add more motes later. Thirdly, if we do wish to add a mote to enable our mote to eat others, it is optimal to always add the largest mote that we can currently eat, which will be 1 unit smaller than our current size.

Together, these suggest that the first thing we want to do is sort the motes from smallest to largest and analyze them in order.  For each mote, we have two possibilities:  first, it may be small enough to eat, in which case we eat it, our mote gets larger, and we move on to the next smallest mote.  Second, it may be too big to eat, in which case we can either add another mote just smaller than our current size in hopes that eating it will allow our mote to grow large enough to continue, or we can simply remove all the remaining motes and be finished.  Which of these we choose depends on which will cost fewer changes.  Removing all remaining motes will cost L, where L is the number of motes remaining.  Adding an additional mote will cost 1 plus the number of changes it takes to eat the remaining motes with our new larger mote.

In general, the cost of eating a list of motes $M$ with a mote of size $A$ is $C(A, M) = \begin{cases} min(L(M), C(2A - 1, M)) & A \le M_0 \\ C(A + M_0, M_{1...L}) & A > M_0 \end{cases}$
We can calculate this fairly simply with a recursive formula. Our base cases will be $A=1$, where A can never grow and we must remove all motes and $L(M)=0$, where there are no motes remaining, and we simply return 0. For other cases, if we can eat the first mote, then we recursively call with $A$ incremented by $M_0$ and $M_0$ removed from $M$. If we cannot, then we return the minimum of $L(M)$, and the recursive call with $A$ incremented by $A - 1$.

Of note is that this can lead to a recursive stack as large as $L(M)$, but as this is limited to 100 in the problem statement, we shouldn’t have to worry about space limitations with this solution.

def changes(A, motes):
if len(motes) == 0:
#We're done!
return 0
elif A == 1:
#Can't eat any, have to destroy them all
return len(motes)
elif A > motes:
#Eat the first one
return changes(A + motes, motes[1:])
else:
#Either add the biggest we can or destroy all remaining motes
return min(1 + changes(A + A - 1, motes), len(motes))

def solve_case(case):
"""Take the input data (structured in case) and perform any necessary
calculations to obtain the desired output, formatted as the appropriate
string.
"""

A, motes = case
motes.sort() #We need to sort them first!

output = changes(A, motes)
return output