- Practice
- Algorithms
- Greedy
- Team Formation
- Discussions
Team Formation
Team Formation
danielmayorga + 0 comments This problem is weird.
Let me try to explain it:
you need to find sets with the property below
1. Every element is unique: No repeats i.e. A set cannot have the element "4" twice 2. Every element is the previous element +1, an increment i.e. {1,2,3} is valid. 1+1=2, 2+1=3 i.e. {1,4,5} is not valid because 4!=1+1
What the Problem is asking:
Output the size of the maximized "minimum set." Sounds, kind of weird, but I'll try to clarify with an example. EX:{1,2,3,5,6,7} Some Potential outputs (I won't list them all): -{1},{2},{3},{5},{6},{7} The size of the minimum list is 1 -{1,2},{3},{5,6,7} The size of the minimum list is 1 -{1,2,3},{5,6,7} The size of the minimum list is 3 Your answer is 3 because it's the maximized size of the "minimum set"
Things you might want to know:
-The problem states "The absolute value of skill levels will not exceed 10^9", that just means that each element will be an int.
-For some weird reason 0 is a value. Just add a line
if(N==0) cout<<"0";//and continue the loop. else solveProblem();
Hints: 1. Problem you may have:
~Repetative numbers and knowing when to stop a list~ {0,1,2,3,4,4,5,6,7}//notice 4 is in the list twice Answer 4:{0,1,2,3,4} and {4,5,6,7} Wrong answer: {0,1,2,3,4,5,6,7},{4}, which is 1 ~Repetative numbers and recognizing how many more are left~ {1,1,1,2,2,2,3,3,3,4,4,4,5,5,5}//Notice repetition Answer 5: {1,2,3,4,5}, {1,2,3,4,5}, and {1,2,3,4,5} Wrong answer:{1},{1},{1},{2},{2},{2},...,{5},{5},{5} ~Unsorted input~ {4,2,5,7,6,1,0} Answer 3:{0,1,2} and {4,5,6,7}
Data Structure are your friends:
-Think Hashmaps, Sets, Priority list,etc. This problem can be approach in a few different ways. -Keep track of how many times an element shows up
alexsapps + 0 comments This problem should not include the case where there are 0 contestants (n=0). Half of the test cases actually test this, and the test case expects that the answer be 0 even though this is wrong and the description doesn't say how to handle this case. I say it is wrong because there is no numerical way to answer "how big is the smallest team when there are 0 teams?" If there are no teams, obviously there is no size to answer with. If questions on Hackerrank are going to be judged in this nitpicky way that doesn't help us learn algorithms, there should at least be some real life lesson in it. So add a line "if n = 0, print 0" then the lesson can be to follow directions :)
dmanjrod + 0 comments Roy is really bad at building teams.
h88191015 + 0 comments For those struggling, consider a skill value x, and teams with a max value of skills x-1
- if there's no x-1, x must start a new team
- if there's more than 1 x-1, then should append x to the smallest team
Solution
- sort
- prepare a map[s][l] (or HashMap, whatever within the space limit), numbers of previous teams of which the max is s and length is l
- for every skill[i], if (map[skill[i]-1]) exists and the smallest length is len*, do map[skill[i]-1][len]--, map[skill[i]][len+1]++
- if not, do map[skill[i]][1]++
- the result is min(for every map[skill][len]>0 ---> len)
Optimization
- as you sorted skill list, for every skill, if map[skill-1] does not exist, then every map[0~skill-2] will never be any longer, thus you actually need a map, just maintain 2 list of length's
- use heap(or PriorityQueue) get the smallest length instead of list or array
- In java, please use BufferedReader, NOT SCANNER, which would help you save a lot of run time
jeremytoddfuller + 0 comments The constraints on the x[i] need to be updated. It says -10^5<=x[i]<=10^5, but many test cases have them outside that range.
Sort 71 Discussions, By:
Please Login in order to post a comment