UnOfficial Editorial - Playing With Numbers - SJ1

editorial
1

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.

2 Likes
2

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);
                }
            }
3

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