http://www.spoj.com/problems/NPC2015E/ it looks like a normal egg dropping problem, but the constraints of the last subtask is really huge. here are some observations i made:
if (k=2) answer is the smallest x where x*(x+1) >= 2*n
if (k=1) answer is n
if(k>= log2(n)) answer is floor(log2(n)) (because we can do binary search)
however, using these three observations, its still not enough to beat the last subtask, because if the input is 10e18 and 5, it would be TLE
is there a faster solution? i tried googling and found a math solution for 2 eggs only
Use dynamic programming to compute the values F(e,a) = the number of different answers I can tell apart if I have e eggs and a attempts.
For example, F(3,2) = 4. If you have three eggs but only two attempts, the best you can do is distinguish between four possible answers. E.g., if you already know that your eggs don't break from height 14 but they do break from height 18, you can still find the exact solution with 3 eggs and 2 attempts.
could you elaborate please?
I think it's better if you try working out the details on your own: try to understand what the values mean and how they can be used to construct an optimal solution.
For the lazy ones, some more details are hidden in the edit history of this post.
sorry, mean, i dont get your dp notion
is f(e,a) the maximum height u can measure using e eggs and a attemps?
Yes, you can see it like that.
Additionally, note that starting with the information "the egg doesn't break from height 17 and does break from height 27" is the same as starting with the information "the egg doesn't break from height 0 and does break from height 10". Only the length of this interval of heights matters.
Thus, my f(e,a) is the largest height h such that the following problem can be solved: "The egg doesn't break from some height x, and does break from height x+h. You have e eggs and a attempts. Can you find, with certainty, the smallest height from which the eggs break?"
I read this article a few weeks back link
Under the heading A better approach I didn't understand a few things. If you understand it fully, then please explain to me as well.
Specifically, I didn't understand this
But we have a problem: f(0,n) is 0 for every n, as well as g(0,n), according to the relation between f and g. However, a contradiction occurs when n=0. Because g(0,0)=(0)C(0)=1, but g(0,n) should be 0 for every n! We can fix this problem defining g(d,n) as: (d)C(n+1)What I don't understand is, that we're using (d)C(n+1). We could've also used (d)C(n+2) or (d)C(n+3), etc. and the recurrence would still hold.
Finally, we have f(d,n) in the form of a sum of (d)C(i) where i goes from 1 to N(no. of eggs) But this final formula depends on our choice previously ( about (d)C(n+1) ). If we chose something else, we'd get a different result.
However, as N<log(floors) , we can see that using (d)C(n+1) will produce the smallest value among all viable options. Our task in this method, is to find the smallest d which satisfies f(d,n)>=k
This means if we chose (d)C(n+2) then we'd get a smaller d. Then why didn't we choose that option?
That's why I'm confused about this approach.
Please correct me if I'm wrong about anything.
i dont even understand why f(d,n) = f(d-1,n-1) + f(d-1,n) + 1
this puzzle is really confusing
f(d,n)=maximum no. of floors we can check with d drops and n eggs.
Thus, after 1 drop, two things can happen-
1. Egg breaks :
In this case, we have n-1 eggs left. If we test the floors above the current floor, the next egg will definitely break, so we won't test it. We'll test the floors below. Thus, f(d-1,n-1) will tell us the max no. of floors we can test with d-1 drops and n-1 eggs. Then we add 1 to it, because we tested a floor and broke an egg. 2. Egg doesn't break :
In this case, we have n eggs left. If we test the floors below the current floor, the next egg will definitely not break, so we won't test it. We'll test the floors above. Thus,f(d-1,n) will tell us the max no. of floors we can test with d-1 drops and n eggs.
Remember, from definition of f(d,n) that we are only counting the max floors we can test with d drops and n eggs. f(d,n) is not the answer we want. minimum value of d is what we ultimately want.
Why is the recurrence correct?
Let's think under what condition will we achieve maximum value of f(d,n). We can easily see that f(d,n)>=d. We can find this maximum by being optimistic about egg not breaking on a certain floor, because if it breaks, then that's it. The value will be less than the number of that floor.
Imagine the egg doesn't break on testing a particular floor. Let's call that floor p. Then, we have 1 less drop but all n eggs. We know we want to test only the floors above p now. So, we have d-1 drops and n eggs to test the max floors we can test above p.
Thus, we can check a total of p+f(d-1,n) floors after testing on p.
But we still don't know what is the value of p.
In order to find the value of p, we must think, can it be arbitrarily large? It's true that no eggs will break below p because it didn't break on p but we still have 1 less drop. So, p can't be arbitrarily large. Thus, we also need to find the maximum floors we can test with d-1 drops and n-1 eggs. This will give us p, as
p=f(d-1,n-1)+1.
I hope you understand.