Chef-Detective Codechef Solution

Hello Programmers In this post, you will know how to solve the Chef-Detective Codechef Solution.

Ezoicreport this adChef-Detective Codechef Solution
Chef-Detective Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

Chef is a private detective. He was asked to investigate a case of murder in the city of Frangton.

Chef arrived in Frangton to find out that the mafia was involved in the case. Chef spent some time watching for people that belong to the clan and was able to build a map of relationships between them. He knows that a mafia’s organizational structure consists of a single Don, heading a hierarchical criminal organization. Each member reports exactly to one other member of the clan. It’s obvious that there are no cycles in the reporting system of the mafia.

There are N people in the clan, for simplicity indexed from 1 to N, and Chef knows who each of them report to. Member i reports to member Ri.

Now, Chef needs to identfy all potential killers to continue his investigation. Having considerable knowledge about the mafia’s activities, Chef knows that the killer must be a minor criminal, that is, one of the members who nobody reports to. Please find the list of potential killers for Chef. Since Don reports to nobody, his Ri will be equal to 0.

Input

The first line of input contains one integer N.

Next line has N space-separated integers, the ith integer denotes Ri — the person whom the ith member reports to.

Output

Output a list of space-separated integers in ascending order — the indices of potential killers.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Ri ≤ N except for Don, whose Ri equals to 0.
  • It is guaranteed that there are no cycles in the reporting structure.

Subtasks

  • Subtask #1 [50 points]: N ≤ 10000
  • Subtask #2 [50 points]: No additional constraints

Sample Input 1 

6
0 1 1 2 2 3

Sample Output 1 

4 5 6

Explanation

The reporting structure:

Chef-Detective Codechef Solution

Chef-Detective CodeChef Solution in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc=new Scanner(System.in);
	    int n=sc.nextInt();
	    Set<Integer>s=new HashSet<>();
	    for(int i=0;i<n;i++){
	        s.add(sc.nextInt());
	    }
	    for(int i=1;i<=n;i++){
	        if(!s.contains(i)){
	            System.out.print(i+" ");
	        }
	    }
	}
}
Ezoicreport this ad

Chef-Detective CodeChef Solution in CPP

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define ld long double
#define phb push_back
#define phf push_front
#define ppf pop_front
#define ppb pop_back
#define in insert
#define as assign
#define nle "\n"
#define fastinput ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int main() {
	fastinput;
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	lli n;
	cin>>n;
	map<lli,lli>m;
	for(lli i=1;i<=n;i++) {
		lli a;
		cin>>a;
		m[a]++;
	}
	for(lli i=1;i<=n;i++) {
		if(m[i]==0)
			cout<<i<<" ";
	}
	cout<<nle;
    return 0;
}

Chef-Detective CodeChef Solution in Python

from sys import stdin, stdout
RL =  lambda : stdin.readline().rstrip()
RLM = lambda : map(int, RL().split())
WL =  lambda s="": stdout.write(s + "\n")
n = int(RL())
R = set(RLM())
r = sorted(set(range(1, n+1)) - R)
WL(" ".join(map(str, r)))

Disclaimer: The above Problem (Chef-Detective) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Chef And His Characters Codechef Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad