algorithm - 一种解决Google Code Jam教程问题C的算法

Question

我想了解解决 Google Code Jam, Tutorial, Problem C 的算法.到目前为止我写了my own basic implementation解决了这个小问题。我发现它无法处理大问题(复杂度 O(min(n, 2*k)!在更大的数据集中为 30!)。

我找到了这个 solution page ，但解决方案当然没有记录(上下文有时间限制)。我看到至少有一个解决方案使用了 Union Find data structure ，但我不明白它是如何应用在这里的。

有谁知道一个页面包含解决这些问题的算法，而不仅仅是代码？

Answer 1

不确定是否有更好的方法来处理这个近乎重复的 GCJ - Hamiltonian Cycles ，但这是我的答案:

基于 O(2^k) 的解决方案使用 inclusion-exclusion principle .假设有 k 个禁止边，则有 2^k 个子集边，包括集合本身和空集。例如，如果有 3 个禁止边:{A, B, C}，则将有 2³=8 个子集:{}, {A}, {B}, {C}, { A,B}, {A,C}, {B,C}, {A,B,C}。

对于每个子集，您计算至少包含该子集中所有边的循环数。如果包含边s的循环数是f(s)和S 是所有禁止边的集合，则根据包含排除原理，没有任何禁止边的循环数为:

 sum, for each subset s of S: f(s) * (-1)^|s|

哪里 |s|是 s 中的元素数。换句话说，具有任何边的循环数之和减去具有至少 1 个禁止边的循环数加上具有至少 2 个禁止边的循环数，。 ..

计算 f(s) 并非易事——至少我没有找到一种简单的方法。在继续阅读之前，您可能会停下来思考一下。

要计算 f(s)，从不涉及任何 s 的节点的排列数开始 节点。如果有 m 个这样的节点，就有 m!排列，如你所知。将排列数称为 c。

现在检查 s 中的边缘是否有链。如果存在任何不可能的组合，例如包含 3 条边的节点或 s 内的子循环，则 f(s) 为 0。

否则，对于每个链递增 m 1 并将 c 乘以 2m。 (有 m 个地方可以将链放在现有排列中，因子 2 是因为链可以向前或向后。)最后，f(s) 是 c/(2m)。最后一个除法将排列转换为循环。