Doubt in Algo

general
1

qstn:-

where my algo is going wrong please help

algo:- greedy approach

1)At first, sort all the contestants in non decreasing order and iterate over them. When a contestant with skill level x is found, and its previous element is x-1 include in the list else form new list.

2)print the size of list whose size is minimum

my code

https://www.hackerrank.com/challenges/team-formation/submissions/code/10832617

2

I can’t see your code. Paste it here or give the ideone link. However, the problem can be misunderstood, although your approach is correct. This test case, can however explain the question in a very clean manner.

8 101 102 103 104 105 106 103 104
sort: 101 102 103 103 104 104 105 106


now start from 101, create and add it in list1
list1 = [101]
next: 102 is 101 + 1 and we have valid list1 so add it
list1 = [101, 102]
next: 103
list1 = [101, 102, 103]
next: 103 now list1 is not valid as it already have 103 so create new list list2
list2 = [103]
next: 104, list1 and list2 both are good but list2 has least elements so
list2 = [103, 104]
next: 104, list2 not valid and ist1 valid
list1 = [101, 102, 103, 104]
next: 105, both list1 and list2 are valid bit list2 has least elements so
list2 = [103, 104, 105]
next: 106
list2 = [103, 104, 105, 106]
so at the end you have
list1 = [101, 102, 103, 104]
list2 = [103, 104, 105, 106]
so answer is 4

So, if you’ll now try using brute force, then you can see my submission here. Please note that we only need to have the last element and the number of element in a particular list. Thus we’ll maintain those two values as a pair in a vector.

vec.push_back(make_pair(skill[0],1));  // push the lowest skill with list count as 1
ll m;
for(i=1;i<n;i++)
{
	temp= skill[i]-1;
	m=n;
	ll pos=-1;
	for(j=0;j<(int)vec.size();j++)
	{
           if(vec[j].first==temp && vec[j].second<m) 
	     {  // search the list with largest skill value as temp which has minimum no. of elements
			pos=j;
			m= vec[j].second;
	     }
	}
	
	if(pos==-1)   // if no suhc skill exists
	{
		vec.push_back(make_pair(skill[i],1));
	}
	else{
	vec[pos].first= skill[i];
	vec[pos].second+=1;
	// if the skill exits, increase that list and update the values.
	}
}
m=n;
for(i=0;i<(int)vec.size();i++)
{
	if(vec[i].second<m)  // find minimum list size
	 m = vec[i].second;
}

The complexity of above code is O(n^2) which can be optimized with the help of map or priority queue.

2 Likes
3

my code @damn_me

4

I don’t think your implementation is correct, you are just comparing the current count for a particular value not all possible counts.

5

See this test case, I have explained it above also.

1
8 101 102 103 104 105 106 103 104

Your code gives 2 as the answer for the same.

6

Thanks dude