this problem is equivalent to 2 eggs problems http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html
On 23 May 2010 22:00, tonka <[email protected]> wrote: > this is the most disgusting and bullcrap question i have ever seen in > code jam. > > On May 23, 11:18 pm, Ahmed Medhat <[email protected]> wrote: > > 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%2bunsubscr...@googlegr oups.com> > > > > > > <google-code%[email protected]<google-code%[email protected]> > <google-code%252bunsubscr...@goo glegroups.com> > > > <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> > > > <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> > > > <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]> > <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 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. > > > > -- > > 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]<google-code%[email protected]> > . > > For more options, visit this group athttp:// > 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.
