{"abstract":"Values present in both sketches occupy two union slots, overstating the union and its overlap.","category":"Probabilistic sketches","checks":8,"contract":"Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].","evaluation_group":"w2-probabilistic_sketches-kmv-distinct","failed_approach":"Keeping every union value lets the overlap count include values beyond the k-th.","family":"w2-probabilistic_sketches-kmv-distinct-union-sketch","id":"FA-73251","implementations":{"attempt":{"sha256":"9f6146ea6213dc92d1c52eed427dc8bfaca021313870347f89d472d8809f266b","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    def kept(hs):\n        return sorted(set(hs))[:k]\n    def est(vals):\n        if len(vals) < k:\n            return len(vals)\n        return round((k - 1) * 2 ** 32 / vals[k - 1])\n    A = kept(x['a'])\n    B = kept(x['b'])\n    U = sorted(set(A) | set(B))\n    eu = est(U)\n    if len(U) < k:\n        inter = len(set(A) & set(B))\n    else:\n        both = sum(1 for v in U if v in A and v in B)\n        inter = round(both / k * eu)\n    return [est(A), est(B), eu, inter]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['streams 0 k=4',\n   {'a': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          2991703416,\n          247407200,\n          502807838,\n          953930153,\n          4276337012,\n          825867426,\n          927935964,\n          767117601,\n          1349057482,\n          512140804],\n    'b': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          3243866592,\n          2367279148,\n          2430077702,\n          2971523655,\n          1478379009],\n    'k': 4},\n   [25, 10, 25, 12]],\n  ['streams 1 k=5',\n   {'a': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          844670565,\n          1574495990,\n          3092220355,\n          1623550118,\n          1677170996,\n          355484359,\n          1577212364,\n          222802868,\n          3302194479,\n          1232086826,\n          4029593972,\n          846568436,\n          2280170916,\n          2039090929,\n          2369642582],\n    'b': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          3736327325,\n          4143402618,\n          3225214513,\n          2668680618,\n          690502660,\n          4038350892,\n          2109753841],\n    'k': 5},\n   [19, 8, 20, 0]],\n  ['streams 2 k=3',\n   {'a': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492,\n          2831125304,\n          3278849932,\n          2146240677],\n    'b': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492],\n    'k': 3},\n   [8, 8, 8, 8]],\n  ['streams 3 k=6',\n   {'a': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          3263214743,\n          1485141222,\n          507376609,\n          870194170,\n          405495016,\n          463928501,\n          3212162911,\n          200606854,\n          3827729694,\n          3442164173,\n          3023093882,\n          3815698597,\n          1832272475,\n          945613159,\n          136487868,\n          1731202674,\n          3903788721,\n          2182062801,\n          1489904681,\n          708728146,\n          1980483838,\n          1269587876,\n          3424059671,\n          3167970027,\n          3314237818,\n          161588255,\n          1347661301,\n          1126717335,\n          1593064253],\n    'b': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          1184217959,\n          795322907,\n          2681969582,\n          1479728863,\n          915549410,\n          1616093956,\n          1998008578,\n          566339276],\n    'k': 6},\n   [42, 16, 42, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          2958152150,\n          1105148405,\n          1551545311,\n          2382410247,\n          299374495,\n          3902367104,\n          3814609907,\n          616469427,\n          2903262975,\n          2673828359],\n    'b': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          1904501607,\n          2415525956,\n          972943297,\n          1101134287,\n          4209348669],\n    'k': 4},\n   [12, 12, 13, 6]],\n  ['streams 1 k=5',\n   {'a': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          3882412494,\n          3638249284,\n          629708383,\n          2652904385,\n          619827854,\n          2252659737,\n          4038367328,\n          751384629,\n          2736132274,\n          2052511795,\n          1546656212,\n          2490980400,\n          1192536461,\n          3397803296,\n          3575214874],\n    'b': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          801257707,\n          231860101,\n          1552367569,\n          2200650299,\n          1300574527,\n          1169595163,\n          1486586779],\n    'k': 5},\n   [14, 14, 23, 5]],\n  ['streams 2 k=3',\n   {'a': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795,\n          3366336454,\n          3360405550,\n          3252767639],\n    'b': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795],\n    'k': 3},\n   [4, 4, 4, 4]],\n  ['streams 3 k=6',\n   {'a': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          2859580621,\n          3296482680,\n          2191809106,\n          4155174719,\n          3651321607,\n          3668767012,\n          3871583709,\n          53568284,\n          232037959,\n          2442976016,\n          217741541,\n          3800768541,\n          2101516655,\n          2409083912,\n          918078055,\n          2969028849,\n          3001715579,\n          3922319082,\n          2100936555,\n          2284049623,\n          3774876442,\n          3238172673,\n          3672802287,\n          3806827876,\n          2442511505,\n          3389659053,\n          1412588383,\n          1682740534,\n          1107531143],\n    'b': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          321792195,\n          4055119656,\n          4005216604,\n          4067339772,\n          2438348428,\n          2893845634,\n          4168021051,\n          1191737207],\n    'k': 6},\n   [15, 9, 19, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          874550077,\n          874052348,\n          2099297276,\n          2917681254,\n          3461079448,\n          4523874,\n          1892412104,\n          1348947199,\n          2220012561,\n          4274378431],\n    'b': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          320314762,\n          2913424927,\n          3760403017,\n          3874375803,\n          3498294633],\n    'k': 4},\n   [15, 8, 15, 4]],\n  ['streams 1 k=5',\n   {'a': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          429269052,\n          4120988501,\n          2192756914,\n          2080257154,\n          215643658,\n          2236181558,\n          3506517446,\n          3204080191,\n          2539102762,\n          1231819029,\n          129435166,\n          1969895105,\n          1451722624,\n          4208772152,\n          2008054505],\n    'b': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          3624728915,\n          4097927174,\n          3560188535,\n          2101457494,\n          1008357362,\n          2961406180,\n          2250944138],\n    'k': 5},\n   [45, 13, 45, 27]],\n  ['streams 2 k=3',\n   {'a': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124,\n          163959442,\n          4243274568,\n          1097577740],\n    'b': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124],\n    'k': 3},\n   [28, 28, 28, 28]],\n  ['streams 3 k=6',\n   {'a': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          4076278131,\n          1681936286,\n          3644273863,\n          1144985545,\n          1058589555,\n          2372866836,\n          2747157307,\n          319015226,\n          1616345963,\n          3215957022,\n          2575778964,\n          2002333856,\n          105152923,\n          971771153,\n          3904739092,\n          139512839,\n          3596088601,\n          3125993293,\n          3698817286,\n          571115313,\n          2651377839,\n          404892510,\n          335085347,\n          3997319691,\n          423428202,\n          1253418186,\n          3736875704,\n          2512119594,\n          3432728552],\n    'b': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          2190917676,\n          1217641816,\n          2195352441,\n          1962797028,\n          1369215451,\n          146219861,\n          2422264426,\n          2740291298],\n    'k': 6},\n   [51, 10, 53, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          469293850,\n          3311372855,\n          3291632216,\n          3532104316,\n          792576761,\n          2383663819,\n          3796612359,\n          534629630,\n          3752143492,\n          3784451643],\n    'b': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          778329530,\n          4126190270,\n          369138172,\n          3244871941,\n          426427744],\n    'k': 4},\n   [5, 17, 24, 6]],\n  ['streams 1 k=5',\n   {'a': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          2365171429,\n          473117839,\n          1494688212,\n          3130081894,\n          3456600902,\n          1870835644,\n          1831585095,\n          856053019,\n          2401707901,\n          8291469,\n          994865049,\n          2075147938,\n          2281118336,\n          470394482,\n          2564274781],\n    'b': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          3616671026,\n          3377000285,\n          291138770,\n          4144176995,\n          410153163,\n          1894447883,\n          2251698],\n    'k': 5},\n   [36, 42, 59, 24]],\n  ['streams 2 k=3',\n   {'a': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100,\n          3123627193,\n          2732919500,\n          1916452664],\n    'b': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100],\n    'k': 3},\n   [25, 25, 25, 25]],\n  ['streams 3 k=6',\n   {'a': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          145050205,\n          1943098641,\n          2902033596,\n          942056830,\n          1094682071,\n          482655062,\n          1597161973,\n          2776457123,\n          540173509,\n          49617459,\n          3062849472,\n          721066780,\n          1881851915,\n          2771669550,\n          271560229,\n          4250659366,\n          849113494,\n          2890310823,\n          2849978717,\n          2813753673,\n          2723489037,\n          3843541794,\n          2539258177,\n          294140292,\n          131741950,\n          1174692757,\n          920449838,\n          3707669583,\n          2705746824],\n    'b': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          396707761,\n          853541794,\n          990402306,\n          2774188573,\n          1932619200,\n          40971593,\n          4209408016,\n          3008903819],\n    'k': 6},\n   [44, 22, 73, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          3402435104,\n          2615317700,\n          2901867586,\n          2191387195,\n          3244643901,\n          143617512,\n          4128185702,\n          3695416152,\n          3485519680,\n          1295479236],\n    'b': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          2172377362,\n          122431251,\n          2879905546,\n          3080363355,\n          742472857],\n    'k': 4},\n   [6, 6, 10, 2]],\n  ['streams 1 k=5',\n   {'a': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3856414966,\n          182199786,\n          3302563887,\n          3489282613,\n          3728782849,\n          2555406465,\n          3392268813,\n          468049757,\n          2334691707,\n          3652253765,\n          2830979039,\n          2618409554,\n          629677788,\n          1134145340,\n          1003578828],\n    'b': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3383921903,\n          1576598490,\n          1966729080,\n          3816342364,\n          951010101,\n          559264201,\n          3070372495],\n    'k': 5},\n   [17, 17, 27, 11]],\n  ['streams 2 k=3',\n   {'a': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371,\n          618180559,\n          2081251765,\n          530858903],\n    'b': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371],\n    'k': 3},\n   [14, 14, 14, 14]],\n  ['streams 3 k=6',\n   {'a': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          3886248964,\n          2353903802,\n          3929595655,\n          3522020961,\n          4226953245,\n          1619288587,\n          3373914572,\n          808857433,\n          2095738713,\n          3699811607,\n          2323854089,\n          4254321459,\n          2563706603,\n          1910759716,\n          2164426481,\n          690823666,\n          2412713602,\n          1704719407,\n          2407797195,\n          541403854,\n          3575208143,\n          381803083,\n          3474890246,\n          3033023633,\n          2039329698,\n          3301104757,\n          1308497545,\n          1688068524,\n          2659577736],\n    'b': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          923787522,\n          3928497192,\n          1582544665,\n          3091940628,\n          1369092784,\n          2483888591,\n          2347320516,\n          1678251482],\n    'k': 6},\n   [13, 13, 16, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]]]\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":"3b5e858073f0393b6f9df6502c1f3768785dd35995bd6cf15fbeda44e60216c0","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    def kept(hs):\n        return sorted(set(hs))[:k]\n    def est(vals):\n        if len(vals) < k:\n            return len(vals)\n        return round((k - 1) * 2 ** 32 / vals[k - 1])\n    A = kept(x['a'])\n    B = kept(x['b'])\n    U = sorted(A + B)[:k]\n    eu = est(U)\n    if len(U) < k:\n        inter = len(set(A) & set(B))\n    else:\n        both = sum(1 for v in U if v in A and v in B)\n        inter = round(both / k * eu)\n    return [est(A), est(B), eu, inter]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['streams 0 k=4',\n   {'a': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          2991703416,\n          247407200,\n          502807838,\n          953930153,\n          4276337012,\n          825867426,\n          927935964,\n          767117601,\n          1349057482,\n          512140804],\n    'b': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          3243866592,\n          2367279148,\n          2430077702,\n          2971523655,\n          1478379009],\n    'k': 4},\n   [25, 10, 25, 12]],\n  ['streams 1 k=5',\n   {'a': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          844670565,\n          1574495990,\n          3092220355,\n          1623550118,\n          1677170996,\n          355484359,\n          1577212364,\n          222802868,\n          3302194479,\n          1232086826,\n          4029593972,\n          846568436,\n          2280170916,\n          2039090929,\n          2369642582],\n    'b': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          3736327325,\n          4143402618,\n          3225214513,\n          2668680618,\n          690502660,\n          4038350892,\n          2109753841],\n    'k': 5},\n   [19, 8, 20, 0]],\n  ['streams 2 k=3',\n   {'a': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492,\n          2831125304,\n          3278849932,\n          2146240677],\n    'b': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492],\n    'k': 3},\n   [8, 8, 8, 8]],\n  ['streams 3 k=6',\n   {'a': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          3263214743,\n          1485141222,\n          507376609,\n          870194170,\n          405495016,\n          463928501,\n          3212162911,\n          200606854,\n          3827729694,\n          3442164173,\n          3023093882,\n          3815698597,\n          1832272475,\n          945613159,\n          136487868,\n          1731202674,\n          3903788721,\n          2182062801,\n          1489904681,\n          708728146,\n          1980483838,\n          1269587876,\n          3424059671,\n          3167970027,\n          3314237818,\n          161588255,\n          1347661301,\n          1126717335,\n          1593064253],\n    'b': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          1184217959,\n          795322907,\n          2681969582,\n          1479728863,\n          915549410,\n          1616093956,\n          1998008578,\n          566339276],\n    'k': 6},\n   [42, 16, 42, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          2958152150,\n          1105148405,\n          1551545311,\n          2382410247,\n          299374495,\n          3902367104,\n          3814609907,\n          616469427,\n          2903262975,\n          2673828359],\n    'b': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          1904501607,\n          2415525956,\n          972943297,\n          1101134287,\n          4209348669],\n    'k': 4},\n   [12, 12, 13, 6]],\n  ['streams 1 k=5',\n   {'a': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          3882412494,\n          3638249284,\n          629708383,\n          2652904385,\n          619827854,\n          2252659737,\n          4038367328,\n          751384629,\n          2736132274,\n          2052511795,\n          1546656212,\n          2490980400,\n          1192536461,\n          3397803296,\n          3575214874],\n    'b': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          801257707,\n          231860101,\n          1552367569,\n          2200650299,\n          1300574527,\n          1169595163,\n          1486586779],\n    'k': 5},\n   [14, 14, 23, 5]],\n  ['streams 2 k=3',\n   {'a': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795,\n          3366336454,\n          3360405550,\n          3252767639],\n    'b': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795],\n    'k': 3},\n   [4, 4, 4, 4]],\n  ['streams 3 k=6',\n   {'a': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          2859580621,\n          3296482680,\n          2191809106,\n          4155174719,\n          3651321607,\n          3668767012,\n          3871583709,\n          53568284,\n          232037959,\n          2442976016,\n          217741541,\n          3800768541,\n          2101516655,\n          2409083912,\n          918078055,\n          2969028849,\n          3001715579,\n          3922319082,\n          2100936555,\n          2284049623,\n          3774876442,\n          3238172673,\n          3672802287,\n          3806827876,\n          2442511505,\n          3389659053,\n          1412588383,\n          1682740534,\n          1107531143],\n    'b': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          321792195,\n          4055119656,\n          4005216604,\n          4067339772,\n          2438348428,\n          2893845634,\n          4168021051,\n          1191737207],\n    'k': 6},\n   [15, 9, 19, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          874550077,\n          874052348,\n          2099297276,\n          2917681254,\n          3461079448,\n          4523874,\n          1892412104,\n          1348947199,\n          2220012561,\n          4274378431],\n    'b': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          320314762,\n          2913424927,\n          3760403017,\n          3874375803,\n          3498294633],\n    'k': 4},\n   [15, 8, 15, 4]],\n  ['streams 1 k=5',\n   {'a': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          429269052,\n          4120988501,\n          2192756914,\n          2080257154,\n          215643658,\n          2236181558,\n          3506517446,\n          3204080191,\n          2539102762,\n          1231819029,\n          129435166,\n          1969895105,\n          1451722624,\n          4208772152,\n          2008054505],\n    'b': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          3624728915,\n          4097927174,\n          3560188535,\n          2101457494,\n          1008357362,\n          2961406180,\n          2250944138],\n    'k': 5},\n   [45, 13, 45, 27]],\n  ['streams 2 k=3',\n   {'a': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124,\n          163959442,\n          4243274568,\n          1097577740],\n    'b': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124],\n    'k': 3},\n   [28, 28, 28, 28]],\n  ['streams 3 k=6',\n   {'a': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          4076278131,\n          1681936286,\n          3644273863,\n          1144985545,\n          1058589555,\n          2372866836,\n          2747157307,\n          319015226,\n          1616345963,\n          3215957022,\n          2575778964,\n          2002333856,\n          105152923,\n          971771153,\n          3904739092,\n          139512839,\n          3596088601,\n          3125993293,\n          3698817286,\n          571115313,\n          2651377839,\n          404892510,\n          335085347,\n          3997319691,\n          423428202,\n          1253418186,\n          3736875704,\n          2512119594,\n          3432728552],\n    'b': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          2190917676,\n          1217641816,\n          2195352441,\n          1962797028,\n          1369215451,\n          146219861,\n          2422264426,\n          2740291298],\n    'k': 6},\n   [51, 10, 53, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          469293850,\n          3311372855,\n          3291632216,\n          3532104316,\n          792576761,\n          2383663819,\n          3796612359,\n          534629630,\n          3752143492,\n          3784451643],\n    'b': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          778329530,\n          4126190270,\n          369138172,\n          3244871941,\n          426427744],\n    'k': 4},\n   [5, 17, 24, 6]],\n  ['streams 1 k=5',\n   {'a': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          2365171429,\n          473117839,\n          1494688212,\n          3130081894,\n          3456600902,\n          1870835644,\n          1831585095,\n          856053019,\n          2401707901,\n          8291469,\n          994865049,\n          2075147938,\n          2281118336,\n          470394482,\n          2564274781],\n    'b': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          3616671026,\n          3377000285,\n          291138770,\n          4144176995,\n          410153163,\n          1894447883,\n          2251698],\n    'k': 5},\n   [36, 42, 59, 24]],\n  ['streams 2 k=3',\n   {'a': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100,\n          3123627193,\n          2732919500,\n          1916452664],\n    'b': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100],\n    'k': 3},\n   [25, 25, 25, 25]],\n  ['streams 3 k=6',\n   {'a': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          145050205,\n          1943098641,\n          2902033596,\n          942056830,\n          1094682071,\n          482655062,\n          1597161973,\n          2776457123,\n          540173509,\n          49617459,\n          3062849472,\n          721066780,\n          1881851915,\n          2771669550,\n          271560229,\n          4250659366,\n          849113494,\n          2890310823,\n          2849978717,\n          2813753673,\n          2723489037,\n          3843541794,\n          2539258177,\n          294140292,\n          131741950,\n          1174692757,\n          920449838,\n          3707669583,\n          2705746824],\n    'b': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          396707761,\n          853541794,\n          990402306,\n          2774188573,\n          1932619200,\n          40971593,\n          4209408016,\n          3008903819],\n    'k': 6},\n   [44, 22, 73, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          3402435104,\n          2615317700,\n          2901867586,\n          2191387195,\n          3244643901,\n          143617512,\n          4128185702,\n          3695416152,\n          3485519680,\n          1295479236],\n    'b': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          2172377362,\n          122431251,\n          2879905546,\n          3080363355,\n          742472857],\n    'k': 4},\n   [6, 6, 10, 2]],\n  ['streams 1 k=5',\n   {'a': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3856414966,\n          182199786,\n          3302563887,\n          3489282613,\n          3728782849,\n          2555406465,\n          3392268813,\n          468049757,\n          2334691707,\n          3652253765,\n          2830979039,\n          2618409554,\n          629677788,\n          1134145340,\n          1003578828],\n    'b': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3383921903,\n          1576598490,\n          1966729080,\n          3816342364,\n          951010101,\n          559264201,\n          3070372495],\n    'k': 5},\n   [17, 17, 27, 11]],\n  ['streams 2 k=3',\n   {'a': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371,\n          618180559,\n          2081251765,\n          530858903],\n    'b': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371],\n    'k': 3},\n   [14, 14, 14, 14]],\n  ['streams 3 k=6',\n   {'a': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          3886248964,\n          2353903802,\n          3929595655,\n          3522020961,\n          4226953245,\n          1619288587,\n          3373914572,\n          808857433,\n          2095738713,\n          3699811607,\n          2323854089,\n          4254321459,\n          2563706603,\n          1910759716,\n          2164426481,\n          690823666,\n          2412713602,\n          1704719407,\n          2407797195,\n          541403854,\n          3575208143,\n          381803083,\n          3474890246,\n          3033023633,\n          2039329698,\n          3301104757,\n          1308497545,\n          1688068524,\n          2659577736],\n    'b': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          923787522,\n          3928497192,\n          1582544665,\n          3091940628,\n          1369092784,\n          2483888591,\n          2347320516,\n          1678251482],\n    'k': 6},\n   [13, 13, 16, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]]]\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":"ec4fd9e25ef3c88447d7d8016f7210714f9324a2a34a4ea3aef1ff6546ed2683","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    def kept(hs):\n        return sorted(set(hs))[:k]\n    def est(vals):\n        if len(vals) < k:\n            return len(vals)\n        return round((k - 1) * 2 ** 32 / vals[k - 1])\n    A = kept(x['a'])\n    B = kept(x['b'])\n    U = sorted(set(A) | set(B))[:k]\n    eu = est(U)\n    if len(U) < k:\n        inter = len(set(A) & set(B))\n    else:\n        both = sum(1 for v in U if v in A and v in B)\n        inter = round(both / k * eu)\n    return [est(A), est(B), eu, inter]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['streams 0 k=4',\n   {'a': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          2991703416,\n          247407200,\n          502807838,\n          953930153,\n          4276337012,\n          825867426,\n          927935964,\n          767117601,\n          1349057482,\n          512140804],\n    'b': [767117601,\n          1349057482,\n          512140804,\n          2709330522,\n          97797847,\n          3243866592,\n          2367279148,\n          2430077702,\n          2971523655,\n          1478379009],\n    'k': 4},\n   [25, 10, 25, 12]],\n  ['streams 1 k=5',\n   {'a': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          844670565,\n          1574495990,\n          3092220355,\n          1623550118,\n          1677170996,\n          355484359,\n          1577212364,\n          222802868,\n          3302194479,\n          1232086826,\n          4029593972,\n          846568436,\n          2280170916,\n          2039090929,\n          2369642582],\n    'b': [2280170916,\n          2039090929,\n          2369642582,\n          1720999519,\n          2642080423,\n          1889774005,\n          2089713092,\n          881963964,\n          3736327325,\n          4143402618,\n          3225214513,\n          2668680618,\n          690502660,\n          4038350892,\n          2109753841],\n    'k': 5},\n   [19, 8, 20, 0]],\n  ['streams 2 k=3',\n   {'a': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492,\n          2831125304,\n          3278849932,\n          2146240677],\n    'b': [2831125304,\n          3278849932,\n          2146240677,\n          1030875024,\n          3846626178,\n          118622987,\n          1526835452,\n          1968349859,\n          112867492],\n    'k': 3},\n   [8, 8, 8, 8]],\n  ['streams 3 k=6',\n   {'a': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          3263214743,\n          1485141222,\n          507376609,\n          870194170,\n          405495016,\n          463928501,\n          3212162911,\n          200606854,\n          3827729694,\n          3442164173,\n          3023093882,\n          3815698597,\n          1832272475,\n          945613159,\n          136487868,\n          1731202674,\n          3903788721,\n          2182062801,\n          1489904681,\n          708728146,\n          1980483838,\n          1269587876,\n          3424059671,\n          3167970027,\n          3314237818,\n          161588255,\n          1347661301,\n          1126717335,\n          1593064253],\n    'b': [1347661301,\n          1126717335,\n          1593064253,\n          3578257729,\n          1184217959,\n          795322907,\n          2681969582,\n          1479728863,\n          915549410,\n          1616093956,\n          1998008578,\n          566339276],\n    'k': 6},\n   [42, 16, 42, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          2958152150,\n          1105148405,\n          1551545311,\n          2382410247,\n          299374495,\n          3902367104,\n          3814609907,\n          616469427,\n          2903262975,\n          2673828359],\n    'b': [616469427,\n          2903262975,\n          2673828359,\n          389501480,\n          3344127933,\n          1904501607,\n          2415525956,\n          972943297,\n          1101134287,\n          4209348669],\n    'k': 4},\n   [12, 12, 13, 6]],\n  ['streams 1 k=5',\n   {'a': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          3882412494,\n          3638249284,\n          629708383,\n          2652904385,\n          619827854,\n          2252659737,\n          4038367328,\n          751384629,\n          2736132274,\n          2052511795,\n          1546656212,\n          2490980400,\n          1192536461,\n          3397803296,\n          3575214874],\n    'b': [1192536461,\n          3397803296,\n          3575214874,\n          1217859995,\n          3883808108,\n          1269760818,\n          296997750,\n          1572046585,\n          801257707,\n          231860101,\n          1552367569,\n          2200650299,\n          1300574527,\n          1169595163,\n          1486586779],\n    'k': 5},\n   [14, 14, 23, 5]],\n  ['streams 2 k=3',\n   {'a': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795,\n          3366336454,\n          3360405550,\n          3252767639],\n    'b': [3366336454,\n          3360405550,\n          3252767639,\n          2239802314,\n          1962451971,\n          4237034881,\n          2990495608,\n          2652720588,\n          2235033795],\n    'k': 3},\n   [4, 4, 4, 4]],\n  ['streams 3 k=6',\n   {'a': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          2859580621,\n          3296482680,\n          2191809106,\n          4155174719,\n          3651321607,\n          3668767012,\n          3871583709,\n          53568284,\n          232037959,\n          2442976016,\n          217741541,\n          3800768541,\n          2101516655,\n          2409083912,\n          918078055,\n          2969028849,\n          3001715579,\n          3922319082,\n          2100936555,\n          2284049623,\n          3774876442,\n          3238172673,\n          3672802287,\n          3806827876,\n          2442511505,\n          3389659053,\n          1412588383,\n          1682740534,\n          1107531143],\n    'b': [1412588383,\n          1682740534,\n          1107531143,\n          3554458900,\n          321792195,\n          4055119656,\n          4005216604,\n          4067339772,\n          2438348428,\n          2893845634,\n          4168021051,\n          1191737207],\n    'k': 6},\n   [15, 9, 19, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          874550077,\n          874052348,\n          2099297276,\n          2917681254,\n          3461079448,\n          4523874,\n          1892412104,\n          1348947199,\n          2220012561,\n          4274378431],\n    'b': [1348947199,\n          2220012561,\n          4274378431,\n          1679674411,\n          803241050,\n          320314762,\n          2913424927,\n          3760403017,\n          3874375803,\n          3498294633],\n    'k': 4},\n   [15, 8, 15, 4]],\n  ['streams 1 k=5',\n   {'a': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          429269052,\n          4120988501,\n          2192756914,\n          2080257154,\n          215643658,\n          2236181558,\n          3506517446,\n          3204080191,\n          2539102762,\n          1231819029,\n          129435166,\n          1969895105,\n          1451722624,\n          4208772152,\n          2008054505],\n    'b': [1451722624,\n          4208772152,\n          2008054505,\n          153986199,\n          31834739,\n          1286658403,\n          379682339,\n          3141003873,\n          3624728915,\n          4097927174,\n          3560188535,\n          2101457494,\n          1008357362,\n          2961406180,\n          2250944138],\n    'k': 5},\n   [45, 13, 45, 27]],\n  ['streams 2 k=3',\n   {'a': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124,\n          163959442,\n          4243274568,\n          1097577740],\n    'b': [163959442,\n          4243274568,\n          1097577740,\n          311555763,\n          710797651,\n          965433560,\n          3806058722,\n          449325668,\n          242872124],\n    'k': 3},\n   [28, 28, 28, 28]],\n  ['streams 3 k=6',\n   {'a': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          4076278131,\n          1681936286,\n          3644273863,\n          1144985545,\n          1058589555,\n          2372866836,\n          2747157307,\n          319015226,\n          1616345963,\n          3215957022,\n          2575778964,\n          2002333856,\n          105152923,\n          971771153,\n          3904739092,\n          139512839,\n          3596088601,\n          3125993293,\n          3698817286,\n          571115313,\n          2651377839,\n          404892510,\n          335085347,\n          3997319691,\n          423428202,\n          1253418186,\n          3736875704,\n          2512119594,\n          3432728552],\n    'b': [3736875704,\n          2512119594,\n          3432728552,\n          1249721439,\n          2190917676,\n          1217641816,\n          2195352441,\n          1962797028,\n          1369215451,\n          146219861,\n          2422264426,\n          2740291298],\n    'k': 6},\n   [51, 10, 53, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          469293850,\n          3311372855,\n          3291632216,\n          3532104316,\n          792576761,\n          2383663819,\n          3796612359,\n          534629630,\n          3752143492,\n          3784451643],\n    'b': [534629630,\n          3752143492,\n          3784451643,\n          3707448500,\n          3478884196,\n          778329530,\n          4126190270,\n          369138172,\n          3244871941,\n          426427744],\n    'k': 4},\n   [5, 17, 24, 6]],\n  ['streams 1 k=5',\n   {'a': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          2365171429,\n          473117839,\n          1494688212,\n          3130081894,\n          3456600902,\n          1870835644,\n          1831585095,\n          856053019,\n          2401707901,\n          8291469,\n          994865049,\n          2075147938,\n          2281118336,\n          470394482,\n          2564274781],\n    'b': [2281118336,\n          470394482,\n          2564274781,\n          1456576635,\n          76225771,\n          1929399051,\n          3087256315,\n          11795723,\n          3616671026,\n          3377000285,\n          291138770,\n          4144176995,\n          410153163,\n          1894447883,\n          2251698],\n    'k': 5},\n   [36, 42, 59, 24]],\n  ['streams 2 k=3',\n   {'a': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100,\n          3123627193,\n          2732919500,\n          1916452664],\n    'b': [3123627193,\n          2732919500,\n          1916452664,\n          2995221416,\n          344825209,\n          1320214633,\n          116279824,\n          3826515764,\n          83053100],\n    'k': 3},\n   [25, 25, 25, 25]],\n  ['streams 3 k=6',\n   {'a': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          145050205,\n          1943098641,\n          2902033596,\n          942056830,\n          1094682071,\n          482655062,\n          1597161973,\n          2776457123,\n          540173509,\n          49617459,\n          3062849472,\n          721066780,\n          1881851915,\n          2771669550,\n          271560229,\n          4250659366,\n          849113494,\n          2890310823,\n          2849978717,\n          2813753673,\n          2723489037,\n          3843541794,\n          2539258177,\n          294140292,\n          131741950,\n          1174692757,\n          920449838,\n          3707669583,\n          2705746824],\n    'b': [920449838,\n          3707669583,\n          2705746824,\n          603387996,\n          396707761,\n          853541794,\n          990402306,\n          2774188573,\n          1932619200,\n          40971593,\n          4209408016,\n          3008903819],\n    'k': 6},\n   [44, 22, 73, 0]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]],\n [['streams 0 k=4',\n   {'a': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          3402435104,\n          2615317700,\n          2901867586,\n          2191387195,\n          3244643901,\n          143617512,\n          4128185702,\n          3695416152,\n          3485519680,\n          1295479236],\n    'b': [3695416152,\n          3485519680,\n          1295479236,\n          2096590373,\n          3787333106,\n          2172377362,\n          122431251,\n          2879905546,\n          3080363355,\n          742472857],\n    'k': 4},\n   [6, 6, 10, 2]],\n  ['streams 1 k=5',\n   {'a': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3856414966,\n          182199786,\n          3302563887,\n          3489282613,\n          3728782849,\n          2555406465,\n          3392268813,\n          468049757,\n          2334691707,\n          3652253765,\n          2830979039,\n          2618409554,\n          629677788,\n          1134145340,\n          1003578828],\n    'b': [629677788,\n          1134145340,\n          1003578828,\n          4058355717,\n          2251438880,\n          2144550018,\n          3171525108,\n          367867543,\n          3383921903,\n          1576598490,\n          1966729080,\n          3816342364,\n          951010101,\n          559264201,\n          3070372495],\n    'k': 5},\n   [17, 17, 27, 11]],\n  ['streams 2 k=3',\n   {'a': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371,\n          618180559,\n          2081251765,\n          530858903],\n    'b': [618180559,\n          2081251765,\n          530858903,\n          86152431,\n          2519876564,\n          1646187280,\n          3524098075,\n          1367524039,\n          2583752371],\n    'k': 3},\n   [14, 14, 14, 14]],\n  ['streams 3 k=6',\n   {'a': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          3886248964,\n          2353903802,\n          3929595655,\n          3522020961,\n          4226953245,\n          1619288587,\n          3373914572,\n          808857433,\n          2095738713,\n          3699811607,\n          2323854089,\n          4254321459,\n          2563706603,\n          1910759716,\n          2164426481,\n          690823666,\n          2412713602,\n          1704719407,\n          2407797195,\n          541403854,\n          3575208143,\n          381803083,\n          3474890246,\n          3033023633,\n          2039329698,\n          3301104757,\n          1308497545,\n          1688068524,\n          2659577736],\n    'b': [1308497545,\n          1688068524,\n          2659577736,\n          1794751184,\n          923787522,\n          3928497192,\n          1582544665,\n          3091940628,\n          1369092784,\n          2483888591,\n          2347320516,\n          1678251482],\n    'k': 6},\n   [13, 13, 16, 3]],\n  ['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],\n  ['exactly k distinct',\n   {'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},\n   [29, 2, 43, 14]],\n  ['shared value beyond union sketch',\n   {'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},\n   [14, 14, 43, 0]],\n  ['duplicated small hashes',\n   {'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},\n   [6, 954437177, 954437177, 318145726]]]]\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-kmv-distinct-union-sketch","generated_at":"2026-09-29T14:48:45.839866+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"KMV sketches power approximate COUNT(DISTINCT) with set operations in analytics engines; the unbiased (k-1)/v_k form and the union rule are easy to get subtly wrong.","repair":"Take the k smallest distinct values of the combined kept sets.","root_cause":"The union concatenates both kept lists without de-duplication.","sha256":"ffd89b52e6e1cc6c5684d6cccd5d195e82d6d84c88cdb4a5ebe66f5823b376b1","title":"K-minimum-values distinct counting: union keeps shared hashes twice · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":44.105,"exit_code":1,"observations":[{"actual":[25,10,25,12],"check":"streams 0 k=4","expected":[25,10,25,12],"passed":true},{"actual":[19,8,20,4],"check":"streams 1 k=5","expected":[19,8,20,0],"passed":false},{"actual":[8,8,8,8],"check":"streams 2 k=3","expected":[8,8,8,8],"passed":true},{"actual":[42,16,42,0],"check":"streams 3 k=6","expected":[42,16,42,0],"passed":true},{"actual":[3,2,4,1],"check":"small exact sets","expected":[3,2,4,1],"passed":true},{"actual":[29,2,43,14],"check":"exactly k distinct","expected":[29,2,43,14],"passed":true},{"actual":[14,14,43,14],"check":"shared value beyond union sketch","expected":[14,14,43,0],"passed":false},{"actual":[6,954437177,954437177,318145726],"check":"duplicated small hashes","expected":[6,954437177,954437177,318145726],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"streams 0 k=4\", \"actual\": [25, 10, 25, 12], \"expected\": [25, 10, 25, 12], \"passed\": true}, {\"check\": \"streams 1 k=5\", \"actual\": [19, 8, 20, 4], \"expected\": [19, 8, 20, 0], \"passed\": false}, {\"check\": \"streams 2 k=3\", \"actual\": [8, 8, 8, 8], \"expected\": [8, 8, 8, 8], \"passed\": true}, {\"check\": \"streams 3 k=6\", \"actual\": [42, 16, 42, 0], \"expected\": [42, 16, 42, 0], \"passed\": true}, {\"check\": \"small exact sets\", \"actual\": [3, 2, 4, 1], \"expected\": [3, 2, 4, 1], \"passed\": true}, {\"check\": \"exactly k distinct\", \"actual\": [29, 2, 43, 14], \"expected\": [29, 2, 43, 14], \"passed\": true}, {\"check\": \"shared value beyond union sketch\", \"actual\": [14, 14, 43, 14], \"expected\": [14, 14, 43, 0], \"passed\": false}, {\"check\": \"duplicated small hashes\", \"actual\": [6, 954437177, 954437177, 318145726], \"expected\": [6, 954437177, 954437177, 318145726], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.073,"exit_code":1,"observations":[{"actual":[25,10,26,13],"check":"streams 0 k=4","expected":[25,10,25,12],"passed":false},{"actual":[19,8,20,0],"check":"streams 1 k=5","expected":[19,8,20,0],"passed":true},{"actual":[8,8,72,72],"check":"streams 2 k=3","expected":[8,8,8,8],"passed":false},{"actual":[42,16,42,0],"check":"streams 3 k=6","expected":[42,16,42,0],"passed":true},{"actual":[3,2,419021200,167608480],"check":"small exact sets","expected":[3,2,4,1],"passed":false},{"actual":[29,2,86,57],"check":"exactly k distinct","expected":[29,2,43,14],"passed":false},{"actual":[14,14,43,0],"check":"shared value beyond union sketch","expected":[14,14,43,0],"passed":true},{"actual":[6,954437177,1073741824,715827883],"check":"duplicated small hashes","expected":[6,954437177,954437177,318145726],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"streams 0 k=4\", \"actual\": [25, 10, 26, 13], \"expected\": [25, 10, 25, 12], \"passed\": false}, {\"check\": \"streams 1 k=5\", \"actual\": [19, 8, 20, 0], \"expected\": [19, 8, 20, 0], \"passed\": true}, {\"check\": \"streams 2 k=3\", \"actual\": [8, 8, 72, 72], \"expected\": [8, 8, 8, 8], \"passed\": false}, {\"check\": \"streams 3 k=6\", \"actual\": [42, 16, 42, 0], \"expected\": [42, 16, 42, 0], \"passed\": true}, {\"check\": \"small exact sets\", \"actual\": [3, 2, 419021200, 167608480], \"expected\": [3, 2, 4, 1], \"passed\": false}, {\"check\": \"exactly k distinct\", \"actual\": [29, 2, 86, 57], \"expected\": [29, 2, 43, 14], \"passed\": false}, {\"check\": \"shared value beyond union sketch\", \"actual\": [14, 14, 43, 0], \"expected\": [14, 14, 43, 0], \"passed\": true}, {\"check\": \"duplicated small hashes\", \"actual\": [6, 954437177, 1073741824, 715827883], \"expected\": [6, 954437177, 954437177, 318145726], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":41.923,"exit_code":0,"observations":[{"actual":[25,10,25,12],"check":"streams 0 k=4","expected":[25,10,25,12],"passed":true},{"actual":[19,8,20,0],"check":"streams 1 k=5","expected":[19,8,20,0],"passed":true},{"actual":[8,8,8,8],"check":"streams 2 k=3","expected":[8,8,8,8],"passed":true},{"actual":[42,16,42,0],"check":"streams 3 k=6","expected":[42,16,42,0],"passed":true},{"actual":[3,2,4,1],"check":"small exact sets","expected":[3,2,4,1],"passed":true},{"actual":[29,2,43,14],"check":"exactly k distinct","expected":[29,2,43,14],"passed":true},{"actual":[14,14,43,0],"check":"shared value beyond union sketch","expected":[14,14,43,0],"passed":true},{"actual":[6,954437177,954437177,318145726],"check":"duplicated small hashes","expected":[6,954437177,954437177,318145726],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"streams 0 k=4\", \"actual\": [25, 10, 25, 12], \"expected\": [25, 10, 25, 12], \"passed\": true}, {\"check\": \"streams 1 k=5\", \"actual\": [19, 8, 20, 0], \"expected\": [19, 8, 20, 0], \"passed\": true}, {\"check\": \"streams 2 k=3\", \"actual\": [8, 8, 8, 8], \"expected\": [8, 8, 8, 8], \"passed\": true}, {\"check\": \"streams 3 k=6\", \"actual\": [42, 16, 42, 0], \"expected\": [42, 16, 42, 0], \"passed\": true}, {\"check\": \"small exact sets\", \"actual\": [3, 2, 4, 1], \"expected\": [3, 2, 4, 1], \"passed\": true}, {\"check\": \"exactly k distinct\", \"actual\": [29, 2, 43, 14], \"expected\": [29, 2, 43, 14], \"passed\": true}, {\"check\": \"shared value beyond union sketch\", \"actual\": [14, 14, 43, 0], \"expected\": [14, 14, 43, 0], \"passed\": true}, {\"check\": \"duplicated small hashes\", \"actual\": [6, 954437177, 954437177, 318145726], \"expected\": [6, 954437177, 954437177, 318145726], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}