What do you mean by the shift? I saved the state (earnings and runs) for every group I needed to calculate and I detected the repetition next time with the same starting group. In most cases it occured much sooner than after N runs. This itself drops the calc time under 0.1s!
I made the cummulative cost array optimalization in my original solution but when I removed that later, it didn't have any negative impact. It's because the # of groups is quite small and it calculates much more than needed in most cases. The caching of group sizes doesn't have any impact too because the cache is used at most once (with rep. detection). So there are several possible optimizations but in this case (small # of groups) the repetition detection makes the other useless :-) On May 9, 4:14 am, Abhishek Chandel <abhidivs...@gmail.com> wrote: > On Sun, May 9, 2010 at 6:09 AM, Abdelrhman Abotaleb < > > > > > > profvip.abota...@gmail.com> wrote: > > mmm > > To deduce all the patterns ; the overhead may be large > > number of groups are 10000 > > and each group members could be upto 10^7 > > > or rather than deducing the patterns > > each time we rotate the queue[or dequeue then enqueue] ; > > compare with the original queue to test if the repetition rate is less than > > N > > > it could dramatically increase the efficiency. > > > On Sun, May 9, 2010 at 2:29 AM, Luke Pebody <luke.peb...@gmail.com> wrote: > > >> Not sure I agree that the queue of the groups is repeated after N times. > > >> Let N = 7, and let k = 6, and let the groups be size 1,1,1,1,1,1,6. > >> Here the repetition is every 2 times. > > >> On Sun, May 9, 2010 at 1:23 AM, Abdelrhman Abotaleb > >> <profvip.abota...@gmail.com> wrote: > >> > mmm you may note that the queue of the groups is repeated after N times > >> > where N is the number of the groups > >> > So if R>N > >> > you will only calculate the earning from N rounds > >> > and multiply this earn by R[i]/N[i] > > >> > if R[i]%N[i] is a value > >> > so make a loop over a rounds number =R[i]%N[i] > >> > and add the earning from it to the first earning > >> > that's all > > >> > I make the solution and the output is so fast with me [about 10 seconds] > >> > but the contest was over :d > > >> > On Sun, May 9, 2010 at 2:03 AM, sanjay sinha <sanjaysur...@gmail.com> > >> wrote: > > >> >> Hey i have also used only one loop for R (Number of rounds in one day) > >> >> but got some values of R about100000000 and looping through this takes > >> >> a lot of time... > >> >> This was the only one which i failed to submitt. > >> >> @Filpe can you paste a sudo code > > >> >> Thanks > > >> >> On Sun, May 9, 2010 at 5:11 AM, Felipe Sodré Silva <fso...@gmail.com> > >> >> wrote: > >> >> > My solution has only one loop with R cycles for each input, and it > >> >> > solved > >> >> > the large input in less than a minute. The problem is probably what > >> you > >> >> > are > >> >> > doing inside the loop. There's no way to solve it in time if you just > >> do > >> >> > a straightforward simulation on each cycle. > >> >> > Malkava > > >> >> > On Sat, May 8, 2010 at 3:12 PM, goutham <goutham...@gmail.com> > >> 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 google-c...@googlegroups.com. > >> >> >> To unsubscribe from this group, send email to > >> >> >> google-code+unsubscr...@googlegroups.com<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 google-c...@googlegroups.com. > >> >> > To unsubscribe from this group, send email to > >> >> > google-code+unsubscr...@googlegroups.com<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 google-c...@googlegroups.com. > >> >> To unsubscribe from this group, send email to > >> >> google-code+unsubscr...@googlegroups.com<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 google-c...@googlegroups.com. > >> > To unsubscribe from this group, send email to > >> > google-code+unsubscr...@googlegroups.com<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 google-c...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> google-code+unsubscr...@googlegroups.com<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 google-c...@googlegroups.com. > > To unsubscribe from this group, send email to > > google-code+unsubscr...@googlegroups.com<google-code%2bunsubscr...@googlegr > > oups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/google-code?hl=en. > > or rather you check out the shifts in the array, the moment the shift is > multiple of N, the pattern is repeated. no need even to compare with orignal > array.Efficiency at its best > (cummulative Cost array would better the solution). > > -- > -- > Thanks and Regards > -- > Abhishek Chandel > > BTech > > Computer Engineering > Malaviya National Institute of Technology,Jaipur. > 91-9660753545 > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to google-c...@googlegroups.com. > To unsubscribe from this group, send email to > google-code+unsubscr...@googlegroups.com. > 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 google-c...@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
