FA-78301 / Subtitle cue timing / Open access
Active cue lookup with prefix maximum ends: backward walk pruning · case 01
A long cue that started earlier is missed when a short cue ends between it and the query.
ROOT CAUSE
The walk stops at the first inactive cue instead of using the prefix maximum end.
VERIFIED REPAIR
Continue while the prefix maximum end exceeds t.
Unsuccessful approach: Requiring both conditions still stops at the first inactive cue.
Case contract
cues [start,end] are sorted by start. Return the ascending indices of cues active at t (start <= t < end). The search bisects the starts and walks backwards while the running maximum end of the prefix exceeds t.
Why this case matters
Subtitle timing defects shift, hide or overlap captions that viewers depend on for comprehension and accessibility.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(cues, t):
starts=[c[0] for c in cues]
hi=bisect.bisect_right(starts,t)
maxend=[]
run=0
for c in cues:
run=max(run,c[1])
maxend.append(run)
res=[]
i=hi-1
while i>=0 and cues[i][1]>t:
if cues[i][1]>t:
res.append(i)
i-=1
return sorted(res)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: backward walk pruning', [[[0, 1000], [100, 200], [300, 400]], 350], [0, 2]), ('regression variant: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair probe: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('partial repair variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 100], [100, 1100], [200, 300], [200, 500]], 50], [0]), ('normal control', [[[100, 400], [300, 400], [300, 400], [300, 350], [400, 500], [500, 800]], 300], [0, 1, 2, 3]), ('normal control', [[[100, 400], [300, 400], [400, 450], [400, 700], [400, 1400]], 0], [])], [('regression: backward walk pruning', [[[0, 50], [0, 500], [200, 250]], 300], [1]), ('regression variant: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair probe: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('partial repair variant: backward walk pruning', [[[0, 1000], [0, 300], [100, 1100], [100, 150], [100, 150], [400, 500]], 200], [0, 1, 2]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 1000], [200, 300], [400, 450]], 200], [0, 1]), ('normal control', [[[100, 200], [200, 250]], 0], []), ('normal control', [[[0, 50], [100, 400], [200, 500], [400, 450], [500, 1500]], 1200], [4])], [('regression: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('regression variant: backward walk pruning', [[[0, 300], [0, 100], [200, 1200], [200, 300], [300, 600], [300, 1300]], 400], [2, 4, 5]), ('partial repair probe: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('partial repair variant: backward walk pruning', [[[100, 1100], [200, 250], [400, 450]], 300], [0]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 1000], [100, 1100], [200, 500], [200, 500]], 200], [0, 1, 2, 3]), ('normal control', [[[0, 50]], 400], []), ('normal control', [[[0, 100], [0, 100], [100, 150]], 200], [])], [('regression: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('regression variant: backward walk pruning', [[[0, 300], [0, 50], [100, 200], [200, 500], [400, 500]], 100], [0, 2]), ('partial repair probe: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair variant: backward walk pruning', [[[0, 100], [200, 1200], [200, 250], [200, 1200], [500, 600]], 500], [1, 3, 4]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 100], [0, 100], [400, 700], [500, 1500]], 150], []), ('normal control', [[[200, 500]], 500], []), ('normal control', [[[500, 550]], 50], [])], [('regression: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('regression variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('partial repair probe: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair variant: backward walk pruning', [[[0, 1000], [300, 350], [400, 1400]], 400], [0, 2]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 300], [100, 1100], [200, 250], [500, 550]], 100], [0, 1]), ('normal control', [[[400, 450]], 150], []), ('normal control', [[[200, 300]], 150], [])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: backward walk pruning | [2] | [0, 2] | Failed |
| regression variant: backward walk pruning | [] | [2] | Failed |
| partial repair probe: backward walk pruning | [] | [1, 4] | Failed |
| partial repair variant: backward walk pruning | [4] | [1, 4] | Failed |
| boundary control | [1] | [1] | Passed |
| boundary control | [] | [] | Passed |
| normal control | [0] | [0] | Passed |
| normal control | [0, 1, 2, 3] | [0, 1, 2, 3] | Passed |
| normal control | [] | [] | Passed |
SHA-256 / 00cdadbffe79a40c69057d97828b3ab961358e2945d4aa6144b042804e63f5c8
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(cues, t):
starts=[c[0] for c in cues]
hi=bisect.bisect_right(starts,t)
maxend=[]
run=0
for c in cues:
run=max(run,c[1])
maxend.append(run)
res=[]
i=hi-1
while i>=0 and maxend[i]>t and cues[i][1]>t:
if cues[i][1]>t:
res.append(i)
i-=1
return sorted(res)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: backward walk pruning', [[[0, 1000], [100, 200], [300, 400]], 350], [0, 2]), ('regression variant: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair probe: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('partial repair variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 100], [100, 1100], [200, 300], [200, 500]], 50], [0]), ('normal control', [[[100, 400], [300, 400], [300, 400], [300, 350], [400, 500], [500, 800]], 300], [0, 1, 2, 3]), ('normal control', [[[100, 400], [300, 400], [400, 450], [400, 700], [400, 1400]], 0], [])], [('regression: backward walk pruning', [[[0, 50], [0, 500], [200, 250]], 300], [1]), ('regression variant: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair probe: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('partial repair variant: backward walk pruning', [[[0, 1000], [0, 300], [100, 1100], [100, 150], [100, 150], [400, 500]], 200], [0, 1, 2]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 1000], [200, 300], [400, 450]], 200], [0, 1]), ('normal control', [[[100, 200], [200, 250]], 0], []), ('normal control', [[[0, 50], [100, 400], [200, 500], [400, 450], [500, 1500]], 1200], [4])], [('regression: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('regression variant: backward walk pruning', [[[0, 300], [0, 100], [200, 1200], [200, 300], [300, 600], [300, 1300]], 400], [2, 4, 5]), ('partial repair probe: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('partial repair variant: backward walk pruning', [[[100, 1100], [200, 250], [400, 450]], 300], [0]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 1000], [100, 1100], [200, 500], [200, 500]], 200], [0, 1, 2, 3]), ('normal control', [[[0, 50]], 400], []), ('normal control', [[[0, 100], [0, 100], [100, 150]], 200], [])], [('regression: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('regression variant: backward walk pruning', [[[0, 300], [0, 50], [100, 200], [200, 500], [400, 500]], 100], [0, 2]), ('partial repair probe: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair variant: backward walk pruning', [[[0, 100], [200, 1200], [200, 250], [200, 1200], [500, 600]], 500], [1, 3, 4]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 100], [0, 100], [400, 700], [500, 1500]], 150], []), ('normal control', [[[200, 500]], 500], []), ('normal control', [[[500, 550]], 50], [])], [('regression: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('regression variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('partial repair probe: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair variant: backward walk pruning', [[[0, 1000], [300, 350], [400, 1400]], 400], [0, 2]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 300], [100, 1100], [200, 250], [500, 550]], 100], [0, 1]), ('normal control', [[[400, 450]], 150], []), ('normal control', [[[200, 300]], 150], [])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: backward walk pruning | [2] | [0, 2] | Failed |
| regression variant: backward walk pruning | [] | [2] | Failed |
| partial repair probe: backward walk pruning | [] | [1, 4] | Failed |
| partial repair variant: backward walk pruning | [4] | [1, 4] | Failed |
| boundary control | [1] | [1] | Passed |
| boundary control | [] | [] | Passed |
| normal control | [0] | [0] | Passed |
| normal control | [0, 1, 2, 3] | [0, 1, 2, 3] | Passed |
| normal control | [] | [] | Passed |
SHA-256 / 9b5123209f0fd1418b6c1f7c18aa8fbf51dc0e4356efdc900928a6b55f4634e1
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(cues, t):
starts=[c[0] for c in cues]
hi=bisect.bisect_right(starts,t)
maxend=[]
run=0
for c in cues:
run=max(run,c[1])
maxend.append(run)
res=[]
i=hi-1
while i>=0 and maxend[i]>t:
if cues[i][1]>t:
res.append(i)
i-=1
return sorted(res)
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('regression: backward walk pruning', [[[0, 1000], [100, 200], [300, 400]], 350], [0, 2]), ('regression variant: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair probe: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('partial repair variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 100], [100, 1100], [200, 300], [200, 500]], 50], [0]), ('normal control', [[[100, 400], [300, 400], [300, 400], [300, 350], [400, 500], [500, 800]], 300], [0, 1, 2, 3]), ('normal control', [[[100, 400], [300, 400], [400, 450], [400, 700], [400, 1400]], 0], [])], [('regression: backward walk pruning', [[[0, 50], [0, 500], [200, 250]], 300], [1]), ('regression variant: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair probe: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('partial repair variant: backward walk pruning', [[[0, 1000], [0, 300], [100, 1100], [100, 150], [100, 150], [400, 500]], 200], [0, 1, 2]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 1000], [200, 300], [400, 450]], 200], [0, 1]), ('normal control', [[[100, 200], [200, 250]], 0], []), ('normal control', [[[0, 50], [100, 400], [200, 500], [400, 450], [500, 1500]], 1200], [4])], [('regression: backward walk pruning', [[[0, 100], [0, 1000], [400, 500], [500, 600], [500, 1500], [500, 550]], 600], [1, 4]), ('regression variant: backward walk pruning', [[[0, 300], [0, 100], [200, 1200], [200, 300], [300, 600], [300, 1300]], 400], [2, 4, 5]), ('partial repair probe: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('partial repair variant: backward walk pruning', [[[100, 1100], [200, 250], [400, 450]], 300], [0]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 1000], [100, 1100], [200, 500], [200, 500]], 200], [0, 1, 2, 3]), ('normal control', [[[0, 50]], 400], []), ('normal control', [[[0, 100], [0, 100], [100, 150]], 200], [])], [('regression: backward walk pruning', [[[0, 100], [200, 1200], [300, 400], [500, 800]], 600], [1, 3]), ('regression variant: backward walk pruning', [[[0, 300], [0, 50], [100, 200], [200, 500], [400, 500]], 100], [0, 2]), ('partial repair probe: backward walk pruning', [[[300, 600], [300, 350], [400, 700], [400, 500]], 600], [2]), ('partial repair variant: backward walk pruning', [[[0, 100], [200, 1200], [200, 250], [200, 1200], [500, 600]], 500], [1, 3, 4]), ('boundary control', [[[0, 100]], 100], []), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('normal control', [[[0, 100], [0, 100], [400, 700], [500, 1500]], 150], []), ('normal control', [[[200, 500]], 500], []), ('normal control', [[[500, 550]], 50], [])], [('regression: backward walk pruning', [[[0, 1000], [100, 150], [100, 400], [200, 1200]], 300], [0, 2, 3]), ('regression variant: backward walk pruning', [[[200, 250], [200, 1200], [300, 350], [300, 350], [400, 700]], 600], [1, 4]), ('partial repair probe: backward walk pruning', [[[100, 1100], [100, 1100], [400, 500], [400, 700], [400, 450], [500, 550]], 500], [0, 1, 3, 5]), ('partial repair variant: backward walk pruning', [[[0, 1000], [300, 350], [400, 1400]], 400], [0, 2]), ('boundary control', [[[0, 100], [100, 200]], 100], [1]), ('boundary control', [[[0, 100]], 100], []), ('normal control', [[[0, 300], [100, 1100], [200, 250], [500, 550]], 100], [0, 1]), ('normal control', [[[400, 450]], 150], []), ('normal control', [[[200, 300]], 150], [])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
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)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: backward walk pruning | [0, 2] | [0, 2] | Passed |
| regression variant: backward walk pruning | [2] | [2] | Passed |
| partial repair probe: backward walk pruning | [1, 4] | [1, 4] | Passed |
| partial repair variant: backward walk pruning | [1, 4] | [1, 4] | Passed |
| boundary control | [1] | [1] | Passed |
| boundary control | [] | [] | Passed |
| normal control | [0] | [0] | Passed |
| normal control | [0, 1, 2, 3] | [0, 1, 2, 3] | Passed |
| normal control | [] | [] | Passed |
SHA-256 / b90509b9f80916f424bc974bb8204e8fdde569162d0027124726327f6f9c3fa6
Verification & scope
A deterministic bounded teaching model with a stipulated toy contract; it does not claim conformance to any subtitle standard. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:49:34.030820+00:00.
Case digest / faa287690b08a90232cce41ad7067190f715737341bcc43b65b9c565120313bb