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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(live),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(set(x[2] for x in kept)),
    'trigger': len(q)>2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded lazy compaction certificate reports an incorrect post size.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access


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

N = 1
observations = []
def solve(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>=2*len(live)+d["slack"]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    q=d['records']; live=d['live']; kept=[x for x in q if x[2] in live and x[3]==live[x[2]]]
    return {'kept': sorted(kept,key=lambda x:(x[0],x[1])),
    'stale': len(q)-len(kept),
    'duplicate_current': sorted({x[2] for x in kept if sum(y[2]==x[2] for y in kept)>1}),
    'missing': sorted(set(live)-{x[2] for x in kept}),
    'post_size': len(kept),
    'trigger': len(q)>2*(len(live)+d["slack"])}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 3}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 4}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 5}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})], [({'records': [], 'live': {}, 'slack': 0}, {'kept': [], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 0, 'trigger': False}), ({'records': [[1, 0, 'a', 0]], 'live': {'a': 0}, 'slack': 0}, {'kept': [[1, 0, 'a', 0]], 'stale': 0, 'duplicate_current': [], 'missing': [], 'post_size': 1, 'trigger': False}), ({'records': [[5, 0, 'a', 0], [3, 1, 'a', 1], [2, 2, 'b', 0]], 'live': {'a': 1, 'b': 0}, 'slack': 0}, {'kept': [[2, 2, 'b', 0], [3, 1, 'a', 1]], 'stale': 1, 'duplicate_current': [], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[1, 0, 'a', 0], [2, 1, 'a', 1]], 'live': {'a': 2}, 'slack': 0}, {'kept': [], 'stale': 2, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False}), ({'records': [[2, 0, 'a', 1], [1, 1, 'a', 1], [3, 2, 'x', 0], [4, 3, 'y', 0]], 'live': {'a': 1}, 'slack': 2}, {'kept': [[1, 1, 'a', 1], [2, 0, 'a', 1]], 'stale': 2, 'duplicate_current': ['a'], 'missing': [], 'post_size': 2, 'trigger': False}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 1}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': True}), ({'records': [[0, 0, 'x', 0], [1, 1, 'x', 0], [2, 2, 'x', 0], [3, 3, 'x', 0]], 'live': {'a': 1}, 'slack': 6}, {'kept': [], 'stale': 4, 'duplicate_current': [], 'missing': ['a'], 'post_size': 0, 'trigger': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded lazy compaction certificate reports an incorrect trigger.

A lazy heap compaction receives arbitrary physical records [priority,serial,id,version] and live map id->version. Preserve only records whose id and version match, retain duplicate physical records for diagnostic detection, heapify by (priority,serial), and report stale count, duplicate-current ids, live-id coverage, storage ratio numerator, and triggering condition physical>2*live+slack.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; n=len(a)
    def depth(i): return (i+1).bit_length()-1
    def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
    return {'parity': [i%2 for i in range(n)],
    'grandparents': [None if i<3 else (i-3)//4 for i in range(n)],
    'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
    'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
    'maximum': None if not a else max(a[1:3] or a),
    'edges': [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    a=d['keys']; n=len(a)
    def depth(i): return (i+1).bit_length()-1
    def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
    return {'parity': [(i.bit_length()-1)%2 for i in range(n)],
    'grandparents': [None if i<3 else (i-3)//4 for i in range(n)],
    'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
    'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
    'maximum': None if not a else max(a[1:3] or a),
    'edges': [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded minmax levels certificate reports an incorrect parity.

A min-max heap certificate is a complete zero-based binary array. Even depth is a minimum level, odd depth a maximum level. Report level parities, grandparent indices, minimum-level grandchild violations, maximum-level grandchild violations, maximum endpoint, and immediate-child level alternation pairs. Empty maximum is None.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['keys']; n=len(a)
    def depth(i): return (i+1).bit_length()-1
    def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
    return {'parity': [depth(i)%2 for i in range(n)],
    'grandparents': [None if i<3 else (i-1)//4 for i in range(n)],
    'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
    'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
    'maximum': None if not a else max(a[1:3] or a),
    'edges': [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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(d):
    a=d['keys']; n=len(a)
    def depth(i): return (i+1).bit_length()-1
    def grandchildren(i): return [j for j in range(4*i+3,4*i+7) if j<n]
    return {'parity': [depth(i)%2 for i in range(n)],
    'grandparents': [None if i<3 else (i-1)//2 for i in range(n)],
    'min_violations': [[i,j] for i in range(n) if depth(i)%2==0 for j in grandchildren(i) if a[j]<a[i]],
    'max_violations': [[i,j] for i in range(n) if depth(i)%2==1 for j in grandchildren(i) if a[j]>a[i]],
    'maximum': None if not a else max(a[1:3] or a),
    'edges': [[i,j] for i in range(n) for j in (2*i+1,2*i+2) if j<n]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 8, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 9, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 10, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 10, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 11, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 11, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})], [({'keys': []}, {'parity': [], 'grandparents': [], 'min_violations': [], 'max_violations': [], 'maximum': None, 'edges': []}), ({'keys': [4]}, {'parity': [0], 'grandparents': [None], 'min_violations': [], 'max_violations': [], 'maximum': 4, 'edges': []}), ({'keys': [1, 8, 9]}, {'parity': [0, 1, 1], 'grandparents': [None, None, None], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2]]}), ({'keys': [2, 9, 8, 3, 2, 4, 7]}, {'parity': [0, 1, 1, 0, 0, 0, 0], 'grandparents': [None, None, None, 0, 0, 0, 0], 'min_violations': [], 'max_violations': [], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]}), ({'keys': [5, 4, 9, 1, 8, 2, 6, 10, 3, 8, 7, 6, 5, 4, 3]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [[0, 3], [0, 5]], 'max_violations': [[1, 7], [1, 9], [1, 10]], 'maximum': 9, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 7, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [[1, 10]], 'maximum': 8, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]}), ({'keys': [0, 12, 8, 2, 3, 1, 4, 7, 7, 7, 9, 8, 8, 8, 8]}, {'parity': [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], 'grandparents': [None, None, None, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], 'min_violations': [], 'max_violations': [], 'maximum': 12, 'edges': [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6], [3, 7], [3, 8], [4, 9], [4, 10], [5, 11], [5, 12], [6, 13], [6, 14]]})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The bounded minmax levels certificate reports an incorrect grandparents.

A min-max heap certificate is a complete zero-based binary array. Even depth is a minimum level, odd depth a maximum level. Report level parities, grandparent indices, minimum-level grandchild violations, maximum-level grandchild violations, maximum endpoint, and immediate-child level alternation pairs. Empty maximum is None.

split: open-access