Форум DL

Мой профиль

https://neerc.ifmo.ru/archive/index.html
Там можно увидеть условия и результаты по годам от 2020 и вниз
Предлагаю готовиться к полуфиналу 2021 (ориентировочно в феврале) так

Хамков Влад движется по теории (графы, ССД, СДП)

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

Либуркин Илья - пока не понимает решение, задаёт там же уточняющие вопросы
(Цель Егора – описать решение так, чтобы вопросов не было)
когда Илья понял, кодирует и проверяет на предложенном Егором множестве тестов.

Для задач, которые Егор придумать не смог (но которые сдали медалисты)
Он пишет МАТЕМАТИЧЕСКУЮ постановку задачи, выкладывает её в форуме
тоже как можно лаконичнее, и в тоже время как можно понятнее.
И, по желанию, вопросы, на которые у него нет ответов

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

Если придумать самим больше ничего не удаётся – читаем разборы
На такой страничке
https://neerc.ifmo.ru/archive/2020.html
NERC Offline Tutorial
Contains analysis for contest problems.

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

Для 2020 года хотелось бы одолеть 7 задач (как победители).

Мой профиль

Задача K 2020
Дана последовательность чисел до 2n 1<=n<=1000
нужно отсортировать последовательность используя две операции
поменять местами числа:
1)a1 и a2, a3 и a4,...,a2n-1 и a2n;
1)a1 и an+1, a2 и an+2,...,an и a2n;
Вывод:
минимальное кол-во операций, если такое не возможно вывести -1
Решение:
исходя из логических рассуждений возможно получить всего 4 последовательности (включая стартовую) отсортированная последовательность может быть как возрастающей так и убывающей. Используя sort и reverse получить две последовательности, перебирая всевозможные варианты найти минимальное кол-во действий.

Мой профиль

K 2020
Тесты:
3
6 3 2 5 4 1
-----------
3

2
3 4 2 1
-----------
-1

4
1 2 3 4 5 6 7 8
-----------
0

5
2 1 4 3 6 5 8 7 10 9
-----------
1

2
2 1 4 3
-----------
1

5
6 7 8 9 10 1 2 3 4 5
-----------
1

Мой профиль

Все тесты работают, кроме 1-ого.
Вопрос:
1)Почему именно 4 комбинации(и точно ли 4 комбинации, т.к. всего комбинаций, количество всех возможных вариантов 2^n).

Мой профиль

Поправка к задаче К 2020
для четных 4 различных варианта
для нечетных 2n различных вариантa
Решение:
можно перебрать все варианты с проверкой на возрастание/ убывание.
т.к. нам доступно 2 действия которые при повторе дают тот же вариант, то можно просто взять стартовый вектор, сделать над ним 1 и 2 операцию и чередовать операции над этими векторами.
На каждом шаге делать проверку

Мой профиль

Задача G 2020
Дано дерево с корнем в 1, 1<=n<=100 вершинами и двунаправленными дорогами.
нужно найти минимальный путь проходящий через 1<=k<=100 различных вершин.
Ввод:
T(кол-во тестов 1<=T<=100)
n k
a2 a3 a4..an (ai - номер вершины родителя для i вершины)
Вывод:
7 (длина пути)
1 2 4 5 7 2 1 3 (последовательность вершин через которые мы прошли)

Решение:
Дфс-ом пройтись из корня записывать длину и останавливать поиск если его длина больше уже найденной.
Перебором всех вариантов выдать нужный ответ

Мой профиль

G 2020
Тесты:
3
6 2
1 1 2 2 3
6 6
1 1 2 2 3
6 4
1 2 3 4 5
-----------
1
1 2
8
1 3 6 3 1 2 5 2 4
3
1 2 3 4

4
2 1
1
1 1
5 3
1 1 3 3
7 5
3 5 1 1 5 6
-----------
0
1
0
1
2
1 3 4 (1 3 5)
5
1 4 1 5 3 2 (1 4 1 5 6 7)

Мой профиль

Написал G(прошла все тесты Егора). Написал K(прошла все тесты Егора).

Мой профиль

