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%[email protected]> > <google-code%[email protected]<google-code%[email protected]> > > > > > . > > > 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%[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]<google-code%[email protected]> > . > 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 at http://groups.google.com/group/google-code?hl=en.
