Introduction
You have several bottles of wine. Unfortunately, some of them may have been poisoned. Naturally,
you don't want to serve poisoned wine to any of your guests, so you need to be sure to discard any
such bottles.
You have some test strips, which may be dipped into a sample of wine-- the sample may be taken
from a single bottle or from several bottles combined together. After some time, the test strip will
indicate if there is any poison present. Test strips which do not indicate a positive result may be
reused, but once a test strip shows a positive result, it can no longer be used again.
Since the test takes some time to process, you will only be able to perform a certain number of
rounds of testing. And, each subsequent round of testing may have less test strips remaining for
use as a result of those that previously tested positive.
Your goal is to optimize your usage of the available test strips, over the allowed number of
rounds of testing, such that you can minimize the number of bottles you discard while still being
certain that no poisoned bottles remain in your possession.
Method Calls
Your code should implement a single method, testWine, that takes the following parameters:
- int numBottles: The number of bottles of wine you have
- int testStrips: The number of test strips you have
- int testRounds: The maximum number of rounds of testing you can perform
- int numPoison: The number of poisoned bottles
Ultimately, your method should return a int[] listing all of the bottles you intend
to discard. Each bottle in the return should be unique.
To perform a round of testing, your code should call library method
int[] PoisonTest::useTestStrips(String[] tests). Each element of tests should be
a comma-delimited list of wine bottles to be sampled against a single test strip. The number of
elements in tests must be less than or equal to the number of remaining test strips. Each value
must be in the range 0..numBottles-1. The return value will be the same length as the input, each
value being 0 (no poison) or 1 (poison detected). Any invalid input to useTestStrips() will return
an empty array.
Scoring
If the return value of your code includes all poisoned bottles of wine, then the score for
that test case will be equal to (bottlesSaved / goodBottles) ^ 2. If any poisoned bottle of wine is
not included in the return, then you will score a 0 for that test case. If the return value is
invalid, or any invalid test calls are made (using more strips than remain, calling with invalid
values, or making more calls than allowed) then you will score a 0 for the test case.
Overall score will be calculated as the average of the scores for each individual test case,
scaled by 1000000.
Test Case Generation
- numBottles is chosen between 50 and 10000
- testStrips is chosen between 5 and 20
- testRounds is chosen between 1 and 10
- A number of bottles to be poisoned are chosen between 1 and numBottles/50
Notes
- Wine bottles are numbered 0..N-1.
- It is up to you to keep track of how many test strips remain, based upon the number of positive
results found during each round of testing.
- Time limit is 60s.
- There are 50 provisional tests and will be 5000 system tests.
Offline Tester
An offline testing tool is available here.
|