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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[1]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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 skew heavy certificate certificate reports an incorrect light right.

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting model.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+max(x[1],x[2]) for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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 skew heavy certificate certificate reports an incorrect subtree sizes.

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting model.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': sum(x[2] for x in a if x[0] in heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(a)-len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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 skew heavy certificate certificate reports an incorrect potential.

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting model.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i in heavy for i in path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': len(path),
    'potential_delta': len(newheavy)-len(heavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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 skew heavy certificate certificate reports an incorrect light visits.

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting model.

split: open-access


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

N = 1
observations = []
def solve(d):
    a=d['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(heavy)-len(newheavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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['before']; after=d['after']; path=d['path']; heavy=[x[0] for x in a if 2*x[2]>1+x[1]+x[2]]; newheavy=[x[0] for x in after if 2*x[2]>1+x[1]+x[2]]
    return {'heavy': heavy,
    'light_right': [x[0] for x in a if x[2]>0 and x[0] not in heavy],
    'subtree_sizes': [1+x[1]+x[2] for x in a],
    'potential': len(heavy),
    'light_visits': sum(i not in heavy for i in path),
    'potential_delta': len(newheavy)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 6], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [7, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 7], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [8, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 8], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [9, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 9], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [10, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})], [({'before': [], 'after': [], 'path': []}, {'heavy': [], 'light_right': [], 'subtree_sizes': [], 'potential': 0, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 0, 0]], 'after': [['a', 0, 0]], 'path': ['a']}, {'heavy': [], 'light_right': [], 'subtree_sizes': [1], 'potential': 0, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 1], ['b', 0, 2]], 'after': [['a', 1, 0], ['b', 2, 0]], 'path': ['a', 'b']}, {'heavy': ['b'], 'light_right': ['a'], 'subtree_sizes': [2, 3], 'potential': 1, 'light_visits': 1, 'potential_delta': -1}), ({'before': [['a', 2, 4], ['b', 1, 3]], 'after': [['a', 0, 5], ['b', 1, 3]], 'path': ['a']}, {'heavy': ['a', 'b'], 'light_right': [], 'subtree_sizes': [7, 5], 'potential': 2, 'light_visits': 0, 'potential_delta': 0}), ({'before': [['a', 2, 3], ['b', 3, 2]], 'after': [['a', 4, 1], ['b', 0, 4]], 'path': ['b']}, {'heavy': [], 'light_right': ['a', 'b'], 'subtree_sizes': [6, 6], 'potential': 0, 'light_visits': 1, 'potential_delta': 1}), ({'before': [['a', 0, 5], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [6, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0}), ({'before': [['a', 0, 10], ['b', 0, 0], ['c', 2, 2]], 'after': [['a', 3, 2], ['b', 0, 0], ['c', 0, 4]], 'path': ['a', 'c']}, {'heavy': ['a'], 'light_right': ['c'], 'subtree_sizes': [11, 1, 5], 'potential': 1, 'light_visits': 1, 'potential_delta': 0})]][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 skew heavy certificate certificate reports an incorrect potential delta.

A skew-heap amortized certificate supplies nodes [id,left_size,right_size] with nonnegative subtree sizes. A right edge is heavy when right_size exceeds half the complete subtree size (1+left+right). Report heavy ids, light right ids, complete sizes, heavy potential, right-path charged light visits, and potential change between before and after certificates. Path ids refer to before nodes; this is a stipulated accounting model.

split: open-access