Hello everyone,
I tried to solve the chain reaction problem using dynamic programming with
recursivity.
*My logic*:
I considered a graph that I built using dictionary where the key is the
node number and the value is a list of nodes that point to the key node.
The Abyss is my node number 0. So key with [ ] as value are
trigerrable nodes.
My recursivity starts from abyss to trigerrable nodes. So, the final score
would be the abyss's fun score.
I passed the sample test but got WA. Could anyone tell me what's wrong with
my code please?
My code in attachment
Thank you in advance
Thierry
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
[email protected]. To unsubscribe from this group, send email to
[email protected]. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
---
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAFqGFGZhXnupzFEXXCGr%2BFgzvaZNE_cWzrxQMRetL-B-ZaE_gQ%40mail.gmail.com.
memo = {}
#recursivity on node from abyss to triggerable nodes
def compute_path_fun(graph, elem, memo):
if elem in memo:
return memo[elem]
else:
memo[elem] = max(funs[elem], min([compute_path_fun(graph,el, memo) for el in graph[elem]])) + \
sum([memo[el] for el in graph[elem]]) -\
min([memo[el] for el in graph[elem]])
return memo[elem]
T = int(input())
for t in range(T):
N = int(input())
F = list(map(int, input().split()))
P = list(map(int, input().split()))
funs = {k:v for k,v in zip(range(1,N+1), F)}
graph = {k:[] for k in range(N+1)}
for node in range(len(P)):
graph[P[node]].append(node+1) # dico of previous element in graph
#initialization of the memo with triggerable nodes (no previous node)
memo = {k:funs[k] for k in graph.keys() if graph[k] == [] and k!=0}
# we build path from abyss to triggerable nodes
out = sum([compute_path_fun(graph,el, memo)for el in graph[0]])
print(f"Case #{t+1}: {out}")
