CD
в смысле?
Size: a a a
2021 April 18
AT
частая хештаблица не поместится в 32 килобайта
AT
или хеш для неё будет дорогой или таблица будет большая
CD
если ты про то, что верхнюю границу искать как 2^2^шаг, то это начало решения, а дальше основная задача - как делать бинпоиск в настолько плохой локализации
EZ
Да, я уже понял
AT
число из
0..inf?CD
число в 2^2^20
CD
требование стоит относительно N, а не maxN
EZ
Не, не понял. Почему нельзя просто
1. Ищем верхнюю границу, так что 2^c < N < 2^2c
2. Ищем c<k<2c так что 2^k<N<2^(k+1)
3. Бинпоиск
1. Ищем верхнюю границу, так что 2^c < N < 2^2c
2. Ищем c<k<2c так что 2^k<N<2^(k+1)
3. Бинпоиск
CD
сколько второй поиск
CD
только не говори, что log c
CD
в общем, лень считать, оригинальное решение точно было красивее, вместо шагов 2-3 надо делать бинпоиск с весом h(k) = 1/k
CD
то есть делить сумму весов пополам
CD
видимо, ты это жульнически апроксимируешь
EZ
Ну вроде да
CD
очень похоже, потому что там получается если диапазон w ... w^2, то сумма 1/k по нему ln w, итого поиск от ln w до 1/N то есть N * ln w и в сумме log N + log ln w
EZ
Геометрическое среднее вместо арифметического типа?
CD
гармоническое среднее, наверное
CD
или геометрическое... хм