I first solved it by basically brute force (loop R times, inside that loop again to fill up the car, etc). That worked well enough for the small input, but I tried it for a "worst-case" scenario (using all the top limits for the big input and randomly generating the groups) and it ran around 3 minutes... clearly brute force wasn't going to cut it under 8 minutes.
I then extracted the inner loop and pre-calculated an array of groups and an array of offsets. That is, for each group Gi, I calculated the size of the groups if Gi was the first group on the queue, and an offset Oi that stores how many groups are in this Gi. That way, the loop over R has a lot less work to do than the brute-force approach of calculating how many groups in each ride. The first solution, over the official Big Input, took 24 minutes. The second one, over the same input, took 21 seconds :) On May 8, 2:12 pm, goutham <[email protected]> wrote: > well I got the prob with Theme Park... the small inputs were solving > good but the large inputs contained loops for 100,000,000 which are > huge and time consuming .... and all my 8 min of submission time went > away... > > is anyone else facing the same problem. > > -- > 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.
