Codejam 2021限定符圆形月亮和雨伞算法说明

2022-04-01 00:00:00 python algorithm dynamic-programming

问题描述

我正在尝试理解标题中提到的codejam problem的解决方案。具体地说，第三部分是额外学分。这是来自Github的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和J，例如CCJCJ？？JC或JCCC？？CJ，问号应替换为C或J。最小化从C&>J或J-&>C过渡的成本。这两种类型的过渡具有不同的成本。

问题是我无法理解kamu104算法背后的直觉……我一直在遵循白板上的值，但我不能得到它...请救救我！谢谢。

我自己的代码如下所示。我遵循了谷歌提供的问题分析部分，但它是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)))

解决方案

这段相当简洁的代码实现了一种动态编程算法，该算法已经过优化，可以将空间使用从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)个)字符，必须是"；J"；或"；C"；。(为什么是m+1而不是m？这只会使从0开始的数组索引的代码变得更简单。)允许将此字符保持不变的替换(J->J或C-&>C)，以及将&q；？？&q；字符替换为J或C。我们防止将现有J更改为C或将C更改为J的方法是为此类替换分配无限成本-这将导致此选择永远不会被接受，因为另一个成本较低的选择始终可用。

我们可以如下计算f(m，a)的值。我将使用写入DP矩阵dp[][]的类似于Python的伪代码。

最高优先级规则是，我们应该始终将无限成本分配给任何尝试将一个硬连接的字母更改为另一个字母。除此之外，分配特定字母的成本取决于前面的字母--除非没有前面的字母，因为我们处于最开始，在这种情况下，我们知道成本为零：

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"]

如果前一个字母是硬连接的，而当前字母是&q；？？&q；，则没有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)使用elifs隐式的一些长if条件。

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

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

更新对称

我们可以排除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都变成了，并且应用在略有不同的地方。Kamyu不是手动写下这两个语句，而是在一个循环中以通用的模板形式分别编写一次，该循环遍历了两种不同的展开"；语句的方式。这就是最里面的for i, j, cost...循环正在做的事情。

If-&>elif

最后，kamyu的代码积极地将一系列if语句中的长AND条件列表替换为elifs链中的较短条件。

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算法。

相关文章