UnOfficial Editorial - Playing With Numbers - SJ1

Problem Link
Contest

Statement

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-1 ,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.

Constraints

  • 1 ≤ T ≤ 8
  • 2 ≤ N ≤ 105
  • 1 ≤ x , y ≤ N
  • 1 ≤ v i ≤ 1018 for each valid i
  • 1 ≤ mi ≤ 1018 for each valid i
  • the graph described on the input is a tree

Soln:

  • The very first idea is if in the worst case the height of the tree can be N here and every node can contain a value up to 1018 , So if we are going to add these the result of addition can be upto 1023 , then probably we shouldn’t add these.

  • Again we have to calculate modulo then we know that -

       m % n = we can make it upto ( n-1 ) by multiplying some number but not always.
    
       if m and n are co-prime or we can say if they have gcd equals to 1 then we can make it.
       but if their gcd's are not equal to 1 then the maximum value of m%n will
       be = n-gcd(m,n)
       try this it is a nice observation.
    
  • So why not we try to make the gcd of every element , that occurs in the path from root to the leaf node ,equals to 1. Then we have to take the cumulative gcd of the element occurring in that path.

  • How do we get the path?

  • Now we can apply dfs from root node and store the cumulative gcd’s like this-

    void dfs(int node , int parent){
      visited[node] = true;
      cumulative_gcd[node] = gcd(value[node],cumulative_gcd[parent]);
      for(auto neighbour : tree[node]){
        if(visited[neighbour] == true)
          dfs(neighbour,node);
     }

  • Now at last we can collect all the leaf node (index ) and sort them in increasing order.

  • Then we’ll apply our gcd trick to get the answer for every leaf.

[Solution Link with comments]

Any doubts or questions are Welcomed.


PS: This is my first editorial on CodeChef. Any suggestion are also welcomed
Happy Coding
Thank You CodeChef.

1 Like

My approach was somewhat more direct. First, process the tree so that for every node we store its parent node and an array of its children (stored in ‘Links’ in the C# code fragment below).

Them for each leaf, evaluate GCD of M and each V on path back to root.

            for (i = 0; i < n; ++i) {
                if (nodes[i].Links.Count == 0) {
                    // This node is a leaf
                    int j = i;
                    long g = nodes[j].M;
                    do {
                        g = GCD(nodes[j].V, g);
                        j = nodes[j].Parent;
                    } while (g > 1 && j >= 0);
                    long result = nodes[i].M - g;
                    // Add result to output buffer
                    CopyChars(LongToString(result), ref out_count, out_str);
                }
            }

It is the same logic that you are calculating gcd of that node with it’s parent. :smile: