SUBREM - Editorial

editorial
, , , , ,
2

My solution also uses dfs and has the exact same logic yet I get TLE on some cases. What am I doing wrong?

#include<bits/stdc++.h>
#define ll long long int
#define li long int
using namespace std;

typedef vector<long long int> vi;
typedef pair<ll, ll> pi;

#define EB emplace_back
#define REP(i, x, y) for(long long int i=x ; i<y ; i++)
#define F first
#define PB push_back
#define S second
#define MP make_pair
#define MT make_tuple
#define INF 9999999
#define MOD 1000000007

struct node{
    ll val;
    vector<ll> children;

};

ll pruneornot( node lol , ll x, vector<node> points, ll visited[])
{
    vector<ll> z =lol.children;
    cout<<lol.val<<" \n";
    ll len = z.size();
    ll sum = 0;
    REP(i,0,len)
    {
        if( visited[z[i]]!=1 )
        {
            visited[ z[i] ]=1;
            sum+= pruneornot( points[z[i]], x , points, visited);
        }
    }
return max(-x , lol.val + sum);

}

int main()
{
ios::sync_with_stdio(0);
ll t;
cin>>t;
while(t–)
{
ll n;
ll x;
cin>>n>>x;
ll visited[n];
vi a(n);
vector points(n);
points.clear();
REP(i,0,n)
{
cin>>a[i];
visited[i]=0;
points[i].val=a[i];
}
ll u,v;
REP(i,0,n-1)
{
cin>>u>>v;
points[u-1].children.emplace_back(v-1);
points[v-1].children.emplace_back(u-1);
}
visited[0]=1;
cout<<pruneornot(points[0], x ,points,visited)<<"\n";

}
return 0;

}

2 Likes
3

Is there any Greedy approach relevant to this problem ?

7 Likes
4

My solution is same as editorialist :XD

1 Like
5

if anyone can look at this solution why is this wrong ?
https://www.codechef.com/viewplaintext/23985717

so approach is sort every node by increasing order of subtree sum( self included) , now whoever is less than -X , that can be removed as it will yeild positive profit, then i updated parents to accomodate that node removal and update children to have subtree sum 0

also this should be amortized linear , but i got TLE too , did i miss anything

1 Like
6

Can someone provide a good test case for the problem, I tried solving it using dictionary and approach similar to given above but got WA. https://ideone.com/JsVXlp (python)

1 Like
7

I think Haskell’s TLE (< 1.01) is too restrictive compared to other languages.
I tested Python3 and C++14 with the same algorithm (as the Editorial) and they pass.
In my attempt of the Haskell codes, I tried Array of List, Sequences, IntSet, and IntMap of Sequences to see all in vain.
Another point of view of unfair TLE for Haskell is that CodeChef configuration does not allow to use Data.Vector which is considered to be the fastest.
I just want to have you consider to either loosen up the TLE for Haskell or to allow Data.Vector library to be used.
Thank you,

  • TJ
1 Like
8

please anyone help me
.
.
i am using exactly the same logic but it is wrong answer
.
.

t=int(input())
lis1=list()
dic=dict()
#dic=dict()
#sum=[]
k=0
def maxi(i):
return max(-k,lis1[i-1]+sum(map(maxi,dic[i])))

while t!=0:
n,k=map(int,input().split())
lis1=list(map(int,input().split()))
dic=dict()
for i in range(1,n+1):
dic[i]=[]
for i in range(n-1):
a,b=map(int,input().split())
if a in dic:
dic[a].append(b)
else:
dic[a]=[]
dic[a].append(b)

print(maxi(1))
t=t-1

i have declared list,dictionary and (X) global.
is it wrong ?
3 Likes
10

I need help please. I used the same logic as the editorialist but I have WA CodeChef: Practical coding for everyone

1 Like
11

Try adding the followings at the top:

import sys
sys.setrecursionlimit(10**5)

3 Likes
12

Here is my easy to understand ac code,you have to sum the value of nodes of a given subtree and check whether its value is less than -x or not,if it is replace it with -x
//subtree removal
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
vectoradj[100005];
ll a[100005];
ll dp[100005];
ll visited[100005];
ll n,x;

void dfs(ll u)
{
visited[u]=true;
dp[u]=a[u];
ll sum=a[u];
for(ll child : adj[u])
{
if(!visited[child])
{
dfs(child);
sum+=dp[child];
}
}
if(sum<-x)
dp[u]=-x;
else
dp[u]=sum;
}

int main()
{
int t;
cin >> t;
while(t–)
{
cin >> n >> x;
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
memset(visited,false,sizeof(visited));
memset(adj,0,sizeof(adj));
for(int i=1;i<=n;i++)
cin >> a[i];
ll u,v;
for(int i=1;i<=n-1;i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
cout << dp[1] << endl;
}
return 0;
}

5 Likes
13

Didn’t check your logic but Why TLE?

Hint:
Argument Passing to Functions
- Pass by Value
- Pass by Reference
3 Likes
14

Hi,

One thing that is still confusing me is the number of operations ‘k’. Our objective is to minimize the value “X*k” and hence k should only take values 0 or 1 (depending on whether we remove any subtree or not). As per my solution, I found the maximum value of remaining nodes by subtracting each subtree sum from whole tree sum i.e. max(sum(root)- sum[i](for all subtrees)).

I am not able to see any case left in this approach but still getting the wrong answer.
My solution: https://www.codechef.com/viewsolution/23943487

1 Like
15

Why we need to add an edge from v to u if we have initialized an edge from u to v already?
If we don’t add an edge from v to u I got wrong answer why is it so? Please explain.

3 Likes
16

Oh thanks a lot.
I understand now. I used to feel that vectors, like arrays, are sent by reference but instead vectors are sent by value and a copy is generated. Due to recursive nature of function, sending by value leads to TLE. After sending by reference, it works correctly.

2 Likes
17

Check the Sample Input again.

1
3 5
1 -5 -10
1 2
2 3
1 Like
18

still wrong answer
is there any problem in declaring the list and dict global ?

1 Like
19

I guess you can’t understand the question.

The question states that you can remove ANY number of subtrees, which are ‘k’ and your profit at the end is the (sum of values of the nodes left in tree - x * k).

You can remove more than one subtree also to maximize the profit. You have to take some test cases and understand that.

Hope this helps :slight_smile:

1 Like
20

dats what i have done .
u can check my soln.

1 Like
21

How do we know about the count (k) of deletions? I didn’t understand the the mathematical equation?

1 Like
22

With this input, following my solution, we get:

  1. whole tree sum[1] = -14
  2. sum of subtree rooted at 2, sum[2] = -15
  3. sum of subtree rooted at 3, sum[3] = -10

Now, max sum we get by trying removing every subtree, (sum[1]-sum[i], for each i<=N), is 1.
now, since k = 1, answer will be 1-5*1, i.e. -4 which is expected.

I’m not sure what kind of case seem to be missing.

1 Like