Minimum Test Subjects (Hard) — Practice with Code Visualizer

You are tasked with identifying a single contaminated container among a collection of containers liquid samples in a laboratory experiment. To detect the contamination, you can use biological test subjects that will exhibit a reaction exactly reactionTime minutes after exposure to the contaminated substance.

Your experiment has a strict time limit of totalTime minutes to conclusively identify which container holds the contaminated sample.

The testing protocol works as follows:

Selection Phase: Choose which active test subjects will participate in the current testing round.
Exposure Phase: For each selected test subject, decide which containers to expose it to. A test subject can be simultaneously exposed to any number of containers, and multiple test subjects can be exposed to the same container. The exposure happens instantaneously.
Observation Period: Wait exactly reactionTime minutes. During this waiting period, no additional exposures can be performed.
Result Collection: After reactionTime minutes, any test subject that was exposed to the contaminated container will show a reaction (and be removed from further testing), while all others remain viable for future rounds.
Iteration: Repeat the process with remaining active test subjects until the time limit is reached.

Given the number of containers, the reactionTime, and the totalTime available, determine the minimum number of test subjects needed to guarantee identification of the contaminated container within the allotted time frame.

Key Insight: Each test subject encodes information through its potential states across multiple testing rounds. If you have T testing rounds available, each test subject can be in one of T + 1 possible states: it could react in round 1, round 2, ..., round T, or never react at all. This multi-dimensional state space is the key to minimizing the number of test subjects required.

With only 15 minutes total and 15 minutes required for reaction observation, we can perform exactly 1 testing round. Each test subject has 2 possible outcomes: reacts or doesn't react. With 2 test subjects, we have 2² = 4 possible combined outcomes (both react, only first reacts, only second reacts, neither reacts), which is exactly enough to distinguish 4 containers.

Example strategy: Expose first subject to containers 1 and 2. Expose second subject to containers 2 and 3.

If only first subject reacts → Container 1 is contaminated
If only second subject reacts → Container 3 is contaminated
If both react → Container 2 is contaminated
If neither reacts → Container 4 is contaminated

With 30 minutes total and 15 minutes per reaction cycle, we can perform 2 testing rounds. Each test subject now has 3 possible states: reacts in round 1, reacts in round 2, or never reacts. With 2 test subjects, we have 3² = 9 possible combined outcomes, which is more than sufficient to distinguish 4 containers.

This demonstrates that more testing rounds allow each test subject to encode more information, potentially reducing the total subjects needed.

When there is only 1 container, no testing is required—the sole container must be the contaminated one by default. Therefore, 0 test subjects are needed.