CodeJam 2021 Qualifier Round Moons and Umbrellas 算法讲解
CodeJam 2021 Qualifier Round Moons and Umbrellas Algorithm Explanation
我试图理解标题中提到的 codejam problem 的解决方案。特别是“额外学分”的第三部分。
这是来自 Github 的“kamyu104”的 solution。
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Qualification Round - Problem B. Moons and Embrellas
# https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145
#
# Time: O(N)
# Space: O(1)
#
def moons_and_umbrellas():
X, Y, S = raw_input().strip().split()
X, Y = int(X), int(Y)
dp = {}
prev = None
for c in S:
new_dp = {}
for i, j, cost in [('C', 'J', Y), ('J', 'C', X)]:
if c == j:
new_dp[i] = INF
elif prev is None:
new_dp[i] = 0
elif prev == i:
new_dp[i] = dp[i]
elif prev == j:
new_dp[i] = dp[j]+cost
elif prev == '?':
new_dp[i] = min(dp[i], dp[j]+cost)
dp = new_dp
prev = c
return min(dp.itervalues())
INF = float("inf")
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, moons_and_umbrellas())
编程问题简而言之就是给出一串
C's 和 J's，例如，CCJCJ??JC 或 JCCC??CJ，问号应替换为 C 或 J。最小化从 C->J 或 J->C 的转换成本。两种类型的转换具有不同的成本。
问题是我无法理解 kamyu104 算法背后的直觉...我一直在遵循白板上的值，但我无法理解...请帮忙！谢谢。
我自己的代码如下所示...我按照Google提供的问题的分析部分进行操作，但它是TLE。我知道我们可以使用 memoization，但我不知道在我的代码中把它放在哪里...
import sys
def help_cody(mystring): #With the help of analysis tab
global X
global Y
if(len(mystring) <= 1):
return 0
else:
mylist = list(mystring)
C_string = mylist.copy()
J_string = mylist.copy()
if(mystring[0] == '?'):
C_string[0] = 'C'
J_string[0] = 'J'
C_string = "".join(C_string)
J_string = "".join(J_string)
return min(help_cody(C_string), help_cody(J_string))
else:
if(mystring[0] == mystring[1]): #Same characters for the first two.
return help_cody(mystring[1:])
else: #Different Characters
if((mystring[0], mystring[1]) == ('C','J')):
return X + help_cody(mystring[1:])
if((mystring[0], mystring[1]) == ('J','C')):
return Y + help_cody(mystring[1:])
if(mystring[1] == '?'):
C_string[1] = 'C'
J_string[1] = 'J'
C_string = "".join(C_string)
J_string = "".join(J_string)
return min(help_cody(C_string), help_cody(J_string))
if __name__ == "__main__":
sys.setrecursionlimit(10**6)
testcase = int(input())
for test in range(1, testcase+1):
X, Y, mystring = input().split()
X = int(X) #Cost for CJ
Y = int(Y) #Cost for JC
print("Case #" + str(test) + ": " + str(help_cody(mystring)))
这个相当简洁的代码实现了一个动态编程算法，该算法已经过优化，可以将 space 的使用从 O(n) 减少到 O(1)。首先，我将描述一个等价的 DP 以及如何计算它，然后展示它需要处理的许多独立案例如何可以被视为少量更通用的“案例模板”的实例，kamyu 的代码利用这些模板来简化.
一个正确但冗长的DP算法
该问题将问题框定为寻找一种成本最低的方法来替换每个“？”带有 J 或 C 的字符，但我们也可以将其构建为找到一种成本最低的方法来替换输入字符串 S 的 all 个字符，前提是我们永远不会将 J 更改为 C反之亦然——也就是说，我们可以想象自己用另一个 J“替换”现有的 J，或者用另一个 C“替换”现有的 C。事实上，甚至可以删除“提供”子句：我们可以通过以下方式获得我们想要的允许所有可能的替换，包括将 J 更改为 C，反之亦然，但要防止这些不需要的更改实际出现在任何最佳解决方案中，并以巨大的成本对其进行惩罚。
让我们将函数 f(m, a) 定义为 解决由输入字符串 S 的前 m+1 个字符组成的子问题的最小成本，假设我们将最后一个（即第 (m+1) 个）字符替换为 ，它必须是“J”或“C”。 （为什么是 m+1 而不是 m？这只会使基于 0 的数组索引的代码更简单。）允许保留此字符不变的替换（J->J 或 C->C），“？”的替换也是如此。字符到 J 或 C。我们将防止将现有 J 更改为 C 或反之亦然的方法是为此类替换分配无限成本——这将导致此选择永远不会被采用，因为另一个成本较低的选择是随时可用。
我们可以如下计算 f(m, a) 的值。我将使用类似于 Python 的伪代码写入 DP 矩阵 dp[][].
最高优先级的规则是，我们应该始终将无限成本分配给任何将硬连线字母更改为另一个字母的尝试。除此之外，分配特定字母的成本取决于前面的字母——除非因为我们处于最开始而没有前面的字母，在这种情况下我们知道成本为零：
if S[m] == "C" && m == 0:
dp[m]["C"] = 0
dp[m]["J"] = INF # Heavily penalise attempt to change hardwired C to J
if S[m] == "J" && m == 0:
dp[m]["C"] = INF # Heavily penalise attempt to change hardwired J to C
dp[m]["J"] = 0
if S[m] == "?" && m == 0:
dp[m]["C"] = 0
dp[m]["J"] = 0
如果我们不在一开始，那么前面的字母可能是固定的，在这种情况下，我们知道结合我们决定用什么替换当前字母来考虑它会花费多少。首先让我们考虑当前字母也是硬连线的情况，在这种情况下，尝试将其更改为另一个字母需要受到惩罚：
if S[m] == "C" && m > 0 && S[m-1] == "C":
dp[m]["C"] = dp[m-1]["C"]
dp[m]["J"] = INF
if S[m] == "C" && m > 0 && S[m-1] == "J":
dp[m]["C"] = dp[m-1]["J"]+costJC
dp[m]["J"] = INF
if S[m] == "J" && m > 0 && S[m-1] == "C":
dp[m]["C"] = INF
dp[m]["J"] = dp[m-1]["C"]+costCJ
if S[m] == "J" && m > 0 && S[m-1] == "J":
dp[m]["C"] = INF
dp[m]["J"] = dp[m-1]["J"]
当前一个字母是硬连线但当前字母是“？”时，没有 INF，因为我们可以用我们想要的任何东西替换当前字母：
if S[m] == "?" && m > 0 && S[m-1] == "C":
dp[m]["C"] = dp[m-1]["C"]
dp[m]["J"] = dp[m-1]["C"]+costCJ
if S[m] == "?" && m > 0 && S[m-1] == "J":
dp[m]["C"] = dp[m-1]["J"]+costJC
dp[m]["J"] = dp[m-1]["J"]
如果前面的字母是“?”，我们可以将其替换为“J”或“C”，这样我们就可以选择成本较低的那个：
if S[m] == "C" && m > 0 && S[m-1] == "?":
dp[m]["C"] = min(dp[m-1]["C"], dp[m-1]["J"]+costJC)
dp[m]["J"] = INF
if S[m] == "J" && m > 0 && S[m-1] == "?":
dp[m]["C"] = INF
dp[m]["J"] = min(dp[m-1]["C"]+costCJ, dp[m-1]["J"])
if S[m] == "?" && m > 0 && S[m-1] == "?":
dp[m]["C"] = min(dp[m-1]["C"], dp[m-1]["J"]+costJC)
dp[m]["J"] = min(dp[m-1]["C"]+costCJ, dp[m-1]["J"])
验证对于 m、运行 的每个可能值，上面的代码将分别分配给 dp[m]["C"] 和 dp[m]["J"] 一次，以及它分配的内容是正确的。我们可以构建一个正确的 O(n) 时间 DP 算法，将此代码放入 for m in range(len(S)) 循环，然后 returns min(dp[len(S)-1]["C"], dp[len(S)-1]["J"])。好吧，kamyu 的代码基本上就是这个算法，但是 (1) space 的使用从 O(n) 减少到 O(1)，(2) 一些“对称性”在更新中排除，并且（3）一些长的 if 条件通过使用 elifs 隐含。
从 O(n) space 到 O(1) space
我们可以做的第一个也是最重要的改变是注意计算 dp[m][...] 的递归关系永远不需要比 dp[m-1][...] 更远，所以只需要 dp[] 之前的 m 值（而不是到目前为止看到的所有 m 值）。我们可以通过删除 dp[] 数组的第一维，将 dp["J"] 解释为 dp[m-1]["J"] 等，并使用新字典 new_dp 来存储我们的内容来实现这一点用于存储在 dp[m] 中。我们在每次迭代结束时将 dp 设置为此。这样做会将 space 的使用从 O(n) 降低到 O(1)。在这一点上，算法已经是渐近最优的（任何算法必须至少花费 O(n) 时间来读取输入，并且至少需要 O(1) space）——余数只是使它 tidier/prettier.
更新对称性
我们可以计算出 INF 处罚。如果我们在主循环的顶部添加以下代码，我们可以去掉上面分配 INF 的 8 行代码：
if S[m] == "C":
new_dp["J"] = INF
break
if S[m] == "J":
new_dp["C"] = INF
break
接下来要注意的是，在上面所有以if S[m] == "C"开头的if语句中，有一个对应的if语句以if S[m] == "J"开头具有非常相似的结构——本质上，所有的“C”都被替换为“J”，反之亦然，所有的 costJC 都变成了 costCJ，并且应用在略有不同的地方。 kamyu 不是手动写下这两个语句，而是在一个循环中以一般的“模板”形式将它们各写一次，该循环通过两种不同的“扩展”它们的方式循环。这就是最里面的 for i, j, cost... 循环正在做的事情。
if -> elif
最后，kamyu 的代码积极地用 elif 链中较短的条件替换了一系列 if 语句中的长长的 ANDed 条件列表。基本上，代码像
if cond1: foo()
elif cond2: bar()
elif cond3: baz()
等同于
if cond1: foo()
if !cond1 && cond2: bar()
if !cond1 && !cond2 && cond3: baz()
（假设在评估 cond1 和 cond2 时没有副作用）。尽管使用一长串 elif 会使代码更难理解，因为您需要跟踪哪些条件已被确定为假，前提是它以 else 子句结尾（ kamyu 没有，但无论如何），总的来说，这是一种快速沟通（或说服自己）的好方法，其中一种情况会被命中，这是对这种 DP 算法正确性的基本要求之一。
特别注意，如果 kamyu 代码中链中的第一个 if 没有执行，从那里往下我们知道我们可以在当前位置写字母 i - - 要么是因为那是已经存在的字母，要么是因为一个“？”有吗
将所有这些转换应用于我描述的原始、冗长的 DP 后，我们恢复了 kamyu 的算法。
我试图理解标题中提到的 codejam problem 的解决方案。特别是“额外学分”的第三部分。 这是来自 Github 的“kamyu104”的 solution。
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Qualification Round - Problem B. Moons and Embrellas
# https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145
#
# Time: O(N)
# Space: O(1)
#
def moons_and_umbrellas():
X, Y, S = raw_input().strip().split()
X, Y = int(X), int(Y)
dp = {}
prev = None
for c in S:
new_dp = {}
for i, j, cost in [('C', 'J', Y), ('J', 'C', X)]:
if c == j:
new_dp[i] = INF
elif prev is None:
new_dp[i] = 0
elif prev == i:
new_dp[i] = dp[i]
elif prev == j:
new_dp[i] = dp[j]+cost
elif prev == '?':
new_dp[i] = min(dp[i], dp[j]+cost)
dp = new_dp
prev = c
return min(dp.itervalues())
INF = float("inf")
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, moons_and_umbrellas())
编程问题简而言之就是给出一串 C's 和 J's，例如，CCJCJ??JC 或 JCCC??CJ，问号应替换为 C 或 J。最小化从 C->J 或 J->C 的转换成本。两种类型的转换具有不同的成本。
问题是我无法理解 kamyu104 算法背后的直觉...我一直在遵循白板上的值，但我无法理解...请帮忙！谢谢。
我自己的代码如下所示...我按照Google提供的问题的分析部分进行操作，但它是TLE。我知道我们可以使用 memoization，但我不知道在我的代码中把它放在哪里...
import sys
def help_cody(mystring): #With the help of analysis tab
global X
global Y
if(len(mystring) <= 1):
return 0
else:
mylist = list(mystring)
C_string = mylist.copy()
J_string = mylist.copy()
if(mystring[0] == '?'):
C_string[0] = 'C'
J_string[0] = 'J'
C_string = "".join(C_string)
J_string = "".join(J_string)
return min(help_cody(C_string), help_cody(J_string))
else:
if(mystring[0] == mystring[1]): #Same characters for the first two.
return help_cody(mystring[1:])
else: #Different Characters
if((mystring[0], mystring[1]) == ('C','J')):
return X + help_cody(mystring[1:])
if((mystring[0], mystring[1]) == ('J','C')):
return Y + help_cody(mystring[1:])
if(mystring[1] == '?'):
C_string[1] = 'C'
J_string[1] = 'J'
C_string = "".join(C_string)
J_string = "".join(J_string)
return min(help_cody(C_string), help_cody(J_string))
if __name__ == "__main__":
sys.setrecursionlimit(10**6)
testcase = int(input())
for test in range(1, testcase+1):
X, Y, mystring = input().split()
X = int(X) #Cost for CJ
Y = int(Y) #Cost for JC
print("Case #" + str(test) + ": " + str(help_cody(mystring)))
这个相当简洁的代码实现了一个动态编程算法，该算法已经过优化，可以将 space 的使用从 O(n) 减少到 O(1)。首先，我将描述一个等价的 DP 以及如何计算它，然后展示它需要处理的许多独立案例如何可以被视为少量更通用的“案例模板”的实例，kamyu 的代码利用这些模板来简化.
一个正确但冗长的DP算法
该问题将问题框定为寻找一种成本最低的方法来替换每个“？”带有 J 或 C 的字符，但我们也可以将其构建为找到一种成本最低的方法来替换输入字符串 S 的 all 个字符，前提是我们永远不会将 J 更改为 C反之亦然——也就是说，我们可以想象自己用另一个 J“替换”现有的 J，或者用另一个 C“替换”现有的 C。事实上，甚至可以删除“提供”子句：我们可以通过以下方式获得我们想要的允许所有可能的替换，包括将 J 更改为 C，反之亦然，但要防止这些不需要的更改实际出现在任何最佳解决方案中，并以巨大的成本对其进行惩罚。
让我们将函数 f(m, a) 定义为 解决由输入字符串 S 的前 m+1 个字符组成的子问题的最小成本，假设我们将最后一个（即第 (m+1) 个）字符替换为 ，它必须是“J”或“C”。 （为什么是 m+1 而不是 m？这只会使基于 0 的数组索引的代码更简单。）允许保留此字符不变的替换（J->J 或 C->C），“？”的替换也是如此。字符到 J 或 C。我们将防止将现有 J 更改为 C 或反之亦然的方法是为此类替换分配无限成本——这将导致此选择永远不会被采用，因为另一个成本较低的选择是随时可用。
我们可以如下计算 f(m, a) 的值。我将使用类似于 Python 的伪代码写入 DP 矩阵 dp[][].
最高优先级的规则是，我们应该始终将无限成本分配给任何将硬连线字母更改为另一个字母的尝试。除此之外，分配特定字母的成本取决于前面的字母——除非因为我们处于最开始而没有前面的字母，在这种情况下我们知道成本为零：
if S[m] == "C" && m == 0:
dp[m]["C"] = 0
dp[m]["J"] = INF # Heavily penalise attempt to change hardwired C to J
if S[m] == "J" && m == 0:
dp[m]["C"] = INF # Heavily penalise attempt to change hardwired J to C
dp[m]["J"] = 0
if S[m] == "?" && m == 0:
dp[m]["C"] = 0
dp[m]["J"] = 0
如果我们不在一开始，那么前面的字母可能是固定的，在这种情况下，我们知道结合我们决定用什么替换当前字母来考虑它会花费多少。首先让我们考虑当前字母也是硬连线的情况，在这种情况下，尝试将其更改为另一个字母需要受到惩罚：
if S[m] == "C" && m > 0 && S[m-1] == "C":
dp[m]["C"] = dp[m-1]["C"]
dp[m]["J"] = INF
if S[m] == "C" && m > 0 && S[m-1] == "J":
dp[m]["C"] = dp[m-1]["J"]+costJC
dp[m]["J"] = INF
if S[m] == "J" && m > 0 && S[m-1] == "C":
dp[m]["C"] = INF
dp[m]["J"] = dp[m-1]["C"]+costCJ
if S[m] == "J" && m > 0 && S[m-1] == "J":
dp[m]["C"] = INF
dp[m]["J"] = dp[m-1]["J"]
当前一个字母是硬连线但当前字母是“？”时，没有 INF，因为我们可以用我们想要的任何东西替换当前字母：
if S[m] == "?" && m > 0 && S[m-1] == "C":
dp[m]["C"] = dp[m-1]["C"]
dp[m]["J"] = dp[m-1]["C"]+costCJ
if S[m] == "?" && m > 0 && S[m-1] == "J":
dp[m]["C"] = dp[m-1]["J"]+costJC
dp[m]["J"] = dp[m-1]["J"]
如果前面的字母是“?”，我们可以将其替换为“J”或“C”，这样我们就可以选择成本较低的那个：
if S[m] == "C" && m > 0 && S[m-1] == "?":
dp[m]["C"] = min(dp[m-1]["C"], dp[m-1]["J"]+costJC)
dp[m]["J"] = INF
if S[m] == "J" && m > 0 && S[m-1] == "?":
dp[m]["C"] = INF
dp[m]["J"] = min(dp[m-1]["C"]+costCJ, dp[m-1]["J"])
if S[m] == "?" && m > 0 && S[m-1] == "?":
dp[m]["C"] = min(dp[m-1]["C"], dp[m-1]["J"]+costJC)
dp[m]["J"] = min(dp[m-1]["C"]+costCJ, dp[m-1]["J"])
验证对于 m、运行 的每个可能值，上面的代码将分别分配给 dp[m]["C"] 和 dp[m]["J"] 一次，以及它分配的内容是正确的。我们可以构建一个正确的 O(n) 时间 DP 算法，将此代码放入 for m in range(len(S)) 循环，然后 returns min(dp[len(S)-1]["C"], dp[len(S)-1]["J"])。好吧，kamyu 的代码基本上就是这个算法，但是 (1) space 的使用从 O(n) 减少到 O(1)，(2) 一些“对称性”在更新中排除，并且（3）一些长的 if 条件通过使用 elifs 隐含。
从 O(n) space 到 O(1) space
我们可以做的第一个也是最重要的改变是注意计算 dp[m][...] 的递归关系永远不需要比 dp[m-1][...] 更远，所以只需要 dp[] 之前的 m 值（而不是到目前为止看到的所有 m 值）。我们可以通过删除 dp[] 数组的第一维，将 dp["J"] 解释为 dp[m-1]["J"] 等，并使用新字典 new_dp 来存储我们的内容来实现这一点用于存储在 dp[m] 中。我们在每次迭代结束时将 dp 设置为此。这样做会将 space 的使用从 O(n) 降低到 O(1)。在这一点上，算法已经是渐近最优的（任何算法必须至少花费 O(n) 时间来读取输入，并且至少需要 O(1) space）——余数只是使它 tidier/prettier.
更新对称性
我们可以计算出 INF 处罚。如果我们在主循环的顶部添加以下代码，我们可以去掉上面分配 INF 的 8 行代码：
if S[m] == "C":
new_dp["J"] = INF
break
if S[m] == "J":
new_dp["C"] = INF
break
接下来要注意的是，在上面所有以if S[m] == "C"开头的if语句中，有一个对应的if语句以if S[m] == "J"开头具有非常相似的结构——本质上，所有的“C”都被替换为“J”，反之亦然，所有的 costJC 都变成了 costCJ，并且应用在略有不同的地方。 kamyu 不是手动写下这两个语句，而是在一个循环中以一般的“模板”形式将它们各写一次，该循环通过两种不同的“扩展”它们的方式循环。这就是最里面的 for i, j, cost... 循环正在做的事情。
if -> elif
最后，kamyu 的代码积极地用 elif 链中较短的条件替换了一系列 if 语句中的长长的 ANDed 条件列表。基本上，代码像
if cond1: foo()
elif cond2: bar()
elif cond3: baz()
等同于
if cond1: foo()
if !cond1 && cond2: bar()
if !cond1 && !cond2 && cond3: baz()
（假设在评估 cond1 和 cond2 时没有副作用）。尽管使用一长串 elif 会使代码更难理解，因为您需要跟踪哪些条件已被确定为假，前提是它以 else 子句结尾（ kamyu 没有，但无论如何），总的来说，这是一种快速沟通（或说服自己）的好方法，其中一种情况会被命中，这是对这种 DP 算法正确性的基本要求之一。
特别注意，如果 kamyu 代码中链中的第一个 if 没有执行，从那里往下我们知道我们可以在当前位置写字母 i - - 要么是因为那是已经存在的字母，要么是因为一个“？”有吗
将所有这些转换应用于我描述的原始、冗长的 DP 后，我们恢复了 kamyu 的算法。