算法求解谷歌code果酱教程问题Ç [英] An algorithm for solving Google Code Jam tutorial problem C

问题描述

我想明白，解决了算法的谷歌code果酱，教程，做题C 。到目前为止，我写了<一href="https://github.com/ripper234/Basic/blob/master/java/src/main/java/org/basic/google/$c$cjam/practicecontest/ProblemCSolver.java"相对=nofollow>我自己基本实现，解决了小问题。我觉得这是对付不了这30大问题（复杂度为O（分（N，2 * K）！在更大的数据集）。

I'd like to understand the algorithm that solves Google Code Jam, Tutorial, Problem C. So far I wrote my own basic implementation that solves the small problem. I find that it's unable to deal with the large problem (complexity O(min(n, 2*k)! which is 30! in the larger data set).

我发现这个解决方案页< /一>，而是解决方案的过程中没有记录（有时间限制的情况下）。我看到的解决方案中的至少一个使用的联盟查找数据结构，但我不'吨了解它是如何在这里使用。

I found this solution page, but the solutions are of course not documented (there's a time limit to the context). I saw that at least one of the solutions used the Union Find data structure, but I don't understand how it's applied here.

有谁知道与解决这些问题的算法，一个页面，而不仅仅是code？

Does anyone know of a page with the algorithms that solve these problems, not just code?

推荐答案

不知道是否有更好的方法来处理的 GCJ - 哈密顿圈的，但这里是我的回答有：

Not sure if there's a better way to deal with this near duplicate of GCJ - Hamiltonian Cycles, but here's my answer from there:

在O（2 ^K ） - 基础的解决方案使用的容斥原理。鉴于氏/ EM> 2 ^K 的那些有 禁止的边缘，还有的的 子集边缘，包括其本身和空集。例如，如果有3禁止边缘：{A，B，C}，将有2 ³ = 8的子集：{}，{A}，{B}，{c}里，{ A，B}，{A，C}，{B，C}，{A，B，C}。

The O(2^k)-based solution uses the inclusion-exclusion principle. Given that there are k forbidden edges, there are 2^k subsets of those edges, including the set itself and the empty set. For instance, if there were 3 forbidden edges: {A, B, C}, there would be 2³=8 subsets: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

有关每个子集，则计算周期包括至少所有在该子集的边缘的数量。如果包含的周期数边缘的的取值的是 F（S）的和的取值 是集中所有禁止的边缘，然后由容斥原理，周期没有任何禁止边数为：

For each subset, you calculate the number of cycles that include at least all the edges in that subset . If the number of cycles containing edges s is f(s) and S is the set of all forbidden edges, then by the inclusion-exclusion principle, the number of cycles without any forbidden edges is:

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

在哪里| 取值的 |是元素的个数的的取值的。换句话说，周期与任何边的数目的总和的减去的周期与至少1禁止边缘数量的加的具有至少2个被禁止的边缘的数量，。 ..

where |s| is the number of elements in s. Put another way, the sum of the number of cycles with any edges minus the number of cycles with at least 1 forbidden edge plus the number with at least 2 forbidden edges, ...

计算的的 F（S）的是不平凡的 - 至少我没有找到一个简单的方法来做到这一点。你可能会停下来阅读之前深思。

Calculating f(s) is not trivial -- at least I didn't find an easy way to do it. You might stop and ponder it before reading on.

要计算的的 F（S）的，开始并未参与任何的的取值的节点。如果有 M 的这样的节点，还有的的 M 的！排列，你也知道。呼叫排列数的的 C 的

To calculate f(s), start with the number of permutations of the nodes not involved with any s nodes. If there are m such nodes, there are m! permutations, as you know. Call the number of permutations c.

现在检查的边缘的的取值的作为链。如果有任何不可能的组合，如涉及3边或在子周期的一个节点的的取值的和的 F（S）的 0

Now examine the edges in s for chains. If there are any impossible combinations, such as a node involved with 3 edges or a subcycle within s, then f(s) is 0.

否则，对于每个链增量的的 M 的按1和繁殖的的 C 的按 2米的。 （有 M 的地方放环比现有的排列和2的因素是因为链条可以向前或向后）。最后， F（S）的是 C 的 /（ 2米的）。最后的分裂排列转化为周期。

Otherwise, for each chain increment m by 1 and multiply c by 2m. (There are m places to put the chain in the existing permutations and the factor of 2 is because the chain can be forwards or backwards.) Finally, f(s) is c/(2m). The last division converts permutations to cycles.

这篇关于算法求解谷歌code果酱教程问题Ç的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！