broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] // r[2] * 100 < live_pct]
    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if time + t > budget:
            break
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 // r[2] <= live_pct]
    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if time + t > budget:
            break
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Nearly full old regions are treated as empty and chosen for evacuation.

Regions are [id, kind, used, live]. All young regions are always collected (their live bytes cost live * cost). Old regions whose liveness is strictly below live_pct percent (live * 100 < pct * used) are candidates; humongous regions never are. Candidates are ordered by reclaimable bytes (used - live) descending, ties by id, and added while the accumulated cost stays within budget; selection stops at the first candidate that does not fit. Return the collection set, its cost and reclaimed bytes.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
    cands.sort(key=lambda r: (r[2] - r[3], r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if time + t > budget:
            break
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
    cands.sort(key=lambda r: (r[3], r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if time + t > budget:
            break
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The pause budget is spent on regions that reclaim the least memory.

Regions are [id, kind, used, live]. All young regions are always collected (their live bytes cost live * cost). Old regions whose liveness is strictly below live_pct percent (live * 100 < pct * used) are candidates; humongous regions never are. Candidates are ordered by reclaimable bytes (used - live) descending, ties by id, and added while the accumulated cost stays within budget; selection stops at the first candidate that does not fit. Return the collection set, its cost and reclaimed bytes.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if time + t > budget:
            continue
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(regions, budget, live_pct, cost):
    cset = []
    time = 0
    for rid, kind, used, live in regions:
        if kind == 'young':
            cset.append(rid)
            time += live * cost
    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
    for rid, kind, used, live in cands:
        t = live * cost
        if t > budget:
            continue
        cset.append(rid)
        time += t
    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    101,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    101,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    85,
    85,
    2),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    102,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    102,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    90,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    103,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    103,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    95,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    104,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    104,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    100,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
 [('regression: candidates fill the budget exactly',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    115,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('budget stops at the first region that does not fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    1),
   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
  ('expensive region first stops selection',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200],
     [11, 'old', 300, 200]],
    105,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
  ('region at exactly the liveness threshold excluded',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    85,
    1),
   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
  ('higher threshold admits more regions',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    1000,
    91,
    1),
   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
  ('cost multiplier',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    105,
    85,
    2),
   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
  ('control: only young regions fit',
   ([[1, 'young', 100, 30],
     [2, 'young', 100, 10],
     [3, 'old', 100, 20],
     [4, 'old', 100, 85],
     [5, 'old', 100, 50],
     [6, 'humongous', 400, 0],
     [7, 'old', 100, 5],
     [8, 'old', 100, 90],
     [9, 'humongous', 200, 200]],
    20,
    85,
    1),
   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Cheaper, less profitable regions are packed in after a better region was rejected.

Regions are [id, kind, used, live]. All young regions are always collected (their live bytes cost live * cost). Old regions whose liveness is strictly below live_pct percent (live * 100 < pct * used) are candidates; humongous regions never are. Candidates are ordered by reclaimable bytes (used - live) descending, ties by id, and added while the accumulated cost stays within budget; selection stops at the first candidate that does not fit. Return the collection set, its cost and reclaimed bytes.

split: open-access