{"abstract":"Nearly full old regions are treated as empty and chosen for evacuation.","category":"Garbage collector invariants","checks":7,"contract":"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.","evaluation_group":"w2-garbage-collector-invariants-collection-set-selection","failed_approach":"Allowing equality admits regions exactly at the threshold.","family":"w2-garbage-collector-invariants-collection-set-selection-liveness-threshold","id":"FA-90641","implementations":{"attempt":{"sha256":"c54af1f2737b2f7857d3f2358dfed906d155b76da0e754c31086feb252ab46a4","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(regions, budget, live_pct, cost):\n    cset = []\n    time = 0\n    for rid, kind, used, live in regions:\n        if kind == 'young':\n            cset.append(rid)\n            time += live * cost\n    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 // r[2] <= live_pct]\n    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))\n    for rid, kind, used, live in cands:\n        t = live * cost\n        if time + t > budget:\n            break\n        cset.append(rid)\n        time += t\n    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)\n    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    85,\n    85,\n    2),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    90,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    95,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    100,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"aa89694c75e46710022b497bdb16315e6845c2fd6942385feac5adea9e33409a","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(regions, budget, live_pct, cost):\n    cset = []\n    time = 0\n    for rid, kind, used, live in regions:\n        if kind == 'young':\n            cset.append(rid)\n            time += live * cost\n    cands = [r for r in regions if r[1] == 'old' and r[3] // r[2] * 100 < live_pct]\n    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))\n    for rid, kind, used, live in cands:\n        t = live * cost\n        if time + t > budget:\n            break\n        cset.append(rid)\n        time += t\n    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)\n    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    85,\n    85,\n    2),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    90,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    95,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    100,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"2324d77e6602475e201cd5306025558e86bafedc7295b36cd173443e854b15ac","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(regions, budget, live_pct, cost):\n    cset = []\n    time = 0\n    for rid, kind, used, live in regions:\n        if kind == 'young':\n            cset.append(rid)\n            time += live * cost\n    cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]\n    cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))\n    for rid, kind, used, live in cands:\n        t = live * cost\n        if time + t > budget:\n            break\n        cset.append(rid)\n        time += t\n    reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)\n    return {'cset': cset, 'time': time, 'reclaimed': reclaimed}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    101,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    85,\n    85,\n    2),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 80}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    102,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    90,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    103,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    95,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    104,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    100,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})],\n [('regression: candidates fill the budget exactly',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    115,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('budget stops at the first region that does not fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),\n  ('expensive region first stops selection',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200],\n     [11, 'old', 300, 200]],\n    105,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40}),\n  ('region at exactly the liveness threshold excluded',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    85,\n    1),\n   {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),\n  ('higher threshold admits more regions',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    1000,\n    91,\n    1),\n   {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),\n  ('cost multiplier',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    105,\n    85,\n    2),\n   {'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),\n  ('control: only young regions fit',\n   ([[1, 'young', 100, 30],\n     [2, 'young', 100, 10],\n     [3, 'old', 100, 20],\n     [4, 'old', 100, 85],\n     [5, 'old', 100, 50],\n     [6, 'humongous', 400, 0],\n     [7, 'old', 100, 5],\n     [8, 'old', 100, 90],\n     [9, 'humongous', 200, 200]],\n    20,\n    85,\n    1),\n   {'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-garbage-collector-invariants-collection-set-selection-liveness-threshold","generated_at":"2026-09-29T14:51:28.533646+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Region-based collectors meet pause goals by choosing the collection set against a cost budget.","repair":"Compare live * 100 with pct * used.","root_cause":"The liveness ratio is computed with integer division before scaling to percent.","sha256":"e08b7950539c161e31bf189159abd9c7df9adbf14f245e23c3706705334bb2f7","title":"Collection set: liveness ratio truncated to zero · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.514,"exit_code":1,"observations":[{"actual":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"check":"regression: candidates fill the budget exactly","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":true},{"actual":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"check":"budget stops at the first region that does not fit","expected":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"expensive region first stops selection","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true},{"actual":{"cset":[1,2,7,3,5,4],"reclaimed":400,"time":200},"check":"region at exactly the liveness threshold excluded","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":false},{"actual":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"check":"higher threshold admits more regions","expected":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":80},"check":"cost multiplier","expected":{"cset":[1,2],"reclaimed":160,"time":80},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"control: only young regions fit","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: candidates fill the budget exactly\", \"actual\": {\"cset\": [1, 2, 7, 3, 5], \"time\": 115, \"reclaimed\": 385}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": true}, {\"check\": \"budget stops at the first region that does not fit\", \"actual\": {\"cset\": [1, 2, 7, 3], \"time\": 65, \"reclaimed\": 335}, \"expected\": {\"cset\": [1, 2, 7, 3], \"reclaimed\": 335, \"time\": 65}, \"passed\": true}, {\"check\": \"expensive region first stops selection\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}, {\"check\": \"region at exactly the liveness threshold excluded\", \"actual\": {\"cset\": [1, 2, 7, 3, 5, 4], \"time\": 200, \"reclaimed\": 400}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": false}, {\"check\": \"higher threshold admits more regions\", \"actual\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"time\": 290, \"reclaimed\": 410}, \"expected\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"reclaimed\": 410, \"time\": 290}, \"passed\": true}, {\"check\": \"cost multiplier\", \"actual\": {\"cset\": [1, 2], \"time\": 80, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 80}, \"passed\": true}, {\"check\": \"control: only young regions fit\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.274,"exit_code":1,"observations":[{"actual":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"check":"regression: candidates fill the budget exactly","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":true},{"actual":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"check":"budget stops at the first region that does not fit","expected":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"expensive region first stops selection","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true},{"actual":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"check":"region at exactly the liveness threshold excluded","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":false},{"actual":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"check":"higher threshold admits more regions","expected":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":80},"check":"cost multiplier","expected":{"cset":[1,2],"reclaimed":160,"time":80},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"control: only young regions fit","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: candidates fill the budget exactly\", \"actual\": {\"cset\": [1, 2, 7, 3, 5], \"time\": 115, \"reclaimed\": 385}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": true}, {\"check\": \"budget stops at the first region that does not fit\", \"actual\": {\"cset\": [1, 2, 7, 3], \"time\": 65, \"reclaimed\": 335}, \"expected\": {\"cset\": [1, 2, 7, 3], \"reclaimed\": 335, \"time\": 65}, \"passed\": true}, {\"check\": \"expensive region first stops selection\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}, {\"check\": \"region at exactly the liveness threshold excluded\", \"actual\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"time\": 290, \"reclaimed\": 410}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": false}, {\"check\": \"higher threshold admits more regions\", \"actual\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"time\": 290, \"reclaimed\": 410}, \"expected\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"reclaimed\": 410, \"time\": 290}, \"passed\": true}, {\"check\": \"cost multiplier\", \"actual\": {\"cset\": [1, 2], \"time\": 80, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 80}, \"passed\": true}, {\"check\": \"control: only young regions fit\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.1,"exit_code":0,"observations":[{"actual":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"check":"regression: candidates fill the budget exactly","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":true},{"actual":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"check":"budget stops at the first region that does not fit","expected":{"cset":[1,2,7,3],"reclaimed":335,"time":65},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"expensive region first stops selection","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true},{"actual":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"check":"region at exactly the liveness threshold excluded","expected":{"cset":[1,2,7,3,5],"reclaimed":385,"time":115},"passed":true},{"actual":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"check":"higher threshold admits more regions","expected":{"cset":[1,2,7,3,5,4,8],"reclaimed":410,"time":290},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":80},"check":"cost multiplier","expected":{"cset":[1,2],"reclaimed":160,"time":80},"passed":true},{"actual":{"cset":[1,2],"reclaimed":160,"time":40},"check":"control: only young regions fit","expected":{"cset":[1,2],"reclaimed":160,"time":40},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"regression: candidates fill the budget exactly\", \"actual\": {\"cset\": [1, 2, 7, 3, 5], \"time\": 115, \"reclaimed\": 385}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": true}, {\"check\": \"budget stops at the first region that does not fit\", \"actual\": {\"cset\": [1, 2, 7, 3], \"time\": 65, \"reclaimed\": 335}, \"expected\": {\"cset\": [1, 2, 7, 3], \"reclaimed\": 335, \"time\": 65}, \"passed\": true}, {\"check\": \"expensive region first stops selection\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}, {\"check\": \"region at exactly the liveness threshold excluded\", \"actual\": {\"cset\": [1, 2, 7, 3, 5], \"time\": 115, \"reclaimed\": 385}, \"expected\": {\"cset\": [1, 2, 7, 3, 5], \"reclaimed\": 385, \"time\": 115}, \"passed\": true}, {\"check\": \"higher threshold admits more regions\", \"actual\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"time\": 290, \"reclaimed\": 410}, \"expected\": {\"cset\": [1, 2, 7, 3, 5, 4, 8], \"reclaimed\": 410, \"time\": 290}, \"passed\": true}, {\"check\": \"cost multiplier\", \"actual\": {\"cset\": [1, 2], \"time\": 80, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 80}, \"passed\": true}, {\"check\": \"control: only young regions fit\", \"actual\": {\"cset\": [1, 2], \"time\": 40, \"reclaimed\": 160}, \"expected\": {\"cset\": [1, 2], \"reclaimed\": 160, \"time\": 40}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}