Foobar、Blossom算法与同构

一位朋友最近邀请我参加Foobar，这是Google的招聘工具，让你解决有趣（有时也不那么有趣）的编程问题。这个名为"Distract the Guards"的问题非常有趣，但我发现网上没有关于它的好文章！虽然存在解决方案，但很难理解作者是如何得出解决方案的。我想尝试详细说明我的解决方法，并在需要时提供正确性证明。

免责声明：如果你正在参加Foobar（你好，Google员工）或将来有 aspirations 这样做，请本着挑战精神在此停止。众所周知，Google的问题库是有限的，如果你只是阅读解决方案，你会错过很多。

首先，这里是问题陈述：

分散守卫注意力

大规模越狱的时刻到了，你需要分散守卫的注意力，以便兔子囚犯能够逃脱！不幸的是，他们正在密切监视兔子。幸运的是，这意味着他们还没有意识到空间站即将因为LAMBCHOP末日设备的毁灭而爆炸。同样幸运的是，你作为下属和亲信所花费的所有时间意味着你知道守卫喜欢香蕉。还有赌博。还有拇指摔跤。

无聊的守卫 readily 接受了你玩香蕉游戏的建议。

你将同时设置拇指摔跤比赛。在每场比赛中，两名守卫将配对进行拇指摔跤。香蕉较少的守卫将押注他们所有的香蕉，另一名守卫将匹配赌注。获胜者将获得所有押注的香蕉。你不会将拥有相同数量香蕉的守卫配对（你很快就会明白为什么）。你足够了解守卫心理学，知道拥有更多香蕉的人总是会过度自信而输掉。一旦比赛开始，这对守卫将继续拇指摔跤并交换香蕉，直到他们拥有相同数量的香蕉。一旦发生这种情况，他们都会失去兴趣并回去看守囚犯，而你不想让这种情况发生！

例如，如果配对的两个守卫开始时有3和5根香蕉，第一轮拇指摔跤后他们将拥有6和2根（有3根香蕉的获胜并从输家那里获得3根香蕉）。第二轮后，他们将拥有4和4根（有6根香蕉的失去2根香蕉）。此时他们停止并回去看守。

这一切如何有用以分散守卫的注意力？注意，如果守卫开始时有1和4根香蕉，那么他们继续拇指摔跤！1, 4 -> 2, 3 -> 4, 1 -> 3, 2 -> 1, 4 依此类推。

现在你的计划很明确。你必须以这样一种方式配对守卫，使最大数量的守卫进入无限的拇指摔跤循环！

编写一个函数answer(banana_list)，给定一个正整数列表，描述每个守卫开始的香蕉数量，返回将留下看守囚犯的最少可能守卫数量。列表的元素i将是守卫i（从0开始计数）开始的香蕉数量。

守卫的数量将至少为1且不超过100，每个守卫开始的香蕉数量将是一个不超过1073741823（即2^30 -1）的正整数。他们中的一些人储存了大量的香蕉。

语言

要提供Python解决方案，请编辑solution.py 要提供Java解决方案，请编辑solution.java

测试用例

输入： (int list) banana_list = [1, 1] 输出： (int) 2

输入： (int list) banana_list = [1, 7, 3, 21, 13, 19] 输出： (int) 0

我喜欢好故事，也喜欢具有挑战性的问题，但这两者就像巧克力和茄子帕尔马干酪一样不合适，但我离题了。如果你解析香蕉和拇指摔跤，很容易看出这是一个组合数学问题。首先要做的是将大问题分解成一些可以拼凑在一起的小问题。在这里我们看到，一个关键部分是弄清楚，对于任何两个给定的守卫，他们是否会进入无限循环。一旦我们弄清楚了这一点，第二部分就是找到哪些守卫可以配对成无限循环，以便最大数量的守卫最终进入无限循环。让我们先解决第二部分。

最大匹配

