I used that O(N log N) strategy for my solution (though I got the large input wrong because I did not check for R>E, sigh), so let me explain how my solution worked:
First, make a copy of all the activity values with their original indexes attached, and sort these in descending order. This is the order that the activities will be processed. Another copy of the activity values remains in original order and each is associated with an expended energy, initially -1 to indicate they are unprocessed. Define a set of intervals of unprocessed activities. For each group, we know the first activity index, the last activity index, the energy entering the first activity, and the energy leaving the last activity. Initially there is only one interval encompassing all activities, with entering energy E and leaving energy R (since I included the energy gained from the activity in my leaving energy - the official analysis treats this as 0) Process the activities in that sorted order. You need to find the interval that the activity is in; this is where the binary search is needed. If you just read through the entire list of intervals in order, the program will be O(N^2) and too slow for the large input. If you keep a pointer to each activity's interval, it will still be O(N^2) because you have to update a bunch of pointers when you split an interval, as described below. When you process each activity, calculate the maximum possible energy entering the activity (given the energy entering the interval, R, and the position within the interval of this activity) and the minimum possible activity leaving the interval (given the energy leaving the interval, etc.). The official analysis explains why you want to spend the maximum possible energy here. Now you split the interval into two new intervals for the unprocessed parts before and after this activity, setting the leaving energy of the first interval to the energy entering this activity, and the entering energy of the second interval equal to the energy leaving this activity. On Tue, Apr 30, 2013 at 12:12 PM, Chi Zhou <[email protected]> wrote: > Can someone explain the binary tree part of the O(NlogN) solution for > problem B to me? Why do we need a binary search tree here? The purpose of > the tree is to help find the nearest activity or find out the limits? I > understand the solution in this way: we need to find the nearest activity > that has been considered and find out the limits it imposed. So can we make > the activity array into an object array, each array element will contain > the limits (how many it needs and how many it will leave unspent) when we > find the nearest activity that has been considered. > > (We copy the array first and make it into another object array so that > each of them contain the original position, then sort it to determine which > one we should consider next so we will always consider the highest values > unconsidered activity.) > > Hope I made the question clear > > > On Mon, Apr 29, 2013 at 11:46 PM, Stanislav Zholnin < > [email protected]> wrote: > >> Thanks you a lot. >> >> As usual in my case (and I think it is more or less true for everybody), >> analysis of problems I solved seems to be much more complicated than my >> solution, while analysis of problems I didn't solve seems to be superficial >> and not detailed enough to easily grasp :) Oh, human irrational nature. >> >> -- >> 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]. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/google-code/-/cyqZTw412AEJ. >> 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.
