JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Round 3
Problem: PoisonedWine

Problem Statement

    

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.

 

Definition

    
Class:PoisonedWine
Method:testWine
Parameters:int, int, int, int
Returns:int[]
Method signature:int[] testWine(int numBottles, int testStrips, int testRounds, int numPoison)
(be sure your method is public)
 

Available Libraries

    
Class:PoisonTest
Method:useTestStrips
Parameters:String[]
Returns:int[]
Sample Call:val = PoisonTest.useTestStrips(tests);
    
 

Examples

0)
    
Seed = 1

numBottles = 1782
testStrips = 17
testRounds = 1
numPoison =  26
1)
    
Seed = 2

numBottles = 1292
testStrips = 15
testRounds = 2
numPoison =  16
2)
    
Seed = 3

numBottles = 7686
testStrips = 9
testRounds = 3
numPoison =  86
3)
    
Seed = 4

numBottles = 3014
testStrips = 11
testRounds = 5
numPoison =  3
4)
    
Seed = 5

numBottles = 5911
testStrips = 5
testRounds = 2
numPoison =  10
5)
    
Seed = 6

numBottles = 8282
testStrips = 8
testRounds = 3
numPoison =  41
6)
    
Seed = 7

numBottles = 5447
testStrips = 18
testRounds = 2
numPoison =  43
7)
    
Seed = 8

numBottles = 2334
testStrips = 14
testRounds = 8
numPoison =  45
8)
    
Seed = 9

numBottles = 8592
testStrips = 7
testRounds = 2
numPoison =  158
9)
    
Seed = 10

numBottles = 75
testStrips = 5
testRounds = 1
numPoison =  1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.