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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': min(a+[["pad",0]],key=lambda x:x[1])[0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': min(a+[["pad",10]],key=lambda x:x[1])[0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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 tournament padding certificate reports an incorrect champion.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length(),
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': max(0,m-1),
    'active_indices': list(range(m)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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 tournament padding certificate reports an incorrect rounds.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(c)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(c-m,c)),
    'key_comparisons': max(0,m-1)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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 tournament padding certificate reports an incorrect active indices.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': c-1}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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['leaves']; m=len(a); c=1
    while c<m: c*=2
    padded=a+[None]*(c-m); champion=min(range(m),key=lambda i:a[i][1]) if m else None
    return {'capacity': c,
    'leaves': padded,
    'champion': None if champion is None else a[champion][0],
    'rounds': c.bit_length()-1,
    'active_indices': list(range(m)),
    'key_comparisons': m}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], None, None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5], 'key_comparisons': 5})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], None], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6], 'key_comparisons': 6})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2]], 'champion': '100', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7], 'key_comparisons': 7})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], None, None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8], 'key_comparisons': 8})], [({'leaves': []}, {'capacity': 1, 'leaves': [None], 'champion': None, 'rounds': 0, 'active_indices': [], 'key_comparisons': 0}), ({'leaves': [['x', 50]]}, {'capacity': 1, 'leaves': [['x', 50]], 'champion': 'x', 'rounds': 0, 'active_indices': [0], 'key_comparisons': 0}), ({'leaves': [['z', 3], ['a', 3]]}, {'capacity': 2, 'leaves': [['z', 3], ['a', 3]], 'champion': 'z', 'rounds': 1, 'active_indices': [0, 1], 'key_comparisons': 1}), ({'leaves': [['a', 8], ['b', 2], ['c', 5]]}, {'capacity': 4, 'leaves': [['a', 8], ['b', 2], ['c', 5], None], 'champion': 'b', 'rounds': 2, 'active_indices': [0, 1, 2], 'key_comparisons': 2}), ({'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]]}, {'capacity': 4, 'leaves': [['a', -2], ['b', 0], ['c', 4], ['d', 1]], 'champion': 'a', 'rounds': 2, 'active_indices': [0, 1, 2, 3], 'key_comparisons': 3}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1]]}, {'capacity': 8, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], None, None, None], 'champion': 'a', 'rounds': 3, 'active_indices': [0, 1, 2, 3, 4], 'key_comparisons': 4}), ({'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4]]}, {'capacity': 16, 'leaves': [['e', 9], ['d', 7], ['c', 5], ['b', 3], ['a', 1], ['100', 0], ['101', 1], ['102', 2], ['103', 3], ['104', 4], None, None, None, None, None, None], 'champion': '100', 'rounds': 4, 'active_indices': [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 'key_comparisons': 9})]][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 tournament padding certificate reports an incorrect key comparisons.

A tournament is built from m real leaves [id,key]. Round leaf capacity to the next power of two (empty capacity one) and append inactive None pads. Inactive pads always lose without numeric sentinel assumptions. Report capacity, padded leaves, champion id with arrival-order ties, match rounds, active-leaf indices, and key-comparison count m-1 for m>0.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['nodes']; actual=[max(x[2],x[3]) if x[2]!=x[3] else x[2]+1 for x in a]; changed=[]; stop=None; visited=0
    for x,r in zip(a,actual):
        visited+=1
        if r>=x[1]: stop=x[0]; break
        changed.append(x[0])
    return {'computed': [1+max(x[2],x[3]) for x in a],
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': [r if x[0] in changed else x[1] for x,r in zip(a,actual)],
    'drops': [x[1]-r for x,r in zip(a,actual) if x[0] in changed],
    'visited': visited}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 5, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [2, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 6, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [3, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 7, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [4, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 8, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [5, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 9, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [6, 1], 'visited': 3})]][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['nodes']; actual=[max(x[2],x[3]) if x[2]!=x[3] else x[2]+1 for x in a]; changed=[]; stop=None; visited=0
    for x,r in zip(a,actual):
        visited+=1
        if r>=x[1]: stop=x[0]; break
        changed.append(x[0])
    return {'computed': [min(x[2],x[3])+1 for x in a],
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': [r if x[0] in changed else x[1] for x,r in zip(a,actual)],
    'drops': [x[1]-r for x,r in zip(a,actual) if x[0] in changed],
    'visited': visited}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 5, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [2, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 6, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [3, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 7, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [4, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 8, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [5, 1], 'visited': 3})], [({'nodes': []}, {'computed': [], 'decreased': [], 'stop': None, 'prefix_ranks': [], 'drops': [], 'visited': 0}), ({'nodes': [['a', 0, -1, -1]]}, {'computed': [0], 'decreased': [], 'stop': 'a', 'prefix_ranks': [0], 'drops': [], 'visited': 1}), ({'nodes': [['a', 3, 0, 0], ['b', 4, 2, 1], ['c', 3, 2, 2]]}, {'computed': [1, 2, 3], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [1, 2, 3], 'drops': [2, 2], 'visited': 3}), ({'nodes': [['a', 1, 0, 0], ['b', 5, 1, 1]]}, {'computed': [1, 2], 'decreased': [], 'stop': 'a', 'prefix_ranks': [1, 5], 'drops': [], 'visited': 1}), ({'nodes': [['a', 2, 0, -1], ['b', 4, 0, 2], ['c', 7, 2, 3]]}, {'computed': [0, 2, 3], 'decreased': ['a', 'b', 'c'], 'stop': None, 'prefix_ranks': [0, 2, 3], 'drops': [2, 2, 4], 'visited': 3}), ({'nodes': [['a', 4, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [1, 1], 'visited': 3}), ({'nodes': [['a', 9, 2, 2], ['b', 4, 3, 2], ['c', 3, 2, 2], ['d', 8, 1, 0]]}, {'computed': [3, 3, 3, 1], 'decreased': ['a', 'b'], 'stop': 'c', 'prefix_ranks': [3, 3, 3, 8], 'drops': [6, 1], 'visited': 3})]][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 rank loss propagation certificate reports an incorrect computed.

A stipulated rank-balanced heap repair trace supplies bottom-up nodes [id,stored_rank,left_rank,right_rank], with null child rank -1. Recomputed rank is max child rank if child ranks differ, otherwise child rank+1. A decrease propagates while computed rank is smaller, stopping at first unchanged node. Report local recomputed ranks, decreased ids, stopping id, new prefix ranks, rank drops, and visited count. This models the stated rule only, not every rank-pairing heap variant.

split: open-access