Разбор второго тура
Задача A
Можно заметить две вещи. Во-первых Cnk при фиксированном k возрастает при росте n. Во-вторых, при n ≥ 2003 . Таким образом, можно посчитать все Cnk для n,k ≤ 2003 и с помощью бинарного поиска найти решения для k ∈ {0,1,2,3}. Еще, конечно, следует помнить, что Cnk = Cnn-k
Задача B
Чтобы найти наименьшего однозначного предка вершины v рассмотрим вершины, из которых есть ребро в v (обозначим из u1, …, uk). Пусть вершина a является однозначным предком v. Тогда для любого пути существует такое i, что wi = a. Для любого j существует такой путь. Получаем, что a обязана быть однозначным предком u1, …, uk.
Пусть p(x) — наименьший однозначный предок вершины x. Поймем, что для любого y однозначного предка x существует такое k, что . Рассмотрим любой путь из root в вершину x. . Очевидно, все однозначные предки x лежат на этом пути. Кроме того, все однозначные предки вершин a1, …, ap лежат на этом пути. Пусть p(ai) = aj. Тогда такое k не является однозначным предком ai. Это значит, что существует путь не содержащий bk. Тогда существует путь в x не содержащий bk. Таким образом, действительно, любой однозначный предок вершины x — результат многократного применения p(x).
Граф с ребрами является корневым деревом. Наименьший однозначный предок x должен быть предком u1, …, uk в этом дереве. Тогда p(x) = lca(u1, …, uk) — наименьший общий предок u1, …, uk.
Чтобы решить задачу, нужно топологически отсортировать граф и строить дерево однозначных предков в порядке топологической сортировки. Добавлять в дерево листья и одновременно отвечать на запрос lca можно, просто каждый раз насчитывая двоичные подъемы из добавленного листа. Получается решение за времени и памяти.
Задача C
Задача - типичная “техника” на реализацию. Главное в таких задачах - не пугаться длинного условия и решать задачу по кускам, старательно их разделяя. Кусочки следует связывать как можно слабее. В идеале один кусочек - отдельный класс/отдельный набор функций, очень ограниченно взаимодействующий с остальными. Идейная часть таких задач - правильная архитектура программы, чтобы было удобно писать, тестировать и отлаживать куски и по отдельности, и вместе.
При первом чтении условия важно не вдаваться в подробности, а сначала понять, что же от нас требуется: описан некоторый формат сжатия последовательности байт, даны сжатые данные, надо вывести сами данные. В первом приближении можно выделить следующие куски-классы будущей программы:
- Разбор формата архива.
- Распаковка строки, сжатой по методу LZSS.
- Чтение входных данных побитово (а не побайтово, как обычно).
- Построение дерева Хаффмана из таблицы (которая по сути представляет собой лишь список длин кодов символов). Будет удобно разделить этот кусок еще на два: отдельно построение кодов символов и отдельно построение дерева по существующим кодам.
- Кодирование чисел через последовательность ai: генерация последовательности и раскодирование. На самом деле последовательность ai - это просто пары “(первые два бита числа, его длина)”.
Начать реализовывать можно с любого конца: как “сверху” (сначала прочитать архив, потом разбить на биты, потом раскодировать таблицы и так далее), так и “снизу” (сначала написать самые вложенные куски: раскодирование LZSS, таблиц Хаффмана, служебных символов и только в конце дописать битовый поток и ввод-вывод). Я предпочитаю смешанный вариант: писать алгоритмические нетривиальные куски (3, 4, 5) в начале, отлаживать их, а уже потом дописывать остальное (“сверху”). При написании “сверху” можно выводить каждый шаг распаковки на экран сразу после написания. В сочетании с тем фактом, что каждый шаг занимает несколько строк (так как всё алгоритмически сложное уже реализовано), ловить ошибки реализации довольно легко прямо в процессе написания. Итоговая архитектура у меня получилась такая:
- Есть функция, генерирующая коды Хаффмана по длинам слов
- Есть класс “бор”, который по набору кодов конструирует дерево Хаффмана и может выдавать итератор, который умеет ходить по дереву: у него есть методы “считай бит” и “скажи, получился ли символ из дерева”.
- Есть класс “поток бит”, который конструируется от массива байт и умеет либо выдавать очередной бит, либо читать сразу несколько как число, либо читать закодированный по Хаффману символ (принимая в качестве параметра дерево, в котором надо этот символ искать).
- Есть кусок кода, предподчитывающий последовательность ai и длины “хвостов”, которые надо прочитать после чтения Xi или Li.
- В теле решения я сначала читаю таблицу, двумя вызовами функций конструирую дерево, потом используя цикл и метод “считай закодированный по Хаффману символ” считываю оставшиеся две таблицы Хаффмана, еще парой вызовов строю по ним дерево. Потом - читаю поток символов (длина целевого файла мне известна) и очевидным образом раскодирую данные.
Возможные проблемы, которые могут возникнуть в процессе решения:
- Неочевидно, какой порядок бит выбирать в каком месте программы. Так как основной поток данных будет считать, что внутри байта биты идут от старших к младшим, и этот же порядок верен при чтении чисел, то этот порядок и разумно выбирать во всём потоке. Например, последовательность 12 34 будет в битах записана как 0001 0010 0011 0100, что довольно естественно. Именно в таком порядке мой класс “поток бит” будет выдавать биты. Если же требуется прочитать число, то прочитав 01001 мой класс выдаст 9, что тоже довольно естественно с точки зрения человека, читающего числа.
- При чтении длины архива возникает проблема: порядок бит big-ending, а вот порядок байт - обратный (little-endian), причём это единственное такое место в формате архива. Поэтому можно прочитать четыре байта по отдельности, а потом их склеить.
- Так как изначально неизвестно количество команд LZSS, а известна лишь длина результата, необходимо раскодировать данные прямо в процессе чтения, а не сначала читать LZSS, а потом передавать его функции - так не получится.
- Требуется выводить шестнадцатеричные числа в верхнем регистре, иначе пройдёт только первые и третий пример.
- Требуется аккуратно выводить символы с кодами от 128 до 255, если вы используете знаковый тип (например, char в C++). В противном случае можно получить 80 баллов вместо 100, потому что символ 133 (он же -123) будет, скорее всего, выведен как четырёхбайтовое отрицательное число: FFFF FFFF FFFF FF85.
- В третьем примере демонстрируется кодирование строк вроде
ab(1,10)
: несмотря на то, что к началу ссылки выведено всего два символа, ссылка может вывести сколько угодно символов. - Неправильный подсчёт длины остатка, выводимого после Xi и Li: в условии написан логарифм, не являющийся целым числом. Поэтому важно посчитать его точно: смысл логарифма - найти минимальное число бит, которым можно закодировать ai+1-ai чисел.
Задача D
Был дан набор A подмножеств множества {1, …, n}, нужно было выделить набор B подмножеств того же множества, такой, что . То есть, задан ориентированный граф G, вершины графа — подмножества {1, …, n} есть ребро из b в a, если . Нужно покрыть набор A, то есть, выделить набор вершин, такой что для любой вершины a из A есть вершина b из выбранного набора, такая, что есть ребро .
Заметим, что граф можно разделить на слои: множества вершин, соответствующих подмножествам фиксированного размера. Ребра в графе будут вести из слоя в тот же слой или в соседнийю Всего в графе будет n+1 слой: множество {1, …, n}, подмножества размера n-1, подмножества размера n-2 и так далее, вплоть до слоя, содержащего пустое множество. Размеры слоев будут, соответственно . В ограничениях задачи .
Тогда можно считать динамику dp[i][mask] — минимальное количество вершин в наборе, таком, что для слоев с номерами покрыты все вершины из A, а для слоя с номером i покрыты вершины множества mask. Понятно, что можно делать переход, перебирая, какое множество будет покрыто на слое i+1, но это долго. Поэтому давайте найдем множество v — множество вершин, которые необходимо покрыть, чтобы набор A был покрыт, если на слое i покрыто множетсво mask. Легко видеть, что v — это просто множество вершин из A не покрытых вершинами из mask. Это дает переходы вида .
После того как посчитана динамика для всех минимальных множеств, можно посчитать переходы внутри слоя, добавляя дополнительные вершины: . Ответ на задачу — это просто .