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)

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 > 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:
A set that would meet the pause budget exactly stops one region short.

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] != 'young' 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' or (r[1] == 'humongous' and r[3] == 0)) 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)

prompt:
Empty humongous regions are scheduled for copying.

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(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
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(pages, events):
    pages = {p: dict(v) for p, v in pages.items()}
    epoch = 0
    unswept = []
    log = []
    def sweep(p):
        parity = epoch % 2
        dead = sorted(o for o, m in pages[p].items() if m != parity)
        for o in dead:
            del pages[p][o]
        log.append([p, dead])
        unswept.remove(p)
    for ev in events:
        if ev[0] == 'gc':
            unswept.clear()
            epoch += 1
            for p in pages:
                for o in pages[p]:
                    if o in ev[1]:
                        pages[p][o] = epoch % 2
            unswept = sorted(pages)
        elif ev[0] == 'alloc':
            if ev[2] in unswept:
                sweep(ev[2])
            pages[ev[2]][ev[1]] = epoch % 2
        else:
            while unswept:
                sweep(unswept[0])
    return {'log': log, 'pages': {str(p): sorted(v) for p, v in sorted(pages.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: lazy sweep before allocation',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']]], 'pages': {'1': ['a1', 'x1'], '2': ['d1']}}),
  ('second cycle with an unswept page',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'd1']], ['alloc', 'x1', 1], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['e1']], [1, ['x1']], [2, ['d1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1']], ['finish'], ['alloc', 'y1', 2], ['gc', ['a1']], ['finish']]),
   {'log': [[1, ['b1', 'c1']], [2, ['d1', 'e1']], [1, []], [2, ['y1']]], 'pages': {'1': ['a1'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['b1', 'e1']], ['alloc', 'y1', 2], ['alloc', 'x1', 1], ['gc', ['x1', 'y1']], ['finish']]),
   {'log': [[2, ['d1']], [1, ['a1', 'c1']], [1, ['b1']], [2, ['e1']]], 'pages': {'1': ['x1'], '2': ['y1']}}),
  ('three cycles',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'd1']], ['gc', ['a1', 'd1']], ['gc', ['d1']], ['finish']]),
   {'log': [[1, ['c1']], [2, ['e1']], [1, ['b1']], [2, []], [1, ['a1']], [2, []]],
    'pages': {'1': [], '2': ['d1']}}),
  ('control: everything live',
   ({1: {'a1': 0, 'b1': 0, 'c1': 0}, 2: {'d1': 0, 'e1': 0}},
    [['gc', ['a1', 'b1', 'c1', 'd1', 'e1']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a1', 'b1', 'c1'], '2': ['d1', 'e1']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']]], 'pages': {'1': ['a2', 'x2'], '2': ['d2']}}),
  ('second cycle with an unswept page',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'd2']], ['alloc', 'x2', 1], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['e2']], [1, ['x2']], [2, ['d2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2']], ['finish'], ['alloc', 'y2', 2], ['gc', ['a2']], ['finish']]),
   {'log': [[1, ['b2', 'c2']], [2, ['d2', 'e2']], [1, []], [2, ['y2']]], 'pages': {'1': ['a2'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['b2', 'e2']], ['alloc', 'y2', 2], ['alloc', 'x2', 1], ['gc', ['x2', 'y2']], ['finish']]),
   {'log': [[2, ['d2']], [1, ['a2', 'c2']], [1, ['b2']], [2, ['e2']]], 'pages': {'1': ['x2'], '2': ['y2']}}),
  ('three cycles',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'd2']], ['gc', ['a2', 'd2']], ['gc', ['d2']], ['finish']]),
   {'log': [[1, ['c2']], [2, ['e2']], [1, ['b2']], [2, []], [1, ['a2']], [2, []]],
    'pages': {'1': [], '2': ['d2']}}),
  ('control: everything live',
   ({1: {'a2': 0, 'b2': 0, 'c2': 0}, 2: {'d2': 0, 'e2': 0}},
    [['gc', ['a2', 'b2', 'c2', 'd2', 'e2']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a2', 'b2', 'c2'], '2': ['d2', 'e2']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']]], 'pages': {'1': ['a3', 'x3'], '2': ['d3']}}),
  ('second cycle with an unswept page',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'd3']], ['alloc', 'x3', 1], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['e3']], [1, ['x3']], [2, ['d3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3']], ['finish'], ['alloc', 'y3', 2], ['gc', ['a3']], ['finish']]),
   {'log': [[1, ['b3', 'c3']], [2, ['d3', 'e3']], [1, []], [2, ['y3']]], 'pages': {'1': ['a3'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['b3', 'e3']], ['alloc', 'y3', 2], ['alloc', 'x3', 1], ['gc', ['x3', 'y3']], ['finish']]),
   {'log': [[2, ['d3']], [1, ['a3', 'c3']], [1, ['b3']], [2, ['e3']]], 'pages': {'1': ['x3'], '2': ['y3']}}),
  ('three cycles',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'd3']], ['gc', ['a3', 'd3']], ['gc', ['d3']], ['finish']]),
   {'log': [[1, ['c3']], [2, ['e3']], [1, ['b3']], [2, []], [1, ['a3']], [2, []]],
    'pages': {'1': [], '2': ['d3']}}),
  ('control: everything live',
   ({1: {'a3': 0, 'b3': 0, 'c3': 0}, 2: {'d3': 0, 'e3': 0}},
    [['gc', ['a3', 'b3', 'c3', 'd3', 'e3']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a3', 'b3', 'c3'], '2': ['d3', 'e3']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']]], 'pages': {'1': ['a4', 'x4'], '2': ['d4']}}),
  ('second cycle with an unswept page',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'd4']], ['alloc', 'x4', 1], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['e4']], [1, ['x4']], [2, ['d4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4']], ['finish'], ['alloc', 'y4', 2], ['gc', ['a4']], ['finish']]),
   {'log': [[1, ['b4', 'c4']], [2, ['d4', 'e4']], [1, []], [2, ['y4']]], 'pages': {'1': ['a4'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['b4', 'e4']], ['alloc', 'y4', 2], ['alloc', 'x4', 1], ['gc', ['x4', 'y4']], ['finish']]),
   {'log': [[2, ['d4']], [1, ['a4', 'c4']], [1, ['b4']], [2, ['e4']]], 'pages': {'1': ['x4'], '2': ['y4']}}),
  ('three cycles',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'd4']], ['gc', ['a4', 'd4']], ['gc', ['d4']], ['finish']]),
   {'log': [[1, ['c4']], [2, ['e4']], [1, ['b4']], [2, []], [1, ['a4']], [2, []]],
    'pages': {'1': [], '2': ['d4']}}),
  ('control: everything live',
   ({1: {'a4': 0, 'b4': 0, 'c4': 0}, 2: {'d4': 0, 'e4': 0}},
    [['gc', ['a4', 'b4', 'c4', 'd4', 'e4']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a4', 'b4', 'c4'], '2': ['d4', 'e4']}})],
 [('regression: lazy sweep before allocation',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']]], 'pages': {'1': ['a5', 'x5'], '2': ['d5']}}),
  ('second cycle with an unswept page',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'd5']], ['alloc', 'x5', 1], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['e5']], [1, ['x5']], [2, ['d5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation after sweeping dies next cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5']], ['finish'], ['alloc', 'y5', 2], ['gc', ['a5']], ['finish']]),
   {'log': [[1, ['b5', 'c5']], [2, ['d5', 'e5']], [1, []], [2, ['y5']]], 'pages': {'1': ['a5'], '2': []}}),
  ('allocation into an unswept page mid-cycle',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['b5', 'e5']], ['alloc', 'y5', 2], ['alloc', 'x5', 1], ['gc', ['x5', 'y5']], ['finish']]),
   {'log': [[2, ['d5']], [1, ['a5', 'c5']], [1, ['b5']], [2, ['e5']]], 'pages': {'1': ['x5'], '2': ['y5']}}),
  ('three cycles',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'd5']], ['gc', ['a5', 'd5']], ['gc', ['d5']], ['finish']]),
   {'log': [[1, ['c5']], [2, ['e5']], [1, ['b5']], [2, []], [1, ['a5']], [2, []]],
    'pages': {'1': [], '2': ['d5']}}),
  ('control: everything live',
   ({1: {'a5': 0, 'b5': 0, 'c5': 0}, 2: {'d5': 0, 'e5': 0}},
    [['gc', ['a5', 'b5', 'c5', 'd5', 'e5']], ['finish']]),
   {'log': [[1, []], [2, []]], 'pages': {'1': ['a5', 'b5', 'c5'], '2': ['d5', 'e5']}})]]
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:
Dead objects from the previous cycle are resurrected when the parity flips back to their stale mark.

Mark bits flip meaning every cycle: an object is live when its mark equals epoch % 2. Initially every object has mark 0 at epoch 0. gc live_ids: finish sweeping every unswept page, advance the epoch, set the mark of each listed live object to the new parity, and mark all pages unswept. alloc id page: sweep the page first if it is unswept, then create the object with the current parity. finish sweeps the remaining pages. Sweeping a page removes objects whose mark differs from the current parity and logs [page, removed]. Return the sweep log and surviving objects per page.

split: open-access