Совместимость USACO

Question

Я запутался с объяснением и кодом решения USACO Cowpatibility.

Проблема определена здесь: http://usaco.org/index.php?page=viewproblem2&cpid=862.

Их решение определено здесь: http://usaco.org/current/data/sol_cowpatibility_gold_dec18.html.

Я знаю, что для их линейного решения требуется свойство включения и исключения (P IE), и я понимаю это свойство, но я не совсем понимаю, как они его реализовали. Я ищу объяснение этих строк:

"Это мотивирует следующее решение включения-исключения: для каждого подмножества вкусов подсчитайте, сколько пар коров, которым нравятся все вкусы в каждом подмножестве. Мы добавляем все значения для подмножеств размера 1, затем, чтобы избежать двойного счета, вычитаем все значения для подмножеств размера 2. Затем добавляем все значения для подмножеств размера 3, вычитаем все значения для подмножеств размера 4. и добавьте количество подмножеств размера 5. "

Как они определяют каждое возможное подмножество и что это за подмножества? Почему есть только 31N подмножеств? Также было бы полезно, если бы кто-нибудь привел примеры того, какие подмножества будут для их примера.

Answer 1

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

Теперь есть 31N подмножеств, потому что для каждой коровы вы можете создать 31 комбинацию любимых ароматов. Например, любимые ароматы мороженого Cow 1 были 1, 2, 3, 4, 5. Таким образом, различные подмножества были:

{1, 0, 0, 0, 0}  {1, 3, 0, 0, 0}  {2, 5, 0, 0, 0}  {1, 2, 5, 0, 0}
{1, 2, 0, 0, 0}  {1, 4, 0, 0, 0}  {1, 3, 4, 0, 0}  {2, 3, 5, 0, 0}
{1, 2, 3, 0, 0}  {1, 5, 0, 0, 0}  {1, 3, 5, 0, 0}  {3, 4, 5, 0, 0}
{1, 2, 3, 4, 0}  {2, 3, 0, 0, 0}  {2, 3, 4, 0, 0}  {1, 2, 3, 5, 0}
{1, 2, 3, 4, 5}  {2, 4, 0, 0, 0}  {2, 4, 5, 0, 0}  {1, 3, 4, 5, 0}
{2, 3, 4, 5, 0}  {2, 0, 0, 0, 0}  {3, 0, 0, 0, 0}  {4, 0, 0, 0, 0}
{5, 0, 0, 0, 0}  {3, 4, 0, 0, 0}  {3, 5, 0, 0, 0}  {4, 5, 0, 0, 0}
{1, 4, 5, 0, 0}  {1, 2, 4, 0, 0}  {1, 2, 4, 5, 0}

Как вы можете видеть, существует 31 подмножество. (Это потому, что можно сделать 2 ^ 5 = 32 набора, включая пустой набор. 32 - 1 = 31.) Поскольку N ≤ 50 000, вы можете сгенерировать 31N подмножеств. После сканирования входных данных код сгенерировал подмножества для каждой коровы и добавил их на карту:

map<S5, int> subsets;

Они сопоставили каждую комбинацию с количеством раз, которое она была замечена. Вот некоторые примеры записей для входных данных:

{

[{1, 0, 0, 0, 0}, 2],    # 2 cows, Cow 1 and Cow 2 both like flavor 1
[{8, 10, 0, 0, 0}, 2],   # 2 cows, Cow 2 and Cow 3 both like flavors 8 and 10
[{50, 60, 80, 0, 0}, 1], # 1 cow, Cow 4 liked flavors 50, 60, 80
# and so on...

}

Наконец, основываясь на количестве ненулевых чисел в подмножестве, алгоритм применяет принцип включения-исключения. Он просто перебирает все 31N подмножеств и либо добавляет, либо вычитает количество, сохраненное в карте для этого подмножества. (Если это были 1, 3 или 5 ненулевых чисел, подсчеты были добавлены; иначе они были вычтены.) Затем он вычитает этот ответ из N * (N-1) / 2, чтобы вывести количество пар коров, которые не являются совместимо.

Надеюсь, это объяснение поможет! Удачи в будущих конкурсах!

Answer 2

Есть 31N различных подмножеств, потому что у каждой коровы есть пять возможных вариантов вкуса. В частности, эта строка объясняет подмножества:

мы можем явно генерировать все подмножества ароматов, где хотя бы одна корова любит все ароматы в этом подмножестве

Способ сделать это, чтобы перебрать всех N коров, а затем создать набор мощности, который им нравится, за исключением пустого набора. В наборе питания есть 2^5 наборов, поэтому удаление пустого набора приводит к 31. Таким образом, общее количество наборов 31N .

Пример очень полезен здесь, взяв образец вход:

4
1 2 3 4 5       # Cow 0
1 2 3 10 8      # Cow 1
10 9 8 7 6      # Cow 2
50 60 70 80 90  # Cow 3

Подмножества будут:

{
  {1}, {1, 2}, {1, 3}, ..., {2, 3, 4, 5}, {1, 2, 3, 4, 5},    # Cow 0
  {1}, {1, 2}, {1, 3}, ..., {2, 3, 10, 8}, {1, 2, 3, 10, 8},  # Cow 1
  ...
}

Каждая корова генерирует 31 подмножество. Оттуда алгоритм подсчитывает количество коров, которые генерируют заданное c подмножество (например, обратите внимание, что {1} генерируется обеими коровами 0 и 1, мы просто отслеживаем, сколько коров генерирует каждое подмножество), и применяет включение-исключение на основе размера подмножества.

Хорошая проблема, я имел обыкновение делать USACO, и у них были действительно интересные проблемы, которые все еще выделяются среди "умных" вопросов интервью, которые дают многие компании. :)