{"abstract":"Keys with equal estimates churn the table, and the reported leader set depends on arrival order.","category":"Probabilistic sketches","checks":10,"contract":"Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.","evaluation_group":"w2-probabilistic_sketches-cms-topk-tracker","failed_approach":"Comparing against the oldest tracked entry instead of the minimum rejects legitimate replacements.","family":"w2-probabilistic_sketches-cms-topk-tracker-strict-replace","id":"FA-73326","implementations":{"attempt":{"sha256":"802a14da519ff4cd6c8066d76ebe072775a98396c8c484143c38bac1ca203876","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    w = x['w']\n    k = x['k']\n    A = [1103515245, 1812433253, 1664525017]\n    B = [12345, 1013904223, 7]\n    P = 2147483647\n    t = [[0] * w for _ in range(3)]\n    top = {}\n    for key, c in x['stream']:\n        for r in range(3):\n            t[r][(A[r] * key + B[r]) % P % w] += c\n        est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))\n        if key in top:\n            top[key] = est\n        elif len(top) < k:\n            top[key] = est\n        else:\n            victim = min(top, key=lambda q: (top[q], q))\n            if est > top[next(iter(top))]:\n                del top[victim]\n                top[key] = est\n    return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[7, 4],\n               [1, 3],\n               [2, 3],\n               [3, 2],\n               [5, 2],\n               [3, 1],\n               [3, 4],\n               [5, 3],\n               [4, 1],\n               [5, 3],\n               [4, 3],\n               [3, 1],\n               [4, 4],\n               [6, 4],\n               [6, 4]],\n    'w': 8},\n   [[3, 8], [5, 8]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 2],\n               [1, 3],\n               [5, 4],\n               [6, 2],\n               [6, 4],\n               [5, 3],\n               [2, 1],\n               [4, 2],\n               [3, 2],\n               [5, 3],\n               [2, 3],\n               [2, 1],\n               [1, 2],\n               [5, 2],\n               [7, 4]],\n    'w': 6},\n   [[5, 12], [6, 6], [7, 6]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 1],\n               [3, 1],\n               [3, 2],\n               [5, 1],\n               [1, 2],\n               [6, 1],\n               [4, 2],\n               [3, 4],\n               [6, 3],\n               [4, 1],\n               [3, 4],\n               [1, 3],\n               [6, 1],\n               [7, 1]],\n    'w': 10},\n   [[3, 15], [6, 6], [1, 5]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[3, 4],\n               [5, 4],\n               [6, 2],\n               [6, 3],\n               [3, 1],\n               [3, 3],\n               [4, 1],\n               [5, 1],\n               [7, 1],\n               [6, 2],\n               [6, 1],\n               [6, 1],\n               [7, 1],\n               [3, 3],\n               [3, 2]],\n    'w': 5},\n   [[3, 13], [6, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},\n   [[1, 9], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},\n   [[7, 6], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 1],\n               [7, 1],\n               [6, 3],\n               [6, 1],\n               [2, 4],\n               [2, 2],\n               [2, 4],\n               [5, 4],\n               [4, 4],\n               [4, 2],\n               [5, 2],\n               [2, 4],\n               [2, 4],\n               [5, 1],\n               [6, 3]],\n    'w': 8},\n   [[2, 19], [4, 9]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 4],\n               [1, 3],\n               [6, 1],\n               [5, 3],\n               [2, 3],\n               [5, 4],\n               [5, 3],\n               [3, 4],\n               [5, 1],\n               [2, 4],\n               [7, 1],\n               [6, 4],\n               [2, 2],\n               [3, 4],\n               [5, 3],\n               [5, 3]],\n    'w': 6},\n   [[5, 17], [2, 9], [3, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [5, 3],\n               [4, 1],\n               [3, 4],\n               [6, 1],\n               [3, 1],\n               [6, 3],\n               [7, 3],\n               [5, 3],\n               [2, 1],\n               [3, 2],\n               [7, 3],\n               [2, 1],\n               [3, 2],\n               [3, 1],\n               [2, 4]],\n    'w': 10},\n   [[3, 13], [5, 6], [7, 6]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[7, 2],\n               [4, 4],\n               [2, 4],\n               [4, 4],\n               [2, 4],\n               [5, 2],\n               [2, 3],\n               [4, 4],\n               [1, 1],\n               [4, 3],\n               [6, 1],\n               [2, 3],\n               [1, 1],\n               [2, 3],\n               [6, 2],\n               [2, 4]],\n    'w': 5},\n   [[2, 21], [4, 16]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},\n   [[1, 10], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},\n   [[7, 7], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [1, 1],\n               [3, 4],\n               [4, 3],\n               [3, 2],\n               [1, 4],\n               [1, 3],\n               [7, 4],\n               [4, 3],\n               [5, 3],\n               [5, 4],\n               [2, 2],\n               [1, 3],\n               [7, 4],\n               [3, 2],\n               [5, 2],\n               [5, 1]],\n    'w': 8},\n   [[1, 11], [5, 10]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[5, 2],\n               [2, 4],\n               [5, 2],\n               [6, 3],\n               [7, 2],\n               [4, 3],\n               [2, 4],\n               [7, 1],\n               [4, 4],\n               [7, 1],\n               [4, 4],\n               [4, 3],\n               [5, 4],\n               [5, 4],\n               [6, 4],\n               [3, 3],\n               [6, 4]],\n    'w': 6},\n   [[4, 14], [5, 12], [6, 11]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [3, 3],\n               [2, 1],\n               [6, 4],\n               [1, 2],\n               [6, 3],\n               [3, 3],\n               [5, 1],\n               [6, 4],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [3, 3],\n               [2, 1],\n               [2, 4],\n               [4, 2],\n               [4, 1]],\n    'w': 10},\n   [[3, 13], [6, 11], [2, 8]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[5, 1],\n               [5, 4],\n               [5, 3],\n               [5, 3],\n               [5, 1],\n               [3, 4],\n               [4, 3],\n               [7, 1],\n               [7, 4],\n               [2, 2],\n               [4, 1],\n               [4, 4],\n               [5, 1],\n               [6, 2],\n               [5, 2],\n               [1, 1],\n               [6, 3]],\n    'w': 5},\n   [[5, 17], [6, 9]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},\n   [[1, 11], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},\n   [[7, 8], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [6, 3],\n               [4, 1],\n               [7, 3],\n               [5, 3],\n               [3, 2],\n               [2, 4],\n               [2, 4],\n               [3, 3],\n               [1, 1],\n               [1, 1],\n               [4, 4],\n               [2, 1],\n               [5, 4],\n               [1, 4],\n               [4, 1],\n               [1, 2],\n               [2, 3]],\n    'w': 8},\n   [[1, 12], [2, 12]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [2, 3],\n               [4, 2],\n               [5, 2],\n               [2, 1],\n               [7, 4],\n               [6, 1],\n               [6, 2],\n               [4, 4],\n               [2, 3],\n               [4, 2],\n               [7, 4],\n               [5, 2],\n               [4, 3],\n               [6, 4],\n               [2, 3],\n               [6, 3],\n               [6, 4]],\n    'w': 6},\n   [[6, 14], [4, 11], [2, 10]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 3],\n               [3, 2],\n               [2, 1],\n               [2, 2],\n               [2, 3],\n               [3, 4],\n               [7, 2],\n               [2, 2],\n               [5, 3],\n               [7, 3],\n               [7, 2],\n               [6, 4],\n               [6, 1],\n               [7, 3],\n               [6, 2],\n               [6, 1],\n               [5, 1]],\n    'w': 10},\n   [[6, 11], [3, 10], [7, 10]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [3, 3],\n               [5, 3],\n               [3, 2],\n               [6, 4],\n               [1, 1],\n               [2, 4],\n               [2, 4],\n               [7, 4],\n               [7, 4],\n               [3, 1],\n               [7, 2],\n               [2, 4],\n               [5, 1],\n               [6, 2],\n               [1, 2],\n               [3, 2],\n               [4, 3]],\n    'w': 5},\n   [[2, 15], [3, 14]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},\n   [[1, 12], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},\n   [[12, 4], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},\n   [[7, 9], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 4],\n               [7, 1],\n               [1, 2],\n               [6, 3],\n               [3, 4],\n               [7, 3],\n               [5, 2],\n               [7, 3],\n               [4, 3],\n               [4, 4],\n               [7, 3],\n               [2, 4],\n               [2, 3],\n               [5, 2],\n               [3, 1],\n               [1, 2],\n               [1, 4],\n               [7, 3]],\n    'w': 8},\n   [[7, 13], [2, 11]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 3],\n               [3, 2],\n               [2, 4],\n               [3, 4],\n               [4, 3],\n               [4, 1],\n               [7, 1],\n               [5, 2],\n               [1, 1],\n               [4, 2],\n               [2, 4],\n               [6, 1],\n               [7, 4],\n               [1, 4],\n               [2, 3],\n               [5, 3],\n               [6, 4],\n               [3, 2],\n               [3, 3]],\n    'w': 6},\n   [[2, 11], [3, 11], [7, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[4, 1],\n               [6, 3],\n               [6, 4],\n               [7, 3],\n               [2, 1],\n               [7, 3],\n               [7, 3],\n               [1, 3],\n               [3, 1],\n               [7, 4],\n               [5, 2],\n               [4, 1],\n               [7, 4],\n               [1, 1],\n               [5, 2],\n               [2, 4],\n               [7, 2],\n               [2, 4],\n               [7, 4]],\n    'w': 10},\n   [[7, 23], [2, 9], [6, 7]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[6, 4],\n               [6, 2],\n               [1, 3],\n               [4, 3],\n               [4, 2],\n               [3, 2],\n               [3, 4],\n               [5, 3],\n               [4, 2],\n               [3, 1],\n               [1, 2],\n               [2, 1],\n               [7, 4],\n               [4, 3],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [1, 2],\n               [7, 1]],\n    'w': 5},\n   [[4, 13], [5, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},\n   [[1, 13], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},\n   [[12, 5], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},\n   [[7, 10], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},\n   [[8, 7], [2, 6]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"9d75ee3ba76b6688ae10f549e39c06fe66d2bcaaa88ab071566e16ec55f24a5b","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    w = x['w']\n    k = x['k']\n    A = [1103515245, 1812433253, 1664525017]\n    B = [12345, 1013904223, 7]\n    P = 2147483647\n    t = [[0] * w for _ in range(3)]\n    top = {}\n    for key, c in x['stream']:\n        for r in range(3):\n            t[r][(A[r] * key + B[r]) % P % w] += c\n        est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))\n        if key in top:\n            top[key] = est\n        elif len(top) < k:\n            top[key] = est\n        else:\n            victim = min(top, key=lambda q: (top[q], q))\n            if est >= top[victim]:\n                del top[victim]\n                top[key] = est\n    return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[7, 4],\n               [1, 3],\n               [2, 3],\n               [3, 2],\n               [5, 2],\n               [3, 1],\n               [3, 4],\n               [5, 3],\n               [4, 1],\n               [5, 3],\n               [4, 3],\n               [3, 1],\n               [4, 4],\n               [6, 4],\n               [6, 4]],\n    'w': 8},\n   [[3, 8], [5, 8]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 2],\n               [1, 3],\n               [5, 4],\n               [6, 2],\n               [6, 4],\n               [5, 3],\n               [2, 1],\n               [4, 2],\n               [3, 2],\n               [5, 3],\n               [2, 3],\n               [2, 1],\n               [1, 2],\n               [5, 2],\n               [7, 4]],\n    'w': 6},\n   [[5, 12], [6, 6], [7, 6]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 1],\n               [3, 1],\n               [3, 2],\n               [5, 1],\n               [1, 2],\n               [6, 1],\n               [4, 2],\n               [3, 4],\n               [6, 3],\n               [4, 1],\n               [3, 4],\n               [1, 3],\n               [6, 1],\n               [7, 1]],\n    'w': 10},\n   [[3, 15], [6, 6], [1, 5]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[3, 4],\n               [5, 4],\n               [6, 2],\n               [6, 3],\n               [3, 1],\n               [3, 3],\n               [4, 1],\n               [5, 1],\n               [7, 1],\n               [6, 2],\n               [6, 1],\n               [6, 1],\n               [7, 1],\n               [3, 3],\n               [3, 2]],\n    'w': 5},\n   [[3, 13], [6, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},\n   [[1, 9], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},\n   [[7, 6], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 1],\n               [7, 1],\n               [6, 3],\n               [6, 1],\n               [2, 4],\n               [2, 2],\n               [2, 4],\n               [5, 4],\n               [4, 4],\n               [4, 2],\n               [5, 2],\n               [2, 4],\n               [2, 4],\n               [5, 1],\n               [6, 3]],\n    'w': 8},\n   [[2, 19], [4, 9]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 4],\n               [1, 3],\n               [6, 1],\n               [5, 3],\n               [2, 3],\n               [5, 4],\n               [5, 3],\n               [3, 4],\n               [5, 1],\n               [2, 4],\n               [7, 1],\n               [6, 4],\n               [2, 2],\n               [3, 4],\n               [5, 3],\n               [5, 3]],\n    'w': 6},\n   [[5, 17], [2, 9], [3, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [5, 3],\n               [4, 1],\n               [3, 4],\n               [6, 1],\n               [3, 1],\n               [6, 3],\n               [7, 3],\n               [5, 3],\n               [2, 1],\n               [3, 2],\n               [7, 3],\n               [2, 1],\n               [3, 2],\n               [3, 1],\n               [2, 4]],\n    'w': 10},\n   [[3, 13], [5, 6], [7, 6]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[7, 2],\n               [4, 4],\n               [2, 4],\n               [4, 4],\n               [2, 4],\n               [5, 2],\n               [2, 3],\n               [4, 4],\n               [1, 1],\n               [4, 3],\n               [6, 1],\n               [2, 3],\n               [1, 1],\n               [2, 3],\n               [6, 2],\n               [2, 4]],\n    'w': 5},\n   [[2, 21], [4, 16]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},\n   [[1, 10], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},\n   [[7, 7], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [1, 1],\n               [3, 4],\n               [4, 3],\n               [3, 2],\n               [1, 4],\n               [1, 3],\n               [7, 4],\n               [4, 3],\n               [5, 3],\n               [5, 4],\n               [2, 2],\n               [1, 3],\n               [7, 4],\n               [3, 2],\n               [5, 2],\n               [5, 1]],\n    'w': 8},\n   [[1, 11], [5, 10]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[5, 2],\n               [2, 4],\n               [5, 2],\n               [6, 3],\n               [7, 2],\n               [4, 3],\n               [2, 4],\n               [7, 1],\n               [4, 4],\n               [7, 1],\n               [4, 4],\n               [4, 3],\n               [5, 4],\n               [5, 4],\n               [6, 4],\n               [3, 3],\n               [6, 4]],\n    'w': 6},\n   [[4, 14], [5, 12], [6, 11]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [3, 3],\n               [2, 1],\n               [6, 4],\n               [1, 2],\n               [6, 3],\n               [3, 3],\n               [5, 1],\n               [6, 4],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [3, 3],\n               [2, 1],\n               [2, 4],\n               [4, 2],\n               [4, 1]],\n    'w': 10},\n   [[3, 13], [6, 11], [2, 8]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[5, 1],\n               [5, 4],\n               [5, 3],\n               [5, 3],\n               [5, 1],\n               [3, 4],\n               [4, 3],\n               [7, 1],\n               [7, 4],\n               [2, 2],\n               [4, 1],\n               [4, 4],\n               [5, 1],\n               [6, 2],\n               [5, 2],\n               [1, 1],\n               [6, 3]],\n    'w': 5},\n   [[5, 17], [6, 9]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},\n   [[1, 11], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},\n   [[7, 8], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [6, 3],\n               [4, 1],\n               [7, 3],\n               [5, 3],\n               [3, 2],\n               [2, 4],\n               [2, 4],\n               [3, 3],\n               [1, 1],\n               [1, 1],\n               [4, 4],\n               [2, 1],\n               [5, 4],\n               [1, 4],\n               [4, 1],\n               [1, 2],\n               [2, 3]],\n    'w': 8},\n   [[1, 12], [2, 12]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [2, 3],\n               [4, 2],\n               [5, 2],\n               [2, 1],\n               [7, 4],\n               [6, 1],\n               [6, 2],\n               [4, 4],\n               [2, 3],\n               [4, 2],\n               [7, 4],\n               [5, 2],\n               [4, 3],\n               [6, 4],\n               [2, 3],\n               [6, 3],\n               [6, 4]],\n    'w': 6},\n   [[6, 14], [4, 11], [2, 10]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 3],\n               [3, 2],\n               [2, 1],\n               [2, 2],\n               [2, 3],\n               [3, 4],\n               [7, 2],\n               [2, 2],\n               [5, 3],\n               [7, 3],\n               [7, 2],\n               [6, 4],\n               [6, 1],\n               [7, 3],\n               [6, 2],\n               [6, 1],\n               [5, 1]],\n    'w': 10},\n   [[6, 11], [3, 10], [7, 10]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [3, 3],\n               [5, 3],\n               [3, 2],\n               [6, 4],\n               [1, 1],\n               [2, 4],\n               [2, 4],\n               [7, 4],\n               [7, 4],\n               [3, 1],\n               [7, 2],\n               [2, 4],\n               [5, 1],\n               [6, 2],\n               [1, 2],\n               [3, 2],\n               [4, 3]],\n    'w': 5},\n   [[2, 15], [3, 14]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},\n   [[1, 12], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},\n   [[12, 4], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},\n   [[7, 9], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 4],\n               [7, 1],\n               [1, 2],\n               [6, 3],\n               [3, 4],\n               [7, 3],\n               [5, 2],\n               [7, 3],\n               [4, 3],\n               [4, 4],\n               [7, 3],\n               [2, 4],\n               [2, 3],\n               [5, 2],\n               [3, 1],\n               [1, 2],\n               [1, 4],\n               [7, 3]],\n    'w': 8},\n   [[7, 13], [2, 11]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 3],\n               [3, 2],\n               [2, 4],\n               [3, 4],\n               [4, 3],\n               [4, 1],\n               [7, 1],\n               [5, 2],\n               [1, 1],\n               [4, 2],\n               [2, 4],\n               [6, 1],\n               [7, 4],\n               [1, 4],\n               [2, 3],\n               [5, 3],\n               [6, 4],\n               [3, 2],\n               [3, 3]],\n    'w': 6},\n   [[2, 11], [3, 11], [7, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[4, 1],\n               [6, 3],\n               [6, 4],\n               [7, 3],\n               [2, 1],\n               [7, 3],\n               [7, 3],\n               [1, 3],\n               [3, 1],\n               [7, 4],\n               [5, 2],\n               [4, 1],\n               [7, 4],\n               [1, 1],\n               [5, 2],\n               [2, 4],\n               [7, 2],\n               [2, 4],\n               [7, 4]],\n    'w': 10},\n   [[7, 23], [2, 9], [6, 7]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[6, 4],\n               [6, 2],\n               [1, 3],\n               [4, 3],\n               [4, 2],\n               [3, 2],\n               [3, 4],\n               [5, 3],\n               [4, 2],\n               [3, 1],\n               [1, 2],\n               [2, 1],\n               [7, 4],\n               [4, 3],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [1, 2],\n               [7, 1]],\n    'w': 5},\n   [[4, 13], [5, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},\n   [[1, 13], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},\n   [[12, 5], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},\n   [[7, 10], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},\n   [[8, 7], [2, 6]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"34a73195594a7665da7339509ce989854344cc08c60290b7354c7bf37860177a","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    w = x['w']\n    k = x['k']\n    A = [1103515245, 1812433253, 1664525017]\n    B = [12345, 1013904223, 7]\n    P = 2147483647\n    t = [[0] * w for _ in range(3)]\n    top = {}\n    for key, c in x['stream']:\n        for r in range(3):\n            t[r][(A[r] * key + B[r]) % P % w] += c\n        est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))\n        if key in top:\n            top[key] = est\n        elif len(top) < k:\n            top[key] = est\n        else:\n            victim = min(top, key=lambda q: (top[q], q))\n            if est > top[victim]:\n                del top[victim]\n                top[key] = est\n    return sorted([[q, v] for q, v in top.items()], key=lambda row: (-row[1], row[0]))\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[7, 4],\n               [1, 3],\n               [2, 3],\n               [3, 2],\n               [5, 2],\n               [3, 1],\n               [3, 4],\n               [5, 3],\n               [4, 1],\n               [5, 3],\n               [4, 3],\n               [3, 1],\n               [4, 4],\n               [6, 4],\n               [6, 4]],\n    'w': 8},\n   [[3, 8], [5, 8]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 2],\n               [1, 3],\n               [5, 4],\n               [6, 2],\n               [6, 4],\n               [5, 3],\n               [2, 1],\n               [4, 2],\n               [3, 2],\n               [5, 3],\n               [2, 3],\n               [2, 1],\n               [1, 2],\n               [5, 2],\n               [7, 4]],\n    'w': 6},\n   [[5, 12], [6, 6], [7, 6]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 1],\n               [3, 1],\n               [3, 2],\n               [5, 1],\n               [1, 2],\n               [6, 1],\n               [4, 2],\n               [3, 4],\n               [6, 3],\n               [4, 1],\n               [3, 4],\n               [1, 3],\n               [6, 1],\n               [7, 1]],\n    'w': 10},\n   [[3, 15], [6, 6], [1, 5]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[3, 4],\n               [5, 4],\n               [6, 2],\n               [6, 3],\n               [3, 1],\n               [3, 3],\n               [4, 1],\n               [5, 1],\n               [7, 1],\n               [6, 2],\n               [6, 1],\n               [6, 1],\n               [7, 1],\n               [3, 3],\n               [3, 2]],\n    'w': 5},\n   [[3, 13], [6, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 2]], 'w': 16},\n   [[1, 9], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 2]], 'w': 1}, [[1, 7], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 6]], 'w': 16},\n   [[7, 6], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 3]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 1],\n               [7, 1],\n               [6, 3],\n               [6, 1],\n               [2, 4],\n               [2, 2],\n               [2, 4],\n               [5, 4],\n               [4, 4],\n               [4, 2],\n               [5, 2],\n               [2, 4],\n               [2, 4],\n               [5, 1],\n               [6, 3]],\n    'w': 8},\n   [[2, 19], [4, 9]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 4],\n               [1, 3],\n               [6, 1],\n               [5, 3],\n               [2, 3],\n               [5, 4],\n               [5, 3],\n               [3, 4],\n               [5, 1],\n               [2, 4],\n               [7, 1],\n               [6, 4],\n               [2, 2],\n               [3, 4],\n               [5, 3],\n               [5, 3]],\n    'w': 6},\n   [[5, 17], [2, 9], [3, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [5, 3],\n               [4, 1],\n               [3, 4],\n               [6, 1],\n               [3, 1],\n               [6, 3],\n               [7, 3],\n               [5, 3],\n               [2, 1],\n               [3, 2],\n               [7, 3],\n               [2, 1],\n               [3, 2],\n               [3, 1],\n               [2, 4]],\n    'w': 10},\n   [[3, 13], [5, 6], [7, 6]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[7, 2],\n               [4, 4],\n               [2, 4],\n               [4, 4],\n               [2, 4],\n               [5, 2],\n               [2, 3],\n               [4, 4],\n               [1, 1],\n               [4, 3],\n               [6, 1],\n               [2, 3],\n               [1, 1],\n               [2, 3],\n               [6, 2],\n               [2, 4]],\n    'w': 5},\n   [[2, 21], [4, 16]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 3]], 'w': 16},\n   [[1, 10], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 2]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 3]], 'w': 1}, [[1, 8], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 7]], 'w': 16},\n   [[7, 7], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 4]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [1, 1],\n               [3, 4],\n               [4, 3],\n               [3, 2],\n               [1, 4],\n               [1, 3],\n               [7, 4],\n               [4, 3],\n               [5, 3],\n               [5, 4],\n               [2, 2],\n               [1, 3],\n               [7, 4],\n               [3, 2],\n               [5, 2],\n               [5, 1]],\n    'w': 8},\n   [[1, 11], [5, 10]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[5, 2],\n               [2, 4],\n               [5, 2],\n               [6, 3],\n               [7, 2],\n               [4, 3],\n               [2, 4],\n               [7, 1],\n               [4, 4],\n               [7, 1],\n               [4, 4],\n               [4, 3],\n               [5, 4],\n               [5, 4],\n               [6, 4],\n               [3, 3],\n               [6, 4]],\n    'w': 6},\n   [[4, 14], [5, 12], [6, 11]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [3, 3],\n               [2, 1],\n               [6, 4],\n               [1, 2],\n               [6, 3],\n               [3, 3],\n               [5, 1],\n               [6, 4],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [3, 3],\n               [2, 1],\n               [2, 4],\n               [4, 2],\n               [4, 1]],\n    'w': 10},\n   [[3, 13], [6, 11], [2, 8]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[5, 1],\n               [5, 4],\n               [5, 3],\n               [5, 3],\n               [5, 1],\n               [3, 4],\n               [4, 3],\n               [7, 1],\n               [7, 4],\n               [2, 2],\n               [4, 1],\n               [4, 4],\n               [5, 1],\n               [6, 2],\n               [5, 2],\n               [1, 1],\n               [6, 3]],\n    'w': 5},\n   [[5, 17], [6, 9]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 4]], 'w': 16},\n   [[1, 11], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 3]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 4]], 'w': 1}, [[1, 9], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 8]], 'w': 16},\n   [[7, 8], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 5]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [6, 3],\n               [4, 1],\n               [7, 3],\n               [5, 3],\n               [3, 2],\n               [2, 4],\n               [2, 4],\n               [3, 3],\n               [1, 1],\n               [1, 1],\n               [4, 4],\n               [2, 1],\n               [5, 4],\n               [1, 4],\n               [4, 1],\n               [1, 2],\n               [2, 3]],\n    'w': 8},\n   [[1, 12], [2, 12]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[3, 3],\n               [2, 3],\n               [4, 2],\n               [5, 2],\n               [2, 1],\n               [7, 4],\n               [6, 1],\n               [6, 2],\n               [4, 4],\n               [2, 3],\n               [4, 2],\n               [7, 4],\n               [5, 2],\n               [4, 3],\n               [6, 4],\n               [2, 3],\n               [6, 3],\n               [6, 4]],\n    'w': 6},\n   [[6, 14], [4, 11], [2, 10]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[3, 4],\n               [6, 3],\n               [3, 2],\n               [2, 1],\n               [2, 2],\n               [2, 3],\n               [3, 4],\n               [7, 2],\n               [2, 2],\n               [5, 3],\n               [7, 3],\n               [7, 2],\n               [6, 4],\n               [6, 1],\n               [7, 3],\n               [6, 2],\n               [6, 1],\n               [5, 1]],\n    'w': 10},\n   [[6, 11], [3, 10], [7, 10]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[1, 4],\n               [3, 3],\n               [5, 3],\n               [3, 2],\n               [6, 4],\n               [1, 1],\n               [2, 4],\n               [2, 4],\n               [7, 4],\n               [7, 4],\n               [3, 1],\n               [7, 2],\n               [2, 4],\n               [5, 1],\n               [6, 2],\n               [1, 2],\n               [3, 2],\n               [4, 3]],\n    'w': 5},\n   [[2, 15], [3, 14]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 5]], 'w': 16},\n   [[1, 12], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 4]], 'w': 16},\n   [[12, 4], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 0]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5]], 'w': 1}, [[1, 10], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 9]], 'w': 16},\n   [[7, 9], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 6]], 'w': 16},\n   [[1, 6], [2, 6]]]],\n [['stream 0 w=8 k=2',\n   {'k': 2,\n    'stream': [[4, 3],\n               [2, 4],\n               [7, 1],\n               [1, 2],\n               [6, 3],\n               [3, 4],\n               [7, 3],\n               [5, 2],\n               [7, 3],\n               [4, 3],\n               [4, 4],\n               [7, 3],\n               [2, 4],\n               [2, 3],\n               [5, 2],\n               [3, 1],\n               [1, 2],\n               [1, 4],\n               [7, 3]],\n    'w': 8},\n   [[7, 13], [2, 11]]],\n  ['stream 1 w=6 k=3',\n   {'k': 3,\n    'stream': [[7, 3],\n               [3, 2],\n               [2, 4],\n               [3, 4],\n               [4, 3],\n               [4, 1],\n               [7, 1],\n               [5, 2],\n               [1, 1],\n               [4, 2],\n               [2, 4],\n               [6, 1],\n               [7, 4],\n               [1, 4],\n               [2, 3],\n               [5, 3],\n               [6, 4],\n               [3, 2],\n               [3, 3]],\n    'w': 6},\n   [[2, 11], [3, 11], [7, 8]]],\n  ['stream 2 w=10 k=3',\n   {'k': 3,\n    'stream': [[4, 1],\n               [6, 3],\n               [6, 4],\n               [7, 3],\n               [2, 1],\n               [7, 3],\n               [7, 3],\n               [1, 3],\n               [3, 1],\n               [7, 4],\n               [5, 2],\n               [4, 1],\n               [7, 4],\n               [1, 1],\n               [5, 2],\n               [2, 4],\n               [7, 2],\n               [2, 4],\n               [7, 4]],\n    'w': 10},\n   [[7, 23], [2, 9], [6, 7]]],\n  ['stream 3 w=5 k=2',\n   {'k': 2,\n    'stream': [[6, 4],\n               [6, 2],\n               [1, 3],\n               [4, 3],\n               [4, 2],\n               [3, 2],\n               [3, 4],\n               [5, 3],\n               [4, 2],\n               [3, 1],\n               [1, 2],\n               [2, 1],\n               [7, 4],\n               [4, 3],\n               [2, 2],\n               [7, 1],\n               [5, 4],\n               [1, 2],\n               [7, 1]],\n    'w': 5},\n   [[4, 13], [5, 10]]],\n  ['hit refreshes estimate',\n   {'k': 2, 'stream': [[1, 2], [2, 3], [1, 5], [3, 4], [1, 6]], 'w': 16},\n   [[1, 13], [3, 4]]],\n  ['tie with minimum',\n   {'k': 2, 'stream': [[9, 3], [4, 3], [5, 2], [7, 3], [12, 5]], 'w': 16},\n   [[12, 5], [9, 3]]],\n  ['equal newcomer keeps incumbent',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 3], [11, 1]], 'w': 16},\n   [[4, 3], [9, 3]]],\n  ['colliding refresh', {'k': 2, 'stream': [[1, 2], [2, 3], [1, 6]], 'w': 1}, [[1, 11], [2, 5]]],\n  ['tie among minima eviction',\n   {'k': 2, 'stream': [[4, 3], [9, 3], [7, 10]], 'w': 16},\n   [[7, 10], [9, 3]]],\n  ['newcomer below minimum',\n   {'k': 2, 'stream': [[1, 6], [2, 5], [3, 1], [2, 1], [8, 7]], 'w': 16},\n   [[8, 7], [2, 6]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-cms-topk-tracker-strict-replace","generated_at":"2026-09-29T14:48:46.567514+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Streaming top-k dashboards pair a frequency sketch with a small candidate table; stale scores or loose replacement rules make the reported leaders wrong.","repair":"Replace only when the newcomer estimate is strictly larger.","root_cause":"Replacement fires on ties with the minimum score.","sha256":"2406e89ed6363c58d572130244b49d8d0aba4e4e5c20e2f029d659417659cc2d","title":"Top-k tracking over a Count-Min sketch: equal estimate replaces the minimum · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":43.693,"exit_code":1,"observations":[{"actual":[[3,8],[5,8]],"check":"stream 0 w=8 k=2","expected":[[3,8],[5,8]],"passed":true},{"actual":[[5,12],[6,6],[2,5]],"check":"stream 1 w=6 k=3","expected":[[5,12],[6,6],[7,6]],"passed":false},{"actual":[[3,15],[6,6],[5,1]],"check":"stream 2 w=10 k=3","expected":[[3,15],[6,6],[1,5]],"passed":false},{"actual":[[3,13],[6,10]],"check":"stream 3 w=5 k=2","expected":[[3,13],[6,10]],"passed":true},{"actual":[[1,9],[2,3]],"check":"hit refreshes estimate","expected":[[1,9],[3,4]],"passed":false},{"actual":[[4,3],[9,3]],"check":"tie with minimum","expected":[[4,3],[9,3]],"passed":true},{"actual":[[4,3],[9,3]],"check":"equal newcomer keeps incumbent","expected":[[4,3],[9,3]],"passed":true},{"actual":[[1,7],[2,5]],"check":"colliding refresh","expected":[[1,7],[2,5]],"passed":true},{"actual":[[7,6],[9,3]],"check":"tie among minima eviction","expected":[[7,6],[9,3]],"passed":true},{"actual":[[1,6],[2,6]],"check":"newcomer below minimum","expected":[[1,6],[2,6]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"stream 0 w=8 k=2\", \"actual\": [[3, 8], [5, 8]], \"expected\": [[3, 8], [5, 8]], \"passed\": true}, {\"check\": \"stream 1 w=6 k=3\", \"actual\": [[5, 12], [6, 6], [2, 5]], \"expected\": [[5, 12], [6, 6], [7, 6]], \"passed\": false}, {\"check\": \"stream 2 w=10 k=3\", \"actual\": [[3, 15], [6, 6], [5, 1]], \"expected\": [[3, 15], [6, 6], [1, 5]], \"passed\": false}, {\"check\": \"stream 3 w=5 k=2\", \"actual\": [[3, 13], [6, 10]], \"expected\": [[3, 13], [6, 10]], \"passed\": true}, {\"check\": \"hit refreshes estimate\", \"actual\": [[1, 9], [2, 3]], \"expected\": [[1, 9], [3, 4]], \"passed\": false}, {\"check\": \"tie with minimum\", \"actual\": [[4, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": true}, {\"check\": \"equal newcomer keeps incumbent\", \"actual\": [[4, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": true}, {\"check\": \"colliding refresh\", \"actual\": [[1, 7], [2, 5]], \"expected\": [[1, 7], [2, 5]], \"passed\": true}, {\"check\": \"tie among minima eviction\", \"actual\": [[7, 6], [9, 3]], \"expected\": [[7, 6], [9, 3]], \"passed\": true}, {\"check\": \"newcomer below minimum\", \"actual\": [[1, 6], [2, 6]], \"expected\": [[1, 6], [2, 6]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.281,"exit_code":1,"observations":[{"actual":[[5,8],[6,8]],"check":"stream 0 w=8 k=2","expected":[[3,8],[5,8]],"passed":false},{"actual":[[5,12],[6,6],[7,6]],"check":"stream 1 w=6 k=3","expected":[[5,12],[6,6],[7,6]],"passed":true},{"actual":[[3,15],[6,6],[1,5]],"check":"stream 2 w=10 k=3","expected":[[3,15],[6,6],[1,5]],"passed":true},{"actual":[[3,13],[6,10]],"check":"stream 3 w=5 k=2","expected":[[3,13],[6,10]],"passed":true},{"actual":[[1,9],[3,4]],"check":"hit refreshes estimate","expected":[[1,9],[3,4]],"passed":true},{"actual":[[7,3],[9,3]],"check":"tie with minimum","expected":[[4,3],[9,3]],"passed":false},{"actual":[[7,3],[9,3]],"check":"equal newcomer keeps incumbent","expected":[[4,3],[9,3]],"passed":false},{"actual":[[1,7],[2,5]],"check":"colliding refresh","expected":[[1,7],[2,5]],"passed":true},{"actual":[[7,6],[9,3]],"check":"tie among minima eviction","expected":[[7,6],[9,3]],"passed":true},{"actual":[[1,6],[2,6]],"check":"newcomer below minimum","expected":[[1,6],[2,6]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"stream 0 w=8 k=2\", \"actual\": [[5, 8], [6, 8]], \"expected\": [[3, 8], [5, 8]], \"passed\": false}, {\"check\": \"stream 1 w=6 k=3\", \"actual\": [[5, 12], [6, 6], [7, 6]], \"expected\": [[5, 12], [6, 6], [7, 6]], \"passed\": true}, {\"check\": \"stream 2 w=10 k=3\", \"actual\": [[3, 15], [6, 6], [1, 5]], \"expected\": [[3, 15], [6, 6], [1, 5]], \"passed\": true}, {\"check\": \"stream 3 w=5 k=2\", \"actual\": [[3, 13], [6, 10]], \"expected\": [[3, 13], [6, 10]], \"passed\": true}, {\"check\": \"hit refreshes estimate\", \"actual\": [[1, 9], [3, 4]], \"expected\": [[1, 9], [3, 4]], \"passed\": true}, {\"check\": \"tie with minimum\", \"actual\": [[7, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": false}, {\"check\": \"equal newcomer keeps incumbent\", \"actual\": [[7, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": false}, {\"check\": \"colliding refresh\", \"actual\": [[1, 7], [2, 5]], \"expected\": [[1, 7], [2, 5]], \"passed\": true}, {\"check\": \"tie among minima eviction\", \"actual\": [[7, 6], [9, 3]], \"expected\": [[7, 6], [9, 3]], \"passed\": true}, {\"check\": \"newcomer below minimum\", \"actual\": [[1, 6], [2, 6]], \"expected\": [[1, 6], [2, 6]], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":41.569,"exit_code":0,"observations":[{"actual":[[3,8],[5,8]],"check":"stream 0 w=8 k=2","expected":[[3,8],[5,8]],"passed":true},{"actual":[[5,12],[6,6],[7,6]],"check":"stream 1 w=6 k=3","expected":[[5,12],[6,6],[7,6]],"passed":true},{"actual":[[3,15],[6,6],[1,5]],"check":"stream 2 w=10 k=3","expected":[[3,15],[6,6],[1,5]],"passed":true},{"actual":[[3,13],[6,10]],"check":"stream 3 w=5 k=2","expected":[[3,13],[6,10]],"passed":true},{"actual":[[1,9],[3,4]],"check":"hit refreshes estimate","expected":[[1,9],[3,4]],"passed":true},{"actual":[[4,3],[9,3]],"check":"tie with minimum","expected":[[4,3],[9,3]],"passed":true},{"actual":[[4,3],[9,3]],"check":"equal newcomer keeps incumbent","expected":[[4,3],[9,3]],"passed":true},{"actual":[[1,7],[2,5]],"check":"colliding refresh","expected":[[1,7],[2,5]],"passed":true},{"actual":[[7,6],[9,3]],"check":"tie among minima eviction","expected":[[7,6],[9,3]],"passed":true},{"actual":[[1,6],[2,6]],"check":"newcomer below minimum","expected":[[1,6],[2,6]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"stream 0 w=8 k=2\", \"actual\": [[3, 8], [5, 8]], \"expected\": [[3, 8], [5, 8]], \"passed\": true}, {\"check\": \"stream 1 w=6 k=3\", \"actual\": [[5, 12], [6, 6], [7, 6]], \"expected\": [[5, 12], [6, 6], [7, 6]], \"passed\": true}, {\"check\": \"stream 2 w=10 k=3\", \"actual\": [[3, 15], [6, 6], [1, 5]], \"expected\": [[3, 15], [6, 6], [1, 5]], \"passed\": true}, {\"check\": \"stream 3 w=5 k=2\", \"actual\": [[3, 13], [6, 10]], \"expected\": [[3, 13], [6, 10]], \"passed\": true}, {\"check\": \"hit refreshes estimate\", \"actual\": [[1, 9], [3, 4]], \"expected\": [[1, 9], [3, 4]], \"passed\": true}, {\"check\": \"tie with minimum\", \"actual\": [[4, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": true}, {\"check\": \"equal newcomer keeps incumbent\", \"actual\": [[4, 3], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": true}, {\"check\": \"colliding refresh\", \"actual\": [[1, 7], [2, 5]], \"expected\": [[1, 7], [2, 5]], \"passed\": true}, {\"check\": \"tie among minima eviction\", \"actual\": [[7, 6], [9, 3]], \"expected\": [[7, 6], [9, 3]], \"passed\": true}, {\"check\": \"newcomer below minimum\", \"actual\": [[1, 6], [2, 6]], \"expected\": [[1, 6], [2, 6]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}