Задать вопрос
wataru

Wataru

Разработчик на С++, экс-олимпиадник.
Ответы пользователя по тегу Алгоритмы

  • Как набрать нужную сумму из определенного количества монет?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно целочисленным линейным программированием решать. Бинплиском перебтрайте ответ (k), потом составляйте задачу, где у вас переменные: сколько монет каждого типа берём в каждый из k разменов. И еще будут неравенства, что каждый тип монет используется суммарно не больше, чем есть монет. Целевая функция - любая.

    Еще можно чуть по-другому: находите переблром все варианты одного размена. Потом у вас переменные будут, сколько раз каждый из вариантов берете. Ограничения на общий расход каждой монеты, а целевая функция - сумма переменных. Тут нет бинплиска, но тоже ЦЛП.
    Ответ написан
    Комментировать
    Комментировать

  • Доработка алгоритмической задачи JAVA. Требуется помощь >?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы не ищите 2 максимума, а перебирайте все пары заборов, считайте площадь и выбирайте лучший вариант. Это точно будет работать, хоть и за квадрат.

    Есть более хитрое решение за линию. Вот два самых крайних забора, они могут быть вариантом ответа. В противном случае можно выкинуть из рассмотрения кротчайший из них: если он и есть в максимальном ответе, то можно сдвинуть вторую границу на другой крайний отрезок и ответ не ухудшится.

    Поэтому решение будет из двух указателей - левого и правого. Пока они не сошлись, считайте площадь, сравнивайте ее с текущим ответом, а потом двигайте указатель на меньшее число в сторону второго.
    Ответ написан
    8 комментариев
    8 комментариев

  • Как вывести кратчайший путь в графе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вам надо в вашем алгоритме еще завести словарь, куда вы для каждой вершины будете складывать предыдущую в пути. Там, где вы соседнюю вершину кладете в очередь - там надо сарзу смотреть, посещенная она или нет и класть только если нет. Вот в этот момент вы знаете, что вы пришли в graph[city][i] из city.

    В конце циклом по этому массиву пердыдущих вершин пройдитесь и так получите путь в обратном порядке.
    Ответ написан
    3 комментария
    3 комментария

  • Алгоритмы и структуры данных. Сложность алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Потому что это 2 разных графика, 2 разных примера. Могли бы на втором обозвать вместо f и g f` и g`. Но авторам, наверно, было лень.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как проходить список и одновременно удалять элементы, в том числе впереди курсора?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Для такой вот работы идеально подходят связные списки. Там можно менять объект не портя никакие итераторы. Проблема только в том, что связные списки в питоне не реализованы на уровне языка. Поищите реализацию, наверняка есть удобный модуль со списками.

    Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:
    i = 0
while i < len(arr):
  x = arr[i]
  j = i+1
  while j < len(arr):
    if ShouldDelete(arr[j], arr[i]):
      del a[j]


    Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

    arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])


    Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

    А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

    Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.
    Ответ написан
    Комментировать
    Комментировать

  • Как транспонировать биты числа максимально быстро?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Занумеруйте все биты от 0 до 16. Потом транспонируйте эту матрицу. Потом посмотрите на разность результата и конца. Вот эти вот числа - это на сколько бит надо сдвинуть исходные биты, чтобы они встали на нужное место.
    0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

0 4 8 12
1 5 9 13
2 6 10 13
3 7 11 15

0 -3 -6 -9
3 0 -3 -6
...


    Все биты с одинаковым смещением можно подсчитать за 3 операции: Сдвиг, битовая маска и побитовое или в ответ.
    Я тут вижу 7 разных чисел -9,-6,-3,0,3,6,9.
    Например, для 0 и 3 у вас будет 
    answer = (source & 0x1248) | ((source << 3) | 0x2480) | ...


    Это не 8 пока еще операций, а аж 20. Возможно можно как-то еще их сгруппировать.

    Edit: Возможно, еще подход с таблицей будет быстрее. Для каждого из 16 возможных значений строк выдавайте битовое число - столбец, где эти 4 бита на позициях 0, 4, 8,12. Тогда ответ будет table[source&0xf0] | (table[(source>>4)&0xf] << 1) | (table[(source>>8)&0xf] << 2) | (table[(source>>12)&0xf] << 3).

    Тут 13 битовых операций и 4 чтения из памяти.
    Ответ написан
    2 комментария
    2 комментария

  • По какому принципу работает алгоритм с массивом очереди?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Много разных вариантов для структур данных. Например, кольцевой буфер. Или связный список. В этом случае можно удалять элемент с начала, не сдвигая все элементы в массиве.
    Ответ написан
    10 комментариев
    10 комментариев

  • Проверка на достижимость в направленном графе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Под конденсацией вы подразумеваете сжатие компонент сильной связности? Ну так у вас остается в конце какой-то произвольный DAG, а не дерево.

    В нем уже нельзя ввести поняие LCA вообще. Например, граф 0->2, 0->3, 1->2, 1->3. Тут для вершин 2 и 3 есть два общих предка: 0 и 1. И какой из них самый нижний?
    Ответ написан
    2 комментария
    2 комментария

  • Как называется такая алгоритмическая задача?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Задача о покрытии, наверное
    Ответ написан
    Комментировать
    Комментировать

  • Как называется это свойство набора кодов (словаря)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Нету у этого свойства никакого имени. Вы его слишком обобщили. Свойство - определенные символы не могут идти в начале слова. Вот и все.
    Ответ написан
    Комментировать
    Комментировать

  • Как устроено окто дерево? Как происходит отсечение видимых грайней?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вернуть все данные в узле. это же самое что дальше продолжать обходить все внутренние рекурсией или стеком узлы, и составить список. В чем профит то тогда? Как можно вернуть все данные по щелчку.


    Да, именно так, надо обойти все узлы дальне.
    Но при этом уже не надо проверять на видимость и код там попроще.

    А профит тут в том, что вы вот так вот обходите не все дерево. а только маленькую его часть.

    Окто дерево используется, чтобы отсечь те объекты, которые сзади или сбоку от камеры и точно не видны. Оно не помогает отсекать объекты, закрытые стеной. Тут, действительно, используется z-buffer.
    Ответ написан
    4 комментария
    4 комментария

  • Как разбить треугольник в прямоугольной области на N треугольников?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    mayton2019 правильно вам сказал: сначала пересеките треугольник и ваш прямоугольник. А потом триангулируйте.

    При пересечении у вас 2 выпуклых многоугольника. Алгоритм Сазерленда-Коэна тут немного перебор, ибо там один из многоугольников может быть не выпуклым. В вашем фиксированном случае скорее всего нет даже смысла заморачиваться с O(n log n) алгоритмом. Просто научитесь пересекать любые 2 отрезка. После чего пересеките каждую сторону треугольника с каждой стороной квадрата. Не надо считать за пересечение, если 2 отрезка параллельны и накладываются. Получите макимум 12 точек. К ним добавьте 3+4=7 вершины ваших многоугольников. Потом каждую точку проверьте на принадлежность обоим фигурам, и оставьте только те, которые лежат внутри или на границе. Потом постройте выпуклую оболочку из них (погуглите, эта-то задача вообще везде расписана).

    Что касается триангуляции, то у вас там получится выпуклый многоугольник. Так что можно, например, провести все хорды из одной вершины. Если же вам нужна какая-то особо "хорошая" триангуляция, то гуглите "Триангуляция Делоне". Этот алгоритм не строит очень приплюснутых треугольников, где это возможно.
    Ответ написан
    Комментировать
    Комментировать

  • Какой алгоритм приближенного решения Задачи Комивояжера выбрать для регулярных точек?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Раз человек легко прокладывает путь, то его можно просто захардкодить.

    Очевидно, что шаг от одной вершины к следующей будет не меньше 1, а значит кратчайший путь - тот, который ходит только горизонтально и вертикально. Если сетка не квадратная, то пусть ровно с 2m более длинных вертикаьных ребер будет мнимальным, потому что путь любую горизонтальнюу линию должен будет пересечь хотя бы в 2 точках.

    Ну и нарисуйте на бумаге 4 случая - когда высота и ширина четные или нечетные.
    Ответ написан
    Комментировать
    Комментировать

  • Когда целесообразно использовать именно такую реализацию DSU?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

    Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
    для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

    Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

    Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

    Т.е. вроде бы имеет смысл использовать пометки+списки, если у вас заметно больше проверок, чем объединений.

    Но на практике там выигрыша нет, ибо редко когда у вас сильно больше проверок. Да и, если у вас много проверок, то оценка O(log*n) - завышена, ведь если вы одну и ту же проверку повторяете, то там пути сжимаются и проверки работают уже за O(1).

    Таким образом, DSU от Тарьяна - лучше всех других структур на практике.
    Ответ написан
    7 комментариев
    7 комментариев

  • Как найти количество помеченных связных графов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

    Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

    Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

    Ражеванное объяснение:

    Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

    Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

    Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.
    Ответ написан
    6 комментариев
    6 комментариев

  • Какой правильный класс коллекции для хранения сортируемого списка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Достаточно списка. При принудительном обновлении берите первый элемент из списка. При любом обновлении перемещайте объект(ы) в конец. Можно перед началом из списка элемент удалить, а после конца в конце вернуть.

    Тут вам еще понадобится какая-то структура, чтобы по объекту получить итератор на него в списке. Если у вас объекты каким-то id определяются, то это может быть 
    std::unordered_map<int, std::list<Object>::iterator>
    .

    Вам нужен какой-то потокобезопасный список, да. Доставать из списка первые 4 элемента можно и циклом, по одному. Операция быстрая. Или пусть каждый поток сам достает из списка первый элемент, лоча для этого список.

    А вообще, есть и Lock-free списки. Если у вас обновления сами по себе очень быстрые операции, то такая структура может быть в итоге работать быстрее.

    Edit: простите за C++-ый код. Не заметил, что вопрос с java тегом. В общем, тут нужны какой-то список и hashmap из id в итераторы в этом листе.
    Ответ написан
    1 комментарий
    1 комментарий

  • Можно ли сравнить большие массивы по частям?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно и по частям. Какой там алгоритм сравнения, если все сразу известно? Два указателя, по одному в каждом массиве. Выкидываем меньшее число из двух - оно уникальное в своем массиве. Если два числа равны - вы нашли совпадение и двигайте оба.

    Можно алгоритм поставить "на паузу". Вам надо будет хранить указатель в первом массиве между порциями второго.
    Когда у вас приходят данные от второго массива, двигайте указатель в первом, пока число там меньше текущего во втором массиве. Если они равны, двигайте оба. Если число в первом больше - дивгайте указатель во втором массиве. И так пока один из массивов не кончится.

    Если сложно сохранять указатель в первом массиве между порциями второго, то можно первый элемент второго массива искать в первом через бин поиск - так вы получите индекс без его сохранения.
    Ответ написан
    Комментировать
    Комментировать

  • Как найти решение для задачи?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Rsa97 правильно написал про геометрический смысл. Но есть более быстрое решение за O(n log n), использующее метод заметающей прямой.

    Пересеките все прямоугольники с тем, который надо покрыть, отрезав от них торчащую наружу часть.

    Если числа в задаче большие или нецелые, то сначала через бинпоиск или хешмап замените все координаты по X и по Y на их порядковый номер в отсортированном массиве (отдельно по каждой оси). Эта операция называется "сжатие координат". Теперь у вас все координаты целые числа от 0 до 2*n.

    Потом примените алгоритм "заметающей прямой". Представьте, что вертикальная линия двигается слева-направо и "заметает" картинку. Вам надо отслеживать, какие прямоугольники ее пересекают в каждый момент времени и проверить, что вся прямая покрыта в каждый момент.

    Для этого каждый прямоугольник (X1, Y1, X2, Y2) создаст 2 события "открылся отрезок с Y1 до Y2 во время X1" и "закрылся отрезок с Y1 до Y2 во время X2". Эти все события вы сортируете по X и в таком порядке обрабатываете.

    Для отслеживания состояния прямой используйте дерево отрезков на минимум с отложенной суммой. Эта структура данных потребует массив на примерно 4n элементов для дерева с 2n листами. Каждая вершина будет хранить минимум на соответсвующем ей отрезке. При открытии прямоугольника вы должны добавить +1 на его отрезок. При закрытии - вычесть 1. Сначала открывайте прямоугольники, если время у событий одинаковое. Учитывайте это при сортировке. Так касающиеся по вертикали прямоугольники не создадут пустых мест.
    Если после обработки какого-либо события вы получили минимум в дереве отрезков 0 и следующее событие имеет большую координату по X - то какая-то часть оказалась не покрыта. Еще есть случай, если первое событие не X1=левая граница покрываемого прямоугольника, или последнее событие - не X2=правая граница всего прямоугольника. Тут тоже покрытия нет.

    Еще, аккуратно с целыми числами, чтобы если у вас 2 прямоугольника касаются горизонтальными сторонами - там пустое место не подсчиталось. Например, каждый лист дерева отвечает за единичный отрезок координат. Тогда изменяйте в дереве всегда отрезок от Y1 до Y2-1 для события с координатам Y1..Y2.
    Ответ написан
    7 комментариев
    7 комментариев

  • Каким алгоритмом воспользоваться для поиска вхождений диапазона чисел в другой диапазон?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Самое быстрое решение - с использованием двумерных структур данных, вроде двумерного дерева отрезков.

    Вы каждый отрезок представляете в виде точки на плоскости. Когда приходит новая точка, вам надо в квадрантах относительно нее (левый верхний и правый нижний) найти минимальный номер точки. При нахождени , она удаляется из мтруктуры данных и вы нашли ей пару. Иначе добаляйте новую точку в структуру данных.
    Ответ написан
    1 комментарий
    1 комментарий

  • Можно ли так доказывать правильность алгоритмов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если их нельзя переворачивать и при равенстве высот все-равно можно вложить (а не только строго меньшее), ио алгоритм правильный. Но доказательство не полное. Надо доказать, что любая неубывающая последовательность в этом массиве даст веладывающиеся прямоугольники.
    Ответ написан
    7 комментариев
    7 комментариев