PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
In Japan, a kind of living things are called G, and they are very hated. You can guess what are they from the problem code CKROACH.
This problem contains the knapsack problem, which is NP-hard. Consider the case N = 1, and use log(probabilities) instead of probabilities, then this problem is formulated as:
minimize sum of c i * x i
subject to sum of log**(1-Pi**) ? log(0.1), xi must be 0 or 1.
Therefore it is hard to get the exact solution of this problem. (even if N = 1)
At first, some greedy approaches work fine. For example, we define the efficiency of the j-th insecticides as (sum of -log**(Pi,j)** for all Gs which alive with probabilities at least 10%) / Cj. Then we use the insecticide having the highest efficiency in the set of unused insecticides, one by one. Very good greedy approaches may get score around 20.
To get more score, something like a local search or simulated annealing may be needed. Almost contestants who got score more than 20 use these methods.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.