Oh okay I see, Thanks for the clarification
On Wed, 6 Apr 2022 at 17:10, porker2008 <[email protected]> wrote: > When taking min, you should only consider the propagated fun value of the > direct child, not the accumulated sum. > > You also need to increase the recursion depth to avoid runtime error. > > See the accepted code below: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > *import syssys.setrecursionlimit(200000)memo = {}#recursivity on node from > abyss to triggerable nodesdef compute_path_fun(graph, elem, memo): if > elem in memo: return memo[elem] else: a = max(funs[elem], > min([compute_path_fun(graph,el, memo)[0] for el in graph[elem]])) b > = sum([memo[el][1] + memo[el][0] for el in graph[elem]]) - min([memo[el][0] > for el in graph[elem]]) memo[elem] = [a, b] 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], 0] 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)[0] + > compute_path_fun(graph, el, memo)[1] for el in graph[0]]) > print(f"Case #{t+1}: {out}")* > > 在2022年4月5日星期二 UTC-7 17:26:30<[email protected]> 写道： > >> 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/101a65db-9974-435b-a16e-68988d5a8f19n%40googlegroups.com > . > -- -- 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/CAFqGFGYzM2S9%2BOjDUBH_gS4X%3DKUg3M-WPNyEtoJ%2B3fDw2_oTcg%40mail.gmail.com.
