Let me give you a rigorous solution to the problem.
Given x and y and c such that x<y and c>1 and that the system can
satisfy x participants but not y of them, we want to find the minimum
number of
tests that can improve the accuracy of our guess to within a factor of
c. Lets call this number f(x,y,c).
What does the statement f(x,y,c) = p mean? This
means that if p is zero, then y <= x*c and if p is not zero, then
there exists a t such that
x < t < y and f(x,t,c) <= p-1 and f(t,y,c) <= p-1. So, in order to
check whether f(x,y,c) is equal to p, we need to find if such a t
exists. We can see that f(x0,y,c)
as a function of y is non decreasing. i.e., f(x0,y,c) <= f(x0,y+1,c)
for all y. Suppose we know a function , say fmax(x,c,p), we will give
us the maximum y s.t
f(x,y,c) = p. Then in order to check for a potential t, we only need
to check if f(fmax(x,p-1,c),y,c) <= p-1 or in other words if we just
need to check y <= fmax(fmax(x,c,p-1),c,p-1).
But how to calculate fmax(x,c,p)? if p is zero,
this is clearly x*c. Otherwise, if p is not zero, fmax(x,c,p) is
simply fmax(fmax(x,c,p-1),c,p-1).
This recurrence relation gives us fmax(x,c,p) = x*(c^(2^p)) for all p
non negative. So, for our original problem we just need to check if y
<= x*(c^(2^p)) to see if f(x,y,c) is equal to p. So, we just find the
minimum p that satisfies this inequality and return it.
On May 24, 12:05 am, Saurabh <[email protected]> wrote:
> 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
> 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.