D 2020
Дано 1<=n<=100000 чисел
нужно взять непустое подмножество этих чисел так, чтобы их произведение было максимальным и заканчивалось на число 0<=d<=9
Ввод:
n d
a1 a2 .. an
Вывод:
с (кол-во взятых чисел)
a2 a3 a4 a5 a7 (взятые числа)
К чему я пришел:
Чтобы произведение чисел оканчивалось на d достаточно взять все числа по модулю 10 и считать произведение также по модулю 10 и если получившееся число равно d то это множество чисел нам подходит.
Чтобы произведение было максимальным и заканчивалось на d
достаточно брать большие из чисел которые по модулю d дают одно и тоже число.
Поэтому создадим вектора для каждого нужного нам числа получаемых при взятии элемента по модулю 10 и отсортируем их.
Список нужных чисел для d
d=0: 0 1 2 3 4 5 6 7 8 9 (если нашло числа из 0 или (2 и 5) то выводим все числа)
d=5: 1 3 5 7 9 (если есть хотя бы одно число из 5 то выводим все числа из этих векторов)
для всех остальных нечетных d:
ищем числа произведение которых по модулю 10 (или число по модулю 10) дает нужное нам число и для всех них выполняем следующее:
убираем пока это возможно любые числа произведение которых по модулю 10 дает 1, из оставшихся чисел находим произведение по модулю 10 и данное число -это число или произведение чисел по модулю 10 которые нужно убрать.
перебираем все варианты получения данного числа и среди всех вариантов находим минимальное произведение (нужно брать минимальные числа из векторов чтобы произведение было минимально) т.к. произведение оставшихся(для нечетных всех из 1 3 7 9) будет максимальным это и будет наш ответ.
Варианты получения произведения для нечетных чисел:
3=7*9=7*7*7
7=3*9=3*3*3
9=3*3=7*7
Для четных чисел алгоритм тот же но добавляются много условий
От новых идей и помощи Влада не отказался бы.
P.S. GL

Мой профиль

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

Решается динамическим программированием по какой-то такой формуле(индексация с единицы):

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

some_other_d берётся таким, что (some_other_d * a[n]) % 10 == d.
dp(n, d) возвращает максимальное произведение, которое можно составить из чисел A[1..n] так, чтобы оно заканчивалось на d.

Я не уверен насчёт деталей: чему должно быть равно dp(0, d) и как запоминать взятые в подмножество числа.
Но в целом решаться должно как я описал.

d принимает одно из 10-и значений. n принимает одно из 10^5 значений, поэтому dp нужно будет вычислить 10^6 раз.
10^6 -- маленькое число для C++.

Update:
Для одного набора (d, a[i] % 10) может быть несколько some_other_d которые удовлетворяют условию (a[i] * some_other_d) % 10 == d.
Их следует предвычислить и запихнуть в map, в котором ключи -- pair<int>.
dp(0, 1) считаем равным 1, а dp(0, d) = 0 для d!=1.
Вычисляя dp(n, d) нужно запоминать какие A[i] мы брали, поэтому нужно заставить dp(n, d) возвращать не только максимальное произведение, но и список чисел которые мы взяли для того, чтобы это произведение получить.
Список следует реализовать при помощи односвязного списка для экономии памяти(несколько односвязных списков могут иметь один и тот же хвост и его не надо будет копировать) и времени(вставка элемента в односвязный список происходит за константное время).
Также можно искать не максимальное произведение, а логарифм от него. Это нужно на всякий случай, чтобы не было переполнения int64 при перемножении 100000 чисел.

Мой профиль

Вопросы:
1)Ты уверен, что сложность 10^6. Я считаю, что 2 ^ n

Мой профиль

т.к dp(n,d)=max(dp(n-1,d),a[n]*dp(n-1,other_d)), то из dp(n,d) мы получаем минимум 2 элемента и у них n уменьшается на 1, тогда в общем если n=10^5 то сложность минимум равна 2^100000=?

Мой профиль

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

т.к dp(n,d)=max(dp(n-1,d),a[n]*dp(n-1,other_d)), то из dp(n,d) мы получаем минимум 2 элемента и у них n уменьшается на 1, тогда в общем если n=10^5 то сложность минимум равна 2^100000=?

Можешь не отвечать, я понял почему 10^6

Мой профиль

D 2020
Тесты:
6 4
4 11 8 2 1 13
-----------
5
1 2 4 11 13

3 1
2 4 6
-----------
-1

5 7
1 3 1 5 3
-----------
-1

6 3
8 9 4 17 11 5
-----------
3
9 11 17

5 6
2 2 2 2 2
-----------
4
2 2 2 2

1 1
1
-----------
1
1

5 0
1 16 3 5 9
-----------
5
1 16 3 5 9

5 0
1 17 3 5 9
-----------
-1

6 3
999 999 999 999 999 997
-----------
6
999 999 999 999 999 997

Мой профиль

Все равно отвечу.
В выражении dp(i, j) есть ограничения:
i -- длина префикса, на котором решаем подзадачу, поэтому i <= n.
j -- цифра, а у нас всего 10 цифр.
Поэтому если правильно вычислять, то получается, что сложность = n*10