Форум DL

Мой профиль

J 2020
Дано множество чисел.
если взять строку(1<=длина<=100000) клеток и заштриховывать клетки по кол-ву чисел в данном множестве, оставляя между каждым числом хотя бы одну пустую клетку, то получим массив bool построенный на данном множестве.
Пример:
{4 3 1}
011110011101 или 111100011101 или ...
но если взять пересечение единиц каждого варианта множества то получим 001100010000
нужно найти любое множество для которого строка является пересечением.
Ввод:
__#_____ (00100000)
Вывод
2(кол-во элементов в множестве)
3 2 (данное множество)
Решение:
будем находить строку единиц и считать кол-во нулей слева до 1(a) или начала массива и кол-во нулей справа до 1(b) или конца массива.
если левой границей является 1, то a1=a-1;
если правой границей является 1, то b1=b-1;
если левой границей является конец массива, то a1=a;
если правой границей является конец массива, то b1=b;
запихиваем во множество сi=min(a1,b1)
В конце в начальном массив меняем (ci) нулей на единиц слева и справа
проходимся по всему массиву и инсертим во множество (кол-во нулей между единицами) -2 если это кол-во большей 2
инсертим между числами которым соответствуют данные единицы
Выводим ответ (если массив на вводе не имеет единиц выволим 0)

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

Мой профиль

Я написал D, считывая максимального произведения. Влад, ты писал про то, что можно это оптимизировать хранением не максимального произведения, а логарифма от него. Каким образом мне считать дп, используя логарифмы?

Мой профиль

ln(x * y) = ln(x) + ln(y), поэтому

dp(n, d) = max(dp(n-1, d), ln(a[n]) + dp(n-1, some_other_d))

dp(0, 1) = ln(1) = 0, а dp(0, d) = ln(0) = -infinity для d!=1.

Мой профиль

Я думал насчёт этого, написал, но зачем-то брал log(dp[i - 1][some_other_d]). Написал дп с логарифмами. На 1-ый тест выводит 1 8 13 11(это тоже правильно), на остальные тесты тоже выводит правильные ответы.

Мой профиль

B 2020
Есть кодовый замок на котором 1<=d<=10 чисел (от 0 до d-1) и кнопка R(Reset) - делает все кнопки не нажатыми
а также 1<=n<=2^d-1 паролей.
Пароли состоят из d чисел 1 и 0 (1 - i-тая кнопка нажата, 0- не нажата)
Нужно найти минимальную комбинацию нажатий кнопок при которой будут использованы все пароли
Ввод:
d=3 n=4
001
111
101
011
Вывод:
6 (кол-во нажатых кнопок)
2 0 R 1 2 0

2 0 - здесь мы используем пароли 001 и 101
1 2 0 - здесь мы используем пароли 011 и 111
Решение:
Нам нужно найти множества кол-во которых минимально, состоящих из паролей, где во всех множествах нет одинаковых паролей (т.е. не используется один и тот же пароль больше одного раза) и в каждом множестве каждый член принадлежит всем членам справа (отняв любой пароль справа от этого мы не получим ни одной -1, Пример: {001 101 111})
паролей максимум 1023(пароля из d нулей быть не может), чисел максимум 10 в каждом пароле.
Была идея разбить пароли на 10 контейнеров по кол-ву единиц и идти от контейнера с самым малым кол-вом единиц, ищя пароли сверху к которым они принадлежат, помечая числа которые мы брали как те которые уже не будем брать.
Итого получается 10! множеств>10^6, не говоря о том, что из них определенным алгоритмом(точно не жадности) нужно будет выбрать те которые нам подходят, удаляя взятые пароли из других множеств.
Больше идей не возникло, может быть как-то дпшкой это сделать
HELP

Мой профиль

Я вижу граф. Снова.
Я в последнее время всюду вижу графы.

Могу предложить такой ЖАДНЫЙ алгоритм:
Строим ориентированный граф, в котором вершины -- пароли, а рёбра -- возможность получить из пароля A пароль B добавлением единичек.
Добавляем в него пароль 00000, у которого детьми являются все остальные пароли.
После этого делаем dfs по графу из пароля 00000:
при попадании в тупик жмёт Reset и возвращаемся в 00000;
когда проходим по ребру выводим его;
из нескольких возможных детей выбираем того, у которого меньше единичек;
по одной вершине два раза не ходим;
через 00000 можно ходить два раза.
Конец.

