CodeJam 2021 预选赛圆月伞算法说明

Question

我试图了解标题提到的codejam 问题的解决方案。具体来说，第三部分为“额外学分”。这是来自 Github 的“kamyu104”的解决方案。

# 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和J，例如CCJCJ??JC或JCCC??CJ，问号应该替换为C或J。最小化从C->J转换的成本或 J->C。这两种类型的转换具有不同的成本。

问题是我无法理解 kamyu104 算法背后的直觉...我一直在跟踪白板上的值，但我无法理解...请帮忙！谢谢。

我自己的代码如下所示...我遵循了 Google 提供的问题的分析部分，但它是 TLE。我知道我们可以使用记忆化，但我不知道将它放在代码中的哪里......

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)))

Answer 1

这段相当简洁的代码实现了动态编程算法，该算法已经过优化，可将空间使用量从 O(n) 减少到 O(1)。首先，我将描述一个等效的 DP 以及如何计算它，然后展示如何将它需要处理的许多单独案例视为较少数量的更通用“案例模板”的实例，kamyu 的代码利用了这些实例来简洁。

正确但冗长的 DP 算法

该问题将问题描述为寻找一种成本最低的方法来替换每个“？”。字符与 J 或 C，但我们也可以将其框架为寻找一种最小成本的方法来替换输入字符串 S 的所有字符，前提是我们永远不会将 J 更改为 C，反之亦然 - 也就是说，我们可以想象一下我们用另一个 J“替换”现有的 J，或者用另一个 C“替换”现有的 C。事实上，甚至可以删除“提供”子句：通过允许所有可能的替换（包括 J ），我们可以得到我们想要的东西。更改为 C，反之亦然，但通过以巨大的成本惩罚它们来防止这些不良更改实际出现在任何最佳解决方案中。

让我们将函数 f(m, a) 定义为解决由输入字符串 S 的前 m+1 个字符组成的子问题的最小成本，假设我们替换最终的（即 (m+1 )-th) 带有 的字符，该字符必须是“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))，然后返回min(dp[len(S)-1]["C"], dp[len(S)-1]["J"])。好吧，kamyu 的代码基本上就是这个算法，但是 (1) 空间使用量从 O(n) 减少到 O(1)，(2) 更新中的一些“对称性”被分解，以及 (3) 提出了一些长if条件通过使用elifs 来代替隐式。

从 O(n) 空间到 O(1) 空间

我们可以做的第一个也是最重要的改变是注意到用于计算的递归关系dp[m][...]永远不需要追溯到比 更远的地方dp[m-1][...]，因此只需保留前一个值dp[]的值m（而不是m到目前为止看到的所有值）就足够了。我们可以通过删除数组的第一个维度dp[]、解释dp["J"]为dp[m-1]["J"]等并使用新字典new_dp来存储我们过去在 中存储的内容来实现此目的dp[m]。我们dp在每次迭代结束时设置此值。这样做可以将空间使用量从 O(n) 降低到 O(1)。此时，该算法已经是渐近最优的（任何算法必须至少花费 O(n) 时间来读取输入，并且至少需要 O(1) 空间）——剩下的只是使其更整洁/更漂亮。

更新对称性

我们可以排除《中导条约》的惩罚。如果我们在主循环的顶部添加以下代码，我们就可以去掉上面分配 INF 的 8 行代码：

if S[m] == "C":
    new_dp["J"] = INF
    break
if S[m] == "J":
    new_dp["C"] = INF
    break

接下来要注意的是，在上述所有以if开头的语句中if S[m] == "C"，都有一个相应的以非常相似的结构if开头的语句if S[m] == "J"——本质上，所有“C”都被“J”替换，反之亦然，所有costJCs 都变成costCJs 并应用于略有不同的地方。kamyu 不是手动写下这两个语句，而是以一般的“模板”形式，在一个循环内将它们各写一次，该循环通过两种不同的方式“扩展”它们。这就是最里面的for i, j, cost...循环正在做的事情。

如果 -> elif

最后，kamyu 的代码积极地将语句序列中的长 AND 条件列表替换为 sif链中的较短条件elif。基本上，代码如下

if cond1: foo()
elif cond2: bar()
elif cond3: baz()

相当于

if cond1: foo()
if !cond1 && cond2: bar()
if !cond1 && !cond2 && cond3: baz()

cond1（假设评估和时不存在副作用cond2）。尽管使用长链elifs 会使代码更难理解，因为您需要跟踪哪些条件已被确定为 false，前提是它以子句结尾else（kamyu's 没有，但无论如何），但总体而言这是一种快速沟通（或说服自己）恰好有一种情况会被击中的好方法，这是此类 DP 算法正确性的基本要求之一。

特别注意，如果ifkamyu 代码中链中的第一个不执行，从那里开始，我们知道我们可以i在当前位置写入字母 - 要么因为该字母已经存在，要么因为“？ ” 有没有。

将所有这些转换应用于我所描述的原始、详细的 DP 后，我们恢复了 kamyu 的算法。