Задачник Базовый курс EN

Оценка по хешам

Сервис хочет знать, сколько разных пользователей заходило за день, но хранить их идентификаторы не готов. Вместо этого каждый идентификатор превращают в 32-битный хеш и пропускают через HyperLogLog с m = 2^p регистрами. Посчитайте оценку по хешам за день.

Правила такие. Вначале все регистры — нули. Для хеша x старшие p бит — номер регистра j. В оставшихся 32 − p битах найдём первую единицу слева: её позиция, считая с единицы, — ранг; если все эти биты нулевые, ранг 32 − p + 1. Регистр j хранит наибольший ранг из попавших в него хешей. Оценка:

$$E = \frac{\alpha_m\, m^2}{\sum_{j} 2^{-M_j}},$$

где α₁₆ = 0,673, α₃₂ = 0,697, α₆₄ = 0,709, а для m ≥ 128 α_m = 0,7213/(1 + 1,079/m). Если E ≤ 2,5·m и есть пустые регистры — их V, — ответом служит m·ln(m/V).

Вход

В первой строке p и n (4 ≤ p ≤ 16, 1 ≤ n ≤ 2·10⁵). Во второй — n хешей, целые от 0 до 2³² − 1. Хеши могут повторяться: один пользователь заходит много раз.

Выход

Оценку E с абсолютной или относительной погрешностью не больше 10⁻⁶.

Примеры

Пример 1

Вход

4 13
1856729543 4260898977 1311859612 1723038053 3989769275 1723038053 1311859612 2160898233 3860162573 3989769275 1723038053 1311859612 1000745423

Выход

7.520058

Пример 2

Вход

