FA-73181 / Probabilistic sketches / Open access
Weighted reservoir sampling by exponential keys: ties favour the larger id · case 01
Equal keys resolve differently from the contract, making replays disagree.
ROOT CAUSE
The tie-break component stores the id itself, so larger ids sort first under reverse order.
VERIFIED REPAIR
Store the negated id so the smaller id wins ties in descending order.
Unsuccessful approach: Dropping the tie-break collapses equal keys into arbitrary order and loses the ids.
Case contract
Input {k, items} where each item is [id, weight, num, den] with u = num/den in (0,1). Items with weight <= 0 are ineligible. Each eligible item gets key u^(1/weight), compared as ln(u)/weight. Return the ids of the k largest keys, largest first, ties broken by smaller id.
Why this case matters
Weighted sampling without replacement (A-Res) chooses representative traces or accounts in proportion to traffic; key or eligibility mistakes skew the sample.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, ident))
keyed.sort(reverse=True)
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
for label, args, expected in cases[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 |
|---|---|---|---|
| weighted sample 0 k=2 | [-2, -7] | [2, 7] | Failed |
| weighted sample 1 k=3 | [-7, -4, 0] | [7, 4, 0] | Failed |
| weighted sample 2 k=4 | [-7, -6, 0, -1] | [7, 6, 0, 1] | Failed |
| zero and negative weights | [-4, -3] | [4, 3] | Failed |
| equal keys tie | [-7, -3] | [3, 7] | Failed |
| heavier weight wins | [-2] | [2] | Failed |
| light weight small uniform | [-3, -2] | [3, 2] | Failed |
SHA-256 / 4e577b7a1f61b1d4f66077cecd457e8d82e2c5f52de6b521e5c487baaacb13f6
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, 0 * ident))
keyed.sort(reverse=True)
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
for label, args, expected in cases[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 |
|---|---|---|---|
| weighted sample 0 k=2 | [0, 0] | [2, 7] | Failed |
| weighted sample 1 k=3 | [0, 0, 0] | [7, 4, 0] | Failed |
| weighted sample 2 k=4 | [0, 0, 0, 0] | [7, 6, 0, 1] | Failed |
| zero and negative weights | [0, 0] | [4, 3] | Failed |
| equal keys tie | [0, 0] | [3, 7] | Failed |
| heavier weight wins | [0] | [2] | Failed |
| light weight small uniform | [0, 0] | [3, 2] | Failed |
SHA-256 / 0b1e40e76ef993188e624ff8f8b594f97dd3a1ba09d25c36cf2819dce1318130
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
k = x['k']
keyed = []
for ident, wt, num, den in x['items']:
if wt <= 0:
continue
key = math.log(num / den) / wt
keyed.append((key, -ident))
keyed.sort(reverse=True)
return [-negid for key, negid in keyed[:k]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['weighted sample 0 k=2',
{'items': [[0, 0.5, 91, 99],
[1, 1, 42, 99],
[2, 5, 91, 99],
[3, 0.5, 48, 99],
[4, 0.5, 13, 99],
[5, 3, 4, 99],
[6, 3, 63, 99],
[7, 2, 87, 99]],
'k': 2},
[2, 7]],
['weighted sample 1 k=3',
{'items': [[0, 1, 65, 99],
[1, 0.5, 34, 99],
[2, 2, 22, 99],
[3, 1, 43, 99],
[4, 1, 77, 99],
[5, 0.5, 50, 99],
[6, 5, 2, 99],
[7, 3, 76, 99]],
'k': 3},
[7, 4, 0]],
['weighted sample 2 k=4',
{'items': [[0, 1, 74, 99],
[1, 3, 25, 99],
[2, 3, 5, 99],
[3, 0.5, 53, 99],
[4, 1, 61, 99],
[5, 1, 6, 99],
[6, 5, 34, 99],
[7, 3, 56, 99]],
'k': 4},
[7, 6, 0, 1]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 41, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 11, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 21, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 31, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 8, 99],
[1, 5, 66, 99],
[2, 5, 27, 99],
[3, 5, 16, 99],
[4, 0.5, 70, 99],
[5, 3, 4, 99],
[6, 0.5, 5, 99],
[7, 0.5, 32, 99]],
'k': 2},
[1, 2]],
['weighted sample 1 k=3',
{'items': [[0, 0.5, 34, 99],
[1, 0.5, 41, 99],
[2, 5, 97, 99],
[3, 3, 35, 99],
[4, 3, 98, 99],
[5, 3, 86, 99],
[6, 0.5, 26, 99],
[7, 1, 66, 99]],
'k': 3},
[4, 2, 5]],
['weighted sample 2 k=4',
{'items': [[0, 2, 63, 99],
[1, 5, 82, 99],
[2, 0.5, 17, 99],
[3, 3, 50, 99],
[4, 3, 90, 99],
[5, 5, 18, 99],
[6, 1, 85, 99],
[7, 1, 8, 99]],
'k': 4},
[4, 1, 6, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 42, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 12, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 22, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 32, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 2, 38, 99],
[1, 2, 4, 99],
[2, 5, 4, 99],
[3, 5, 92, 99],
[4, 5, 71, 99],
[5, 1, 36, 99],
[6, 2, 24, 99],
[7, 3, 79, 99]],
'k': 2},
[3, 4]],
['weighted sample 1 k=3',
{'items': [[0, 1, 74, 99],
[1, 5, 71, 99],
[2, 3, 25, 99],
[3, 0.5, 97, 99],
[4, 5, 51, 99],
[5, 1, 86, 99],
[6, 1, 82, 99],
[7, 5, 81, 99]],
'k': 3},
[7, 3, 1]],
['weighted sample 2 k=4',
{'items': [[0, 5, 98, 99],
[1, 2, 23, 99],
[2, 5, 17, 99],
[3, 2, 35, 99],
[4, 0.5, 16, 99],
[5, 3, 77, 99],
[6, 3, 56, 99],
[7, 0.5, 87, 99]],
'k': 4},
[0, 5, 6, 7]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 43, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 13, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 23, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 33, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 5, 55, 99],
[1, 2, 83, 99],
[2, 2, 87, 99],
[3, 3, 17, 99],
[4, 1, 74, 99],
[5, 0.5, 82, 99],
[6, 2, 71, 99],
[7, 1, 7, 99]],
'k': 2},
[2, 1]],
['weighted sample 1 k=3',
{'items': [[0, 1, 55, 99],
[1, 1, 50, 99],
[2, 2, 55, 99],
[3, 1, 34, 99],
[4, 1, 58, 99],
[5, 3, 47, 99],
[6, 0.5, 66, 99],
[7, 2, 69, 99]],
'k': 3},
[7, 5, 2]],
['weighted sample 2 k=4',
{'items': [[0, 3, 42, 99],
[1, 0.5, 69, 99],
[2, 3, 41, 99],
[3, 0.5, 42, 99],
[4, 2, 48, 99],
[5, 5, 91, 99],
[6, 5, 74, 99],
[7, 3, 31, 99]],
'k': 4},
[5, 6, 0, 2]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 44, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 14, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 24, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 34, 100], [3, 1, 70, 100]], 'k': 2},
[3, 2]]],
[['weighted sample 0 k=2',
{'items': [[0, 1, 87, 99],
[1, 1, 1, 99],
[2, 2, 6, 99],
[3, 5, 67, 99],
[4, 1, 66, 99],
[5, 3, 45, 99],
[6, 0.5, 25, 99],
[7, 1, 41, 99]],
'k': 2},
[3, 0]],
['weighted sample 1 k=3',
{'items': [[0, 1, 25, 99],
[1, 3, 18, 99],
[2, 5, 2, 99],
[3, 2, 65, 99],
[4, 3, 14, 99],
[5, 3, 89, 99],
[6, 3, 10, 99],
[7, 1, 78, 99]],
'k': 3},
[5, 3, 7]],
['weighted sample 2 k=4',
{'items': [[0, 2, 49, 99],
[1, 2, 66, 99],
[2, 0.5, 24, 99],
[3, 0.5, 88, 99],
[4, 1, 6, 99],
[5, 1, 8, 99],
[6, 1, 93, 99],
[7, 0.5, 41, 99]],
'k': 4},
[6, 1, 3, 0]],
['zero and negative weights',
{'items': [[1, 0, 50, 99], [2, -1, 30, 99], [3, 2, 45, 99], [4, 1, 90, 99]], 'k': 3},
[4, 3]],
['equal keys tie',
{'items': [[7, 2, 49, 100], [3, 2, 49, 100], [5, 1, 15, 100]], 'k': 2},
[3, 7]],
['heavier weight wins', {'items': [[1, 1, 60, 100], [2, 4, 25, 100]], 'k': 1}, [2]],
['light weight small uniform',
{'items': [[1, 0.25, 90, 100], [2, 3, 35, 100], [3, 1, 70, 100]], 'k': 2},
[2, 3]]]]
for label, args, expected in cases[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 |
|---|---|---|---|
| weighted sample 0 k=2 | [2, 7] | [2, 7] | Passed |
| weighted sample 1 k=3 | [7, 4, 0] | [7, 4, 0] | Passed |
| weighted sample 2 k=4 | [7, 6, 0, 1] | [7, 6, 0, 1] | Passed |
| zero and negative weights | [4, 3] | [4, 3] | Passed |
| equal keys tie | [3, 7] | [3, 7] | Passed |
| heavier weight wins | [2] | [2] | Passed |
| light weight small uniform | [3, 2] | [3, 2] | Passed |
SHA-256 / 258ac424db1b6b4e7c70eee463ec0fe659d88534f1c2d31dfd76d70200b5f4ae
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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:48:45.185660+00:00.
Case digest / c6dccbae7617f7dd9e1039376fd29de9e2a1e4cbfa9e0fb4a7e8650ff6f94cc4