假设我们有一个谓词willLoop(x,y)，用于两个守卫，分别有x根香蕉和y根香蕉，如果该对将循环则返回true。我们能否 then 最优地配对所有守卫，使我们有最多数量的无限循环？注意一旦我们有了这个，答案就很简单了：只需返回守卫总数减去配对成无限循环的守卫数量。

如果我们只是暴力尝试并尝试找到所有可能的配对呢？我们取一个守卫，尝试将她与另一个守卫配对，如果她们不循环，我们尝试将她与不同的守卫配对。这将为我们找到一个解决方案，但我们如何找到最大的一个，其中最多数量的守卫被配对？那么我们可以尝试找到所有可能的配对集合。这需要多长时间？假设有n个守卫。那么找到一个配对集合需要O(n^2)时间。要找到所有可能的配对，注意一旦我们配对两个守卫，这两个守卫就不能用于与其他人配对。所以对于每个配对集合中的每个配对，我们可以移除该特定对，重新分配剩余的配对，并得到另一个潜在的解决方案。这意味着整个过程可能需要O(2^{n^2})时间来处理！显然不可行。

此时我们应该退后一步，以另一种方式处理这个问题。与其尝试找到解决这个特定问题的算法，我们应尝试将其转化为现有问题。为此，我们需要找到一个可以支撑问题的结构。单词"图"现在应该在你脑海中尖叫，确实这看起来完美适合图：我们有一组守卫（节点），其中任何两个守卫通过willLoop相关（边）。让我们为第二个测试用例绘制一个图。

这里我们按他们开始的香蕉数量标记每个节点（守卫）。如果willLoop在它们之间为真，我们在两个守卫之间画一条边。拥有一组配对意味着什么？如果配对是一组边，这意味着每个节点在配对中最多可以有一条边。这是一个配对集合的例子。

注意有13根香蕉的守卫和有19根香蕉的守卫没有与任何人配对。我们不能为它们中的任何一个选择边，因为这样做意味着一个已经着色的节点在解决方案集中将有两个边，这是不允许的。然而，我们可以找到更好的配对集合。

现在每个守卫都配对了，因此我们知道不会无限循环的最少守卫数量为零。这是一个简单的例子，我们可以直观地找到解决方案，但如果有100个守卫呢？如果解决方案大于零呢？我们如何知道何时达到最小值并且没有更好的配对集合？最重要的是，是否可能以亚指数时间解决这个问题（否则我们的解决方案将不可行，我们会得到可怕的执行超时错误）？事实证明，计算机科学家几十年来一直在问这些确切的问题。这是图论中称为完美匹配的问题，可以简化为一个密切相关的最大匹配问题。正式地，最大匹配可以这样定义：给定一个图G=(V,E)，找到一个最大的集合S ⊆ E，其中对于每个v ∈ V，最多有一个s ∈ S使得v ∈ s。注意我说"一个最大的集合"，因为可以有多个基数相等的最大集合。

在1960年代，Jack Edmonds通过找到解决任何图的完美匹配的多项式时间（具体为O(V^2E)=O(n^3)）算法点燃了算法世界。他的"blossom算法"并不简单，我不会在这里尝试解释它。如果你想知道更多关于它如何工作的信息，Roughgarden教授在这些笔记中以本科水平呈现了它。关键是我们可以直接将此算法应用于我们的图以获得最大匹配。快速Google搜索Python实现会找到这个页面。

现在剩下的就是定义willLoop(x,y)。

循环检测

我们直观的方法将非常简单：让我们只是模拟游戏，直到它结束或我们检测到循环。我们将如何检测循环？我们可以保留一个"见过的香蕉数量"列表，并在每一轮后检查当前的香蕉数量是否之前被见过。如果是，我们知道我们处于循环中，因为相同的香蕉数量序列将继续。否则，在某个点上，我们将看到两个玩家最终拥有相同数量的香蕉。这表现如何？如果n是"游戏中"的香蕉总数（两个玩家开始时的香蕉之和），那么我们看到最多的回合数将是O(n)回合，因为经过n回合后，你必须要么看到两个玩家有相同的计数，要么看到每个香蕉计数，因此必须重复一个这样的计数。但n可能大到2^{30}-1，所以这不行。必须是亚线性或失败！

