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

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

    Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

    Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

    Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.
    Ответ написан
  • Как разложить полигон на дерево вершин?

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

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

    В случае с ближайшей точкой - если и есть структура, то это то-то вроде trapezoidal map - это такая мозговыносящая штука, что не советую о ней даже думать. Нужно разбить пространство на области, ближайшие к каждой стороне.

    За логарифм есть решение через бинарный поиск.
    Разбейте пространство на вертикальные колонны всеми x координатами всех вершин многоугольника. Внутри каждой из них будет проходить четное количество сторон. Составьте для каждой стороны уравнение и отсортируйте их по высоте.

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

    Проблема этого метода, что он требует O(n^2) памяти в худшем случае и такую же предобработку.
    Но, для выпуклых многоугольников, прямых в каждой колонне будет всего две. Вот описание метода с реализацией для этого упрощенного случая.
    Ответ написан
  • Какой алгоритм для поиска подстрок в списке кортежей будет быстрее comprehension?

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

    Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.
    Ответ написан
  • Как построить функцию декодирования классического кода Элиаса, если прямое кодирование работает правильно?

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

    И читайте это:
    1) подсчитайте сколько нулей идет в начале строки.
    2) Это сколько бит надо прочитать дальше и перевести в десятичную систему счисления.
    3) Это столько бит, сколько нужно прочитать дальше и перевести в десятичную систему, чтобы раскодировать число.
    Ответ написан
  • Как найти количество перестановок числа?

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

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

    Еще, в вашей формуле направшивается добавить пустое число ("") в ответ. Давайте разрешим его и вычтем в конце 1.

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

    Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).

    Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).

    Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.

    Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.

    Вырисовывается следующее динамическое программирование:

    F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).

    F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
    F(0, n>0) = 0
    F(i,0) = 1.
    Ответ - sum(k=0..a0+...+a9) F(9, k)

    У функции как бы неявный параметр массив a[] количеств всех цифр, но я его не включаю в параметры динамики, потому что по нему не надо мемоизировать.

    Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.

    Этот алгоритм работает за O(9*n), где n - длина входного числа.

    Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).

    F(0,0) = 1
    F(0,1) = 0
    F(0,2) = 0
    F(0,3) = 0
    F(1, 0) = 1
    F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
    F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
    F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
    F(2,0) = 1
    F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
    F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
    F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3

    Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.

    Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.
    Ответ написан
  • Как быстро найти вершину,которая имеет наибольшее количество ребер и не соединена с данной вершиной?

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

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

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

    Но в этой задаче можно проще: Найдите все вершины с максимальной степенью. Если из 3 и более, то найдите среди них 2 не связанные (берете любую, потом еще одну любую. Если они связанны, то берите любую третью - она не связанна с одной из двух первых).

    Если их 2, то проверьте, вдруг они не связанны. Если же они соседние или такая всего одна, то найдите в графе еще одну вершину с максимальной степенью, которая не связанна хотя бы с одной из этих двух. Чтобы это работало за линию - заведите массив и прибавьте 1 ко всем соседям каждой из 1/2 максимальных вершин. Потом смотрите на те, где стоит 0 (или 1, если максимальных две).

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

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

    Теперь рассмотрим случай двух связанных максимальных вершин. Рассмотрим оптимальный ответ. Если в нем нет одной из максимальных вершин, то мы могли бы заменить один из концов на максимум. Мы не можем этого сделать, только если оба конца связанны с обоими максимумами, а это означало бы циклы в графе. Но у нас же дерево! Значит, оптимальный ответ обязательно содержит одну из максимальных вершин. Но мы этот вариант в алгоритме перебрали.

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

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

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

    Во-первых, когда встает вопрос о можно-нельзя ли какими-то операциями получить что-то, первая мысль должна быть - придумать инвариант. Какое-то свойство, которое не меняется при применении операции. С опытом наберетесь идей для инвариантов. Тут сразу приходит в голову такой: Обозначим цвета цифрами от 0 до 2. Тогда при любом перекрашивании сумма всех чисел по модулю 3 не меняется. Если столбы одинаковые - сами числа не меняются, если 01 перекрасить в 22, 02 в 11 и 12 в 00, то сумма остается с таким же остатком от деления на 3.

    Отсюда можно сразу сделать вывод, что при N делящемся на 3 ответа нет. Потому что в конце мы должны получить все цвета одинаковые, а значит сумма будет 0, N или 2N - делится на N. Раз N делится на 3, то и итоговая сумма дает остаток 0 (по модулю 3). Но изначальная раскраска может иметь любой остаток (например, 00..0001). Значит решения для таких N нет.

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

    Так можно получить ответ для 2,4,8,16, но этого мало.

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

    Следующая идея должна быть - раз для существования решения важно неделимость на 3, то возможно мы сможем к группе одинаковых столбов добавить 3 столба?

    После разбора нескольких случаев на бумаге я понял, что надо отдельно рассматривать случаи N%3=1 и N%3=2.

    Рассмотрим первый случай. У нас есть 3k столбов цвета А, и в конце еще 4 столба - AXYC (один из N и 3 новых). Задача - получить в конце 4 одинаковых цвета. У нас уже есть решение для N=4 в примере. Просто примените его к 4-м последним столбцам. Теперь у нас есть ...AAAZZZZ. Если A=Z, то все наши операции ничего не сделают. Рассмотрим только случай A!=Z. Красим A+Z, получаем AAYYZ..Z на конце Красим 2 раза A+Y. Т.е. за 3 операции мы перекрасили 3 последние A в Z. Повторяем операцию, пока все A не перекрасим (их же 3k, напоминаю).

    Теперь случай N=3k+2. У нас есть 3k A, и в конце AAXYC. Если у вас есть решение для 5, то получаете на конце 5 Z и аналогично предыдущему случаю перекрашиваете 3 последних A в цвет последних столбов.

    Т.е. отдельно рассматриваете случай разных остатков N%3. Потом решаете задачу для N=4 или 5 первых столбцов, потом добавляете по 3 столба: решаете задачу для 4/5 последних столбов и итеративно перекрашиваете по 3 столба из предыдущих.

    Это решение потребует максимум N/3*(F(5)+N) шагов, где F(5) - сколько нужно операций для решения N=5.

    Теперь решение для N=5. Тут и надо будет воспользоваться наблюдением о дополнении плана для разных входных данных. Вот есть 5 столбов. Покрасим 1+2 и 3+4. Теперь у нас есть AABBC. Возможно какие-то цвета одинаковые. Но сначала допустим, что они все три разные. Красим попарно A+B(1+3 и 2+4). Все. Но что, если B=C, B!=A? У нас было AABBB. Мы покрасили 1+3 и 2+4 - получили ССССA. Красим 4+5 - CCCBB. Теперь, как раньше, перекрасим 3С в B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
    Теперь надо рассмотреть случай B=A, C!=A: AAAAC. Надо аккуратно повторить все операции выше - получим BBBBB. План для этого случая работает, ничего дописывать не надо. Остался случай A=C, C!=B. Т.е. дано AABBA. Применяем шаги выше и получим (перепроверьте!) AAAAA.

    Т.е весь план для N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.

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

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

    Возьмите максимальную степень двойки, помещающуюся в N. Пусть это k (2k > N, k <= N). Примените план для первых k. потом для последних k. Итого вы получите N-k столбов одного цвета и k столбов (возможно) другого цвета в конце. Если N-k делиться на 3 то, по известному плану "перекрашивания по тройкам" перекрасьте первые N-k в цвет последних k. Если же N-k не делиться на 3, то покрасьте попарно столбы цвета первых N-k и цвета вторых N-k. Потом останутся какие-то столбы в конце другого цвета, но их количество точно будет делиться на 3 (доказательство этого факта придумайте сами. Рассмотрите какие могут быть остатки от деления на 3 у k и N-k). Раз у нас группа другого цвета состоящая из троек, то мы умеем ее перекрашивать.

    Этот вариант будет требовать не квадратичное, а O(n log n) количество операций.
    Ответ написан
  • Как найти все комбинации определенных слагаемых числа?

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

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

    Функция перебирает 2 варианта. Пусть отсавшаяся сумма s, а разрешенное максимальное число имеет номер i (они хранятся в каком-нибуть отсортированном a[]).

    1) Берем текущее максимальное слагаемое. Естественно, если оно помещается в остаток s >= a[i]. Кладем его к текущим слагаемым в массив и рекурсивно вызываемся от уменьшенного остатка, не меняя максимальное число - (s-a[i], i). Важно - если слагаемые хранятся в глобальной переменной, то надо после рекурсивного вызова "вернуть как было" - удалить только что добавленное слагаемое из массива.

    2) Пропускаем текущее максимальное число. Значит, больше его брать вообще нельзя. Вызываемся от (s, i-1). Естественно, этот вариант есть только если i>0.

    Если мы получили, что оставшаяся сумма s равна нулю, то мы подобрали разбиение, надо вывести текущие слагаемые.

    Ах да, чтобы этот метод хорошо работал имеет смысл слагаемые отсортировать по возрастанию. Чтобы сначала брались самые большие.

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

    Для этого смотрите задачу о рюкзаке. Почти как в ней сделаейте динамическое программирование, которое будет считать, сколько способов собрать заданную сумму k мешьшими слагаемыми. После этого в рекурсивной функции вы можете сразу же возвращаться, если ДП говорит, что вариантов набрать s первыми i слагаемыми - 0.

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

    EDIT: Только заметил, что вам порядок важен и 1,2,3 считается отдельно от 3,1,2

    Изменения просты - рекурсивная функция теперь принимает только один параметр - сколько осталость добрать. Вместо двух вариантов она перебирает N вариантов - какое именно число из разрешенных взять.

    Оптимизация такая же. реализуете ДП, которое считает, сколько способов собрать заданное число и, если способов нет, возвращаемся из функции.
    Ответ написан
  • Почему не работает алгоритм Брона-Кербоша?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас две большие ошибки с языком питон. Вы в цикле в alg итерируетесь по списку add, меняя его. Так делать нельзя. Ломаются итераторы и вы пропускаете половину элементов.

    Вместо этого используйте цикл while:

    while add:
      item = add[0]
      add.remove(item)
      s.append(item)
    ...


    Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

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

    Еще по коду:
    range(n) в python возвращает 0..5. У вас там цикл по ребрам в __main__ и там идет обращение к i-1 в массиве graf. Т.е. обращение к [-1]. Вряд ли вы это хотели. Работает по чистой случайности, потому что в питоне a[-1] дает последний элемент.

    И вообще, вы матрицу смежности строите, но нигде не используете.

    Вместо функции check(), вы сделайте нормальный список смежности один раз, а то просто глаз режет от неоптимальности.
    neighbors = [[] for i in range(count_vershin)]
    for edge in graf:
      neighbors[edge[0]-1].append(edge[1]-1)
      neighbors[edge[1]-1].append(edge[0]-1)
    Ответ написан
  • Как ускорить программу?

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

    Для понимания алгоритма, сначала сделаем немного другую версию за O(n), а потом соптимизируем до константы.
    Вы вместо сравнения с сортированным массивом пройдитесь по массиву и смотрите, что для всех соседних элементов следующий более или равен предыдущему.
    Следующий шаг - заведите массив bool на n-1 элемент и храните в нем пометки, что в данной позиции массив отсортирован. При помене местами двух элементов надо пересчитать 4 позиции в этом массиве. Потом пройдитесь по массиву и проверьте, что там все элементы true. Пока все еще работает за линию и еще хранит лишний массив.
    А теперь последний шаг - можно не проходиться по массиву bool каждый раз, если поддерживать счетчик, сколько там истинных элементов. После ввода массива list надо будет заполнить массив bool-ов и подсчитать, сколько там true. При перестановке a и b у вас максимум 4 элемента в массиве bool могут поменяться. Вот при этих изменениях вы счетчик пересчитывайте. Просто тупо при каждой записи в этот массив вычтите 1 из счетчика, если текущее там значение true и прибавьте 1, если новое значение true.
    Ответ написан
  • В чём разница в скорости работы между перебором всех состояний игры и функций Шпрага-Гранди?

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

    Но она обладает замечательным свойством - если состояние игры можно разложить на несколько независимых игр и игорк в свой ход может сделать ход в любой из игр, то функция Гранди может быть подсчитана как xor значений для всех состояний. По умному это называется, что игра является суммой игр. В некоторых задачах это позволяет колоссально сократить простарнство состояний.

    Один пример - игра Ним. Есть несколько кучек камней. За свой ход игрок может взять сколько угодно камней из любой кучки. Проигрывает тот, кому не останется камней. В простом переборе вам придется в качестве состояния хранить вектор количеств камней в каждой кучке. Но ведь тут стостяние очевидно раскладвается на под-игры: каждая кучка - своя отдельная игра. Причем, функция Гранди тут тривиальна - это просто количество камней. Вот и получается решение игры Ним - взять xor размеров всех кучек. Если не 0, то состояние выгрышное. Надо взять из какой-то кучки столько камней, чтобы получился xor, равный 0.

    Еще пример - есть плитка шоколада. Игроки ее ломают вдоль клеток. За свой ход игрок может взять любой прямоугольный кусок и разломить его как-то вдоль клеток (если там более 1x1 клеток, конечно). Проигрывает тот, кто не сможет сделать ни одного хода. Опять же, при простом переборе пришлось бы хранить в состоянии размеры всех кусоков. Тут ОЧЕНЬ много вариантов. А с функцией Гранди - достаточно рассмотреть состояния вида "одна плитка размера n x m". После одного хода у вас будет 2 плитки, но меньшего размера. Вы уже знаете для них функцию гранди, XOR'ите их и получаете функцию для возможного перехода.
    Ответ написан
  • Как найти кратчайший путь с минимальным количеством поворотов(повороты в приоритете)?

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

    Во-первых, все расстояния в графе будут не одно число, а пара - собственно, длина пути и количество поворотов. При суммировании двух длин складывайте их покомпонентно, при сравнении сравнивайте сначала длины, а потом количество поворотов. Теоретически, можно схлопнуть все назад в одно число, если считать 100000*<длина> + <количество поворотов>. Но могут быть спецэффекты, если пути очень сложные и имеюют более 100000 поворотов. Еще, опасайтесь переполнения.

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

    Создайте 4 ребера между соседними направлениями с длиной {0, 1} (длина 0, но 1 поворот). От каждой вершины создайте также ребро длинной {1, 0} (длина - 1, 0 поворотов) в вершину в соседней клетке с тем же направлением (от "верхней" из 4-х вершин сделайте ребро в "верхнюю" же вершину в клетке сверху. Аналогично по трем остальным направлениям).

    Теперь кратчайший путь в этом графе будет то - что вам надо. Есть еще вопрос с начальными конечным направлением. Можно добавить в начальную и конечную клетки "центральную" вершину, в которая связанна ребрами длины {0, 1} (Важно сделать 1 поворот, иначе можно будет крутиться на месте через эту центральную вершину). Считайте, что эта вершина - "смотреть в пол". Вы начинаете в какой-то клетке, смотря в пол, и вам надо оказаться в другой клетке, опять же смотря в пол. Вы можете в клетке повернуться, или перейти в клетку впереди вас.

    Поскольку тут уже разные длины ребер, обход в ширину уже не будет искать кратчайшее расстояние. Но можно использовать дейкстру/A*.

    При реализации не надо даже хранить все вершины и ребра. Просто у вас теперь вершина вместо {x, y} будет описываться {x, y, d}. Вместо перебора 4-х направлений [-1,0],[0,-1],[0,1],[1,0] - вы делаете переход {x+dx[d],y+dy[d],d} или меняете d на (d+1)%d и (d+3)%4. И в очередях вы сохраняете не одно число, а пару {length, turns}. Для A* нужно еще прикидывать оставшуюся длину - ну вы по длине берите, что у вас уже есть, а по количеству поворотов берите 1, если у начала и конца разные направления.

    Играясь с длинами ребер и их сравнениями вы можете, например, разрешать чуть более длинные пути, если в них сильно меньше поворотов. (например, можно обойти лабиринт по периметру, чем чуть короче но зиг-загами ходить внутри). Для этого длина ребра может быть length*K+turns.

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

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

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

    Ваше условие не очень понятно, но вот, как сгрупировать массив по датам:
    st = 0; 
    end = 0;
    while (st < a.length) {
      end = st + 1;
      while(end < a.length && a[end].date == a[end-1].date) end++;
      console.log(a[st].date);
      for (st = st; st < end; st++) {
        console.log(a[st].id);
      }
    }


    Тут мы просто откусываем от массива кусок с одинаковыми датами, пока массив не кончится. Если вам нужна только последняя группа, то можно откусить только один раз с конца:
    end = a.length - 1;
    st = end - 1;
    while (st >= 0 && a[st].date == a[st+1].date) st--;
    console.log(a[end].date);
    for (st = st+1; st <= end; ++st) 
      console.log(a[st].id);


    Только учтите, этот код не работает на пустом массиве. Надо отдельно проверить этот случай.
    Ответ написан
  • Как сделать поличество пропусков при замене равными длине слова или же сделать пересчёт чтоб не рушились замены?

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

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

    Но все-равно остается вопрос, а вдруг нормаль смотрит в сторону отчки (0,0,0).
    Постройте уравнение плоскости ax+by+cz+d=0. (a,b,c) - это ваш найденный вектор нормали. d высчитывается, если подставить одну любую точку полигона.

    Теперь, если d положительно, то точка (0,0,0) лежит в том полупространстве, куда смотрит вектор и вам надо развернуть нормаль.

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

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

    Сначала немного теории игр.
    Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

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

    Правильная функция choize должна быть:
    def choose(s):
      if s%4 == 0: return 1
      else return s%4


    Тогда бот обязательно выиграет, если выигрышная позиция есть, или если человек допустит ошибку, хоть у него и была выигрышная стратегия.

    Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
    Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.
    Ответ написан
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

    Теперь можно считать ботов точками и они могут касаться полигонов.

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

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

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

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

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

    Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

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

    Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

    Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

    Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

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

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

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

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

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

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

    Теперь, как в задаче о рюкзаке, считайте динамическое програмимрование DP(i,j) - какая минимальная цена, чтобы набрать ровно i штук у первых j заказчиков (и каждый продает ровно какой-то свой priceBreak).

    База тривиальна: DP(0,0) = 0, DP(i>0, 0) = infinity (на практике - большое число, или -1 и это значение надо отдельно проверять при переходе).

    Переход:
    DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

    Тут мы просто перебираем, сколько продает последний поставщик. Берем оставшиеся у предыдущих (DP(...,j-1) и прибавляем, сколько заплатим последнему.

    Вот, подсчитали вы ДП. Теперь ответ - min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Перебирайте, сколько вы купите у особого поставщика. Берите оставшееся из динамического программирования.

    Если поставщиков M, надо купть N штук, у каждого поставщика по K цен, но это решение будет O(M*(M*N*K + N)) по времени и O(M*N) по памяти. (На самом деле, можно уточнить оценку по времени- O(M*(M*N+N*L+N)), где L - общее количество записей в массивах цен у всех поставщиков).

    Для восстановления ответа вместе с DP() запоминайте, какое значение k выдало лучший результат. Потом можно будет с конца размотать оптимальный ответ, выдавая известное значение последнему поставщику.

    Если цены у поставщиков могут возрастать при увеличении количества, то решение остается в силе, только надо дописать в каждый массив "количество=>цена" элементы с количеством на 1 меньше каждого priceBreak. Потому что теперь в любом ответе все-равно можно будет перекидывать от одного заказчика к другому, пока не упремя или в priceBreak сверху, или в последнее количество с неменяемой ценой. И опять получается, что только один поставщик будет продавать не фиксированное в массиве значение.

    Можно вместо ДП гнать симплекс метод, как Philipp уже написал (будет быстрее, если поставщиков мало, а количесто штук очень большое).

    Возможно, можно ускорить решение в M раз, если вместо M разных ДП гнать одно со всеми поставщиками. Потом перебрать i<=n, распределить i штук по поставщикам беря только priceBreak, а потом прибавить остаток к поставщику с минимальной ценой (не переваливая за следующий priceBreak!). Но я не уверен, что это будет работать (не смог пока доказать, что, если у оптимального ответа урезать торчащий от priceBreak хвост у кого-то поставщика, то ответ останется оптимальным для нового количества).
    Ответ написан