4 1000
1732980223 1545853915 1583835433 3499470910 2204741051 124772194 1656885216 2564311215 3467332097 1292300686 1981340336 1970175902 3735864658 3989892609 2695076996 902519949 1975059463 289444178 3410984020 3834649315 1011356328 4023618091 2629109903 1285294846 963624500 2341895196 2336661896 4115055973 568395834 2129776185 2112694588 1836206571 3852685685 3313819082 3485114640 1411687386 4097322490 2611563065 1322691698 980870816 1469634395 1371699264 1230535773 2218764985 2793928913 253504731 2006744275 2938927838 1043176267 2382115974 1983813420 3836808173 3445910347 2072571142 1605524225 1136527740 843487496 3812376607 1712563315 2244969403 2241168382 2358563705 2517478841 1563775572 3187925283 3910981542 3703240474 3997757973 2724754035 3611203530 905561983 4040648480 2560949661 2219241430 3458635496 4176981695 2337068989 2168986281 1237729693 1899080151 4134045606 2072548802 2023549616 1357749360 1782403438 4240975149 689145340 1134939394 2109696693 121782654 3471950039 1721786031 634992147 673288547 850441487 2010210813 736957745 3791914628 4190524420 45780068 4138549705 2191006320 1150524073 4097489810 1126571172 3735129202 3727490550 280945505 2436348543 1274110638 2570616726 487696766 2649832722 2314286747 1208892862 1329377282 261516446 4280707810 4040748415 3390283167 3538395031 2614589237 3313051986 2297321420 3464751865 3933258654 1470322864 1503262537 609471482 675296522 3499052380 33863220 1511792619 3450045731 1908983276 2982275711 3544823239 720317452 1723134845 1439654636 3911421032 2456790880 197148340 347948341 488425777 434257245 1302988570 725071930 1447780234 3674536667 3366116430 888368684 3021495254 2648610048 2342041130 2114287313 2166570489 3440527502 4065273192 971913788 3515772787 2333057364 1687931342 1375255436 268916085 3384413378 518288448 3943049617 2921531109 1406722842 1662477921 2522851726 363528980 16317624 2090007468 1388199345 3845525528 4137719500 2793732506 1200675469 2947688869 2415346676 1733218943 2366254905 3150008414 416618539 2445768790 3248706404 3399318276 911517658 3181600885 3703911268 2710544580 3493488858 1293741959 2016722414 1884755727 1105204081 3010766658 2044134599 1566987393 950193377 1147170134 1047669907 901258029 1032200585 2765209954 405996316 3459701621 2388735964 3537017812 4266186850 2088709406 3296917726 75802308 1410821939 4229371332 1593960277 2751728679 2139543898 2555166458 1393505306 3677963060 3939424953 121634598 3264108984 3165797934 397594240 2241601119 1673869897 4278817245 4091641518 4252430278 3579627574 554988675 3445097460 4140304849 2316944754 4011467038 1111403707 2818579491 328873215 2727045954 636089163 787088777 1198126761 2520092714 2907882657 3613904431 2163862521 3461207747 3789699415 2657523459 146723792 110459006 2515343456 3442947011 211202643 290129357 2231488452 138907916 3357649352 1743055003 3204116288 3348101030 751053594 2867751895 418830365 753070453 1649664602 743173801 2749868738 2418161975 1683931575 2694373767 1633290584 1292486320 726855253 3092671317 868826554 2874218024 195514922 1665985651 2756236346 3006684332 2330571336 909968243 2793892025 4091229747 3573291809 3606928561 1294143329 3040348515 441406241 1076076586 2654417014 3383520671 2960721423 400983912 3231921297 2192658165 2601282293 3808468504 3703925431 3266385184 1198401532 873498370 3506333342 244683578 483989705 4076373157 3246599088 2733695631 2689927880 3530740184 2451908172 2315368811 3681610593 2422154303 196670815 3174275345 4137320002 4290501791 1310401892 2112923653 3934250567 2054286669 2541148058 687330985 2403967185 4021718952 3605946748 4084420411 1512475505 683192082 3260296729 1440064662 1633402928 262717358 64272159 3826404771 4232752898 3073946774 1388672785 4055102370 3657237398 1868059529 1322479372 3773848295 3208747959 2475450715 343903912 329894133 4019344747 1952315841 2404902763 3963299156 4256988365 2549759983 1500014499 2407723585 3444661635 337127160 2270149978 2020639050 459987932 2928169062 2852263489 265240866 992056946 2748173878 1630709322 3876160963 1043305288 479806108 3098855116 2806118694 789477852 704531637 4108739841 135869439 3495617975 1791354664 1496658547 2393984130 285675883 1892623073 3163352264 328921882 4125413224 953592261 1931267408 2594450350 193596886 934856791 3798788329 4208273602 2342574773 64355194 564065743 542369044 1780826687 3156036974 1708081453 3677351491 1875759091 1093070213 3363769466 615766207 3344172306 2182422973 472925128 150401741 1570945916 2928349101 3657774499 1347089787 1078894673 117059985 3097112875 2427215002 2024398439 1837292015 429081108 1499448824 1063286338 928006251 2731225954 3144655146 1149496209 2356691622 692502998 3827377005 2738905334 1819898243 4020235283 3977653501 2627887904 1015808326 2071932264 4160207055 257801281 2599633193 2524283484 3366712941 819909125 611739742 3267501523 755834377 1542541324 4006212479 2918856320 4010995968 3759070912 2901307534 1478361454 3516963578 2528630598 2480213233 2416871881 3145656642 3567618378 333539528 739392780 629702782 1543616066 2700393803 3125275366 435051187 3019113902 1886783341 388135864 1625904888 1604257705 1415498444 1509209125 39119575 3313300677 2151772611 4100975232 2619710147 4210089333 3240867837 1698738852 1425375527 3247832629 2355736569 1102109217 3291035960 4108867913 1756689883 4139123917 3752642419 1986045884 421909655 3620876080 3808541112 170296042 1203805569 3436721595 3111133281 2647557360 868165303 1783331586 2216273328 502494292 59102169 2921737221 1692294390 1369462957 3071529099 3466934889 1607275317 192497752 4097791317 2102154836 4200937674 1640648262 4216051004 3200233675 363828200 933819154 3226763548 2375565724 626599365 2351118747 2728543900 2146375477 801883344 4188537748 3376860479 1553392461 2758834666 2989110771 2587955378 480474660 11949233 831725986 2640980510 663088327 3860908586 2711828581 169269457 1344787072 2400285701 3664497280 2253138041 51393477 2781956964 3612486639 4276969221 2385011236 1013085535 827025220 1200570991 1926345448 4096198307 476892435 2040399097 1075036746 851525960 3597839767 1829654192 4166408890 4124732057 3095296962 1297961103 1244192346 2200754608 417372796 3703811730 1445224609 3540943085 1390020399 3975149780 1928851190 2507724353 3164899789 2843593650 3774293890 594981564 1022824831 722489301 4248127696 1915557791 4213151655 1211380523 928290423 4074649039 836516934 1816834299 2989310759 3355959108 3414563374 2679654320 3168542996 1275590018 9694510 3647817110 400327613 3925193985 3895921332 1265337390 4047734495 3914402088 1450068 272124321 2056791117 3524926954 3466070638 1224635111 883774092 772788953 1571005453 3991933364 3606891343 3485358198 2508410473 3706565142 3904691885 1819601885 245776358 3941388619 2531885211 284220289 148357035 1900008035 2789912363 4161570217 3413105235 4053620533 1746920403 228571072 3428835520 535219447 2415499089 3683718617 4114750071 2243380703 1547178762 503149603 2648155641 1546408970 1351041628 1828057881 3067798216 527275315 3672289278 205727016 1385554886 764362249 4017663385 2359174774 1493168483 2081486086 3610848113 1401177484 3438277429 3524833448 4170695795 360004251 702115528 3314838150 3318172375 4258611557 1828575190 197105923 3674212170 525025155 3660065925 1215901020 809166688 613635555 2973029846 2797243885 1340157499 3131293155 1899249407 73171369 2888448523 397863750 313985386 3630284821 3442362452 12623861 2703367576 2986840782 2637879819 3131468083 788597482 1819084816 2861471371 112723431 1203606672 1547489019 4089143548 1829520563 239789915 3967921553 2107746260 458561318 135564584 2552240733 558346765 3875873922 3009020558 972879944 4288064214 2891724120 3845920036 3612867933 4065964968 366330610 242814472 2017346376 1598631003 2357916196 842080802 2042850333 1505217753 2373560120 2682136602 207449910 882048932 471707535 2945840731 2579993595 2474120597 46139998 1133404869 2431477644 1962119002 1120410234 624919195 2522819791 4133874927 2745574102 3592701713 2603757482 2915591369 1052627509 2775800290 4138977254 687181945 1401526838 167011477 4121563260 172494077 3924490371 2944711949 3802797646 750387018 608520335 3139600771 3789579948 3579409035 571870167 4185529654 18822888 3119110982 371676962 790461581 1915635393 948930991 3976158861 193003654 2038915018 1213091395 710327043 541574269 2524522412 2762137573 1577081950 3413213388 157946266 2272172522 3360180434 3701995960 4255337255 4056568292 3039300409 390497888 3221203520 3572085329 3895358472 2059665682 824582199 1096787989 739550552 1792540595 2690191633 2219874573 580083599 1887291797 774303836 104621643 3208657182 1435831242 1814817380 3272271110 3024021357 3613288364 2870330746 1973815899 4090956373 3519941633 3970702953 1550511845 567975099 1504117218 3765812998 1300635949 265886520 2757937904 1177238850 139269041 3529908162 2328807226 4185872578 1139424434 2658037392 2772781312 3092665510 3692594281 3512379512 4245578537 4047292994 3253096877 3846579868 3665576384 3688254194 3418638833 666396628 3472585121 934820093 833985601 2149449904 968713221 3203274190 1043957437 1043743202 2494780663 1776519957 2358910091 2896741391 713727163 1841060385 1457968900 372205961 1450554988 3709107099 1169115139 3037277568 3334737234 1803091333 3908319315 4252238956 3816578158 1087101239 615227260 2512497940 853409493 1558062539 3177114354 159697987 113600954 4185734730 666993724 3691461364 3934251661 3014742059 186040275 1307928608 2816526577 3720529761 195844126 2048908507 891553095 2689044818 1147363527 1028779315 3955736757 2562387667 1662707045 2548389911 4194652119 942647714 3616279822 568546323 2263733927 2298887927 328262619 897636391 2630997900 2584738516 4052576109 3222453010 3283154551 2411812048 1422658244 3264376438 1838553295 1503278664 2544091284 991925460 1794295890 1345598360 2771522270 2678054617 406866531 3975783597 3062244934 2518352601 2988599232 3208213727 330607976 2479547265 2157241279 1534164425 239686945 4227915390 3940315906 3327058845 2119877386 722211032 1888106678 2671215995 2107844628 1886560738 4259091176 1679251200 4093832652 3579431217 610882217 1726051683 2195563112 3383512935 608712561 3865192068 369656441 3587578749 436602523 847315121 2906243439 1531622855 3391952983 383101369 1085649847 2348294710 2078673465 3100152913 1719054102 508132205 1395793773 1533135225 1964974803 3573773722 3952895694 1753052022 3086316109 1516333311 3996625086 3554133750 425607163 3225082839 3558863236 2072152203 4003950676 2503623181 1942430237 799397560 2384092598 3257775504 618643380 1722851288 877726754 773947050 3452033663 2078221644 3791730682 1510155731 1125429776 911145915 1095185299 3433935592 116493861 2076976587 326650974 122902941 71374776 79388107 1278940893 3225932458 1105684153 1235469810 1423989486 1561186503 2244884565 7688105 1475185630

