Soft-Deadline Bin Packing

Background. Pack items into a sequence of indexed bins with fixed capacities. Each item has a size, a value (earned only if it is packed on time), and a deadline (the highest bin index that counts as "on time"). Packing an item after its deadline is allowed but incurs a late penalty proportional to its value; dropping an item (not assigning it to any bin) incurs a drop penalty proportional to its value. The goal is to maximize the overall score balancing on-time rewards, late penalties, and drop penalties.

Implement the solve(instance) function in solution.py.

INPUT FORMAT

The function receives a single argument instance, a dataclass with fields:

• name: str (optional identifier)
• bin_capacities: List[int] — list of positive integers, length B (bins indexed 0..B-1)
• items: List[Item] — list of Item objects in input order. Each Item has fields:
  • id: int (canonical id assigned 0..N-1 in input order)
  • size: int (positive)
  • value: int (positive)
  • deadline: int (non-negative; an item placed into any bin with index <= deadline is on-time)
• late_penalty_factor: float (>= 0)
• drop_penalty_factor: float (>= 0)

OUTPUT FORMAT

Return a dict with keys:

• "bins": List[List[int]] — a list of length B; each element is a list of item ids assigned to that bin. No item id may appear more than once across all bins.
• "dropped": optional List[int] — explicit list of dropped item ids. Any item not present in any bin and not in the explicit "dropped" list is implicitly treated as dropped. The dropped list, if provided, must be disjoint from all bin lists.

A solution is valid only if no bin's total packed sizes exceed its capacity, and every referenced item id is in range 0..N-1 and appears at most once across bins/dropped.

SCORING

Score = (sum of values of on-time packed items) - late_penalty_factor * (sum of values of late packed items) - drop_penalty_factor * (sum of values of dropped items)

Higher score is better. The two penalty terms (late and drop) are multiplied by the respective instance factors and subtracted. Solutions may trade packing items late vs dropping them depending on the penalty factors.

WORKED EXAMPLE

Input: { "name": "example_small", "bin_capacities": [10, 8, 5], "items": [ {"size": 2, "value": 5, "deadline": 0}, {"size": 5, "value": 8, "deadline": 1}, {"size": 4, "value": 6, "deadline": 2}, {"size": 6, "value": 10, "deadline": 0} ], "late_penalty_factor": 1.5, "drop_penalty_factor": 2.0 }

A valid return value (one possible packing): { "bins": [[0, 3], [1], [2]], "dropped": [] }

Explanation: bin 0 holds items 0 and 3 (sizes 2+6 <= 10) and both are on-time (index 0 <= their deadlines). Bins 1 and 2 hold items 1 and 2 on-time. No item is late or dropped, so the score is 5 + 8 + 6 + 10 = 29.

HOW SUBMIT JUDGES

• The second public test first runs solve() on a few tiny hand-built instances, each with a single forced choice, and requires the best possible score on every one.
• Each scoring test samples 120–150 instances from data/instances.txt, requires every output to be valid, and compares the average score with a threshold: 1300 and 1475 on the two public samples, 1350 and 1620 on the two hidden ones.
• All instances of a test share its 10-second limit, which also covers loading the data, so budget well under 70 ms per instance.

Done when Submit goes green.

Input: {"name":"example_small","bin_capacities":[10,8,5],"items":[{"size":2,"value":5,"deadline":0},{"size":5,"value":8,"deadline":1},{"size":4,"value":6,"deadline":2},{"size":6,"value":10,"deadline":0}],"late_penalty_factor":1.5,"drop_penalty_factor":2.0}

Output: {"bins": [[0, 3], [1], [2]], "dropped": []}