我们希望找到一个公式（谓词）来预测游戏的结果而不玩它。首先，让我们写下几个例子并尝试找到模式。下面，每一行(x,y)是一轮香蕉拇指摔跤游戏，其中x和y是每个玩家当前拥有的香蕉数量。我将在下面列出几个游戏，包括有循环和没有循环的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

(3,5)
(6,2)
(4,4)

(5,7)
(10,2)
(8,4)
(4,8)
(8,4)
...

(1,4)
(2,3)
(4,1)
(3,2)
(1,4)
...

(3,13)
(6,10)
(12,4)
(8,8)

你可以闻到一丝模式的气味，尽管可能还不明显。让我们尝试找出线索。我们知道有一些周期性结构（你说群？），但我们如何在不遵循复杂规则的情况下从一行转到下一行？有没有更简单的方法生成这个序列？好吧，如果一开始你没有成功，尝试改变领域。注意一个关键事实：每一轮香蕉的总和总是相同的。考虑到每轮没有香蕉被创造或毁灭，这可能是显而易见的——让我们称之为香蕉守恒定律。考虑到这一点，让我们在\pmod n中工作，其中n=x+y。注意在模n下处理数字时，负数-y与n-y相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

(3,-3) % 8
(6,-6) % 8
(4,4)  % 8

(5,-5) % 12
(-2,2) % 12
(-4,4) % 12
(4,-4) % 12
(-4,4) % 12
...

(1,-1) % 5
(2,-2) % 5
(4,-4) % 5
(-2,2) % 5
(1,-1) % 5
...

(3,-3) % 16
(6,-6) % 16
(-4,4) % 16
(8,8)  % 16

你看到了吗？我们注意到两个事实。首先，根据我们如何定义n，我们有x=-y \pmod n。这是给定的。更重要的事实是，我们可以看到每一轮恰好是前一轮的两倍\pmod n。这似乎是一个重要的事实，但它并没有立即给我们答案。我们也做了很多似乎不稳定的假设，尽管我们可能找到了一个模式——它也可能是一个红鲱鱼。我强烈支持我称之为3示例规则的东西，即：如果某事物适用于你编造的三个随机示例，它可能适用于所有整数。QED。然而，在数学界接受我的规则作为法律之前，我们不幸必须用老式的方式做事。

我的首选工具，一如既往，是群论，因为它简单但听起来很难，从而最大化炫耀因素。让我们将这个游戏形式化为一个群，其元素可以由群运算符生成。我们稍后会看到，这样做的好处是我们可以站在巨人的肩膀上，而不必证明任何重大的东西。让我们在n上定义群\mathcal{G}[n]，元素e=(x \pmod n, y \pmod n)和运算符\oplus，我们现在将构造它。

在构造\oplus时，我们注意到我们关心的唯一元素是运算符如何为(x,y) \oplus (x,y)工作（从此处开始，为简洁起见，我们在明显时省略\pmod n）。我们想说类似"如果我们将\oplus应用于(x,y) t次，那么我们得到元素(u,v)，这是玩t轮香蕉拇指摔跤游戏的结果"。我们不关心（目前）\oplus对其他元素对做什么。让我们形式化这个

