ECPC10D - Editorial

PROBLEM LINK: Tree and Unwanted leaves

Author: Sumeet Pachauri
Tester: Pankaj Sharma
Editorialist: Sumeet Pachauri

Difficulty:

Easy-Medium

Prerequisites:

Generic Trees, DFS

Problem:

There exist a rooted tree with n nodes, in each operation on the tree: all leaf nodes with count in a multiple of 3 and with the same parent node are removed. Also if all children of a parent are removed it becomes a new leaf node and the operation is again repeated until the operation can not be performed. The number of nodes finally left on tree after all operations is the required answer.

Explanation:

Keenly observing the question we just need to use a count for each node and add the nodes which

  1. are a leaf node
  2. are a potential leaf node(they will turn into a leaf node, after one or more operations) under the condition that the leaf nodes and potential leaf nodes are originating from same parent.

Identifying potential leaf node: If the count calculated above is equal to the total child nodes of a parent node and is a multiple of 3, then this parent node is a potential leaf node.

If count is not a multiple of 3 it is assigned a number which is a multiple of 3 and is also the maximum possible such number lesser than count

Sum of count of all nodes can be saved in a counter.
Subtracting the value in counter from the total nodes will give the required answer, the nodes finally left on the tree.

DFS: Applying dfs on root node which is given as 1, and moving to adjacent nodes until a leaf node is reached, and then backtracking to repeat it for other leafs too. For each parent under consideration, declaring count variable and counting leaf or potential leaf nodes. Encountering leaf node or potential leaf node, returns 1 otherwise 0 is returned.

Solution:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define int               long long
#define fastio			  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0                return 0
#define test			  int T; cin>>T; while(T--)

vector<int> tree[100001];
int cnt;
//this function follows dfs approach
int cntleaves(int n)
{   // leaf node, return 1 to its counter 
    if(tree[n].size()==0)
    return 1;
    else
    {   //counter for the current node under consideration
        int count=0;
        
        for(int i=0;i<tree[n].size();i++)
        {   
            count+=cntleaves(tree[n][i]);
        }

        //counted leafs and potential leafs sum up to the total child nodes, 
        //hence node under consideration is a potential leaf node, and returns 1 to its counter
        if(count%3==0&&tree[n].size()==count)
        {   cnt+=count; 
            return 1;
        }
        //all other cases won't cause current node to be a potential leaf node, hence returns 0
        //if count is greater than or equal to 2, the Unwanted leafs are counted out of 
        //the variable 'count' and removed 
        else
        if(count>2)
        {
            int temp=count/3;
            cnt+=(temp*3);
            return 0;
        }else
        return 0;
    }
}

void solve()
{   
    for(int i=0;i<100001;i++)
        tree[i].clear();
	int n;
    cin>>n;
    tree[0].push_back(-1);
    for(int i=1;i<n;i++)
    {
        int x;
        cin>>x;
        tree[x].push_back(i+1);
    }
    cnt=0;
    // cntleaves either return 1 or 0, if it is 1 then root node is itself either a leaf or potential leaf node
    if(cntleaves(1))
    cout<<"1\n";
    else
    cout<<n-cnt<<"\n";    
} 

