Link to the Problem
Nice try by Mythalez, Vivek and Ankit! I had never thought of such a solution!
Here goes my Solution:
2^11 = 2048 which is greater than 2009. Hence, all numbers from 1 to 2009 can be represented
using 11 bits! Now represent each bottle number in 11 bit binary format and list them row wise. Each row now has a 11 bit number representing a bottle number. Let each column be a single bit. So, each column would contain either a 0 or a 1 corresponding to each bottle(row). Keep one slave per column and make the slave drink from all the bottles which have a 1 in that column! Hence, you get the poisoned bottle using the combination of slaves who die (write 1's for the slaves who die and 0's for the slaves who don't and the binary number hence formed gives the bottle number corresponding to the poisoned bottle).
e.g.
Let's say the third bottle was poisoned.
1 2 3 4 5 6 7 8 9 10 11 - Slave numbers
0 0 0 0 0 0 0 0 0 0 1 - 1st bottle
0 0 0 0 0 0 0 0 0 1 0 - 2nd bottle
0 0 0 0 0 0 0 0 0 1 1 - 3rd bottle
0 0 0 0 0 0 0 0 1 0 0 - 4th bottle
.
.
.
.
Now the slaves from 1 to 9 wont die and 10th and 11th slave would die after 10 to 15 hrs. From this we can decode the bottle number by writing nine 0s followed by two 1s i.e. 00000000011 which is 3. Hence, we conclude that the third bottle is poisoned!
Here time of death was included just to introduce some confusion while solving the problem. However, if Vivek's time window concept is used (which seems reasonable) we can achieve this using ceil(11/3) slaves i.e. 4 slaves!!!!
7 comments:
good solution, i initially thought the same, however used a binary tree to traverse, resulting in more time consumption, your solution of making them all drink at a time is the big AHA here .. nice work dude keep them coming .....
Thanks a lot Ankit!
Awesome solution :)
Thanks meghna!
The solution that struck instantly to me is binary search, which will give the same ceil(log(n)) answer as yours. Elaborating a bit, get one chap to drink half the bottles at once. Depending on whether he survives or not, you have reduced your search space by a factor of 2. Repeat that until the search space is limited to 1 element. In the worst case, in each level, you will incur one death, making the worst case bound ceil(log(n)).
PS: I haven't used the time-till-death info here.
@Pulkit: True, but then this would work only if the slaves die immediately after they drink the poison, otherwise the total time you would take is time_taken_to_die*log(n) which would be in this case 15*11 and in the question it was specified that the poisoned bottle had to be found out within one day!
Aah, missed that!
Post a Comment