Whats wrong with algo of SUBREM

1

I tried to solve the CodeChef: Practical coding for everyone using the following algorithm, but got WA.
Solution
Can someone help me whats wrong with the algo.

At every node I maintain 3 values

  • first: number of cut operations performed in it’s subtree
  • second: total sum of the nodes in the subtree after the cut operation has been performed.
  • third: total sum of the nodes in the subtree when the cut operation has not been performed. This value is used to decide whether I cut this particular node itself, so that all the child cut operations can be converged to 1 by cutting all their parents.
  • My final answer to the problem is: second - first *X

Logic to cut/not cut is if sum of the subtree < 0 and |sum|>X, then I cut.

Excerpt from my solution

  ilpair compute(int u, vector<vector<int> > &adj, vector<int> &weights, int X) {
    
    long total=0;
    ilpair ans;
    // initialise the ans to 000
    for(auto v:adj[u]) {
        pair<int, lpair > p = compute(v,adj,weights,X);
        ans.first+= p.first;
        ans.sec+=p.sec;
        ans.third+=p.third;
    }
    ans.sec+=weights[u];
    ans.third+=weights[u];
    if(ans.sec<0&&abs(ans.third)>X) {
        // remove 
        ans.first=1;
        ans.sec=0;
    }
    return ans;
}
1 Like