Join Us
Loading Similar Posts
Entering edit mode
Question 1
The MNIC "CompSoft" maintains a hierarchy for its employees. In the hierarchy there are N employees with employee ID labeled from 1 to N. The CEO of the company is the head of the hierarchy with ID 0. If
employee X is working under employee Y, then Y will be the manager of X and so on. At the end of the year the company had made extra profit on some of its projects so they have decided to award some employees with
bonuses. The company uses this hierarchy to distribute bonuses among its employees. If an employee has worked on a project then the manager of the employee will be given bonus. For example in the given hierarchy X-Y-Z where Y reports to X and Z reports to Y, If employee Z has worked on the project then bonus will be offered to the highest person in the hierarchy LeX. If X has already got the bonus earlier then Y will get the bonus and in case Y also has earlier got the bonus then Z will get the bonus. Similar bonus allocation pattern will be followed for all the employees in the hierarchy. The head of the hierarchy Le the CEO is not included in this process of bonus distribution.
Write an algorithm to find the IDs of the employees who won't receive a bonus.
Input
The first line of the input consists of two space-separated integers - numEmployess (N) and numProjects(P), representing the total number of employees in this hierarchy and the total number of
projects worked upon respectively The second line consists of N space-separated integers representing the managers IDs where the position of the manager in the list depicts the employee ID working under that manager. The CEO will have the ID 0 The third line consists of P space- separated integers representing the IDs of the employees who worked on the project.
Output
Print space-separated integers representing the IDs of the employees who did not receive the bonus. The IDs should be sorted in ascending order
Examples
Input
8 4
0 1 1 2 2 3 4 4
8 4 6 5
Output:
4678
Explanation:
The hierarchy is as follows
The employee with ID 8 has worked on the project therefore the bonus will be given to the manager
with employee ID 1 The employee with ID 4 has worked on the project therefore the bonus will be given to the manager
with employee ID 2 The employee with ID 6 has worked on the project therefore the bonus will be given to the manager
with employee ID 3 The employee with ID 5 has worked on the project but the manager with ID 2 and the manager's manager with ID 1 have both received the bonus carlior
hence the bonus will be given to 5 So, the employees with IDs 4, 6, 7 and 8 can't receive the bonus
Question 2
The Health Ministry of Torris county has decided to set up medical centers for the benefit of its citizens. The Ministry selects N different cities in the county in which to establish a medical center. Each city is identified by a city ID ranging from 0 to N-1. Multiple medicle centers are needed in different cities according to requirement. Each day a medical center will be set up in one of the selected cities. On any two consecutive days the chosen city must be different. Write an algorithm to determine the maximum number of medicle centers that will be set up in the county covering the maximum number of locations.
Input
The first line of the input consists of an integer - numCity representing the number of cities selected for a medical center (N).
The next line consists of N space- separated integers - loc1, loc2, . .logN representing the number of locations to set up a medical centers in a city.
Output
Print an integer representing the maximum number of medicle centers that will be set up in the county covering the maximum number of locations.
Constraints
1 <= numCity <= 104
1 <= log <= 109
Σlog <= 105
1 <= I <= N
Example
Input:
3
11 4 5
Output:
19
Explanation:
The first, second and third cities are selected with locations 11, 4 and 5,
respectively. The locations of different cities are selected on successive days in a
sequence:
1st, 2nd, 1st, 3rd, 1st, 2nd, 1st,
3rd,1 st, 2nd, 1st, 3rd, 1st, 2nd, 1st,
3rd, 1st. 3rd, 1st
So, the maximum number of medical
centers that may be set up in the
county is 19.
Entering edit mode
Answer for Question no. 3
include<bits/stdc++.h>
using namespace std;
int main(){ int n; cin>>n; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; }
map<int,int> pos;
map<int,int> neg;
for(int i=0;i<n;i++){
if(arr[i]>0 && pos[arr[i]]==1){
neg[arr[i]]++;
}
else if(arr[i]>0 && pos[arr[i]]<1){
pos[arr[i]]++;
}
else if(arr[i]<0 && neg[arr[i]]<1){
neg[arr[i]]++;
}
else if(arr[i]<0 && neg[arr[i]==1]){
pos[arr[i]]++;
}
}
int posSum = 0;
for(auto i:pos){
posSum += i.first;
}
int negSum = 0;
for(auto i:neg){
negSum += i.first;
}
cout<
Entering edit mode
solution of question 1
#include<bits/stdc++.h>
#include <stdio.h>
using namespace std;
void travel(vector<int> &list, vector<int> &vis){
int n = list.size();
int flag =0;
for( int i =0;i<n;i++){
if(!vis[list[i]]) continue;
else {
vis[list[i-1]]=1;
flag =1;
break;
}
}
if(!flag){
vis[list[n-1]]=1;
}
}
vector<int> bonus(int e,int p,vector<int> &id,vector<int> &project){
vector<int> ans;
unordered_map<int, vector<int> > mpp;
vector<int> vis (e+1, 0);
for(auto it: project){
vector<int> list={};
int node = it;
list.push_back(node);
while(true){
node = id[node-1];
if(node ==0) break;
list.push_back(node);
}
mpp[it]=list;
}
for(auto it: project){
vector<int> list = mpp[it];
travel(list, vis);
}
for( int i =1;i<=e;i++){
if(!vis[i]) ans.push_back(i);
}
sort(ans.begin(), ans.end());
return ans;
}
int main(){
vector<int> res;
int n;
vector<int> id ={0,1,1,2,2,3,4,4};
vector<int> project ={8,4,6,5};
res= bonus(8,4,id, project);
for( int i =0;i<res.size();i++){
cout<<res[i]<<" ";
}
return 0;
}
