I have taken a look into your solution and despite it has the correct O(N) idea, unfortunately oversimplifying mixed up different aims in calculations. 1. the node X should be counted to the thread which has the lowest possible thread value of its triggerer elements 2. the full subtree rooted at node X has an aggregated value of the thread where X will count to (this is not fixed yet, subject to change in the further reaction chain part) _and_ sum of other subtree values of the non-minimum elements This way, when moving to the triggered node of X, you are using the 2. but you are thinking of 1. The max is not taken on fun values, but a fun value and an aggregation. You could either store both 1. and (2. minus 1.) separately in mem, or alternatively, you could only track of the 1. and immediately add the aggregated "other" parts to the result which are not reaching the abyss and won't change any more.
This type of failure could be revealed in a tiny example F=[3,1,6,10,1] and P=[0,1,1,2,2] which selects node 3 as min when calculating node 1, given node 2 has mem value = subtree sum = 11 and not min thread value to consider = 1 (and node 3 has both = 6). This means the initiators in your solution are meant to trigger in the sequence 3,5,4 which gives 17 and not as 5,3,4 which gives 19. [I hope I haven't made any typo in the data.] Kata Thierry Njike <[email protected]> ezt írta (időpont: 2022. ápr. 6., Sze, 2:26): > 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 > <https://groups.google.com/d/msgid/google-code/CAFqGFGZhXnupzFEXXCGr%2BFgzvaZNE_cWzrxQMRetL-B-ZaE_gQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- -- 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/CAPOU4JOoyuTCykGB%3DM9nq7NPa0%3DXyAY4U-3R9hgwvu3epZGSCA%40mail.gmail.com.
