THOUSES - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Anshul Garg
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Greedy, Exchange argument.

PROBLEM

Given a tree with N nodes numbered from 1 to N with root at node 1, You need to Assign values to nodes satisfying following conditions.

  • value of node 1 is X
  • All immediate children of a node have pairwise distinct values
  • For all nodes having at least one child, the gcd of value of child nodes must be equal to the value of node.

Among all such assignments, find the sum of values of node in the assignment which minimizes the sum of value of nodes.

QUICK EXPLANATION

  • For each node, calculate the contribution of the subtree of a node assuming the root of subtree is assigned 1.
  • Considering all children of a node, assign 1 to the child with largest contribution, 2 to second largest contribution and so on.

EXPLANATION

Let us make a couple of observations first.

Observation 1: Value of a child node is a multiple of value of its parent node, since gcd of value of children nodes is equal to value of parent node.

In order to minimize sum, if value of parent node is x, it makes sense to assign value to children nodes as multiples of x, say x, 2*x, 3*x \ldots k*x where k is the number of immediate children. This way, gcd of values of immediate children would be equal to the value of node as well.

Now, we need to order the children in some optimal way so as to minimize sum.

Observation 2: For a subtree rooted at node u, if we find an assignment of values to nodes in subtree of u where A_u = 1, We can multiply the values in subtree by A_u to obtain a value assignment without violating any conditions, with the sum of values being multiplied by A_u as well.

Significance of observation 2: This observation allows us to compute the contribution of nodes in subtree of node u, irrespective of value assigned to node u. Hence, we can first compute it’s contribution, and then assign value so as to minimize sum.

Let’s denote the sum of value of nodes in subtree of node u, assuming A_u = 1 by f(u). For leaf nodes, f(u) = 1, since the only node in subtree has value 1.

If u is not a leaf node, assuming it has k children, we can see that each child will be assigned value from 1 to k such that each child gets a distinct value. Let’s assume node u has children a and b. Then f(u) = 1 + min(f(a) + 2*f(b), f(b) + 2*f(a)). We can see that if f(a) < f(b), it makes sense to assign 1 to b and 2 to a.

Formally, to minimize sum, we should assign children values from 1 to k by first ordering children in the non-increasing order of their contribution function. It can be proven using exchange argument that this assignment minimizes sum.


dfs(f, u):
    f(u) = 1
    list = []
    for(v in g[u]):
        dfs(f, v)
        list.append(f[v])

    list.sort(reverse=True)
    for i in range(len(list)):
        f(u) += (i+1)*list[i]

Finally, after computing f(1), which assumes A_1 = 1, we can multiply value of all nodes by X, effectively multiplying the sum of values by X, to obtain minimum sum assignment with root node having A_1 = X. Hence, X*f(1) is the required sum of values.

What if the values during computation of f(1) overflows?

It won’t happen with long long int. The maximum values we were able to achieve were for tests like star, stars attached at end of binary tree. Even in those cases, the maximum values we were able to achieve were near 10^{11}. Please let me know if you can achieve higher values.

Getting WA on last 1 or 2 files?

Those files were intended to fail some solutions taking MOD, or using int and getting overflow.

TIME COMPLEXITY

The time complexity is O(N*log(N)) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
const int mod = 1000000007;
 
vector<int> adj[500001];
 
int dfs(int node, int parent) {
    multiset<int> s;
    for (auto i : adj[node]) {
        if (i == parent) continue;
        int ans = dfs(i, node);
        s.insert(ans);
    }
    int res = 1, val = 1;
    for (auto i = s.rbegin(); i != s.rend(); i++) {
        res += (val++) * (*i);
    }
    return res;
}
 
void solve() {
    int n, x; 
    cin >> n >> x;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans = dfs(1, -1); ans %= mod;
    cout << (ans * x) % mod << endl;
    for (int i = 1; i <= n; i++) adj[i].clear();
}
 
signed main() {
    fast
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
Tester's Solution
import java.util.*;
import java.io.*;
class THOUSES{
    //SOLUTION BEGIN
    long MOD = (long)1e9+7;
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long X = ni();
        int[] from = new int[N-1], to = new int[N-1];
        for(int i = 0; i< N-1; i++){
            from[i] = ni()-1;
            to[i] = ni()-1;
        }
        int[][] tree = make(N, from, to);
        long[] f = new long[N];
        dfs(tree, f, 0, -1);
        long ans = f[0]%MOD*X%MOD;
        pn(ans);
    }
    void dfs(int[][] g, long[] f, int u, int p){
        List<Long> list = new ArrayList<>();
        for(int v:g[u]){
            if(v == p)continue;
            dfs(g, f, v, u);
            list.add(f[v]);
        }
        Collections.sort(list, Collections.reverseOrder());
        f[u] = 1;
        int mul = 1;
        for(long x:list)
            f[u] += x * mul++;
    }
    int[][] make(int N, int[] from, int[] to){
        int[] cnt = new int[N];
        for(int x:from)cnt[x]++;
        for(int x:to)cnt[x]++;
        int[][] g = new int[N][];
        for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< N-1; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new THOUSES().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

4 Likes

https://www.codechef.com/viewsolution/46599314

Can anybody please tell me why my this solution is giving runtime error.Please can any one help ?

https://www.codechef.com/viewsolution/46600948
Why does this give WA on test 3 and 6?

2 Likes

Try removing dp[u]%=mod in line 32.

Solution: 46525056 | CodeChef.
I am not getting why first 2 testcases are not passing. I used a heap and sorted them based on number of children .

Am I the only one who thinks that this question should be in Medium category? Anyway nice explanation.

2 Likes

https://www.codechef.com/viewsolution/46586547
getting wrong answer in first two cases plz help anyone !

2 Likes

can you tell me why removing this gives the correct answer .
What is the problem here @ayush_2407

Hi Team,

Can anyone help with counter example for my solution Solution: 46575836 | CodeChef where it failed. I was thinking of the same approach but clearly may have made mistake in implementation.

Thanks in Advance

Has any done by bfs??

Remove all \%MOD you have used and write one in the final answer. I think that should fix your code.

yes me !@karina1234

Thanks for help leo. This was one of the issue. 1)Needed to remove mod 2) use lon long int in the pair in the vector I used for sorting 3) in the dfs recursive call I haven’t used the braces properly adn was adding the parent as well in the vector.

https://www.codechef.com/viewsolution/46604384

fixed them all

Have you got the correct answer

https://www.codechef.com/viewsolution/46591172

could you help me where is the bug

first 2 test cases is not accepted @karina1234

https://www.codechef.com/viewsolution/46495679

is my solution. Did the same way as described by @taran_1407
But getting TLE on 1st and 3rd Test cases and WA on 2nd test case, don’t know why. Please help me find the error in the code.
For TLE, can anyone tell me the reason and for WA can someone share the testcases that FAIL
For the help, Thanks in advance;)

Not sure though it worked for me as well. I think maybe taking mod will not compare the actual answer for each child and as mentioned above if it dose not overflows then its better to remove it.

2 Likes

@ayush_2407 can you plz me ! why it is not accepting 1st 2 cases using bfs traversal;

I think there is a problem in the test case itself… For me as well, removing mod is giving correct answer but this does not makes sense…