A brief outline:
Problem A:
If A=1, no motes can ever be eaten, so the answer is you have to remove all N.
On the other hand, if A>1, suppose that in the optimal solution you remove k
motes. It seemed intuitive to me that the k motes you remove would be the
largest k and that for the others what you could do is:
Arrange the smallest N-k motes in increasing size
Then loop through the motes you are going to eat in increasing size:
If you are already big enough to eat the mote, eat it.
Otherwise, you add a mote of size A-1 (if you are going to add a mote, you
might as well add as big a mote as you can possibly eat).
To put another way, what you do is: whenever there is a mote you can eat, eat
it. When there isn't, add the biggest mote you could eat and eat that.
This leads to an O(N) solution - actually O(N log N) because you have to sort
the motes.
* Sort the motes in increasing order.
* Set record = N // It is always possible to just remove all N motes, but
maybe a boring level.
* Set removals = N
* Set additions = 0
* Set currentSize = A
* for each moteSize in motes:
* while currentSize <= moteSize:
* currentSize += currentSize - 1
* additions += 1
* currentSize += moteSize
* removals -= 1
* if additions + removals < record:
* Set record = additions + removals
* Output "Case #CaseNumber: record"
Before submitting for large, if using fixed length integers, think about
whether any of your integer variables can overflow.
In this case, they won't - you will only double in size until you are bigger
than a mote, which means doubling won't make you bigger than 2,000,000. The
remaining increases in size will be from eating all the other motes, of which
there are 100 of size at most 1,000,000, so you cannot possibly end up larger
than 102,000,000, which is less than 10^9, which fits in a signed 31-bit
integer.
Sent from my iPad
On 5 May 2013, at 00:43, Jugesh Sundram <[email protected]> wrote:
> This time I was completely knocked out. I knew how to solve them but ended up
> spending time in debugging. Can't wait for the Contest Analysis.
>
> Any idea when they will be out?
>
> --
> Jugesh Sundram
> ([email protected])
> --
> You received this message because you are subscribed to the Google Groups
> "Google Code Jam" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
