Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Правильные ли ответы в рамках составления алгоритма?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В зависимости от уровня задающего задание, ваш ответ правильный или не совсем правильный.
    Да, именно if-ов сравнений 2N. Но внутри цикла for тоже закопано N сравнений. Как цикл-то работает? У него есть переменная счетчик и он ее сравнивает с граничным условием. Это хорошо видно на блок схеме - блок-цикл имеет 2 выхода. Значит в нем есть ветвление и, следовательно, сравнения.

    Так что более точный ответ 3N. Еще более точный ответ 4 N. Потому что функция readln тоже должна какие-то сравнения делать, чтобы остановить ввод на конце строки, но это уже nitpick, который от вас почти точно не ожидается.
    Ответ написан
    2 комментария
  • Как выполнить свертку сочетаний?

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

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

    Пусть общее количество карт - N.

    Для простоты понимания, давайте забудем про колоду, просто карты раздаются как-то в 2 кучки по N/2 карт. Это пригодится попозже. Удобнее не вероятность считать, а количество способов раздать карты. Потом надо будет поделить количество хороших способов на все способы.

    Сразу комбинаторно подсчитаем, сколько всего способов есть. Это просто количество всех различных колод. Гуглите "перестановки с повторениями". Формула будет такой:
    N!/ a[1]! ... a[n]!
    Раз мы на это число в конце будем делить, то сразу же считайте перевернутую формулу: подсчитайте факториал числа всех карт по модулю, обратите, умножьте на все маленькие факториалы.

    Теперь самое главное, подсчитаем количество способов раздать карты так, что у всех поровну уникальных карт.
    Динамическое программирование DP(k, t, i, j) - сколько способов раздать первые k типов карт так, что у первого игрока t карт всего, из них i уникальных, а у второго игрока j уникальных карт (при этом мы знаем, сколько у него всего карт - a[1]+...+a[k] - t).

    База:
    DP(0,0,0,0) = 1,
    DP(0,*,*,*) = 0


    Ответ:
    sum {i=1..n} DP(n, N/2, i, i)

    Пересчет:
    DP(k,t,i,j) = sum{v=0..min(a[k],t)} DP(k-1, t-v, i - {v>0}, j-{v < a[k]}) * C(t, v) * C(a[1]+a[2]+...+a[k]-t, a[k]-v)


    Тут надо объяснить: мы перебираем, сколько карт последнего типа досталось первому игроку: v. Это все разные колоды, поэтому их надо суммировать. Как бы убираем все карты этого последнего типа из рассмотрения. Что остается? То же самое ДП, но типов на 1 меньше, у первого игрока на v карт меньше и уникальные карты надо уменьшить на 1, если какому-то игроку хоть одна карта досталась. Но есть еще множители - это количество сочетаний. Эти самые v карт последнего типа могут быть на любом из t мест в колоде у первого игрока. Аналогично для второго игрока. Тут надо умножать, потому что любую колоду из предыдущего состояния ДП можно разбавить картами последнего типа в разных позициях и все эти способы дадут разные результирующие колоды. Надо домножить на оба сочетания, потому что мы независимо можем тасовать карты у первого и второго игрока.

    Сочетания считаются факториалами С(n,k) = n!/ k! (n-k)!.
    Я бы посоветовал предподсчитать все факториалы до 500 по модулю в массив, а так же обратные к ним.

    Еще, если не будет влезать по памяти, обратите внимание, что в ДП достаточно хранить лишь 2 слоя по первому параметру. Т.е. надо места для 2*500*50*50 элементов, что для 4-х байтных значений будет занимать ~10mb памяти. Может даже long long можно хранить. Но тут надо переписать ДП снизу вверх, а не рекурсивно. Просто посмотрите, какие состояния куда плюсуются и с какими множителями. В этом случае вы будете не убирать карты последнего типа, а добавлять карты нового типа. Опять же, перебирайте сколько кому этих карт достанется. Надо только осторожно смотреть множители - С(сколько карт после добавления, сколько добавили).

    Теперь прикинем на коленке сложность вычислений таким алгоритмом.
    Само ДП имеет состояний 50*500*50*50 и пересчет 11 вариантов. Если все перемножить, получается что-то меньше 700 миллионов - в одну-две секунды должно влезать.

    Полный перебор у вас, занимает что-то типа 11^50 - никогда не дождетесь на сколько нибудь не тривиальном тесте.
    Ответ написан
    21 комментарий
  • Какие есть алгоритмы сжатия числа?

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

    Будет небольшое замедление при записи и считывании чисел из такого массива (Надо найти смещение, прочитать 2 каких-то байта, отбросить лишние биты)

    Возможно последний байт в массиве не до конца использован (+6 лишних бит), когда как в текущем решении у вас лишние 6 бит на каждое число.
    Ответ написан
    2 комментария
  • Почему рекурсия неверно отрабатывает?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваша программа ломается, если X=Y, например.
    Чтобы ее исправить, вместо веса edge и сравнения его со стоимостью товара, передавайте в функцию число от 1 до 3. Если число <=1, то можно брать x и передавать 1. Если <=2 - то можно брать y и передавать 2, и т.д.
    Ответ написан
    2 комментария
  • Эффективна ли сортировка выбором?

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

    На больших массивах сортировка выбором будет крайне не эффективна, потому что она имеет квадратичную сложность. Есть более эффективные сортировки - слиянием, quicksort, radixsort, и т.д.

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

    Вызов одной функции из другой - это нисколько не показатель эффективности алгоритма (или его реализации).
    Тут даже рекурсии нет - можно вызов функции развернуть, если он вам так не нравится (просто ее код с небольшими правками вставить вместо вызова), но это не сильно улучшит эту сортировку.

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

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

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

    Ищите parallel dfs или parallel maximum flow.

    Собственно, параллелизации поиска паросочетаний я нигде не видел. Слишком специфичная задача.

    Однако, есть алгоритм поиска через максимальный поток.
    Если добавить в граф исток, соединенный с левой долей, и исток, соединенный с правой долей, а пропускные способности сделать по 1, то любой поток тут будет равнозначен паросочетанию. Есть алгоритм Форда-фолкерсона, там основная работа - это делать dfs в графе для поиска пути из истока в сток. Собственно, можно распараллелить этот dfs. Это более популярная задача и алгоритмы гуглятся легко.

    Полной параллелизации тут не будет, потому что dfs запускается последовательно n раз и их нельзя параллельно пускать, ведь после каждого dfs-а граф меняется.
    Ответ написан
    6 комментариев
  • ABCPascal.Net. Олимпиадная задача, как ускорить код?

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

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

    1) Пронумеруйте всех крокодилов. Рекомендую в новой матрице записать 0 для пустоты и номер крокодила, где такой есть.

    2) Как у вас уже сделано, для всех крокодилов в нужном направлении смотрите все клетки, но не останавливайтесь на первом встречном крокодиле. Продолжайте движение и считайте всех встреченных крокодилов. Таким образом вы для каждого крокодила узнаете, скольких надо прогнать перед ним.

    Сразу же, сложите всех крокодилов со счетчиком 0 (которых уже можно прогонять прямо сейчас) в очередь. Прогоняйте крокодилов из очереди, пока она не пуста. При обработке такого крокодила - считайте его в ответе, сотрите его из матрицы, и, что важно, обновите счетчики для всех крокодилов, которым он мешал. Для этого от текущего крокодила пройдитесь во ВСЕ стороны и, если крокодил там идет вам навстречу и еще не убран, уменьшите его счетчик. Если счетчик стал равен 0, добавьте этого крокодила в очередь. Все.

    Это решение за O(n^3), а ваше - за O(n^4).

    Получается что-то вроде обхода в ширину на графе крокодилов. Можно было бы все ребра подсчитать сначала (сделать списки кто кому мешает), но эти списки суммарно будут N^3 памяти занимать, что может не влезть в память, а на скорость работы принципиально не влияет (ну, в 4 раза ускорит, где-то). Если опять не пройдет по времени, а по памяти куб у вас влезает, то постройте граф и при удалении крокодила не в матрице ищите, кому он мешает, а уже в графе пройдитесь по списку смежных вершин.
    Ответ написан
    Комментировать
  • Как решить задачу на сложность алгоритмов ниже?

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

    Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

    Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.
    Ответ написан
    2 комментария
  • Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

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

    Но, если ограничить класс допустимых формул, то решение есть - например, среди полиномов для n заданных эталонов можно всегда найти полином степени n-1, который будет через эти точки проходить. Это если у вас входные и выходные данные - по одному числу.

    Тут можно решить систему из n линейных уравнений (обозначаете неизвестными коэффициенты полинома, подставляете известные значения x и y для всех эталонов, гоните метод Гаусса).

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

    Формально, задача будет решена, но практического смысла в этом нет совсем. Формулы будут огромными и страшными.
    Ответ написан
  • Наиболее эффективный алгоритм для бронирования?

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

    Если у нас есть n людей, то заводим массив от 0 до n. Помечаем, что 0 человек можно размесить за 0 рублей, а все остальное за бесконечность. Потом для каждого свободного номера ()проходиммассив с конца в начало и, если (текущаяя цена + цена номера) для k человек лучще чем цена размещения (k+вместимость номера), то перезаписываем лучшую цену для k+вместимость. Так же сохраняем в вспомагательном массиве, какой номер мы сейчас взяли для данного количества человек (k+вместимость номера).

    В конце смотрим на ячейку для n человек - там минимальная стоимость будет.

    В итоге, время работы алгоритма O(n*m), где n человек и m свободных номеров.

    Это решение динамическим программированием даже короче и легче полного перебора: буквально 2 вложенных цикла для расчета и один while для восстановления ответа.
    Ответ написан
  • Как использовать транспортную сеть оптимально?

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

    Раздуйте граф, сделав копии каждой вершины для каждого возможного времени. Т.е.если предполагается, что есть решение не длинее 1000 едениц веремни, то создаете граф с 1000*V вершинами, по одной для каждой вершины начального графа и возможного времени. Для каждого ребра входного графа u->v создайте ребро {u,t}->{u,t+1}. В этом графе есть много входных вершин (любое время, начальная вершина) и много конечных вершин (любое время). Но тут уже нет условия на непересечение машин в одно и то же время. Вместо этого пути машинок просто не могут пересекаться по вершинам вообще. Ведь каждая вершина символизирует вершину+время.

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

    В этом графе пути уже должны не пересекаться по ребрам (ведь каждая вершина заменена ребром между двумя новыми вершинами) и все пути ведут из начала в конец. Чтобы разрешить машинам пересекаться в начальной и конечной вершине, начальные и конечные вершины графа не раздваивайте и сделайте пропускную способность ребер из начальной и в конечную вершины равными n. Все остальные пропускные способности равны 1.

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

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

    Изначальную верхнюю границу по времени можно взять n+V (V - путь в графе, и все машины идут по нему колонной одна за другой).

    Возможно есть улучшение этого решения такое: Вместо бинарного поиска по ответу вы увеличиваете максимальное время на 1, добавляете новые вершины и ребра в граф и каждый раз ищете дополняющие пути (не отчищая уже найденый максимальный поток). Это рещение вроде будет побыстрее, но тут надо аккуратно понимать, что такое остаточная сеть.
    Ответ написан
    1 комментарий
  • Правильный ли алгоритм?

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    При данных ограничениях можно создать искусственный граф, где каждая вершина соответствует вершине в исходном графе и некоторому запасу топлива (я обозначу такую вершину как (v, f) - в вершине v с топливом f).
    Вершин в таком графе будет до 500*10000. Для каждого ребра v->u длинной l в исходном графе создаем ребро из вершины (v, f) в вершину (u, f-l) для всех f (т.е. из вершины v, имея f топлива, можно попасть в вершину u, имея f-l топлива). Эти ребра ценой 0. Также, в каждую вершину v, где есть заправка, добавьте ребро (v, f) -> (v, n) ценой 1 (заправились до упора). В графе будет до 500*10000 + 500*10000 ребер.

    Теперь запустите там обход в ширину с двумя очередями или deque из вершины (start, n) пока не найдете путь в любую вершину (finish, f). Длина пути будет равна количеству заправок. Преходы по ребрам ценой 1 - это процесс заправки, по ребрам цены 0 - просто передвижения в исходном графе.

    Это известное обобщение обхода в ширину на 0-1 графе:
    Когда берете вершину из deque и смотрите всех ее соседей, если длина ребра до соседа 1, то кладете конец ребра в конец deque, а если цена 0 - то в начало. С двумя очередями делается так: пока очереди не пусты, берем вершину из текущей очереди и кладем ее соседей на расстоянии 0 в конец той же очереди, а соседей через ребро длины 1 - во вторую очередь. Когда текущая очередь опустеет, переходим к другой и так далее.
    Ответ написан
    4 комментария
  • Фибоначчи: Возможно ли найти порядковый номер последовательности Фибоначчи ( x ), исходя из числа ( y )?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Не школьник, но вроде все просто.
    У вас есть y = B^x/A
    Дано y, отсюда x= log_B(A*y) = ln(A*y) / ln(B).

    Надо будет округлить. Формула может давать сбои на мелких числах.
    Ответ написан
    1 комментарий
  • Как посчитать кол-во возможных исходов?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Ответ - количество сочетаний по n-1 из (n+m-2), или сколько способов выбрать n-1 объект из n+m-2.

    Это потому что нужно обязательно сделать n-1 шагов вниз и m-1 шагов вправо. Вопрос только, в каком порядке их делать. Всего будет сделано n-1+m-1 шагов и из них надо выбрать какие-то n-1 вниз, остальные будут шаги вправо. Вот и получаются сочетания.

    Можно считать треугольником Паскаля, получится в точности то же, что описал poznavaka,
    можно считать по формуле факториалов: (n+m-2)! / (n-1)! / (m-1)!

    Для вашего примера, где N=3 и M=4 ответ будет 5!/2!/3! = 120/2/6 = 10.
    Ответ написан
    Комментировать
  • Можно ли единожды обойти все вершины связного неориентированного графа и вернуться в начальную вершину?

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

    Эта задача NP-полна - следовательно, простого и быстрого алгоритма человечеству не известно. Можно делать полный перебор с отсечениями и эвристиками. Какие-нибудь методы имитации отжига или генетические алгоритмы могут работать быстрее, но это не точно и нужно долго и мучительно ковыряться, что бы оно заработало.
    Ответ написан
    Комментировать
  • Python: Сколькими способами можно представить заданное натуральное число N в виде суммы после- довательных нечетных натуральных чисел?

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

    1 + 3 + 5 + 7 = 16 - 0
    7 + 9 = 25 - 9

    Таким образом - вопрос в том, сколько различных пар квадратов дают разность в заданное N.

    N = a^2 - b^2 = (a-b)(a+b)

    Или же сколько чисел a и b, т.ч. N раскладывается на множители (a+b) и (a-b).

    Достаточно найти все делители N (не больше корня) т.ч. делитель и оставшаяся часть имеют четную разность (эта разность же равна 2b). Т.е. (n/d - d) %2 = 0.

    Перебирайте все числа d до корня N, и если N%d == 0 and (N/d -d) %2 == 0, то прибавляйте единицу к ответу.
    Ответ написан
    Комментировать
  • Какой оптимальный алгоритм нахождения суммы Минковского?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Для двух невыпуклых многоугольников с n и m вершинами сложность вычесления (nm)^2. Для 300 вершин - это уже порядка нескольких секунд. Можно сильно напрячься и ускорить на несколько процентов. Но сильно быстрее вы ничего не найдете.
    Ответ написан
    Комментировать
  • Как найти последную ненулевую цифру K!?

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

    Для этого какая там степерь 2 и 5 и возьмите минимум.
    Простое p войдет в k! в степени floor(k/p) + floor(k/p^2) + floor(l/p^3)...
    Можно легко это реализовать рекурсивно PowerInFactorial(n, p) = n >= p ? n/p + PowerInFactorial(n/p) : 0;

    Теперь вы знаете, сколько нулей в факториале. Если их все убрать, то задача становится совсем простой - найти последнюю цифру. Это можно сделать просто ведя все вычисления по модулю 10.

    Т.е. перемножаете все числа от 2 до k, предворительно сокращая двойки и пятерки, сколько надо.

    twos = fives = min(PowerInFactorial(k, 2), PowerInFactorial(k, 5));
    ans = 1;
    for ( i = 2; i <= k; i++) {
      j = i;
      while (j % 2 == 0 && twos > 0) {
        j/=2;
        twos--;
      }
      // same for fives
      ...
      ...
      ans = (ans*j)%10;
    }


    В итоге решение за O(k), потому что вложенные циклы вполнятся суммарно столько раз, сколько нулей в k!, а их по формуле выше, меньше O(k).
    Ответ написан
    Комментировать