Выход

1019.785618

Ограничения

Время · Python: 3000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Как получить старшие p бит 32-битного числа и младшие 32 − p? И где в младших битах первая единица слева, если известна длина числа в битах?

2Идея

Номер регистра — x >> (32 − p). Младшие биты — x & (2^32−p − 1). Если у этого числа L значащих бит (bit_length в Python, bits.Len32 в Go), то перед первой единицей стоит 32 − p − L нулей, и ранг — 32 − p − L + 1. Для нуля L = 0, и формула сама даёт 32 − p + 1. Дальше — формула из условия.

3Разбор

В первом примере — тринадцать слов фразы «в начале было слово…», из них восемь разных, и шестнадцать регистров. Хеши попадают в восемь регистров или меньше, восемь или больше регистров остаются пустыми, и «сырая» формула оценивает 14,3: при пустых регистрах она сильно завышает. Поправка для малых чисел, m·ln(m/V), даёт 7,5. Она пришла из другой задачи: если n шаров бросать в m корзин, пустыми останутся примерно m·e^−n/m, и n восстанавливается по числу пустых. Подробно — в статье о HyperLogLog.

Повторы хешей ничего не меняют: регистр берёт максимум. Поэтому HyperLogLog считает разные элементы, а не все: седьмой тест — сто двадцать тысяч заходов двадцати тысяч пользователей, и оценка около двадцати тысяч.

3+Решение

4Сложность

O(n + m): по одной операции на хеш и проход по регистрам.

5Типичные ошибки

Без поправки для малых чисел. Для одного-единственного хеша и 1024 регистров «сырая» формула даёт около 739 — третий тест.
Младшие биты как номер регистра. Условие говорит о старших. Для случайного хеша это всё равно, но ответ будет другим.
Ранг с нуля. Если первая единица стоит сразу, ранг 1, а не 0: ноль в регистре значит «ничего не попало».
Нулевой хвост. Если младшие биты все нулевые, ранг 32 − p + 1: шестой тест.

Алгоритмы задачи

SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача