E - Bad Juice Editorial by spheniscine


First re-index the juice bottles so that it’s from \(0\) to \(N-1\); remember to adjust the indices upon input and output.

Then, consider the base-\(2\) representation of these indices. You call \(M = \lceil \log_2 N \rceil\) friends, and you give the \(i\)-th friend the bottles where the \(2^{i-1}\) place is \(1\).

We can prove this is optimal using information theory. That is, we need to receive at least \(\log_2 N\) bits of information from the interactor in order to confidently decide between \(N\) possible outcomes (Otherwise, there would exist outcomes that do not map to any possible input, and given that the interactor is adaptive, it will try to find such outcomes regardless of probability). Since we can only receive a whole number of bits in this problem, it’s easy to see that \(M = \lceil \log_2 N \rceil\) is the lower bound for the number of friends required, and that the strategy above matches this lower bound, therefore it must be optimal.

posted:
last update: