take a look here http://en.wikipedia.org/wiki/Pigeonhole_principle
what you have to do is to get a cycle on the groups and the cycle will always be found in O(N)(this is proofed by the Pigeonhole Principle). then the answer will be something like that = before cycle+(cost of cycle*number of cycles)+ after cycle. you can make it by O(N) if you use variable length window to move on the array and preprocess the array which tells you the length of that group. On May 9, 10:56 pm, Felipe Sodré Silva <[email protected]> wrote: > http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2 > > > > > > On Sun, May 9, 2010 at 12:33 PM, Pakku <[email protected]> wrote: > > Guys, > > > I am wondering what all optimization we can really do. > > Though, in the qualification, for the theme park problem, i could not > > solve the large input problem in the given time frame, i optimized it > > latter in the practice mode. > > > These are the optimization that I did. > > > for each test case, > > > 1. if capacity of roller coaster >= total strength [ sum of all groups > > ] then simply total earnings = total strength * number of rides. > > 2. detect if can get a rep if yes, then > > TotalEarnings = ( EarningsForRep * (RidesPerDay / TripsNeededToGetARep ) > > ); > > and then TotalEarnings += earnings for the TripsStillLeftInADay ; > > > Apart from these 2 optimization is there any other place we can > > optimize. what is the best possible optimized solution. > > anyone willing to share the best solution. > > > -Prakash > > > -- > > You received this message because you are subscribed to the Google Groups > > "google-codejam" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<google-code%2bunsubscr...@googlegr > > oups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group > athttp://groups.google.com/group/google-code?hl=en. -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