signed main(){
	fastio
	test
		solve();
	r0;
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

2 Likes

I tried doing this but I it gave me WA somewhere
39285453

Can you please point out what’s wrong with this code ?

WA CODE
#include<bits/stdc++.h>
using namespace std ;
const int mxN =1e5+2 ;
int n,a[mxN],ans;
vector<int>adj[mxN] ; 
int ok[mxN]  ;
void dfs(int v=1,int p=0){
  for(int x:adj[v])
    if(x^p)
      dfs(x,v) ;
  int r=0 ;
  for(int x:adj[v]){
    if(x==p)
      continue; 
    r+=ok[x] ;
  }
  if(r%3==0)
    ok[v]=1 ;
  ans-=(r/3)*3 ;
}
void solve(){
  cin >> n ;
  for(int i=1;i<n;i++){
    cin >> a[i] ;
    adj[a[i]].push_back(i+1) ;
    adj[i+1].push_back(a[i]) ;
  }  
  ans =n ;
  dfs() ;
  cout << ans << '\n' ;
  for(int i=1;i<=n;i++)
    adj[i].clear()  ;
  memset(ok,0,sizeof(ok)) ;
  memset(a,0,sizeof(a)) ;
}
signed main(){
  int t ;
  cin >> t ;
  while(t--)
    solve() ;
}

Whats wrong with the logic of my code ? https://www.codechef.com/viewsolution/39285878

Try this input
2
17
1 1 1 1 1 4 3 4 4 3 4 3 6 5 5 5
15
1 1 1 3 3 3 3 3 5 6 6 12 12 12
Correct -
5
9
Yours
5
6

1 Like

Found my problem . Wasnt counting the nodes which cant be deleted

Try this
2
17
1 1 1 1 1 4 3 4 4 3 4 3 6 5 5 5
15
1 1 1 3 3 3 3 3 5 6 6 12 12 12

Oh thanks broski
I was stuck on this for a long time
Thanks for the help :smile:

Thanks @ash432, the testcase you mentioned is where above mentioned codes fail,
Feel free to write if you need me again here :grin: :blush:

@kaalbhairav01 Hi In Question :
(i) For each parent node(which has a valid leaf node attached to it). Can u explain valid leaf nodes means?
(ii) If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node. (from this what I understand is count only leaf nodes and if the count of the leaf node is multiple of 3 then parent also become new leaf but in the editorial problem statement says if all children of a parent are removed it becomes a new leaf node which means I have to check non leaf node also ).
can u explain why my understanding is wrong

@sivayempalli

  1. You can see that in the problem statement, leaf node was defined as the one, with no outgoing edges

  2. “if a parent has all its leaf nodes cut”, this is the source of confusion I assume, carefully reading further and to full, the question provides every non leaf node a scope to convert itself into a leaf node. The counting of any non leaf node can not be skipped as such because there would be no guarantee if it had the capability to turn into a leaf node. Hence if you have checked all child nodes of a parent to see if a non leaf node can become leaf, only then will you know the actual number of leaf nodes. We require a strong basis to not take into account a node which is non leaf, which can’t be obtained without checking it. Now after confirming all nodes which are “actually leaf”, we can count them and if this count is a multiple of 3, all of them will be removed, so in this case all child nodes are being removed, and all child nodes were leaf nodes too.

Also see the explanation to sample testcase, for better clarity, you can also think of a sudoku or minesweeper, where you must be sure before taking the decision. Same goes with ignoring a non leaf node.
Hope it helps

Thanks man.one point
for example, a parent node with child nodes is (1 leaf and 2 potential leaf nodes and 2 non-leaf nodes(its child node are not multiplies of 3 )). this information I will get doing dfs on parent node . now what I’m doing is counting leaf node and potential leaf node (1+2 = 3) so 3 multiply of 3 so I’m considering parent as a potential leaf node.

But after reading the editorial, what I got is, for that parent 2 non-leaf child node are present so parent cannot be a new leaf node or potential leaf node

Can u explain for this example?

Hey brother, I recognise the confusion you are referring to, and that is why the case similar to the one you wrote was shown in the explanation which might be you have missed out, here
Sample1
Consider node 4 which had 3 nodes removed but was not considered a leaf because it still had a outgoing edge. “If a parent has all its leaf nodes cut, only then the parent node itself becomes a new leaf node” the line is the next parameter for any parent node to satisfy, it nowhere demurs the basic definition of leaf node- which has no outgoing edges as written in the problem statement, i hope the explanation image above clarifies it in the question

Hi, have you uploaded the Editorials for ECPC10E, ECPC10F and ECPC10G? If not, could you please upload it? If yes, could you please provide the link? I am not able to find them.
Thanks

Hey there @shashank2409 , Those three editorials are underway and will be posted as soon as possible, the same will be notified on the Contest Invitation post too. The delay has occured due to the sudden ill health of the setter cum editorialist, we hope the wait will be worth

1 Like

Okay. Not an issue. Hope he gets well soon. :slight_smile:

I’m thinking about a solution where I would find the level of every nodes, then going up level by level from the leaf nodes, calculating how many nodes will be deleted and which parent will no longer be parent node, would this work ?

@shashank2409 They are available now, refer to rest editorials here Invitation to ECPC 1.0

Okay. Thank you.

@bubu2006, as i see that, it’s a straight forward dfs approach ques, however what you wrote sounds exactly what needs to be done, it depends on your implementation, you can try that

1 Like