Hi All,
just tack a look at this code i think it is simple to implement and it is
a valid solution
int b[10000];
int i=0;
b[0]=0;
b[1]=1;
for(i=2;i<10000;i++)b[i]=b[i/2]+1;
for(ll i = L*C ; i <P ; i*=C){
count++;
}
fout << "Case #"<<ncase<<": "<<b[count]<<endl;
On 23 May 2010 19:05, TheBeast <[email protected]> wrote:
> 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%[email protected]>
> <google-code%2bunsubscr...@googlegr oups.com>
> > > > <google-code%[email protected]<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%[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%[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]<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 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.
>
>
--
Kind Regards,
Ahmed Medhat Osman
[email protected]
+20122870644
Software Engineer
Egypt Development Center (EDC)
Egypt
--
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.