Показываю алгоритм на примере, т.к. без примера будет непонятно:
Пусть нам дано: 001 111 101 011
1) Строим граф.
001 -> 011
001 -> 101
001 -> 111
011 -> 111
101 -> 111
2) Добавляем в корень пароль 00000.
000 -> 001
000 -> 011
000 -> 101
000 -> 111
001 -> 011
001 -> 101
001 -> 111
011 -> 111
101 -> 111
3) DFS с возвращением в 000 если попали в тупик
000 -> 001 -> 011 -> 111 -> reset to 000 -> 101
Для каждого пройденого ребра выводим кнопки, которые нужно нажать, чтобы из начала ребра попасть в конец.
000 -> 001 = 2
001 -> 011 = 1
011 -> 111 = 0
111 -> 000 = R
000 -> 101 = 0 2
Итого вывод:
2 1 0 R 0 2

Пусть нам дано: 00001 10001 10101 11110
1) Строим граф.
00001 -> 10001
00001 -> 10101
10001 -> 10101
2) Добавляем пароль 00000.
00000 -> 00001
00000 -> 10001
00000 -> 10101
00000 -> 11110
00001 -> 10001
00001 -> 10101
10001 -> 10101
3) DFS
00000 -> 00001 -> 10001 -> 10101 -> reset to 00000 -> 11110
Пройденные рёбра:
00000 -> 00001 = 4
00001 -> 10001 = 0
10001 -> 10101 = 3
10101 -> 00000 = R
00000 -> 11110 = 0 1 2 3
Вывод:
4 0 3 R 0 1 2 3

Анализ алгоримта:
Паролей у нас максимум n = 2^10-1 = 1023 = 10^3
Построение графа подразумевает проверку каждой пары паролей на достижимость одного пароля из другого.
Это займёт n^2 = (10^3)^2 = 10^6 времени.
Проход dfs займёт n = 10^3 времени.

Итого: алгоритм в худшем случае выполняется за 10^6 итераций.

Мой профиль

Владислав Хамков:

Я вижу граф. Снова.
Я в последнее время всюду вижу графы.

Могу предложить такой ЖАДНЫЙ алгоритм:
Строим ориентированный граф, в котором вершины -- пароли, а рёбра -- возможность получить из пароля A пароль B добавлением единичек.
Добавляем в него пароль 00000, у которого детьми являются все остальные пароли.
После этого делаем dfs по графу из пароля 00000:
при попадании в тупик жмёт Reset и возвращаемся в 00000;
когда проходим по ребру выводим его;
из нескольких возможных детей выбираем того, у которого меньше единичек;
по одной вершине два раза не ходим;
через 00000 можно ходить два раза.
Конец.

Показываю алгоритм на примере, т.к. без примера будет непонятно:
Пусть нам дано: 001 111 101 011
1) Строим граф.
001 -> 011
001 -> 101
001 -> 111
011 -> 111
101 -> 111
2) Добавляем в корень пароль 00000.
000 -> 001
000 -> 011
000 -> 101
000 -> 111
001 -> 011
001 -> 101
001 -> 111
011 -> 111
101 -> 111
3) DFS с возвращением в 000 если попали в тупик
000 -> 001 -> 011 -> 111 -> reset to 000 -> 101
Для каждого пройденого ребра выводим кнопки, которые нужно нажать, чтобы из начала ребра попасть в конец.
000 -> 001 = 2
001 -> 011 = 1
011 -> 111 = 0
111 -> 000 = R
000 -> 101 = 0 2
Итого вывод:
2 1 0 R 0 2

