{"abstract":"Cells already inflated by other keys are lowered to this key's target, so other keys become underestimated.","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":"Adding count to every cell is the plain Count-Min update and overestimates colliding keys.","family":"w2-probabilistic_sketches-cms-conservative-raise-rule","id":"FA-73041","implementations":{"attempt":{"sha256":"75475eceb73f73bf4d49e4e815261a6f7e3df81591fa031c34f2dca9055f427e","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] = t[r][b] + 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":"21b32a52432b45fc4c80bff9ae6b007856d4fe333c77991ca4084aaa214e0133","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] = 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-raise-rule","generated_at":"2026-09-29T14:48:43.904723+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":"Raise each cell to max(cell, e + count).","root_cause":"Each cell is assigned est + count unconditionally instead of being raised only when smaller.","sha256":"4a5c73db204505b5d2f136b31c3aef925c32a24e54dcdb12cd99d7546ee6f447","title":"Count-Min sketch with conservative update: conservative update lowers larger cells · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":37.722,"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":[["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,5,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":false},{"actual":[["ok","ok","ok","ok",5,5,2],12,9,[[7,0,5,0],[7,0,0,5],[0,0,10,2],[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",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,7,7,3,"rejected"],30,17,[[10,3,3,7,7],[5,7,7,6,5],[0,10,1,9,10]]],"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\": [[\"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, 5, 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\": false}, {\"check\": \"uneven rows\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", 5, 5, 2], 12, 9, [[7, 0, 5, 0], [7, 0, 0, 5], [0, 0, 10, 2], [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\", 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, 7, 7, 3, \"rejected\"], 30, 17, [[10, 3, 3, 7, 7], [5, 7, 7, 6, 5], [0, 10, 1, 9, 10]]], \"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":40.521,"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":[["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",2,2,0],5,2,[[0,2,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":false},{"actual":[["ok","ok","ok","ok",2,2,2],12,9,[[2,0,5,0],[2,0,0,5],[0,0,5,2],[2,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",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,1,1,2,"rejected"],30,17,[[5,2,2,4,4],[2,3,5,5,2],[0,1,1,5,1]]],"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\": [[\"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\", 2, 2, 0], 5, 2, [[0, 2, 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\": false}, {\"check\": \"uneven rows\", \"actual\": [[\"ok\", \"ok\", \"ok\", \"ok\", 2, 2, 2], 12, 9, [[2, 0, 5, 0], [2, 0, 0, 5], [0, 0, 5, 2], [2, 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\", 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, 1, 1, 2, \"rejected\"], 30, 17, [[5, 2, 2, 4, 4], [2, 3, 5, 5, 2], [0, 1, 1, 5, 1]]], \"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":38.831,"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"}