母牛兼容性 USACO

Question

我对 USACO Cowpatibility 解决方案的解释和代码感到困惑。

问题定义在这里：http://usaco.org/index.php?page=viewproblem2&cpid=862.

他们的解决方案定义在这里：http://usaco.org/current/data/sol_cowpatibility_gold_dec18.html。

我知道他们的线性解决方案需要属性包含和排除 (PIE)，我理解这一点属性，但我对他们如何实现它感到困惑。我正在寻找这些行的解释：

"This motivates the following inclusion-exclusion solution: for every subset of flavors, count how many pairs of cows that like all flavors within each subset. We add all the counts for subsets of size 1, then to avoid double-counting, we subtract all the counts for subsets of size 2. We then add all the counts of subsets of size 3, subtract all the counts of subsets of size 4, and add the counts of subsets of size 5."

他们如何确定每个可能的子集，这些子集是什么？为什么只有 31N 个子集？如果有人举例说明子集对于他们的示例案例来说是什么，那也会很有帮助。

Answer 1

有 31N 个不同的子集，因为每头奶牛有五种可能的口味选择。具体来说，这一行解释了子集：

we can explicitly generate all the subsets of flavors where at least one cow likes all the flavors in that subset

这样做的方法是遍历所有 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个子集。从那里，算法计算生成特定子集的奶牛数量（例如，注意 {1} 由奶牛 0 和 1 生成，我们只跟踪生成每个子集的奶牛数量），然后应用基于子集大小的包含排除。

好问题，我曾经做过 USACO，他们有非常有趣的问题，这些问题在许多公司提供的 "clever" 面试问题中仍然很突出。 :)

Answer 2

他们生成并存储了子集，以跟踪具有 1 种共同风味、2 种共同风味、3 种共同风味、4 种共同风味以及全部 5 种共同风味的奶牛对的数量。为此，他们使用了地图。

现在，有 31N 个子集，因为对于每头奶牛，您可以创建 31 种最喜欢的口味组合。例如，奶牛 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 中减去这个答案以输出不是的奶牛对的数量兼容。

希望这个解释对您有所帮助！祝以后的比赛好运！

母牛兼容性 USACO

Cowpatibility USACO

language-agnostic

algorithm

optimization

combinatorics