Пусть нам дано: 00001 10001 10101 11110
1) Строим граф.
00001 -> 10001
00001 -> 10101
10001 -> 10101
2) Добавляем пароль 00000.
00000 -> 00001
00000 -> 10001
00000 -> 10101
00000 -> 11110
00001 -> 10001
00001 -> 10101
10001 -> 10101
3) DFS
00000 -> 00001 -> 10001 -> 10101 -> reset to 00000 -> 11110
Пройденные рёбра:
00000 -> 00001 = 4
00001 -> 10001 = 0
10001 -> 10101 = 3
10101 -> 00000 = R
00000 -> 11110 = 0 1 2 3
Вывод:
4 0 3 R 0 1 2 3

Анализ алгоримта:
Паролей у нас максимум n = 2^10-1 = 1023 = 10^3
Построение графа подразумевает проверку каждой пары паролей на достижимость одного пароля из другого.
Это займёт n^2 = (10^3)^2 = 10^6 времени.
Проход dfs займёт n = 10^3 времени.

Итого: алгоритм в худшем случае выполняется за 10^6 итераций.

Не сработает
Если 010 001 011 101 111
То т.к. мы берем жадностью, то мы берем
Либо 010 011 111 R 001 101 либо 001 011 111 R 010 R 101 либо ...
Кнопка R тоже считается за кнопку и в итоге комбинация не короткая во 2 случае
Итого: как я и говорил жадностью так не сделаешь.

Мой профиль

Егор Короткевич:

Не сработает
как я и говорил жадностью так не сделаешь.

Ты абсолютно прав!
И... у меня не получается придумать что-нибудь нежадное.

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

Мой профиль

Поговорил с Сашей Лосевым - он сказал "максимальное паросочетание".
Обещал чуть подробнее написать - я его "за руку схватил перед уходом"
Я только сейчас увидел - прочитал сообщение Влада.

Мой профиль

Только что перечитал, не заметил надпись "по длине ребер", но решение не будет сильно отличается от классического
Собственно
В ориентированном ацикличном графе(DAG) решается через максимальное паросочетание в двудольном графе
Сразу может показать, откуда взяться двудольному графу? Мы его сами сделаем
Давай разделим вершину в графе на Lv и на Rv, что соответствует копиям в левой и правой доле соответственно
Ребро u -> v теперь меняется на ребро Lu -> Rv. Теперь чтобы найти минимальное покрытие графа путями, мы должны максимизировать количество использованных ребер.
Вот и свелась задача к нахождения максимального паросочетания в двудольном графе
С взвешанными ребрам сильно не изменится, просто надо уже найти паросочетание минимального веса
Более подробно можно почитать на https://e-maxx.ru/algo/path_cover

Мой профиль

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

Я пока вижу какой-то такой вариант:

Строим наш исходный ациклический граф с истоком в нулевой вершине, ребра будут с пропускной способностью 1, а вес ребер - это количество операций для перехода. Дополнительно для всех ребер, исходящих из истока, стоимость увеличить на 1, чтобы учесть Reset (в конце надо будет вычесть единицу из ответа). Создать фиктивную вершину сток, к которой направить ребра из всех вершин с пропускной способностью 1 и весом 0. И потом найти максимальный поток минимальной стоимости. Сработает?

Уже понял, что не сработает.

Мой профиль

У нас в команде сейчас полное разногласие по поводу того, какой граф следует рассматривать.
И какое представление паролей в графе являестя наиболее натуральным и естественным для этой задачи и вообще.
Доспорились до того, что индексация с 0 -- это ненатурально и неестественно.
А яйцо появилось раньше курицы.
В общем, мы зависли в решении задачи, т.к. ушли в полемику.
При этом решения мы ещё никакого не придумали ни на каком графе...
Как-то так.

Задача далеко не классическая.
Решение Саши(если я правильно его понял) не подходит, т.к. оно ищет минимальное ЗАМОЩЕНИЕ вершин графа путями.
А у нас:
1) пути не обычные, а с истока.
2) покрытие, а не замощение.
На сайте https://e-maxx.ru/algo/path_cover Максим называет замощения покрытиями, т.е. там алгоритм нахождения минимального замощения.

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

Замощения является частным случаем покрытий, но оптимальное(в любом смысле оптимальное) замощение не всегда будет оптимальным покрытием.
Мы ищем оптимальное покрытие, а не замощение, т.к. пути могут пересекаться.

