Chef-Detective Codechef Solution

Chef-Detective Codechef Solution: 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 And His Characters – 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+" ");
	        }
	    }
	}
}

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  Chase2learn.This tutorial is only for Educational and Learning purpose.

Leave a Comment