{"abstract":"Each key is scored without its current occurrence, so newcomers can never beat equal incumbents.","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":"Reading the maximum cell uses the most collision-contaminated row.","family":"w2-probabilistic_sketches-cms-topk-tracker-post-update-estimate","id":"FA-73336","implementations":{"attempt":{"sha256":"e3fa5e0327eaa588b33b7a52b3467ab345d73c1e41216477ae072e24f6d6fd67","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 = max(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"},"broken":{"sha256":"a743b2f5779c859e293a58b2c168e63a45f3a5ddc05283af67636e7c3931e953","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        est = min(t[r][(A[r] * key + B[r]) % P % w] for r in range(3))\n        for r in range(3):\n            t[r][(A[r] * key + B[r]) % P % w] += c\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-post-update-estimate","generated_at":"2026-09-29T14:48:46.593611+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":"Update the sketch first, then read the minimum estimate.","root_cause":"The estimate is read before the sketch is updated with the current count.","sha256":"d95abaa2829ad137f6e96776f2ec5770767f5eb4903f269ea612f6d2733db215","title":"Top-k tracking over a Count-Min sketch: candidate scored before its own update · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":43.288,"exit_code":1,"observations":[{"actual":[[4,12],[5,11]],"check":"stream 0 w=8 k=2","expected":[[3,8],[5,8]],"passed":false},{"actual":[[7,24],[5,20],[1,14]],"check":"stream 1 w=6 k=3","expected":[[5,12],[6,6],[7,6]],"passed":false},{"actual":[[1,23],[3,20],[4,16]],"check":"stream 2 w=10 k=3","expected":[[3,15],[6,6],[1,5]],"passed":false},{"actual":[[3,22],[6,17]],"check":"stream 3 w=5 k=2","expected":[[3,13],[6,10]],"passed":false},{"actual":[[1,9],[3,4]],"check":"hit refreshes estimate","expected":[[1,9],[3,4]],"passed":true},{"actual":[[4,6],[9,3]],"check":"tie with minimum","expected":[[4,3],[9,3]],"passed":false},{"actual":[[9,6],[4,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,6]],"check":"tie among minima eviction","expected":[[7,6],[9,3]],"passed":false},{"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\": [[4, 12], [5, 11]], \"expected\": [[3, 8], [5, 8]], \"passed\": false}, {\"check\": \"stream 1 w=6 k=3\", \"actual\": [[7, 24], [5, 20], [1, 14]], \"expected\": [[5, 12], [6, 6], [7, 6]], \"passed\": false}, {\"check\": \"stream 2 w=10 k=3\", \"actual\": [[1, 23], [3, 20], [4, 16]], \"expected\": [[3, 15], [6, 6], [1, 5]], \"passed\": false}, {\"check\": \"stream 3 w=5 k=2\", \"actual\": [[3, 22], [6, 17]], \"expected\": [[3, 13], [6, 10]], \"passed\": false}, {\"check\": \"hit refreshes estimate\", \"actual\": [[1, 9], [3, 4]], \"expected\": [[1, 9], [3, 4]], \"passed\": true}, {\"check\": \"tie with minimum\", \"actual\": [[4, 6], [9, 3]], \"expected\": [[4, 3], [9, 3]], \"passed\": false}, {\"check\": \"equal newcomer keeps incumbent\", \"actual\": [[9, 6], [4, 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, 6]], \"expected\": [[7, 6], [9, 3]], \"passed\": false}, {\"check\": \"newcomer below minimum\", \"actual\": [[1, 6], [2, 6]], \"expected\": [[1, 6], [2, 6]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.129,"exit_code":1,"observations":[{"actual":[[3,7],[5,5]],"check":"stream 0 w=8 k=2","expected":[[3,8],[5,8]],"passed":false},{"actual":[[5,10],[2,4],[1,3]],"check":"stream 1 w=6 k=3","expected":[[5,12],[6,6],[7,6]],"passed":false},{"actual":[[3,11],[6,5],[4,2]],"check":"stream 2 w=10 k=3","expected":[[3,15],[6,6],[1,5]],"passed":false},{"actual":[[3,11],[6,9]],"check":"stream 3 w=5 k=2","expected":[[3,13],[6,10]],"passed":false},{"actual":[[1,7],[2,0]],"check":"hit refreshes estimate","expected":[[1,9],[3,4]],"passed":false},{"actual":[[4,0],[9,0]],"check":"tie with minimum","expected":[[4,3],[9,3]],"passed":false},{"actual":[[4,0],[9,0]],"check":"equal newcomer keeps incumbent","expected":[[4,3],[9,3]],"passed":false},{"actual":[[1,5],[2,2]],"check":"colliding refresh","expected":[[1,7],[2,5]],"passed":false},{"actual":[[4,0],[9,0]],"check":"tie among minima eviction","expected":[[7,6],[9,3]],"passed":false},{"actual":[[2,5],[1,0]],"check":"newcomer below minimum","expected":[[1,6],[2,6]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"stream 0 w=8 k=2\", \"actual\": [[3, 7], [5, 5]], \"expected\": [[3, 8], [5, 8]], \"passed\": false}, {\"check\": \"stream 1 w=6 k=3\", \"actual\": [[5, 10], [2, 4], [1, 3]], \"expected\": [[5, 12], [6, 6], [7, 6]], \"passed\": false}, {\"check\": \"stream 2 w=10 k=3\", \"actual\": [[3, 11], [6, 5], [4, 2]], \"expected\": [[3, 15], [6, 6], [1, 5]], \"passed\": false}, {\"check\": \"stream 3 w=5 k=2\", \"actual\": [[3, 11], [6, 9]], \"expected\": [[3, 13], [6, 10]], \"passed\": false}, {\"check\": \"hit refreshes estimate\", \"actual\": [[1, 7], [2, 0]], \"expected\": [[1, 9], [3, 4]], \"passed\": false}, {\"check\": \"tie with minimum\", \"actual\": [[4, 0], [9, 0]], \"expected\": [[4, 3], [9, 3]], \"passed\": false}, {\"check\": \"equal newcomer keeps incumbent\", \"actual\": [[4, 0], [9, 0]], \"expected\": [[4, 3], [9, 3]], \"passed\": false}, {\"check\": \"colliding refresh\", \"actual\": [[1, 5], [2, 2]], \"expected\": [[1, 7], [2, 5]], \"passed\": false}, {\"check\": \"tie among minima eviction\", \"actual\": [[4, 0], [9, 0]], \"expected\": [[7, 6], [9, 3]], \"passed\": false}, {\"check\": \"newcomer below minimum\", \"actual\": [[2, 5], [1, 0]], \"expected\": [[1, 6], [2, 6]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.516,"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"}