New answers tagged

2

This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it. You can solve it as follows: Number your bottles from $0$ to $n-1$, and label your beakers from $1$ to $\lfloor\log_2(n-1)\rfloor+1$ (the number of bits needed to ...


1

The function $$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) = \begin{cases} 1; &\text{if there is a solution of size $k$,}\\ 0; &\text{otherwise} \end{cases} $$ is monoton, since if there is no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $...


Top 50 recent answers are included