Need an approach
closed account (yUCGwA7f)
You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. For each valid i, the i-th node has a value vi and another parameter mi.
A leaf is a node without sons. Let's denote the number of leaf nodes in the tree by L and their numbers by l1,l2,…,lL, in increasing order. Then, for each valid i, let's define the answer for the leaf li in the following way:
Consider the path from the root to li. For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it.
Sum up the resulting values of all nodes on this path.
The answer ai for this leaf is defined as the maximum possible remainder of this sum modulo mli.
Find the answers for all leaves.
A leaf is a node without sons. Let's denote the number of leaf nodes in the tree by L and their numbers by l1,l2,…,lL, in increasing order. Then, for each valid i, let's define the answer for the leaf li in the following way:
Consider the path from the root to li. For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it.
Sum up the resulting values of all nodes on this path.
The answer ai for this leaf is defined as the maximum possible remainder of this sum modulo mli.
Find the answers for all leaves.
if its truly a tree (every node has only one entry point, and 0-N exit points) then you can get away with having the node data type contain the incoming weight value. The rest of it looks like pretty generic tree algorithm stuff (not BST though). You may want to write and get your tree working with like a single double as the data type, make sure you can store/add/delete/traverse/find leaves/etc first, then go back and add the computational logic and enhance the storage.
if the number of nodes is going to be large, you may want to consider basing the tree out of a vector (push back into vector, take the address of that, use that in the tree pointer string or use the array index itself as the 'pointer' ).
if the number of nodes is going to be large, you may want to consider basing the tree out of a vector (push back into vector, take the address of that, use that in the tree pointer string or use the array index itself as the 'pointer' ).
Last edited on
closed account (yUCGwA7f)
Is there any good approach to solve it? other than the stereotypical method.
That is what I meant.
That is what I meant.
Most leaves will share most of their path back to the root. So make sure you never have to sum the same node twice; once you've summed a path for one leaf, you can reuse most of that work for leaves that share the path.
well since this is an ongoing CodeChef contest question, I can only provide you with a hint...think greedily as to how would you maximise the possible sum at a give node from its children...think how would you find whether you should keep a given node n or remove it from your answer in the bottom up fashion meaning that use the children of a node to think whether that node should be kept or removed.
@honeybuzz I think you have given hint for another question.
Last edited on
It seem to question from an on going contest https://www.codechef.com/APRIL19B/problems/SJ1
still if you want that badly here you can buy i guest but I have not tried https://www.instamojo.com/Allexamcorner/
https://www.instamojo.com/Allexamcorner/playing-with-numbers-sj1-codechef-problem-so/?ref=store
still if you want that badly here you can buy i guest but I have not tried https://www.instamojo.com/Allexamcorner/
https://www.instamojo.com/Allexamcorner/playing-with-numbers-sj1-codechef-problem-so/?ref=store
Last edited on
Topic archived. No new replies allowed.