3 ms·
This is essentially the same approach as the solution described in the article. You are observing the bits of the poisoned bottle number in binary, bit by bit.
by Chinjut 2y ago
This is essentially the same approach as the solution described in the article. You are observing the bits of the poisoned bottle number in binary, bit by bit. The only difference is that you avoid retesting any bottles once they have been ruled out by previous tests, whereas the fixed design in the article does not bother with this.
- bo1024 2y agoIn these situations one can also ask about the "adaptivity gap", which is the difference in how many tests are required if one is allowed to be adaptive -- make a test, look at the result, then decide what to test next -- versus nonadaptive, i.e. decide in advance what all the tests will be and conduct them all at once.