Ohkkies .. got it .. Thanks a lot Bharath ! On May 23, 6:37 pm, Bharath Raghavendran <[email protected]> wrote: > Well .. lets consider the set of numbers L to P. > anything before it, we know that it will succeed. Anything greater than P, > we know that it will fail. > > Lets say we are trying to find a set of numbers L' to P' such that left of > L', it will succeed and right of P' it will fail. > > Also, lets say that we are trying to find the set such that P' is atmost C > greater than L'. For this, we will do a simple binary search. Everytime, we > will check mid of current set. If it succeeds for mid, we take the new set > as the one on the right of mid. If not, we take the left of mid. We keep > shrinking the set this way till the size becomes < C. > > Now, the question asks you that P' should be atmost C times L'. So, when we > split the set into 2 sets, we need to ensure that both sets have the same > ratio P'/L'. If we don't do that, the one with bigger ratio will take longer > than the optimal solution. So, we need a number such that P'/x = x/L'. > Geometric mean!!. So check whether it succeeds for geometric mean. If yes, > take right of it as new set. Else take left of it as new set. When new set > is such that P'/L' is less than C, we stop the algorithm as L' will be the > required value of 'a'. > > Hope this helps. > > On 23 May 2010 18:53, Saurabh <[email protected]> wrote: > > > > > > > Hi Bharath, > > > Thanks for your reply. But I couldn't understand one thing. Why is > > taking the geometric mean the most optimal method ? > > Could you explain a bit more on this ? > > > Thanks. > > > On May 23, 5:19 pm, Bharath Raghavendran <[email protected]> wrote: > > > You are trying to find a value of a between L and P such that u r sure > > that > > > a contestants can access at a time but C*a contestants cannot. > > > > Its basically a binary search for a satisfying element between L and P > > with > > > a small modification that instead of taking (L+P)/2 each time, go for > > their > > > geometric mean. This will maintain the ratio of first and last between > > the > > > two halves and hence will be most optimal. > > > > On 23 May 2010 17:40, Saurabh Aggarwal <[email protected]> wrote: > > > > > Hi Guys, > > > > > Could anyone please explain the logic behind the "Load Testing" problem > > ? > > > > From the solutions I gathered that they have found the number of bits > > in X, > > > > where > > > > > L * (C^X) > P > > > > > But couldn't understand why this was done ? > > > > > Thanks. > > > > > -- > > > > Regards, > > > > Saurabh Aggarwal > > > > > -- > > > > 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> > > <google-code%[email protected]<google-code%252bunsubscr...@goo > > glegroups.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]<google-code%2bunsubscr...@googlegr > > oups.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 [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.
