Разбор второго тура

Задача 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

Задача - типичная “техника” на реализацию. Главное в таких задачах - не пугаться длинного условия и решать задачу по кускам, старательно их разделяя. Кусочки следует связывать как можно слабее. В идеале один кусочек - отдельный класс/отдельный набор функций, очень ограниченно взаимодействующий с остальными. Идейная часть таких задач - правильная архитектура программы, чтобы было удобно писать, тестировать и отлаживать куски и по отдельности, и вместе.

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

  1. Разбор формата архива.
  2. Распаковка строки, сжатой по методу LZSS.
  3. Чтение входных данных побитово (а не побайтово, как обычно).
  4. Построение дерева Хаффмана из таблицы (которая по сути представляет собой лишь список длин кодов символов). Будет удобно разделить этот кусок еще на два: отдельно построение кодов символов и отдельно построение дерева по существующим кодам.
  5. Кодирование чисел через последовательность ai: генерация последовательности и раскодирование. На самом деле последовательность ai - это просто пары “(первые два бита числа, его длина)”.

Начать реализовывать можно с любого конца: как “сверху” (сначала прочитать архив, потом разбить на биты, потом раскодировать таблицы и так далее), так и “снизу” (сначала написать самые вложенные куски: раскодирование LZSS, таблиц Хаффмана, служебных символов и только в конце дописать битовый поток и ввод-вывод). Я предпочитаю смешанный вариант: писать алгоритмические нетривиальные куски (3, 4, 5) в начале, отлаживать их, а уже потом дописывать остальное (“сверху”). При написании “сверху” можно выводить каждый шаг распаковки на экран сразу после написания. В сочетании с тем фактом, что каждый шаг занимает несколько строк (так как всё алгоритмически сложное уже реализовано), ловить ошибки реализации довольно легко прямо в процессе написания. Итоговая архитектура у меня получилась такая:

  1. Есть функция, генерирующая коды Хаффмана по длинам слов
  2. Есть класс “бор”, который по набору кодов конструирует дерево Хаффмана и может выдавать итератор, который умеет ходить по дереву: у него есть методы “считай бит” и “скажи, получился ли символ из дерева”.
  3. Есть класс “поток бит”, который конструируется от массива байт и умеет либо выдавать очередной бит, либо читать сразу несколько как число, либо читать закодированный по Хаффману символ (принимая в качестве параметра дерево, в котором надо этот символ искать).
  4. Есть кусок кода, предподчитывающий последовательность ai и длины “хвостов”, которые надо прочитать после чтения Xi или Li.
  5. В теле решения я сначала читаю таблицу, двумя вызовами функций конструирую дерево, потом используя цикл и метод “считай закодированный по Хаффману символ” считываю оставшиеся две таблицы Хаффмана, еще парой вызовов строю по ним дерево. Потом - читаю поток символов (длина целевого файла мне известна) и очевидным образом раскодирую данные.

Возможные проблемы, которые могут возникнуть в процессе решения:

  1. Неочевидно, какой порядок бит выбирать в каком месте программы. Так как основной поток данных будет считать, что внутри байта биты идут от старших к младшим, и этот же порядок верен при чтении чисел, то этот порядок и разумно выбирать во всём потоке. Например, последовательность 12 34 будет в битах записана как 0001 0010 0011 0100, что довольно естественно. Именно в таком порядке мой класс “поток бит” будет выдавать биты. Если же требуется прочитать число, то прочитав 01001 мой класс выдаст 9, что тоже довольно естественно с точки зрения человека, читающего числа.
  2. При чтении длины архива возникает проблема: порядок бит big-ending, а вот порядок байт - обратный (little-endian), причём это единственное такое место в формате архива. Поэтому можно прочитать четыре байта по отдельности, а потом их склеить.
  3. Так как изначально неизвестно количество команд LZSS, а известна лишь длина результата, необходимо раскодировать данные прямо в процессе чтения, а не сначала читать LZSS, а потом передавать его функции - так не получится.
  4. Требуется выводить шестнадцатеричные числа в верхнем регистре, иначе пройдёт только первые и третий пример.
  5. Требуется аккуратно выводить символы с кодами от 128 до 255, если вы используете знаковый тип (например, char в C++). В противном случае можно получить 80 баллов вместо 100, потому что символ 133 (он же -123) будет, скорее всего, выведен как четырёхбайтовое отрицательное число: FFFF FFFF FFFF FF85.
  6. В третьем примере демонстрируется кодирование строк вроде ab(1,10): несмотря на то, что к началу ссылки выведено всего два символа, ссылка может вывести сколько угодно символов.
  7. Неправильный подсчёт длины остатка, выводимого после 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. Это дает переходы вида .

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