We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Greedy
  4. Team Formation
  5. Discussions

Team Formation

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 71 Discussions, By:

votes

Please Login in order to post a comment

  • danielmayorga 5 years ago+ 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
    
    37|
    Permalink
  • alexsapps 6 years ago+ 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 :)

    23|
    Permalink
  • dmanjrod 4 years ago+ 0 comments

    Roy is really bad at building teams.

    8|
    Permalink
  • h88191015 2 years ago+ 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
    3|
    Permalink
  • jeremytoddfuller 3 years ago+ 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.

    3|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature