Телеграмм чат группы proalgorithms страница 3426

IEEE Xplore опубликуют старые выпуски Computer Group News, которые есть только в бумажном виде. И они сфотали статью ^_^. спасибо за советы. Пока только MIT не дал ответа

источник

10:57пожаловаться #12

Evgenii Zheltonozhsk... in pro.algorithms

11:05пожаловаться #13

Alexey Dergunov in pro.algorithms

Kotomord_λapki

Можно ссылку? Интересно

https://acm.timus.ru/problem.aspx?space=1&num=1896

источник

11:26пожаловаться #14

‌‌Gleb Pilipets... in pro.algorithms

Kotomord_λapki

а зачем не дерево отрезков?

Сложнее реализовать + интересно с Фенвиком разобраться.

источник

11:33пожаловаться #15

‌‌Gleb Pilipets... in pro.algorithms

Alexey Dergunov

убрать иф с == , поменять/не поменять > на >=, прибавить 1/0/-1 к результату, в каком то сочетании будет правильно

Не думаю, что это сработает. Ладно, попробую лучше поддержку с другой стороны

источник

11:39пожаловаться #16

Kotomord_λapki in pro.algorithms

Alexey Dergunov

https://acm.timus.ru/problem.aspx?space=1&num=1896

спасидо

источник

11:49пожаловаться #17

‌‌Gleb Pilipets... in pro.algorithms

Задал вопрос на стек оверфлов

https://stackoverflow.com/questions/62911120/fenwick-treebit-find-the-smallest-index-with-given-cumulative-frequency-in-o

Stack Overflow

Fenwick tree(BIT). Find the smallest index with given cumulative frequency in O(logN)

let's say I have a BIT(Fenwick Tree) with non-negative values and I want to find the smallest index in it for given cumulative frequency in O(logN).
Now, I can do it O(log^2(N)) like this.
int l = ...

источник

12:12пожаловаться #18

Alexey Dergunov in pro.algorithms

int lowerBoundIndex(int s) {
    int i = 0;
    int step = 1 << 20;
    int curS = 0;
    while (step > 0) {
        if (i + step <= n && curS + t[i + step] < s) {
            curS += t[i + step];
            i += step;
        }
        step /= 2;
    }
    return i + 1;
}

источник

12:19пожаловаться #19

Alexey Dergunov in pro.algorithms

upperBound - меняем < на <=, возвращаем i

источник

12:20пожаловаться #20