CHEFDETE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Maksym Bevza
Tester: Istvan Nagy
Editorialist: Miguel Oliveira

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given a rooted tree with N nodes, what nodes are leaves?

A leaf is a node with no children when we walk down the tree from the root node (the Don).

EXPLANATION:

We are given a list R of N integers, where element R_i denotes to whom person i reports to.
For every person P, we want to know if there is any other person reporting to P.

Subtask1

A simple approach is: for every person i, search the given list to see if anyone reports to i.

for i from 1 to N do
    for j from 1 to N do
        if R[i] equals i then  
            person j reports to i and is not a leaf
    if person i does not have any reports, add to solution

For every person, we do a linear scan on the given list. It’s clear that the time complexity of this approach is O(N^2) which was enough for the first subtask but not for the second.

Subtask 2

We can do better. We really just want to know for every person P if there is anyone that reports to P.

There are several ways to do this efficiently. A simple way is to use a boolean array, e.g. has_reports, and use this to store if node i has anyone reporting to it. We can process the given list only once and mark has_reports[i] to true when someone reports to i. Sample pseudo-code:

Initialise has_reports array to false in all positions
for i from 1 to N do
   has_children[R[i]] = true
for i from 1 to N do
   if has_children[i] is true then
      print i 

We only process the list once and use an array to mark the reports information. So the time complexity of this approach is O(N). Also, the space complexity is O(N).

Sample Solutions

Author
Tester
Editorialist

This problem can also be solved by using std::set in c++.

Initially we assume that every node is in the answer and add to the set(containing the answers)

Since, ith node reports to a[i] (i is the child of a[i]), that means a[i] is the parent.

So, a[i] cannot be in the answer we need to remove it if it is there!

After removing all the parents, we are left with the leaf nodes in the answer set!

One such solution : CodeChef: Practical coding for everyone

5 Likes

I have done the same thing. But I have used set_difference() to find the set of leafs.

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

2 Likes

To all the people who are saying that this can be solved using sets, you are right,

but beware because the access time of a set is O(log(N)) where N is the number of elements in a set.

you can view my accepted solution for simple implementation. AC Solution

1 Like

@admin

In subtask 2 code,

in second loop, it should be false instead of true

if has_childred[i] is false then
     print i
1 Like

i’m still not getting the question what is the input we’re taking in second line?
whats the meaning of this line-
“Next line has N space-separated integers, the ith integer denotes Ri — the person whom the ith member reports to.”

can anyone tell me that why i am getting AC when i am taking array a globally (CHEFDETE Problem - CodeChef) and why wrong on taking array inside tha main function?(CHEFDETE Problem - CodeChef )

Subtask 1:

Line 3 should be:

if R[j] equals i then

But very inneficient…

whats the meaning of input we’re giving i’m just not getting it but i understood the question correctly.

Hello Chefs,

Will you please help me on the following code, why it is getting partially accepted ?

n = int(input())
s = set(list(map(int,input().split())))
l = range(1,n+1)
l = set(l)
l = l-s
for i in l:
    print(i,end=' ')

What’s wrong with this code . This code checks which node have 0 child i.e leaf should be accepted acc. to me can some one have a look and tell me what’s wrong ?

#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
vector<int> tree[MAX];
int child[MAX];
void dfs(int u,int p){
    for(int v : tree[u]){
        if(v==p){
            continue;
        }
        else{
            dfs(v,u);
            child[u] += child[v]+1;
        }
    }
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	int n; cin>>n;
	int u,v;
	cin>>u;
	memset(child,0,sizeof(child));
	for(int i=2;i<=n;i++){
	    cin>>u;
	    v=i;
	    tree[u].push_back(v);
	    tree[v].push_back(u);
	}
	
	dfs(1,0);
	for(int i=1;i<=n;i++){
	    if(child[i]==0){
	        cout<<i<<" ";
	    }
	}
	return 0;
}

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

it’s failing some cases ,
need help
https://www.codechef.com/viewsolution/54250909