Ответы пользователя по тегу Алгоритмы
  • Как объединить списки, полученные от 2 REST API с параметрами `limit` и `offset`, и вернуть его, согласно параметрам `limit` и `offset`?

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

    Но, если вам надо обязательно вот так извращатся, то это практически задача с leetcode: https://leetcode.com/problems/median-of-two-sorted...

    Почитайте решения, погулите - есть куча видео с понятным разбором. Суть в бинарном поиске.

    У вас же тут надо не медиану найти, а k-ый элемент.
    У вас тут фактически дано 2 массива API1 и API2. Чтобы прочитать один (или несколько) элементов вам надо сделать запрос к АПИ.

    Вам надо найти offset-ый, offset+1 и т.д элементы в объедененном массиве.
    Для начала просто найдите offset-ый элемент. Зная его позиции в обоих массивах сделайте 2 запроса с этих
    позиций и данным limit. Потом как в задаче о слиянии двух массивов выведите первые limit.

    Во время бинпоиска делайте запросы с limit=1, а offset = индекс в массиве.

    Update:
    Забыл написать, тут у вас будет что-то около 2*log(offer+limit) запросов с limit=1 к разным апи, и потом еще 2 запроса с limit=limit из общего запроса.
    Ответ написан
    4 комментария
  • Как правильно удалять элементы хэш таблицы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Никак. Конечно, можно проверить, что там дальше ячейка пустая через k*k для всех возможных k (или что ячейка на (k-1)^2 назад пуста), но это слишком долго. И не сработает во всех случаях. Поэтому так и не делают вообще. Обычно "удаленные" значения убирают при перехешировании, которое все-равно придется делать при достаточном заполнении таблицы.
    Ответ написан
    3 комментария
  • Хэш-таблица без разрешения коллизий?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Нет. Ну, только если вы не будете заводить таблицу на 4 миллиарда с копейками элементов (2^32) и использовать тривиальную хеш-функцию.

    Потому что важно не столько количество элементов в таблице, а их значения. Их может быть 4 миллиарда различных. И даже только с 2 элементами я вам для любого меньшего размера таблицы найду 2 таких элемента, что у них хеш функция совпадет.

    Вообще, теоретически, для фиксированного набора элементов можно подобрать хеш-функцию без коллизий. Она тогда называется идеальная хеш-функция. И тогда размер таблицы может быть очень маленьким - аж до количества этих элементов. Но вам надо подбирать новую хеш-функцию для каждого набора хранимых чисел.
    Ответ написан
    Комментировать
  • Как оптимизировать алгоритм самонаведения ракеты?

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

    Обозначьте |MSL_VEL - TGT_VEL| за t.

    Получите уравнение TGT_DIR = (MSL_VEL-TGT_VEL)/t

    Преобразуйте: TGT_DIR*t = (MSL_VEL-TGT_VEL)

    Но тут неизвестные вектор MSL_VEL и t. Но они связаны, ведь t - это длина вектора. Обозначим неизвестный вектор MSL_VEL как (x, y, z) Значит:
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2

    Ну и еще вы знаете, что скорость ракеты фиксированная же:
    x^2+y^2+z^2 = MSL_SPEED^2

    У вас тут 4 неизвестных и аж 5 уравнений (ведь первое - это векторное уравнение):
    TGT_DIR_x*t = x - TGT_VEL_x
    TGT_DIR_y*t = y - TGT_VEL_y
    TGT_DIR_z*t = z - TGT_VEL_z
    t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2
    x^2+y^2+z^2 = MSL_SPEED^2


    Раскройте скобки в 4-ом, подставьте туда пятое и из первых трех выразите x, y, z:

    t^2 = MSL_SPEED^2+TGT_SPEED^2-2*TGT_VEL_x*(TGT_DIR_x -t*TGT_VEL_x)-... = MSL_SPEED^2+(1-2t)TGT_SPEED^2-2(TGT_DIR*TGT_VEL)


    Там в конце векторное произведение векторов. Дальше сами раскройте и получите квадратное уравнение на t. Решите его по школьной формуле. Если дискриминант отрицательный, то решения тупо нет. Слишком быстро цель улепетывает. Потом не забудьте проверить, чтобы t получилось положительное. Потом подставьте t в первые 3 уравнения и найдите искомые x, y, z.

    Еще можно так себе это все представить. Свяжем систему координат с целью. Тогда множество точек, куда может смотреть скорость ракеты - это сфера с центром в TGT_VEL и радиусом MSL_SPEED. Вам надо выбрать на этой сфере точку так, чтобы она была коллинеарна с вектором TGT_DIR. Т.е. у вас есть луч из центра координат вдоль векторо TGT_DIR. Вам надо найти где он пересечет сферу. Введите параметр t вдоль луча и дальше получите то же самое квадратное уравнение.
    Ответ написан
    2 комментария
  • Как выбрать диапазоны значений по вхождению значения в диапазон?

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

    Оно как раз позволяет быстро искать все отрезки, пересекающие данную точку, но изменять его очень тяжело. Хорошо, что вам это и не надо.
    Ответ написан
    Комментировать
  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    то в первом пункте мне не понятно как связаны индексы i и 2*i


    Если нумерация массива идет с 1, то два ребенка элемента i будут 2*i и 2*i+1. У вас же нумерация с 0, т.ч. у вас дети - 2*i+1 и 2*i+2.

    Первое условие достигается правильной расстановкой строгого и нестрогого неравнества в условиях в алгоритме.

    Похоже, проблема в том, что у вас нумерация с 0 и, если новый элемент оказывается итак максимальным, вы вернете индекс 0, вместо нужного 1. Если вы элемент вниз просеиваете, то у вас там +1 стоит в res.first, но изначально у вас-то там 0.

    Далее, вы вектор неправильно используете. Вы делаете reserve и потом работаете с пустым вектором, как-будто он фиксированного размера. Вам надо делать resize вместо reserve. Или еще лучше, вместо вашей переменной size вы используйте arr.size(). При изменении размера массива делайте pop_back() и push_back().
    Ответ написан
    8 комментариев
  • Как использовать двусвязный список в Buddy аллокаторе?

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

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

    Можно это в массиве делать и хранить указатели вперед-назад в двух элементах под двух buddy. У вас в списке же только один из парочки всегда может быть.
    Ответ написан
  • Как построить граф по его граням?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Как-то странно вы его релизовали. В самом алгоритме надо вершины и раскладывать на плоскости. Когда первый цикл укладываете - можно просто по большой окружности. Потом ребра или напрямую, если они внутри грани, или по дуге какой-то окружности вокруг.
    Ответ написан
  • Как ускорить поиск элементов из статичного string[] по подстроке?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Сначала объедините все ваши строки в одну через какой-то раздилитель, которого не может быть в искомой строке (можно и без него, но с ним код чуть проще будет). В конце поставьте этот же разделитель 2 раза. Вроде "строка1$строка2$строка3$...$строкаN$$".

    Вот уже ваша задача - быстро искать какую-то остроку в фиксированном тексте, а не куче строк.
    Тут есть много вариантов. Например, постройте суффиксное дерево алгоритмом Укконена. Вот эта ваша структура. При запросе, как в боре, поищите искомую строку в этом дереве. Если где-то перехода нет - вхождения вы не нашли. Если вы остановились на какой-то вершине (или ребре в дереве), то вам осталось каким-нибудь обходом в глубину найти все листья в поддереве этого места. Каждый лист соответствует вхождению. Еще при построении суффиксного дерева вы каждый лист пометите началом суффикса. Можно в тот же момент место в строке и конкатенаций перобразовать в номер исходной строки (например, бинпоиском по индексам начал строк в тексте. Или просто заведите массив, где для каждого символа в тексте при построении запишите, какая изначальная строка там была).

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

    Другой вариант - через преобразование Барроуза — Уилера. Вот есть лекция. Этот алгоритм часто упоминается в курсах по биоинформатике. Реализацию может даже найдете где-то. Потом можно найти номера исходных строк из индексов вхождений через тот же бинпоиск по сортированному массиву индексов начал всех строк в тексте.

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

    Учтите, что построение структуры данных тут будет в несколько раз медленнее простого for+Contains. Выигрыш вы получите, если у вас текст действительно статичный и вы в нем много раз что-то ищите.
    Ответ написан
    7 комментариев
  • Какой тип бинарного дерева используется для Buddy аллокатора?

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

    Его можно вообще без указателей реализовать в массиве. У блока с номером i два ребенка с номерами 2i+1 и 2i+2.

    Можно вообще битовый массив использовать для пометок.
    Ответ написан
    Комментировать
  • Как разместить N файлов по папкам?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это задача об упаковке. Она сложная. И ближе даже не к задаче о рюкзаке, а к задаче о мульти-рюкзаке. Для больших размеров файлов и N решения, кроме переборного, нет.

    Если N маленькое, то есть быстрые алгоритмы вроде Динамического Программирования. Но там и перебор будет не то, чтобы сильно медленнее.

    Если вам не важно получить абсолютно минимально возможное количество папок, то подойдет какое-нибудь жадное решение. Оно даст хорошее приближение. Скажем, вместо 30 идеальных папок вы часто получите 40.

    Например, кладите файлы в текущую папку, пока они туда помещаются. Потом создавайте следующую папку. Заполняйте ее, пока размер папки + размер следующего файла <= 2Mb.

    Можно всякие эвристики сюда навешивать: например, отсортиовали файлы по размеру. Жадно пихаем самые большие файлы, пока помещается. Потом жадно пихаем самые маленькие. Потом начинаем новую папку.
    Ответ написан
    Комментировать
  • Как декодировать матрицу?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В комментариях мы выяснили, что была матрица 3x4 из цифр от 1 до 9. над ней произвели одно из трех действий и выдали результат. Надо по нему восстановить исходную матрицу. Надо решить на одной конкретной матрице.

    Надо попробовать применить все 3 метода и посмотреть, какой из них даст матрицу из цифр 1-9.

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

    Вот так проделайте для 9^3 вариантов, если по пути получили числа не из диапазона 1-9, то можно дальше не считать, надо пробовать другой вариант для первого столбца.

    Чуть хуже для случая "стороны и диагонали не включая элемент". Все так же переберите 3 числа в первом столбце. Во втором столбце вы получаете 3 уравнения: сумма первых двух чисел известна из числа в первой строке. Сумма всех трех известна из числа для второй строки. Сумма двух последних - из последнего числа. Т.е. вам дано x+y=A, x+y+z=B, y+z=C. Отсюда элементарно z=B-A, x=B-C, y=A+C-B.

    Этот перебор отработает где-то за 1мс - довольно быстро.

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

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

    Изначально в стек поместите корень дерева и 0. Потом в цикле, пока стек не пуст, смотрите на вершину стека. Если там счетчик 0, то выводите вершину в ответ. Увеличивайте там счетчик на 1. Если он стал равен количеству детей у вершины, удаляйте ее из стека. Иначе добавляйте в стек вершину-ребенка с номером из счетчика с 0. Можно чуть по другому: выводите вершину при помещении ее в стек с 0. Но тогда надо отдельно вывести корень дерева.
    Ответ написан
    Комментировать
  • Как ускорить решение задачи "Детский праздник"?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Бинпоиск - правильная идея. Но вот вы плохо считаете, сколько шариков один работник надует за заданное время. Вы линейно по одному шарику надуваете, а можно за 2 действия: поделите время на ti*zi+ci - узнаете, сколько полных групп шариков надуется. Остаток отдельно подсчитайте, поделив на ti. Учтите только, что оставшееся время может быть прервано на отдыхе - не насчитайте там больше zi шаров по ощибке.

    Решение через кучи страдает той же проблемой - вы по одиночке каждый шар считаете, а их очень-очень много.
    Ответ написан
    3 комментария
  • Как решить задачу "Шестерки" с меньшими затратами памяти?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Выведите 6^2, 66^2 и так далее. N до 20 хотя бы. Посмотрите на числа. Можете ли вы угадать цифру на заданной позиции без подсчета всего числа?

    Подсказка, вы получите вот такие вот числа:
    36
    4356
    443556
    44435556
    4444355556
    444443555556
    44444435555556
    4444444355555556
    444444443555555556
    44444444435555555556
    4444444444355555555556
    444444444443555555555556
    44444444444435555555555556
    4444444444444355555555555556
    444444444444443555555555555556
    44444444444444435555555555555556
    4444444444444444355555555555555556
    444444444444444443555555555555555556
    44444444444444444435555555555555555556
    4444444444444444444355555555555555555556


    Этот паттерн можно и доказать. Надо лишь представить возводимое в квадрат число как (10**n-1)2/3 и применить чуть-чуть элементарной алгебры, вроде формулы квадрата разности.
    Ответ написан
    Комментировать
  • Как правильно рассчитать коэффициент полезного использования пространства?

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

    Можно ускорить алгоритм сжатием координат: вввпишите все x и y координаты всех углов блоков, отсортируйте и унифицируйте (отдельно по каждой оси). Потом замените все координаты в блоках на порядковый номер в массиве уникальных координат. Примените алгоритм выше, но в конце надо помнить, что каждая ячейка теперь не 1x1, а сколько-то больше по вертикали и горизонтали.
    Ответ написан
  • Задача о рюкзаке, используя 1-D массив?

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

    Этот трюк не всегда возможен. Например, если вам надо не только максимальный вес/цену найти, а еще и набор предметов. Восстановление ответа не всегда можно сделать лишь по последней строке.
    Ответ написан
  • Как найти наикратчайшие пути взвешенного орграфа, представленного матрицей инцидентности, используя алгоритм Дейкстры?

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

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

    Кстати, у вас матрица инцидентности неправильная: должно быть по 2 числа в каждой строке. Обычно ставят -цену у начальной вершины и +цену у конечной.
    Ответ написан
    4 комментария
  • В чем проблема в коде работы с графом?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.
    Ответ написан
  • Что не так с кодом, проверяющим логическую схему?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Во-первых, у вас цикл от 0 до 32 включительно. Т.е. вы на последней, 33-ей итерации пытаетесь преобразовать 0b100000 в bitset, фактически, второй раз учитывая вариант со всеми нолями. Вот почему вы получаете 33 а не 32.

    Во-вторых, у вас ошибка с тем, что вы из bitmask берете биты, которые есть числа 0 и 1 и проводите над ними битовые операции, а не логические. И это у вас там 32-битные числа же! Для | и & оно еще совпадает с вашими ожиданиями, а вот ~ обращает ВСЕ 32 бита числа.

    Поэтому ~(bitset[E] | bOrD) всегда выдаст или -1 или -2. Вы потом это пропустите через or, получите опять же -1 или -2 и в конце преобразуете это в bool. И вот тут-то оно всегда и станет true.

    Чтобы это исправить, или используйте логические операции (||, &&, !), или вместо ~x используйте x^1, или в самом конце возвращайте результат с &1, чтобы значения остальных бит ни на что не влияли.
    Ответ написан
    5 комментариев