{"abstract":"Deletions are acknowledged although conservative cells cannot decrease, and the stream total drifts.","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].","evaluation_group":"w2-probabilistic_sketches-cms-conservative","failed_approach":"Rejecting only negative counts still acknowledges zero-count updates.","family":"w2-probabilistic_sketches-cms-conservative-nonpositive-reject","id":"FA-73051","implementations":{"attempt":{"sha256":"1bb067936fba3b2d277338cc72f1578a9081bd4129c435fb526f40859a875427","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]) % 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":"91cae4156aad433d4b5bb115f6e375c370271422bd8f4fd960174cc906cff13e","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]) % 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            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"},"fixed":{"sha256":"0e18fcfdc61a0aa0508c64b1667c489c348c474f4cfb57183103a8face239005","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]) % 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"}},"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-nonpositive-reject","generated_at":"2026-09-29T14:48:43.990173+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.","repair":"Reject any count <= 0.","root_cause":"Non-positive counts are not rejected.","sha256":"9420d0877ec1c24a53f98cbd7bd6fdf48483e153d418589438880492198d872e","title":"Count-Min sketch with conservative update: zero and negative counts accepted · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":43.084,"exit_code":1,"observations":[{"actual":[["ok","ok","ok",5,2,0],7,4,[[5,0,0,0,2],[0,2,0,0,5],[0,2,0,0,5]]],"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":true},{"actual":[["ok","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":false},{"actual":[["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]]],"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":true},{"actual":[["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]]],"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":true},{"actual":[["ok","ok",2,"ok"],5,5,[[2,3,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",1,4,4,2,"ok"],30,17,[[5,2,2,4,4],[3,4,5,5,2],[0,4,1,5,4]]],"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\", 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]], \"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\": true}, {\"check\": \"zero and negative counts\", \"actual\": [[\"ok\", \"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\": false}, {\"check\": \"huge keys wrap prime\", \"actual\": [[\"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]]], \"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\": true}, {\"check\": \"uneven rows\", \"actual\": [[\"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]]], \"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\": true}, {\"check\": \"single row\", \"actual\": [[\"ok\", \"ok\", 2, \"ok\"], 5, 5, [[2, 3, 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\", 1, 4, 4, 2, \"ok\"], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]], \"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":38.743,"exit_code":1,"observations":[{"actual":[["ok","ok","ok",5,2,0],7,4,[[5,0,0,0,2],[0,2,0,0,5],[0,2,0,0,5]]],"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":true},{"actual":[["ok","ok","ok",5],3,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":false},{"actual":[["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]]],"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":true},{"actual":[["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]]],"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":true},{"actual":[["ok","ok",2,"ok"],5,5,[[2,3,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",1,4,4,2,"ok"],30,17,[[5,2,2,4,4],[3,4,5,5,2],[0,4,1,5,4]]],"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\", 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]], \"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\": true}, {\"check\": \"zero and negative counts\", \"actual\": [[\"ok\", \"ok\", \"ok\", 5], 3, 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\": false}, {\"check\": \"huge keys wrap prime\", \"actual\": [[\"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]]], \"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\": true}, {\"check\": \"uneven rows\", \"actual\": [[\"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]]], \"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\": true}, {\"check\": \"single row\", \"actual\": [[\"ok\", \"ok\", 2, \"ok\"], 5, 5, [[2, 3, 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\", 1, 4, 4, 2, \"ok\"], 30, 17, [[5, 2, 2, 4, 4], [3, 4, 5, 5, 2], [0, 4, 1, 5, 4]]], \"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"},"fixed":{"elapsed_ms":40.862,"exit_code":0,"observations":[{"actual":[["ok","ok","ok",5,2,0],7,4,[[5,0,0,0,2],[0,2,0,0,5],[0,2,0,0,5]]],"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":true},{"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,3,0,0,0,0,0],[2,0,0,0,3,0,0],[2,0,0,3,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":true},{"actual":[["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]]],"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":true},{"actual":[["ok","ok",2,"rejected"],5,5,[[2,3,0]]],"check":"single row","expected":[["ok","ok",2,"rejected"],5,5,[[2,3,0]]],"passed":true},{"actual":[["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]]],"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":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"colliding keys\", \"actual\": [[\"ok\", \"ok\", \"ok\", 5, 2, 0], 7, 4, [[5, 0, 0, 0, 2], [0, 2, 0, 0, 5], [0, 2, 0, 0, 5]]], \"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\": true}, {\"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, 3, 0, 0, 0, 0, 0], [2, 0, 0, 0, 3, 0, 0], [2, 0, 0, 3, 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\": true}, {\"check\": \"uneven rows\", \"actual\": [[\"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]]], \"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\": true}, {\"check\": \"single row\", \"actual\": [[\"ok\", \"ok\", 2, \"rejected\"], 5, 5, [[2, 3, 0]]], \"expected\": [[\"ok\", \"ok\", 2, \"rejected\"], 5, 5, [[2, 3, 0]]], \"passed\": true}, {\"check\": \"many keys\", \"actual\": [[\"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]]], \"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\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}