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

Wataru

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

  • Как выполнить свертку сочетаний?

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

  • Как реализовать алгоритм комбинаторики в программе?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Сначала переведите картинку из залачи в числа. Вот есть у вас 20 точек, пронумерованные от 1 до 20, как-то. Выпишите все 12 групп (9 окружностей и 3 диаметра). Будет у вас 12 наборов по 5-6 номеров. Запишите их в программе константными массивами.

    Затем делайте перебор рекурсией: У вас в глобальном массиве или списком в параметре будет набор пока не поставленных чисел. Сначала проверьте, что вы не сделали уже 2 группы с разной суммой. Пройдитесь по всем 9+3 группам, если какая-то целиком уже заполнена, то записываете ее сумму в переменную для окружности или диаметра, соответственно. Если перед записью там уже была другая сумма -то вы нашили противоречие. В этом случае надо просто вернуться из текущей рекурсии назад.

    Если противоречий нет и вы все 20 чисел поставили - выводите ответ.

    Иначе - перебираете, какое число ставите в первую незаполненую точку циклом. Ставите туда число и вызываетесь рекурсивно.

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

    Просто перебирать все перестановки (наборы массивов из чисел без повторений) и в конце проверять суммы, как вы хотите сделать - будет слишком долго. Их 21! (факториал) - это дофига слишком.
    Ответ написан
    2 комментария
    2 комментария

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

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

  • Какой размер доминирующего множества направленного графа (турнира)?

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

    Пусть degree(v) - количество вершин, инцидентных v.
    Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
    С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

    Теперь докажем основное утверждение.
    Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

    Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.
    Ответ написан
    Комментировать
    Комментировать

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это перефразированная задача о рюкзаке. Надо только заметить, что в оптимальном ответе будет набрано менее K+100 очков. Иначе можно безболезненно выкинуть какую-нибудь миссию (а они все <100 секунд занимают).

    Решение динамическим программированием. Не буду тут повторять - оно простое и везде расписано. Еще раз напомню ключевые слова - "задача о рюкзаке".
    Теперь цена предмета в задаче о рюкзаке - это время, а вес предмета - это очки. Заполняем DP[i] - минимальное время за которое можно набрать i очков. Потом ищем минимум на отрезке [k..k+100). Это и есть ответ к задаче.
    Ответ написан
    Комментировать
    Комментировать

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

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

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

    F(i, j) - длина наибольшей общей подстроки у префиксов длины i у первой строки и длины j у второй.

    База F(0,*)=F(*,0)=0

    Переход: F(i,j) = max(F(i-1,j), F(i,j-1), F(i-1,j-1)+1). Третий вариант рассматривается только, если i-ый символ в первой строке и j-ый во второй равны.

    Ответ - 52-F(52,52) для вашей задачи

    Если надо выдать куда что перемещать, то задача чуть сложнее. Динамика модифицируется сохранением, какой из трех вариантов был выбран, чтобы потом восстановить НОП. Эти карты помечаются как неподвижные. Потом, для всех карт во второй колоде найдите их места в первой колоде. А потом, тупо, перемещайте подвижные карты по одной на нужные места в возрастающем порядке результирующих мест. Тогда не надо будет вообще учитывать пока не перемещенные карты.
    Ответ написан
    Комментировать
    Комментировать