What's incorrect about my solution in this google code jam exercise?

Question

Today, I've participated in google code jam round 1B. In code jam, there was a problem called 'Osmos': https://code.google.com/codejam/contest/2434486/dashboard

problem description

The problem states that there's a game, where the player is a thing, that can only eat things smaller than it, and will become larger by the size of the thing he ate. For example, if the player has size 10 and eats something of size 8, it becomes size 18.

Now, given the size the player starts off at, and the sizes of all the other things in the game, you should give the minimum number of operations required to make the game beatable, which means that you're eventually able to eat everything.

An operation can either be adding some thing, or removing some thing.

The code I used

write_case is a function that writes the output for every test case in the right format. I've used it in other code jam rounds, and I know it is correct, and inp is the file object of the input file.

cases = int(inp.readline())
for case in xrange(cases):
    # armin is the variable containing the size of the player,
    armin, n = int(inp.readline.split()[0])
    # others is a list of sizes of other things
    others = [int(x) for x in inp.readline().split()]

    # changes obviously holds the number of required changes
    changes = 0
    for other in sorted(others):  #we loop over all the other things in order.
        if other < armin:  #if the other thing is smaller, eat it, no change needed.
            armin += other
        else: # we'll need to make some changes
            # adding is the biggest size thing the player can eat,
            adding = armin - 1
            if other < armin + adding:  #if adding such a thing is good enough
                                        # to eat the other thing
                armin += adding + other # add it and eat them
                changes += 1 #we've made a change.
            else: # we can't add a big enough thing
                # we have to elete it from the game (skip it from the loop)
                # which is a change 
                changes += 1

    write_case(case + 1, changes ) #output the changes.

My logic behind it

By looping over te other things froom small to large, the player first eats everything it can normally eat. When we encounter something we can't eat, we've eaten everything that's smaller than it, so we'll have to add a new thing so we can grow. If we're adding something new, we might as well make it as big as possible, since the size of the thing we add doesn't change the number of operations. The largest eatable thing I can add, is the player's size -1. If that's enough to eat the next thing, we add it, eat the thing we added, and than eat the thing we previously couldn't eat.

If the addition wouldn't be enough, we don't add it, and just delete (ignore) the current thing). At this point, I could just break from the loop to skip all the other things (since the'll all be too large to eat, the list is sorted.), but add their number to the number of operationns to speed up my sollution, but that wouldn't change the outcome.

This code correctly computes the values for the sample input, but it's incorrect for the contest input. Any idea why?

Answer 1

So your problem looks like what happens if addition isn't good enough... because you could introduce another mote after that to keep feeding yours until it is big enough. If you aren't going to feed it another mote, you might as well just say that you are going to delete all remaining motes.

I published a pretty good description of this problem here, if you are interested.

Answer 2

My approach was that each time I found a block, I figured out how many additions were required to continue. I then built a log of the number of additions and the number of remaining. After I had completed the set, I looped through the log in reverse to determine if it was more efficient to add motes to continue, or remove the remaining motes at each block point. Looking at this now, I can see a number of places I could optimize, but I passed both the small and large with the below C# code.

protected string Solve(string Line1, string Line2)
{
    string[] Inputs = Line1.Split();
    uint A = uint.Parse(Inputs[0]);
    byte N = byte.Parse(Inputs[1]);
    Inputs = Line2.Split();
    List<uint> Motes = new List<uint>(N);
    foreach (string Size in Inputs)
    {
        Motes.Add(uint.Parse(Size));
    }
    Motes.Sort();
    List<Action> Actions = new List<Action>();

    while (Motes.Count > 0)
    {
        if (A > Motes[0])
        {
            A += Motes[0];
            Motes.RemoveAt(0);
        }
        else if(A > 1)
        {
            uint I;
            for (I = 0; A <= Motes[0]; I++)
            {
                A = (A << 1) - 1;
            }
            Actions.Add(new Action(I, Motes.Count));
        }
        else
        {
            Actions.Add(new Action(101, Motes.Count));
            break;
        }
    }

    uint TotalInserts = 0;
    int TotalRemoved = 0;
    for (int I = Actions.Count - 1; I >= 0; I--)
    {
        int StepRemaining = Actions[I].Remaining - TotalRemoved;
        uint StepInsert = Actions[I].Inserts;
        if (StepInsert >= StepRemaining)
        {
            TotalRemoved += StepRemaining;
            TotalInserts = 0;
        }
        else
        {
            TotalInserts += StepInsert;
            if (TotalInserts >= Actions[I].Remaining)
            {
                TotalRemoved = Actions[I].Remaining;
                TotalInserts = 0;
            }
        }
    }

    return (TotalInserts + TotalRemoved).ToString();
}
struct Action
{
    public uint Inserts;
    public int Remaining;
    public Action(uint inserts, int remaining)
    {
        Inserts = inserts;
        Remaining = remaining;
    }
}

Answer 3

Here're what I thought the key points were:

1. It's never desirable to remove from the center of the list. That's a wasted operation. Consider armin, others == 2, [1, 10, 11] - removing the 10 will never make the 11 easier to get to
2. Given this, it's only valid to remove all the remaining items in the list. Therefore, if you have to add more items than there are remaining in the list to progress to the next element, it's more efficient just to remove those large ones.

My correct solution was implemented as:

def solve(armin_size, sizes):
    sizes = sorted(sizes)
    steps = 0

    for i, size in enumerate(sizes):
        add_count = 0
        remove_count = len(sizes) - i
        while armin_size <= size:
            armin_size += armin_size - 1
            add_count += 1

            if add_count >= remove_count:
                return steps + remove_count

        armin_size += size
        steps += add_count

    return steps

EDIT: Just checked the scoreboard again - I got it wrong. Whoops.