I don't get it that just checking all additions + removals < record for a mode is just enough. Could you please help me understand that? Please check mine. http://ideone.com/gPoM1g
On Sun, May 5, 2013 at 12:27 PM, Luke Pebody <[email protected]> wrote: > 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. > > > -- 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.
