At most you will have to remove all motes (it doesn't make sense to add more motes than n, since we can just remove all motes instead).
So, the lower limit is 0 (if you can already eat all the motes) and the upper limit is n (all of them, since you can just remove all). On Sun, May 5, 2013 at 8:57 PM, Vaibhav Tulsyan <[email protected]>wrote: > *"So the only cases for removing motes that you have to consider are > cases where all of the n largest motes are removed, for some n between 0 > and all of them."* > > I didn't understand this. > > > On Sun, May 5, 2013 at 8:30 PM, Joseph DeVincentis <[email protected]>wrote: > >> The point is that removing a mote out of the middle of the sorted >> sequence doesn't help. If you can already eat that mote then you are better >> off not removing it. If you can't eat that mote without adding other motes, >> then you will have to add other motes to be able to eat the next larger >> remaining mote, and you will have to add at least as many as you would have >> needed to eat the removed mote + the next larger mote. >> >> So the only cases for removing motes that you have to consider are cases >> where all of the n largest motes are removed, for some n between 0 and all >> of them. >> >> Also, for eating motes, if you need to add motes, you will add the fewest >> motes if you eat them in increasing order of size. So for both cases you >> want to process them in increasing order. >> >> After adding any motes necessary to eat each mote in the sorted sequence, >> Luke's program computes the score for the case where you remove all the >> remaining motes. By doing it this way, he checks all the cases for removing >> motes that might be optimal, keeping track of the best score found so far >> (record) along the way. >> >> >> On Sun, May 5, 2013 at 10:25 AM, sumit sharma <[email protected]> wrote: >> >>> 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. >>> >>> >>> >> >> -- >> 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. >> >> >> > > > > -- > Regards, > Vaibhav Tulsyan. > > -- > 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.
