When will the editorial of codejunk will come

please someone tell when the editorials for problem of codejunk will come …
meanwhile … can someone share the approach to solve this problem…
https://www.codechef.com/COJK2020/problems/CKOJ20C
I am thankful to every help offered …

1 Like

I think I might have an approach. I have not participated in the contest nor implemented it so I am not certain it will work.

The most important observation is that the input graph is a tree. This follows from the fact that the tree is connected and contains one vertex more than the number of edges.
The second observation is that the values A_i don’t matter, only if they are prime or not.

How I would solve the problem

I would first root the tree. Then I would calculate two values for each vertex: min_i and max_i , the minimum/maximum value of prime-composite that can be achieved in the subtree below vertex i. This can be done in \mathcal{O}(n) when considered in leaf-root order. Next I would evaluate the vertices in root-leaf order to update the max and min values to represent the maximum/minimum value for the whole graph. Again this could be done in \mathcal{O}(n). And finally print out ans_i=\max(-min_i,max_i)

1 Like

thanks for your help… really appretiated it

It can be done by using in-out dp considering first for only primes for computing in-out dp (by making a[i] = 1 for prime and a[i] = -1 for non-prime) and then considering only non-prime for in-out dp(make a[i] = 1 for non-prime and a[i] = -1 for prime).

Where in-dp[u] for a node is the maximum we can gain from all of it’s children(v1, v2, … vn). This can be done by basic dfs by fixing a node as a root.

Code for in-dp
    void dfs (int u, int par) {
           in[u] = a[u];
           for (int v: g[u]) {
                if(v != par) {
                        dfs(v, u);
                        in[u] += max(0LL, in[v]);
                }
          }
    }

and out-dp[u] for a node is what we can gain outside the subtree of u. So simply we have to ask the parent. (here in out[u] I am storing max of max(in[u], out[u]))

Code for out-dp
    void dfs2(int u, int par) {
         out[u] = in[u];
         if(par) {
               if(in[u] >= 0) {
                     out[u] = max(out[u], out[par]); 
                }
               else {
                    out[u] = max(out[u], in[u] + out[par]);
               }
         }
         for(int v : g[u])
              if(v != par)
                 dfs2(v, u);
}

and final ans node i = max(out1[u], out2[u]);
out1: when considering primes only, out2: considering non-prime only.

Full Code
vector<bool> prime(N + 1, 1);

void seive(){
    prime[0] = prime[1] = 0;
    for(int i = 2; i * i <= N; ++i) {
        if(prime[i]) {
            for(int j = i * i; j <= N;j += i)
                prime[j] = 0;
        }
    } 
}

int a[N], in[N], out[N];
vvi g;
int ans[N];

void dfs(int u, int par) {
    in[u] = a[u];
    for(int v: g[u]) {
        if(v != par) {
            dfs(v, u);
            in[u] += max(0LL, in[v]);
        }
    }
}

void dfs2(int u, int par) {
    out[u] = in[u];
    if(par) {
        if(in[u] >= 0) {
            out[u] = max(out[u], out[par]);
        }
        else {
            out[u] = max(out[u], in[u] + out[par]);
        }
    }
    for(int v : g[u])
        if(v != par)
            dfs2(v, u);
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    seive();    
    int n;
    cin >> n;
    g = vvi(n + 1);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = 2 * prime[a[i]] - 1;
    }

    for(int i = 0; i + 1 < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }

    dfs(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; ++i) {
        ans[i] = out[i];
    }
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    
    for(int i = 1; i <= n; ++i) {
        a[i] = -1.0 * a[i];
    }
    dfs(1, 0);
    dfs2(1, 0);

    for(int i = 1; i <= n; ++i) {
        cout << max(ans[i], out[i]) << ' ';
    }
    cout << '\n';
    return 0;
}
3 Likes

thanks a lot for your help…

1 Like