|
On November 21 2012 06:40 Shady Sands wrote:
Imagine you have, at most, two identical rocks and a 100-floor building.
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break?
1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc.
Once you have calculated this for the 100-floor building, what is the answer for an n-floor building?
The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor.
The answer cannot be 1 (the rock breaks at 1st floor) because then there would be no floor from which the rock would be intact. This is unless you are allowed to use the exclusion principle and just drop one rock from the 2nd floor and you then know the rock would be intact on the 1st floor (then it would be only 1 drop).
I did it this way becuase the question is the least number of drops.
Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact.
|
On November 21 2012 19:45 Cyber_Cheese wrote:Show nested quote +On November 21 2012 19:35 AcrossFiveJulys wrote:
The "at most 2 identical rocks" condition is confusingly worded. One interpretation would be that you start with either 1 rock or 2 identical rocks, and if a rock breaks, you can't drop it anymore. So the challenge is that if you break all rocks you start with without finding a floor in which a rock doesn't break you can't say with certainty any floor in which a rock does not break.
So under that interpretation, if you start with 1, the only strategy that is guaranteed to give you an answer is to start at floor 1 and continue upwards until the rock breaks; the floor before the one in which it breaks is the answer. If you start with 2, the best strategy that is guaranteed to give you an answer would be one in which you ascend 2 floors at a time and drop one rock at each floor until it breaks. Then you try the other rock on the floor below. If it breaks, the answer is the floor below; if it doesn't break, the current floor is the answer. .... What? The first rock exsists to narrow down the range such that the second could act as your only rock example. What if the answer was 99? Are you seriously calling 51 potential drops optimal?
Mmmm you're right. It's 6am here ><
|
I think the question needs to be rephrased into something like this:
How do you drop the rocks in such a way that yields the best worst-case scenario? i.e. the worst case scenario for a particular way to drop the rocks would require the lowest number of drops compared to other ways to do so
|
On November 21 2012 19:48 Ota Solgryn wrote:Show nested quote +On November 21 2012 06:40 Shady Sands wrote:
Imagine you have, at most, two identical rocks and a 100-floor building.
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break?
1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc.
Once you have calculated this for the 100-floor building, what is the answer for an n-floor building? The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor.
Except you don't know what n is.
I did it this way becuase the question is the least number of drops.
Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact.
What you answered is the least number of drops you need to verify that the highest non-breaking-floor is n, when n is provided a priori. If n is not known, you need to the "best worst-case-scenario", which is what people have been calculating.
|
On November 21 2012 15:29 peidongyang wrote:
Base case: For 0 rocks we are able to determine whether or not 1 floor is passable (we assume it is)
Recursive Relation: a(n)=2*a(n-1), where n is the number of rocks
Proof
For 1 rock, we are able to drop it from floor 1 and if it breaks, and it won't break from floor 0
For 2 rocks, we are able to drop it from floor 2. If it breaks, we drop it from floor 1. If not, we will drop it from floor 3. Therefore we are able to determine breaking from floors 1-4.
Without going into rigorous mathematical proof, it is very easy to see that 2^n floors can be determined with n rocks, or the reserve, the binary search tree with log(2)n time.
Therefore the solution for 100 floors is ceil(log(2)100).
The general solution is ceil(log(2)n)
edit2: nvm again I think my solution holds. Guaranteed to produce result in 7 searches
The problem only allows you 2 rocks, your solution requires more. Specifically, if the rock already breaks on the first floor, your binary search tree requires you to break 7 rocks. This is why binary search trees are not a correct way of approaching the problem. (The problem would be rather dull otherwise, since binary search trees are such a common technique.)
|
But if a rock would normally break when thrown from, say, the 50th floor, then if it's already been dropped from all the previous floors, it won't be able to reach 50, it would break much sooner because each fall, no matter how small affects its structural integrity.
|
On November 21 2012 22:17 Incze wrote:
But if a rock would normally break when thrown from, say, the 50th floor, then if it's already been dropped from all the previous floors, it won't be able to reach 50, it would break much sooner because each fall, no matter how small affects its structural integrity.
It's an abstract problem. The only reason it's described with physical concepts such as rocks and floors is to make it accessible. In this case, you must assume that the rocks is completely unaffected by a drop that doesn't outright break it. If you can't do that, I can give you a purely mathematical description of the problem.
|
On November 21 2012 21:47 Rannasha wrote:Show nested quote +On November 21 2012 19:48 Ota Solgryn wrote:On November 21 2012 06:40 Shady Sands wrote:
Imagine you have, at most, two identical rocks and a 100-floor building.
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break?
1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc.
Once you have calculated this for the 100-floor building, what is the answer for an n-floor building? The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor. Except you don't know what n is. Show nested quote +I did it this way becuase the question is the least number of drops.
Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact. What you answered is the least number of drops you need to verify that the highest non-breaking-floor is n, when n is provided a priori. If n is not known, you need to the "best worst-case-scenario", which is what people have been calculating.
No, I provided the least number of drops you need if you make a lucky guess, I do not need to know n, nowhere does the question state that you could not make guess, and be lucky with that guess. Anyhow, I just answered it as was it a trick question, which to me it is, because of a vague formulation.
|
On November 21 2012 22:46 Ota Solgryn wrote:Show nested quote +On November 21 2012 21:47 Rannasha wrote:On November 21 2012 19:48 Ota Solgryn wrote:On November 21 2012 06:40 Shady Sands wrote:
Imagine you have, at most, two identical rocks and a 100-floor building.
Using only the method of dropping a rock from a certain floor and seeing whether it will crack open or not, what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break?
1) Breaking is ordinal--a rock that breaks from a 60 floor etc. can be safely assumed to break from a 70 floor drop, etc.
Once you have calculated this for the 100-floor building, what is the answer for an n-floor building? The least number of drops you need to use is 2. You drop the first rock from n+1 floor -> it breaks. You drop the next rock from n floor -> it doesn't break. So now you know the highest floor from which is doesn't break is the n floor. Except you don't know what n is. I did it this way becuase the question is the least number of drops.
Most people here seem to calculate what is the maximum number of drops you would need to use in the case you have the most optimal way of generally finding the highest floor of which the rock would be intact. What you answered is the least number of drops you need to verify that the highest non-breaking-floor is n, when n is provided a priori. If n is not known, you need to the "best worst-case-scenario", which is what people have been calculating. No, I provided the least number of drops you need if you make a lucky guess, I do not need to know n, nowhere does the question state that you could not make guess, and be lucky with that guess. Anyhow, I just answered it as was it a trick question, which to me it is, because of a vague formulation.
While I understand that possible ambiguity/ need to be clever, I'm also pretty sure that based on the context, you really understood that it wasn't a trick question. It means for any given floor, the fact that you're always looking to optimize your answer (not just "get lucky"), and the understanding that you can't risk both rocks breaking without knowing for a fact what the correct floor is. You can't just arbitrarily say, "I choose to pick the two perfect floors to give me the correct answer, meaning the answer's two", because you're incapable of knowing for sure that you'd pick those two ideal floors. You'd need to already know the answers, and then drop the rocks to reconfirm them. However, as the person dropping the rocks, you don't actually know yet what those ideal floors are.
I mean, after all, if you really want to be a dick about it, why not just say, "Well I was super lucky in my individual trial because the answer was "the rock breaks at the first floor" and I dropped my first rock on the first floor and it broke, and therefore I didn't even need the second rock. Answer's one."  It's really missing the point of the brain teaser, because if it hadn't broken, I would have only eliminated one floor in one step, and I'd still have ninety-nine to go... and you simply can't work under the assumption that it will be the first floor, so it's silly to pick floor one to drop the first rock. It will be better for you (probability-wise) to drop the first rock at floor two at step one than at floor one.
|
I'd throw the first rock in increases of sqrt(n) (floors 10, 20, 30... in our example), and of course the second rock in single steps from the last known safe position. That yields a worst case of 2*sqrt(n). Probably not optimal, but should be decent enough for starters.
|
In case you missed it, Phael posted the right answer on page 1. There's no way to improve on it because all the worst case scenarios for rock 2 yield the same result, and it deals with the worst case scenario for rock 1, floor 99/100, as well with the same upper limit. Well ok, that wasn't a real proof. But since we're dealing with minima and integer values, proving it might be ugly...
|
|
|
+ Show Spoiler +my initial thought is n/2 if i start on floor 2 and go up 2 each time it does not break, gonna think about it some more 
|
On November 21 2012 06:40 Shady Sands wrote:
what is the least number of drop attempts you need to use to figure out the highest floor from which a rock, dropped, will not break?
+ Show Spoiler +Two. I drop my first rock from floor X which just so happens to be the floor above the one from which it won't break, of course at this time I don't know this.. not until I drop the rock from the floor X-1 and discover it is intact!
In case I am missunderstanding I could be wrong but it seems to me as thought this was a silly trick question and not a puzzle with a clever mathematical answer.
I would appreciate if you told me which one is
EDIT: oh nvm I get it.. so the idea is that if the rock doesn't break I can pick it up and use it again so the question is which is the most effective method for finding the floor without breaking more than 2 rocks.
Meh I don't see it! Seems like too much of a shot in the dark - I would start by throwing it from the [ highest floor - 1 ],
if it doesn't break you can go test the highest floor, if it does I would just go back to floor 0 and go one up every throw...
every other method I can come up with on the fly seems flawed in that it could be really bad depending on what the right floor number actually is.
|
Well, if you have a large wooden plank that you can pin outside the windows and you are very precise in throwing the rocks, you need but one rock =p
|
This is actually a nice problem looking at it in a non-zombie state today. It's a sequential decision making problem but the objective is to minimize the worst-case number of steps needed subject to the condition that you cannot break both rocks.
Here's my solution which ends up more rigorously deriving Phael's solution. So you drop the first rock on some floor x_1. If it breaks, you are forced to start from floor 1 and increase to x_1-1 until the rock breaks, at which point you know the answer in x_1 steps. If it doesn't break, you get to choose another floor x2 to drop the first rock, where if it breaks you have to ascend from floor x_1+1 to x_2-1, which makes you take x_2-x_1+1 steps. Extending this reasoning to general x_k, the worst case becomes x_k - x_{k-1} + k-1.
So the problem can be formulated as choosing x1, x2, ..., xN to minimize max_k {x_k-x_{k-1}+k-1},
Let the number of steps that strategy G takes given the answer is F be G(F). Now consider the space of strategies that contains those that are valid (always outputs a solution) and never perform useless drops (ones that give no additional information); call that space S. Obviously this space of strategies contains the optimal strategy. Then for all G in S, G(F) summed over F=1 to N is the same. I think this is a safe assertion that could be easily proved via a proof by contradiction.
Then, we conclude that in order to minimize the maximum number of steps, the number of steps required for each possible F in the optimal strategy should be the same. So we need to find x_1, ..., x_M such that x_k-x_{k-1}+k-1 for all k from 1 to M, and where M <= N. The unique solution to that recurrence relation is Phael's solution.
|
FYI, I heard this in a Google interview. I guess this is somehow related to indexing and searching webpages?
|
1.
since question is poorly formulated; i get to interpret it to my convenience.
drop it from the top floor, if it doesn't break, it won't break at any floor; hence
it is the highest floor from which a rock dropped will not break (since tehre is no higher floor).
question doesnt' say whether to look for best or worst case scenarios; so i choose best case
|
I think:
+ Show Spoiler +Drop it from the midway point of the available floors, rounded up.
Longest solve (answer 1st floor):
-50 (break)
-25 (break)
-13 (break)
-7 (break)
-4 (break)
-2 (break)
-1 (break)
=7
Overall: Log 2 of n. (rounded up)
|
On November 21 2012 06:55 AiurZ wrote:
fastest way to find out is to drop from 10th floor, then 20th floor, then 30th floor, etc. until it breaks and then you drop the 2nd rock ascending each floor 1 by 1.
for an n-floor building u just find the minimum of (n/x)+x=y and that is the amount of floors u skip each try (for a 100 floor building it is 10).
This was my original idea too, just get the minimum of (n/x)+x-1=y, I think you missed out the -1, because say you drop and break on the tenth floor then you only need to drop the second rock nine times. However this only yields the optimal solution in the case that x is fixed, so it is less optimal that the 14 + 13 + 12... solution.
Binary search would be fastest if we had more rocks, but since we only have two its not workable.
|
|
|
|
|
|
EPT
