{"abstract":"Large keys land in buckets that differ from other nodes using the specified hash family.","category":"Probabilistic sketches","checks":6,"contract":"Input {w, d, ops}. Row r hashes key to ((A_r*key + B_r) mod 2^31-1) mod w with fixed A and B. add with count <= 0 is \"rejected\" (conservative update cannot represent deletions). Otherwise the current estimate e is the minimum of the key's cells, and each cell is raised to max(cell, e + count). The stream total counts accepted mass and the overestimate bound is ceil(e/w * total). q returns the minimum of the key's cells. Return [results, total, bound, table].","contract_signature":"x","evaluation_group":"w2-probabilistic_sketches-cms-conservative","failed_approach":"Reducing the key modulo w first changes the hash family for every key larger than w.","family":"w2-probabilistic_sketches-cms-conservative-prime-reduction","id":"FA-73061","implementations":{"attempt":{"sha256":"4627452fe5e4ab14fb834c257a439c81a5dafa85137e4093cdf23d5558f50253","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    w = x['w']\n    A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677]\n    B = [12345, 1013904223, 7, 99991, 31337]\n    P = 2147483647\n    d = x['d']\n    t = [[0] * w for _ in range(d)]\n    def bucket(r, key):\n        return (A[r] * (key % w) + B[r]) % P % w\n    total = 0\n    res = []\n    for op in x['ops']:\n        if op[0] == 'add':\n            key, cnt = op[1], op[2]\n            if cnt <= 0:\n                res.append('rejected')\n                continue\n            est = min(t[r][bucket(r, key)] for r in range(d))\n            for r in range(d):\n                b = bucket(r, key)\n                t[r][b] = max(t[r][b], est + cnt)\n            total += cnt\n            res.append('ok')\n        else:\n            res.append(min(t[r][bucket(r, op[1])] for r in range(d)))\n    return [res, total, math.ceil(math.e / w * total), t]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000007, 3],\n            ['add', 2700000021, 2],\n            ['q', 900000007],\n            ['q', 2700000021],\n            ['q', 7]],\n    'w': 7},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 2],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 2],\n    12,\n    9,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 2],\n            ['add', 2, 3],\n            ['add', 3, 4],\n            ['add', 4, 1],\n            ['add', 5, 2],\n            ['add', 6, 3],\n            ['add', 7, 4],\n            ['add', 8, 1],\n            ['add', 9, 2],\n            ['add', 10, 3],\n            ['add', 11, 4],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     4,\n     4,\n     2,\n     'rejected'],\n    30,\n    17,\n    [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000014, 3],\n            ['add', 2700000042, 2],\n            ['q', 900000014],\n            ['q', 2700000042],\n            ['q', 7]],\n    'w': 8},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 2, 0, 0, 0, 3], [0, 0, 2, 3, 0, 0, 0, 0], [3, 0, 2, 0, 0, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 3],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 3],\n    13,\n    9,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 3], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 3],\n            ['add', 2, 1],\n            ['add', 3, 3],\n            ['add', 4, 1],\n            ['add', 5, 3],\n            ['add', 6, 1],\n            ['add', 7, 3],\n            ['add', 8, 1],\n            ['add', 9, 3],\n            ['add', 10, 1],\n            ['add', 11, 3],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     3,\n     3,\n     3,\n     'rejected'],\n    24,\n    14,\n    [[4, 3, 3, 3, 3], [3, 3, 4, 4, 3], [0, 3, 1, 4, 3]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000021, 3],\n            ['add', 2700000063, 2],\n            ['q', 900000021],\n            ['q', 2700000063],\n            ['q', 7]],\n    'w': 9},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 2, 0, 0, 3, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 2, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 4],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 4],\n    14,\n    10,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 4], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 4],\n            ['add', 2, 3],\n            ['add', 3, 2],\n            ['add', 4, 1],\n            ['add', 5, 4],\n            ['add', 6, 3],\n            ['add', 7, 2],\n            ['add', 8, 1],\n            ['add', 9, 4],\n            ['add', 10, 3],\n            ['add', 11, 2],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     3,\n     3,\n     4,\n     'rejected'],\n    30,\n    17,\n    [[5, 4, 4, 3, 3], [4, 3, 5, 3, 4], [0, 4, 1, 5, 4]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000028, 3],\n            ['add', 2700000084, 2],\n            ['q', 900000028],\n            ['q', 2700000084],\n            ['q', 7]],\n    'w': 10},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 0, 2, 0, 0, 0, 3, 0],\n     [0, 0, 0, 0, 0, 3, 2, 0, 0, 0],\n     [0, 0, 0, 0, 3, 0, 0, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 5],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 5],\n    15,\n    11,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 5], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 1],\n            ['add', 2, 1],\n            ['add', 3, 1],\n            ['add', 4, 1],\n            ['add', 5, 1],\n            ['add', 6, 1],\n            ['add', 7, 1],\n            ['add', 8, 1],\n            ['add', 9, 1],\n            ['add', 10, 1],\n            ['add', 11, 1],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     1,\n     1,\n     1,\n     'rejected'],\n    12,\n    7,\n    [[2, 1, 1, 1, 1], [1, 1, 2, 2, 1], [0, 1, 1, 2, 1]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000035, 3],\n            ['add', 2700000105, 2],\n            ['q', 900000035],\n            ['q', 2700000105],\n            ['q', 7]],\n    'w': 11},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 2],\n     [0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0],\n     [0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 6],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 6],\n    16,\n    11,\n    [[6, 0, 5, 0], [6, 0, 0, 5], [0, 0, 5, 6], [6, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 2],\n            ['add', 2, 3],\n            ['add', 3, 4],\n            ['add', 4, 1],\n            ['add', 5, 2],\n            ['add', 6, 3],\n            ['add', 7, 4],\n            ['add', 8, 1],\n            ['add', 9, 2],\n            ['add', 10, 3],\n            ['add', 11, 4],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     4,\n     4,\n     2,\n     'rejected'],\n    30,\n    17,\n    [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]]]\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":"27a9ef937b50774bc02cc3ac453e5e56490b3e4c42d1c1d438f4c080e9f9f662","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nN = 1\nobservations = []\ndef solve(x):\n    w = x['w']\n    A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677]\n    B = [12345, 1013904223, 7, 99991, 31337]\n    P = 2147483647\n    d = x['d']\n    t = [[0] * w for _ in range(d)]\n    def bucket(r, key):\n        return (A[r] * key + B[r]) % w\n    total = 0\n    res = []\n    for op in x['ops']:\n        if op[0] == 'add':\n            key, cnt = op[1], op[2]\n            if cnt <= 0:\n                res.append('rejected')\n                continue\n            est = min(t[r][bucket(r, key)] for r in range(d))\n            for r in range(d):\n                b = bucket(r, key)\n                t[r][b] = max(t[r][b], est + cnt)\n            total += cnt\n            res.append('ok')\n        else:\n            res.append(min(t[r][bucket(r, op[1])] for r in range(d)))\n    return [res, total, math.ceil(math.e / w * total), t]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000007, 3],\n            ['add', 2700000021, 2],\n            ['q', 900000007],\n            ['q', 2700000021],\n            ['q', 7]],\n    'w': 7},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 2],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 2],\n    12,\n    9,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 2],\n            ['add', 2, 3],\n            ['add', 3, 4],\n            ['add', 4, 1],\n            ['add', 5, 2],\n            ['add', 6, 3],\n            ['add', 7, 4],\n            ['add', 8, 1],\n            ['add', 9, 2],\n            ['add', 10, 3],\n            ['add', 11, 4],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     4,\n     4,\n     2,\n     'rejected'],\n    30,\n    17,\n    [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000014, 3],\n            ['add', 2700000042, 2],\n            ['q', 900000014],\n            ['q', 2700000042],\n            ['q', 7]],\n    'w': 8},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 2, 0, 0, 0, 3], [0, 0, 2, 3, 0, 0, 0, 0], [3, 0, 2, 0, 0, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 3],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 3],\n    13,\n    9,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 3], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 3],\n            ['add', 2, 1],\n            ['add', 3, 3],\n            ['add', 4, 1],\n            ['add', 5, 3],\n            ['add', 6, 1],\n            ['add', 7, 3],\n            ['add', 8, 1],\n            ['add', 9, 3],\n            ['add', 10, 1],\n            ['add', 11, 3],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     3,\n     3,\n     3,\n     'rejected'],\n    24,\n    14,\n    [[4, 3, 3, 3, 3], [3, 3, 4, 4, 3], [0, 3, 1, 4, 3]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000021, 3],\n            ['add', 2700000063, 2],\n            ['q', 900000021],\n            ['q', 2700000063],\n            ['q', 7]],\n    'w': 9},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 2, 0, 0, 3, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 3, 0, 0, 0, 0, 2, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 4],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 4],\n    14,\n    10,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 4], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 4],\n            ['add', 2, 3],\n            ['add', 3, 2],\n            ['add', 4, 1],\n            ['add', 5, 4],\n            ['add', 6, 3],\n            ['add', 7, 2],\n            ['add', 8, 1],\n            ['add', 9, 4],\n            ['add', 10, 3],\n            ['add', 11, 2],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     3,\n     3,\n     4,\n     'rejected'],\n    30,\n    17,\n    [[5, 4, 4, 3, 3], [4, 3, 5, 3, 4], [0, 4, 1, 5, 4]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000028, 3],\n            ['add', 2700000084, 2],\n            ['q', 900000028],\n            ['q', 2700000084],\n            ['q', 7]],\n    'w': 10},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 0, 2, 0, 0, 0, 3, 0],\n     [0, 0, 0, 0, 0, 3, 2, 0, 0, 0],\n     [0, 0, 0, 0, 3, 0, 0, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 5],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 5],\n    15,\n    11,\n    [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 5], [5, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 1],\n            ['add', 2, 1],\n            ['add', 3, 1],\n            ['add', 4, 1],\n            ['add', 5, 1],\n            ['add', 6, 1],\n            ['add', 7, 1],\n            ['add', 8, 1],\n            ['add', 9, 1],\n            ['add', 10, 1],\n            ['add', 11, 1],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     1,\n     1,\n     1,\n     'rejected'],\n    12,\n    7,\n    [[2, 1, 1, 1, 1], [1, 1, 2, 2, 1], [0, 1, 1, 2, 1]]]]],\n [['colliding keys',\n   {'d': 3,\n    'ops': [['add', 1, 4], ['add', 6, 2], ['add', 1, 1], ['q', 1], ['q', 6], ['q', 11]],\n    'w': 5},\n   [['ok', 'ok', 'ok', 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]]],\n  ['zero and negative counts',\n   {'d': 2, 'ops': [['add', 3, 0], ['add', 3, -2], ['add', 3, 5], ['q', 3]], 'w': 7},\n   [['rejected', 'rejected', 'ok', 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]]],\n  ['huge keys wrap prime',\n   {'d': 3,\n    'ops': [['add', 900000035, 3],\n            ['add', 2700000105, 2],\n            ['q', 900000035],\n            ['q', 2700000105],\n            ['q', 7]],\n    'w': 11},\n   [['ok', 'ok', 3, 2, 0],\n    5,\n    2,\n    [[0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 2],\n     [0, 0, 0, 3, 2, 0, 0, 0, 0, 0, 0],\n     [0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0]]]],\n  ['uneven rows',\n   {'d': 4,\n    'ops': [['add', 2, 3],\n            ['add', 9, 5],\n            ['add', 2, 2],\n            ['add', 5, 6],\n            ['q', 2],\n            ['q', 9],\n            ['q', 5]],\n    'w': 4},\n   [['ok', 'ok', 'ok', 'ok', 5, 5, 6],\n    16,\n    11,\n    [[6, 0, 5, 0], [6, 0, 0, 5], [0, 0, 5, 6], [6, 0, 5, 0]]]],\n  ['single row',\n   {'d': 1, 'ops': [['add', 1, 2], ['add', 4, 3], ['q', 1], ['add', 0, 0]], 'w': 3},\n   [['ok', 'ok', 2, 'rejected'], 5, 5, [[2, 3, 0]]]],\n  ['many keys',\n   {'d': 3,\n    'ops': [['add', 0, 1],\n            ['add', 1, 2],\n            ['add', 2, 3],\n            ['add', 3, 4],\n            ['add', 4, 1],\n            ['add', 5, 2],\n            ['add', 6, 3],\n            ['add', 7, 4],\n            ['add', 8, 1],\n            ['add', 9, 2],\n            ['add', 10, 3],\n            ['add', 11, 4],\n            ['q', 0],\n            ['q', 3],\n            ['q', 6],\n            ['q', 9],\n            ['add', 2, 0]],\n    'w': 5},\n   [['ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     'ok',\n     1,\n     4,\n     4,\n     2,\n     'rejected'],\n    30,\n    17,\n    [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]]]]]\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-conservative-prime-reduction","generated_at":"2026-09-29T14:48:44.007104+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Conservative update reduces Count-Min overestimation in heavy-hitter monitors, but only if the raise-to-target rule is applied exactly.","root_cause":"The bucket index reduces modulo w without first reducing modulo 2^31-1.","sha256":"f47cd09e771090415794d764b46dbedfc5ea702a0a9616371dc3c6ff1ec9b68d","title":"Count-Min sketch with conservative update: bucket skips the prime-field reduction · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":44.437,"exit_code":1,"observations":[{"actual":[["ok","ok","ok",7,7,7],7,4,[[7,0,0,0,0],[0,0,0,0,7],[0,0,0,0,7]]],"check":"colliding keys","expected":[["ok","ok","ok",5,2,0],7,4,[[5,0,0,0,2],[0,2,0,0,5],[0,2,0,0,5]]],"passed":false},{"actual":[["rejected","rejected","ok",5],5,2,[[0,0,0,5,0,0,0],[0,0,0,5,0,0,0]]],"check":"zero and negative counts","expected":[["rejected","rejected","ok",5],5,2,[[0,0,0,5,0,0,0],[0,0,0,5,0,0,0]]],"passed":true},{"actual":[["ok","ok",3,2,0],5,2,[[0,0,3,0,0,0,0],[0,0,0,0,3,0,0],[0,3,2,0,0,0,0]]],"check":"huge keys wrap prime","expected":[["ok","ok",3,2,0],5,2,[[0,3,0,0,0,0,0],[2,0,0,0,3,0,0],[2,0,0,3,0,0,0]]],"passed":false},{"actual":[["ok","ok","ok","ok",5,7,7],12,9,[[5,0,7,0],[0,7,0,5],[7,0,5,0],[7,0,5,0]]],"check":"uneven rows","expected":[["ok","ok","ok","ok",5,5,2],12,9,[[5,0,5,0],[5,0,0,5],[0,0,5,2],[5,0,5,0]]],"passed":false},{"actual":[["ok","ok",5,"rejected"],5,5,[[5,0,0]]],"check":"single row","expected":[["ok","ok",2,"rejected"],5,5,[[2,3,0]]],"passed":false},{"actual":[["ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok",6,5,9,3,"rejected"],30,17,[[9,3,0,7,0],[7,5,0,6,9],[0,0,6,0,9]]],"check":"many keys","expected":[["ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok",1,4,4,2,"rejected"],30,17,[[5,2,2,4,4],[3,4,5,5,2],[0,4,1,5,4]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"colliding keys\", \"actual\": [[\"ok\", \"ok\", \"ok\", 7, 7, 7], 7, 4, [[7, 0, 0, 0, 0], [0, 0, 0, 0, 7], [0, 0, 0, 0, 7]]], \"expected\": [[\"ok\", \"ok\", \"ok\", 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]], \"passed\": false}, {\"check\": \"zero and negative counts\", \"actual\": [[\"rejected\", \"rejected\", \"ok\", 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]], \"expected\": [[\"rejected\", \"rejected\", \"ok\", 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]], \"passed\": true}, {\"check\": \"huge keys wrap prime\", \"actual\": [[\"ok\", \"ok\", 3, 2, 0], 5, 2, [[0, 0, 3, 0, 0, 0, 0], [0, 0, 0, 0, 3, 0, 0], [0, 3, 2, 0, 0, 0, 0]]], \"expected\": [[\"ok\", \"ok\", 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]], \"passed\": false}, {\"check\": \"uneven rows\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", 5, 7, 7], 12, 9, [[5, 0, 7, 0], [0, 7, 0, 5], [7, 0, 5, 0], [7, 0, 5, 0]]], \"expected\": [[\"ok\", \"ok\", \"ok\", \"ok\", 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]], \"passed\": false}, {\"check\": \"single row\", \"actual\": [[\"ok\", \"ok\", 5, \"rejected\"], 5, 5, [[5, 0, 0]]], \"expected\": [[\"ok\", \"ok\", 2, \"rejected\"], 5, 5, [[2, 3, 0]]], \"passed\": false}, {\"check\": \"many keys\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", 6, 5, 9, 3, \"rejected\"], 30, 17, [[9, 3, 0, 7, 0], [7, 5, 0, 6, 9], [0, 0, 6, 0, 9]]], \"expected\": [[\"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", 1, 4, 4, 2, \"rejected\"], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.125,"exit_code":1,"observations":[{"actual":[["ok","ok","ok",7,7,7],7,4,[[7,0,0,0,0],[0,7,0,0,0],[0,0,0,0,7]]],"check":"colliding keys","expected":[["ok","ok","ok",5,2,0],7,4,[[5,0,0,0,2],[0,2,0,0,5],[0,2,0,0,5]]],"passed":false},{"actual":[["rejected","rejected","ok",5],5,2,[[0,0,0,0,5,0,0],[0,0,0,0,0,0,5]]],"check":"zero and negative counts","expected":[["rejected","rejected","ok",5],5,2,[[0,0,0,5,0,0,0],[0,0,0,5,0,0,0]]],"passed":false},{"actual":[["ok","ok",3,2,0],5,2,[[0,0,0,0,3,0,0],[3,2,0,0,0,0,0],[0,0,0,0,3,2,0]]],"check":"huge keys wrap prime","expected":[["ok","ok",3,2,0],5,2,[[0,3,0,0,0,0,0],[2,0,0,0,3,0,0],[2,0,0,3,0,0,0]]],"passed":false},{"actual":[["ok","ok","ok","ok",5,7,7],12,9,[[0,0,7,5],[7,5,0,0],[7,5,0,0],[7,5,0,0]]],"check":"uneven rows","expected":[["ok","ok","ok","ok",5,5,2],12,9,[[5,0,5,0],[5,0,0,5],[0,0,5,2],[5,0,5,0]]],"passed":false},{"actual":[["ok","ok",5,"rejected"],5,5,[[5,0,0]]],"check":"single row","expected":[["ok","ok",2,"rejected"],5,5,[[2,3,0]]],"passed":false},{"actual":[["ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok",6,5,9,3,"rejected"],30,17,[[9,0,0,0,0],[3,9,5,6,7],[3,7,6,5,9]]],"check":"many keys","expected":[["ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok","ok",1,4,4,2,"rejected"],30,17,[[5,2,2,4,4],[3,4,5,5,2],[0,4,1,5,4]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"colliding keys\", \"actual\": [[\"ok\", \"ok\", \"ok\", 7, 7, 7], 7, 4, [[7, 0, 0, 0, 0], [0, 7, 0, 0, 0], [0, 0, 0, 0, 7]]], \"expected\": [[\"ok\", \"ok\", \"ok\", 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]], \"passed\": false}, {\"check\": \"zero and negative counts\", \"actual\": [[\"rejected\", \"rejected\", \"ok\", 5], 5, 2, [[0, 0, 0, 0, 5, 0, 0], [0, 0, 0, 0, 0, 0, 5]]], \"expected\": [[\"rejected\", \"rejected\", \"ok\", 5], 5, 2, [[0, 0, 0, 5, 0, 0, 0], [0, 0, 0, 5, 0, 0, 0]]], \"passed\": false}, {\"check\": \"huge keys wrap prime\", \"actual\": [[\"ok\", \"ok\", 3, 2, 0], 5, 2, [[0, 0, 0, 0, 3, 0, 0], [3, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 3, 2, 0]]], \"expected\": [[\"ok\", \"ok\", 3, 2, 0], 5, 2, [[0, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 0, 0, 0]]], \"passed\": false}, {\"check\": \"uneven rows\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", 5, 7, 7], 12, 9, [[0, 0, 7, 5], [7, 5, 0, 0], [7, 5, 0, 0], [7, 5, 0, 0]]], \"expected\": [[\"ok\", \"ok\", \"ok\", \"ok\", 5, 5, 2], 12, 9, [[5, 0, 5, 0], [5, 0, 0, 5], [0, 0, 5, 2], [5, 0, 5, 0]]], \"passed\": false}, {\"check\": \"single row\", \"actual\": [[\"ok\", \"ok\", 5, \"rejected\"], 5, 5, [[5, 0, 0]]], \"expected\": [[\"ok\", \"ok\", 2, \"rejected\"], 5, 5, [[2, 3, 0]]], \"passed\": false}, {\"check\": \"many keys\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", 6, 5, 9, 3, \"rejected\"], 30, 17, [[9, 0, 0, 0, 0], [3, 9, 5, 6, 7], [3, 7, 6, 5, 9]]], \"expected\": [[\"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", \"ok\", 1, 4, 4, 2, \"rejected\"], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]], \"passed\": false}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}