I was trying to understand the solution to the codejam problem mentioned by the title. Specifically the third part for “extra credits”. This is the solution by “kamyu104” from Github.
# 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())
The programming problem in a nutshell is given a string of C’s and J’s, for example, CCJCJ??JC or JCCC??CJ, the question marks should be replaced by either C or J. Minimize the cost of transitioning from C->J or J->C. The two types of transitions have different costs.
The problem is I can’t understand the intuition behind the algorithm by kamyu104… I’ve been following the values on a whiteboard, but I can’t get it… Please help! Thank you.
My own code is shown below… I followed the analysis portion of the question provided by Google but it is TLE. I know that we can use memoization, but I don’t know where to put it in my code…
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)))
Advertisement
Answer
This rather terse code implements a dynamic programming algorithm that has been optimised to reduce the space usage from O(n) to O(1). First I’ll describe an equivalent DP and how it can be computed, and then show how the many separate cases it needs to handle can be viewed as instances of a smaller number of more general “case templates”, which kamyu’s code exploits for concision.
A correct but verbose DP algorithm
The question frames the problem as finding a minimum-cost way to replace each “?” character with a J or C, but we can alternatively frame it as finding a minimum-cost way to replace all characters of the input string S, provided that we never change a J to a C or vice versa — that is, we can imagine ourselves “replacing” an existing J with another J, or an existing C with another C. In fact, that “provided” clause can even be removed: We can get what we want by permitting all possible replacements, including a J to be changed to a C or vice versa, but prevent these undesirable changes from actually appearing in any optimal solution by penalising them with enormous costs.
Let’s define the function f(m, a) to be the minimum cost of a solution to the subproblem consisting of the first m+1 characters of the input string S, under the assumption that we replace the final (i.e., (m+1)-th) character with a, which must be either “J” or “C”. (Why m+1 and not m? That just makes code with 0-based array indices simpler.) Replacements that leave this character unchanged (J->J or C->C) are allowed, as are replacements of “?” characters to either J or C. The way we will prevent changing an existing J to a C or vice versa is to assign infinite cost to such a replacement — this will result in this choice never being taken, since another lower-cost choice is always available.
We can compute values of f(m, a) as follows. I’ll use Python-like pseudocode that writes to a DP matrix dp[][].
The highest-priority rule is that we should always assign infinite cost to any attempt to change a hardwired letter to the other letter. Other than that, the cost of assigning a particular letter depends on the preceding letter — unless there is no preceding letter because we are at the very start, in which case we know that the cost is zero:
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 we are not at the start, then the preceding letter might be hardwired, in which case we know how much it will cost when considered in combination with whatever we decide to replace the current letter with. First let’s consider the cases where the current letter is also hardwired, in which case attempts to change it to the other letter need to be penalised:
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"]
When the previous letter is hardwired but the current letter is “?”, there are no INFs because we are allowed to replace the current letter with whatever we want:
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"]
If that preceding letter is “?”, we could replace it with either “J” or “C”, so we can pick whichever gives us the lower cost:
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"])
Verify that for every possible value of m, running the above code will assign to dp[m]["C"] and to dp[m]["J"] exactly once each, and that what it assigns is correct. We could build a correct O(n)-time DP algorithm that puts this code inside a for m in range(len(S)) loop, and then returns min(dp[len(S)-1]["C"], dp[len(S)-1]["J"]). Well, kamyu’s code is basically just this algorithm, but with (1) space usage reduced from O(n) to O(1), (2) some “symmetries” in the updates factored out, and (3) some long if conditions made implicit by using elifs instead.
From O(n) space to O(1) space
The first and most important change we can make is to notice that the recurrence relation for calculating dp[m][...] never needs to reach back further than dp[m-1][...], so it suffices to keep just the dp[] values for the previous m value (rather than for all m values seen until now). We can achieve this by dropping the first dimension of the dp[] array, interpreting dp["J"] as dp[m-1]["J"], etc., and using a new dictionary, new_dp, for storing what we used to store in dp[m]. We set dp to this at the end of each iteration. Doing this drops space usage from O(n) to O(1). At this point, the algorithm is already asymptotically optimal (any algorithm must take at least O(n) time to read the input, and at least O(1) space) — the remainder is just making it tidier/prettier.
Update symmetries
We can factor out the INF penalties. If we add the following code at the top of the main loop, we can get rid of the 8 code lines above that assign INF:
if S[m] == "C":
new_dp["J"] = INF
break
if S[m] == "J":
new_dp["C"] = INF
break
The next thing to notice is that, in all the above if statements that begin with if S[m] == "C", there is a corresponding if statement that begins with if S[m] == "J" with a very similar structure — essentially, all “C”s are replaced with “J”s and vice versa, and all costJCs become costCJs and are applied in slightly different places. Instead of manually writing down both statements, kamyu writes them just once each, in a general “template” form, inside a loop that loops through the 2 different ways of “expanding” them. That’s what the innermost for i, j, cost... loop is doing.
if -> elif
Finally, kamyu’s code aggressively replaces long lists of ANDed conditions in a sequence of if statements with shorter conditions in a chain of elifs. Basically, code like
if cond1: foo() elif cond2: bar() elif cond3: baz()
is equivalent to
if cond1: foo() if !cond1 && cond2: bar() if !cond1 && !cond2 && cond3: baz()
(assuming absence of side-effects in evaluating cond1 and cond2). Although using a long chains of elifs can make code harder to understand, since you need to keep track of which conditions have already been determined to be false, provided that it ends with an else clause (which kamyu’s doesn’t, but anyway), overall it’s a good way to communicate quickly (or convince yourself) that exactly one of the cases will be hit, which is one of the basic requirements for correctness of this kind of DP algorithm.
Notice in particular that if the first if in the chain in kamyu’s code does not execute, from there on down we know that we are allowed to write letter i at the current position — either because that’s the letter that’s already there, or because a “?” is there.
After applying all these transformations to the original, verbose DP I described, we recover kamyu’s algorithm.