Но это в моей интерпретации.
Напомню, что моя интерпретация такова:
Есть ациклический граф с истоком в нулевой вершине, вес ребера - это количество операций для перехода из одной вершины в другую. Вершины -- пароли, которые нужно получить, + нулевая вершина(пароль 00000). Ребра -- способность от одного паролья кнопками прийти к другому не нажимая reset.
Задача: найти минимальное(по весам ребер) покрытие путями всех вершин графа. При этом все пути должны начинаться в нулевой вершине.
Ещё нужно подкорректировать веса так, чтобы учитывать стоимость кнопки reset, но это уже мелочи.

[Моя интерпретация интерпретации Егора]
У Егора есть альтернативная интерпретация. Она отличается от моей тем, что в ней нет истока(пароля 00000).
При этом я ещё не понял, какие у чего веса и что мы оптимизируем. Но он утверждает, что задача (возможно) сведётся к наждению замощения.
Но это не точно. Хай Егор сам за себя говорит...

Мой профиль

Владислав Хамков:

Задача далеко не классическая.
Решение Саши(если я правильно его понял) не подходит, т.к. оно ищет минимальное ЗАМОЩЕНИЕ вершин графа путями.
А у нас:
1) пути не обычные, а с истока.
2) покрытие, а не замощение.
На сайте https://e-maxx.ru/algo/path_cover Максим называет замощения покрытиями.

Я, честно говоря, не знаю такого термина как "замощение" в контексте графов. В статье на e-maxx - это называется так, как обычно и называется: вершинное покрытие путями, по-английски это path cover либо vertex-disjoint path cover в зависимости от ситуации. Поэтому мне кажется, все всё правильно поняли. И искать тут надо (после небольшой модификации весов ребер) вершинное покрытие путями минимальной стоимости, с тем отличием, что пути должны все начинаться из одной конкретной вершины.

P.S. Отвечал на первую, более короткую версию сообщения.

P.P.S. У нас в этой задаче веса переходов между состояниями обладают таким свойством, что w(i, k) + w(k, j) = w(i, j). Поэтому тут не сильно то важно, пересекающиеся ли по вершинам пути или нет. Можно рассматривать, что нет.

Мой профиль

Алексей Данченко:

Я, честно говоря, не знаю такого термина как "замощение" в контексте графов. В статье на e-maxx - это называется так, как обычно и называется: вершинное покрытие путями, по-английски это path cover либо vertex-disjoint path cover в зависимости от ситуации. Поэтому мне кажется, все всё правильно поняли. И искать тут надо (после небольшой модификации весов ребер) вершинное покрытие путями минимальной стоимости, с тем отличием, что пути должны все начинаться из одной конкретной вершины.

Я использовал "замощение" и "покрытие" по аналогии с этими понятиями в теории множеств. Прошу прощения за неправильную терминологию.

Теперь буду использовать английскую терминологию с wiki/Path_cover.
Есть path-cover -- это "set of directed paths such that every vertex v ? V belongs to at least one path".
Есть vertex-disjoint path cover -- это "a set of paths such that every vertex v ? V belongs to exactly one path"
Иногда path-cover используется для обозначения vertex-disjoint path cover, но мы этого делать не будем.
В нашей задаче мы ищем path-cover а не vertex-disjoint path cover.
А на algo есть алгоритм только нахождения минимального vertex-disjoint path cover а нам нужно path-cover.
Т.е. нам тот алгоритм не подходит.

Алексей Данченко:

У нас в этой задаче веса переходов между состояниями обладают таким свойством, что w(i, k) + w(k, j) = w(i, j). Поэтому тут не сильно то важно, пересекающиеся ли по вершинам пути или нет. Можно рассматривать, что нет.

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

P.S. идею с потоками я ещё понял. Пойму потом)

Мой профиль

Владислав Хамков:

P.S. идею с потоками я ещё понял. Пойму потом)

Не стоит, я уже сдался и прочитал авторское решение, там ближе к тому, что Саша писал, но надо еще существенную часть придумать. Не самая простая задача, конечно. Я сначала не прочитал, что это с последнего NEERC, думал, это что-то попроще.