CHEFDETE - Editorial

editorial
, , , ,
1

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

2

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 : https://www.codechef.com/viewsolution/9426100

2 Likes
3

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

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

1 Like
4

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.

5

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

1 Like
6

But very inneficient…

7

@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
8

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.”

9

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

10

can anyone tell me that why i am getting AC when i am taking array a globally (https://www.codechef.com/problems/CHEFDETE) and why wrong on taking array inside tha main function?(https://www.codechef.com/problems/CHEFDETE )

11

Subtask 1:

Line 3 should be:

if R[j] equals i then