[(x,y)⊕(x,y)=⎧⎩⎨(x−y,2y)(2x,y−x)(x,y)x>yx<yx=y=⎧⎩⎨(x−(n−x),2(n−x))(2x,(n−x)−x)(x,(n−x))x>yx<yx=y=(2x,−2x)=(2x,2y)(x,y)⊕(x,y)={(x−y,2y)x>y(2x,y−x)x<y(x,y)x=y={(x−(n−x),2(n−x))x>y(2x,(n−x)−x)x<y(x,(n−x))x=y=(2x,−2x)=(2x,2y)]

注意我们从游戏的定义开始，并应用香蕉守恒定律移除y依赖性。然后我们应用模数并简化以获得我们的最终形式(2x,2y)。注意这不应该令人惊讶，给定我们最初的直觉。现在再次到了我们想将问题转化为更熟悉的东西的时刻。很容易看出\mathcal{G}[n]是一个有效的群，但我们希望将由(x,y)生成的子群同构于某些众所周知的东西（如加法群\pmod n）。为什么？这样我们就可以做很酷的复杂事情，如乘法和除法，而不必担心所有烦人的细节，如"这是一个环吗？"。考虑到这一点，让我们完成\oplus的定义为(x_1,y_1) \oplus (x_2,y_2) \equiv (x_1+x_2 \pmod n,y_1+y_2 \pmod n)。你现在确信这个一般定义与我们上面的特殊情况一致。

所以事实证明我们的\oplus只是+，有什么大不了的，对吧？嗯，事实证明这正是加法群\pmod n \times \pmod n，但这不太重要。重要的是我们的子群同构于加法群\pmod n。我不会在这里给出证明，因为没有什么实质内容，但注意(2x \pmod n, 2y \pmod n) \equiv (2x \pmod n, -2x \pmod n)，因为通过构造n=x+y。这意味着我们丢弃了y依赖性。再次，这一切都应该感到冗余，因为我们从直觉到达这一点，这强烈表明这是正确的。

回到游戏，我们看到在第t轮，我们可以通过取x \cdot 2^t \pmod n找到(x,y)^{t}。现在我们可以定义谓词

[willLoop(x,y) = \forall t, x \cdot 2^t \not \equiv n/2 \pmod n]

如果这是数学课，那么我们就完成了。但作为程序员，我们不关心解的存在性——我们想要该死的解！那么我们如何得到封闭形式？通过一点操作，上述变为

[willLoop(x,y)=∀t,x⋅2t≢0(modn)=∀t,n˜∤x⋅2t=n˜∤xwillLoop(x,y)=∀t,x⋅2t≢0(modn)=∀t,n~∤x⋅2t=n~∤x]

其中\widetilde{n}只是n移除了所有因子2（例如，如果n=112，那么\widetilde{n}=7）。（如果你以前没有见过\nmid，它的意思是"不整除"）。立即得出的是willLoop(x,y)的算法：

1
2
3
4
5
6

def willLoop(x, y):
    n = x+y
    n_tilde = n
    while n_tilde % 2 == 0:
        n_tilde = n_tilde / 2
    return (x % n_tilde) != 0

很容易看出，这个算法中唯一的工作是除以n，这最多发生\log(n)次，所以这在O(\log(n))时间内运行。事实上，出于所有意图和目的，这实际上是O(1)时间，因为while循环只是修剪n的二进制表示的前导0位。然而，不要对计算机科学家这么说，除非你想被word-ram-model击中头部（相当重）。

附录A

这是没有Edmonds的blossom算法Python实现的完整解决方案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def willLoop(x, y):
    n = x+y
    n_tilde = n
    while n_tilde % 2 == 0:
        n_tilde = n_tilde / 2
    return (x % n_tilde) != 0

def bananaGraph(banana_list):
    G = {i: [] for i in range(len(banana_list))}
    for i, a in enumerate(banana_list):
        for j, b in enumerate(banana_list):
            if i != j and willLoop(a, b):
                G[i].append(j)
    return G

def answer(banana_list):
    G = bananaGraph(banana_list)
    matches = matching(G)
    return len(banana_list) - len(matches)

print answer([1, 1])
print answer([1, 7, 3, 21, 13, 19])
print answer([1])
print answer([1, 7, 1, 1])