Size: a a a

2021 April 03

AT

Anatoly Tomilov in pro.algorithms
В термодинамике есть проблема с формулой для энтропии для значений близких к нулю, тоже
источник

CD

Constantine Drozdov in pro.algorithms
Constantine Drozdov
Тут есть понятная схема (привет арифметическому кодированию) - мы считаем, что нам выписывают вещественное число по разрядам и как только мы следующий разряд знаем мы его отдаем
class Solution {
public:
   double acc = 0;
   double err = 1;
   
   void push_randk(int x, int k) {
       err = err / k;
       acc += err * x;
   }
   
   int pull_randk(int k) {
       double left = acc * k;
       double right = (acc + err) * k;
       int left_n = static_cast<int>(left);
       int right_n = static_cast<int>(right);
       if (left_n != right_n)
           return -1;
       
       acc = acc * k - left_n;        
       err = err * k;
       return left_n;
   }
   
   int rand10() {
       for (;;) {
           if (auto x = pull_randk(10); x != -1)
               return x + 1;
           
           push_randk(rand7() - 1, 7);
       }
   }
};

вот это по понятным причинам работает, да?
источник

CD

Constantine Drozdov in pro.algorithms
кажется, мои попытки записать это в целых достаточно неудачные :)
источник

CD

Constantine Drozdov in pro.algorithms
это 1.183618 на 9999 случайных
источник

AT

Anatoly Tomilov in pro.algorithms
Яннп. Поменьше бы разностей и побольше использования 1-based там, где это органично подходит, и я осилю)
источник

CD

Constantine Drozdov in pro.algorithms
Anatoly Tomilov
Яннп. Поменьше бы разностей и побольше использования 1-based там, где это органично подходит, и я осилю)
мы считаем, что на вход поступает вещественное число [0;1] и на выходе вещественное число [0;1]
источник

AT

Anatoly Tomilov in pro.algorithms
Constantine Drozdov
это 1.183618 на 9999 случайных
Если равномерное распределение генерируется, то это эквивалент моего)
источник

CD

Constantine Drozdov in pro.algorithms
наша задача перекодировать число из одной системы счисления в другую
источник

AT

Anatoly Tomilov in pro.algorithms
floatы здесь лишние, кмк
источник

CD

Constantine Drozdov in pro.algorithms
эта формулировка точна
источник

CD

Constantine Drozdov in pro.algorithms
источник

CD

Constantine Drozdov in pro.algorithms
Constantine Drozdov
class Solution {
public:
   double acc = 0;
   double err = 1;
   
   void push_randk(int x, int k) {
       err = err / k;
       acc += err * x;
   }
   
   int pull_randk(int k) {
       double left = acc * k;
       double right = (acc + err) * k;
       int left_n = static_cast<int>(left);
       int right_n = static_cast<int>(right);
       if (left_n != right_n)
           return -1;
       
       acc = acc * k - left_n;        
       err = err * k;
       return left_n;
   }
   
   int rand10() {
       for (;;) {
           if (auto x = pull_randk(10); x != -1)
               return x + 1;
           
           push_randk(rand7() - 1, 7);
       }
   }
};

вот это по понятным причинам работает, да?
если здесь даблы заменить на рациональные дроби, это будет просто точный способ без потери энтропии
источник

CD

Constantine Drozdov in pro.algorithms
ну и 1/11 + 1/11 преобразовать в 0 + 1 по причине 10/11 + 10/11 было и правда не лучшим решением
источник

AT

Anatoly Tomilov in pro.algorithms
LinkedHashMap кроме LRU cache для чего ещё полезен на практике?
источник

AM

Andre Macareno in pro.algorithms
Anatoly Tomilov
LinkedHashMap кроме LRU cache для чего ещё полезен на практике?
Предсказуемым порядком итерирования?
источник

AD

Alexey Dergunov in pro.algorithms
и не ТЛящимся итерированием
источник

DZ

Dmitry Zvorygin in pro.algorithms
Andre Macareno
Предсказуемым порядком итерирования?
Ещё, вроде, по нему можно итерироваться пока меняешь
источник
2021 April 04

С

Сергей in pro.algorithms
Приветствую! Уважаемы знатоки ) задача : есть 10^4 точек типа А на плоскости и 10^6 точек типа В.
Нужно найти среди точек типа А такую, возле которой наибольшее количество точек типа В на расстоянии не более 20 метров от неё. Расстояние стандартное - корень из суммы квадратов. Времени - 1 секунда. памяти тоже не особо - 64Мб.
Куда смотреть? я что-то потыкался с сортировками - фигня получается. Если использовать partition (С++ - то есть массив типа В каждый раз на 2 части делить- расстояние меньше-больше 20 ) - понятно по времени не прохожу. Может в полярные координаты перейти - там как-то квазилогарифмически искать ??
Учитывая, что задача учебная, использование конструкций типа дерева квадрантов видится излишне мудреным. Задача в разделе о хешах, если что..
источник

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Сергей
Приветствую! Уважаемы знатоки ) задача : есть 10^4 точек типа А на плоскости и 10^6 точек типа В.
Нужно найти среди точек типа А такую, возле которой наибольшее количество точек типа В на расстоянии не более 20 метров от неё. Расстояние стандартное - корень из суммы квадратов. Времени - 1 секунда. памяти тоже не особо - 64Мб.
Куда смотреть? я что-то потыкался с сортировками - фигня получается. Если использовать partition (С++ - то есть массив типа В каждый раз на 2 части делить- расстояние меньше-больше 20 ) - понятно по времени не прохожу. Может в полярные координаты перейти - там как-то квазилогарифмически искать ??
Учитывая, что задача учебная, использование конструкций типа дерева квадрантов видится излишне мудреным. Задача в разделе о хешах, если что..
А если поделить плоскость на квадраты 20*20? (Дальше я ещё не придумал)
источник

AT

Anatoly Tomilov in pro.algorithms
Сергей
Приветствую! Уважаемы знатоки ) задача : есть 10^4 точек типа А на плоскости и 10^6 точек типа В.
Нужно найти среди точек типа А такую, возле которой наибольшее количество точек типа В на расстоянии не более 20 метров от неё. Расстояние стандартное - корень из суммы квадратов. Времени - 1 секунда. памяти тоже не особо - 64Мб.
Куда смотреть? я что-то потыкался с сортировками - фигня получается. Если использовать partition (С++ - то есть массив типа В каждый раз на 2 части делить- расстояние меньше-больше 20 ) - понятно по времени не прохожу. Может в полярные координаты перейти - там как-то квазилогарифмически искать ??
Учитывая, что задача учебная, использование конструкций типа дерева квадрантов видится излишне мудреным. Задача в разделе о хешах, если что..
тебе нужна диаграмма Вороного
источник