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': actual,
    'decreased': [x[0] for x,r in zip(a,actual) if r<x[1]],
    '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': actual,
    'decreased': [x[0] for x,r in zip(a,actual) if r<=x[1]],
    '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 decreased.

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


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': actual,
    'decreased': changed,
    'stop': a[-1][0] if a else None,
    '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)

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['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': actual,
    'decreased': changed,
    'stop': None,
    '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 stop.

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


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': actual,
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': 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': actual,
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': [x[1]-1 if x[0] in changed else x[1] for x in a],
    '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 prefix ranks.

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


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': actual,
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': [r if x[0] in changed else x[1] for x,r in zip(a,actual)],
    'drops': [1 for x 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': actual,
    'decreased': changed,
    'stop': stop,
    'prefix_ranks': [r if x[0] in changed else x[1] for x,r in zip(a,actual)],
    'drops': [r-x[1] 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 drops.

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


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': actual,
    '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': len(a)}
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': actual,
    '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': len(changed)}
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 visited.

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


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': [x[0] for x in a if x[2]>x[1]],
    '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)-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': [x[0] for x in a if 2*x[2]>=1+x[1]+x[2]],
    '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)-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 heavy.

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