Cover every element at the lowest total cost

You inherit a set-covering solver: each instance has m elements and n sets, where set j has an integer cost and covers a subset of the elements. For every instance you must choose a subfamily of sets whose union covers all elements, minimizing the total chosen cost. The shipped baseline (/app/methods/main/solver.py) is Chvátal greedy + redundancy pruning, which leaves a real gap to the optimum on these instances. Your goal is to cover at lower cost — by any approach you choose; a sealed verifier re-runs your solve on a HIDDEN, sealed set of instances and scores the total cost (lower is better).

Hard Constraints

• You may only edit code under /app/methods/main/; you may add sibling .py modules.
• Keep the entrypoint signature solve(data) -> {"selected_sets": [[set_idx, ...], ...]}.
• Standard library + numpy only — no internet, no other third-party packages. The verifier sandbox ships the SAME numpy and nothing else, so import numpy is fine but any other third-party import (scipy, networkx, solvers, …) makes the submission score 0.
• Per-instance 20s hard cap. The grader solves each instance in isolation and kills any instance whose solve takes longer than 20 seconds, scoring that instance 0 (the others are unaffected). Self-pace so every instance returns within 20s.
• Return one selection per instance, in the same order as data["instances"]. Each selection is a list of 0-indexed set indices whose union covers every element. For a given instance, an incomplete cover, an out-of-range index, or a timeout makes that instance score 0 (not the whole submission) — so a bad instance costs you only its own share of the mean.

What You Have

• /app/data/visible.json: 8 public instances to develop against, from the hard large-column families (rail 47-63k cols, scpnrg/scpnrh 10k cols, scpa/scpc/scpd). data["instances"] is a list of {name, n_elements, n_sets, set_costs, set_elements}; set_elements[j] is the list of 0-indexed element ids that set j covers, and set_costs[j] its integer cost.
• /app/methods/main/solver.py (+ scp_lib.py): the greedy baseline — this directory is what gets graded. Improve it in place or rewrite the algorithm entirely. Matching the baseline earns nothing; the task is to beat it.
• /app/selfcheck.py: a free local dry-run on the visible instances (python /app/selfcheck.py). It mirrors the grader: it runs your solver on each instance under the SAME 20s per-instance hard cap, prints each instance's runtime + the RAW COST of the cover it produced, and tells you exactly which instances were KILLED for exceeding 20s. Use it to keep every instance in budget — but the hidden instances are a different sealed batch of the same families, so do not overfit.

What You Submit

Edit /app/methods/main/solver.py, keeping the signature:

def solve(data):
    # data: {"instances": [{name, n_elements, n_sets, set_costs, set_elements}, ...], ...}
    # returns: {"selected_sets": [[set_idx, ...], ...]}  — one selection per instance, same order
    ...

You may add helper modules next to solver.py. There is no submit step and no per-attempt feedback — iterate against the self-check for as long as your run window allows, then leave your best solver.py in place; it is graded once at the end on the hidden instances.

How It Is Judged

After your run, the grader copies your methods/main/ into a clean sandbox and re-runs solve on a HIDDEN, sealed set of 11 instances, one instance at a time under a 20s hard cap. Each instance is scored independently on the total cost of the cover you return — lower is better. A crash, incomplete cover, out-of-range index, or a >20s timeout forfeits that instance only (the rest still count), so a constant or hard-coded answer cannot score.

How the raw costs map to the final reward is deliberately not disclosed. Optimise the cost itself: drive the total cost of a valid cover as low as you can, on every instance.

Common Pitfalls

• Returning an incomplete cover (some element uncovered) or an out-of-range set index — that instance is forfeited, not counted as a high cost.
• A solver that is strong but too slow: any instance over the 20s cap is killed and forfeited. The visible set includes the large rail/scpnrg instances precisely so you feel this budget while developing — watch the per-instance times selfcheck.py prints.
• Settling for the baseline's approach: these OR-Library instances are deliberately hard and the greedy baseline leaves real headroom — how you close the gap is yours to choose.
• Tuning only for the visible instances; the hidden set is a different sealed batch of the same hard families.
• Importing third-party packages other than numpy — the sandbox ships only stdlib + numpy and any other import fails.