A region has n districts (numbered 0 to n - 1) and a list of candidate sites for ambulance
stations. Opening site s costs costs[s], and an ambulance there reaches the districts in
covers[s]. Write choose_sites(n, costs, covers) that returns a list of distinct site indices so
that every district is reached by at least one chosen site, with the total cost as low as you
can make it.
The tests build their regions with district_map(n, k, seed), which returns (costs, covers) for
k candidate sites. It is available in your code, so you can try it with Run.
How this problem is scored
A choice passes if every district is reached and it costs no more than this simple rule: go through the districts in index order and, whenever one is not reached yet, open the cheapest site that reaches it (the smaller index on a tie). Its quality (0 to 100) says how much of the gap between that rule and the optimum you close: 0 matches the rule, 100 is the cheapest possible choice (the optima were proven with an exact solver).
Examples
Input: n = 5, costs = [4, 3, 3, 5], covers = [[0, 1, 2], [2, 3], [3, 4], [0, 4]]
Output: [0, 2]
Explanation: sites 0 and 2 reach all five districts for 4 + 3 = 7.
The simple rule opens sites 0, 1 and 2 for 10.
Input: n = 30, (costs, covers) = district_map(30, 25, 2)
Output: any list of sites that reaches all 30 districts and costs no more than the simple rule
Constraints
1 <= n <= 200,1 <= len(costs) <= 150,1 <= costs[s] <= 100- Every district appears in at least one
covers[s]. - Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.
Goals
- Build a cover greedily by value for money
- Remove choices that became redundant
- Compare a heuristic with a proven optimum