"Team formation" challenge

Question

I'm trying to solve this problem but am getting a timeout. Can someone help me to improve?

using namespace std;

typedef multimap<int,int> MMap;

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t;
    cin>>t;
    for(int tcase=0; tcase<t; tcase++) {
        // contains input for each test case
        vector<int> in_vec;
        // array of different teams
        vector<vector<int> > vec_teams;
        int size;
        cin>> size;
        int val;
        int min = size;
        for(int i=0;i<size;++i) {
            cin>>val;
            in_vec.push_back(val);
        }
        if(size==0) {
            cout<<"0"<<endl;
            continue;
        }
        sort(in_vec.begin(),in_vec.end());
        vec_teams.push_back(vector<int>());
        // maintains ordered, key value pair of size and its position(index) in vec_teams
        MMap mmap;
        mmap.clear();
        vec_teams[0].push_back(in_vec[0]);
        mmap.insert(pair<int,int>(vec_teams[0].size(),0));

        for(int id=1; id<in_vec.size(); ++id) {
            bool added = false;
            MMap::iterator it = mmap.begin();
            //inserts the skill level to correct team
            // if not possible to add to any
            // then new team is created after the loop
            for(int i=0; i<vec_teams.size(); ++i,++it) {
                int mpos = (*it).second;
                if (vec_teams[mpos][vec_teams[mpos].size() -1 ] + 1 == in_vec[id]) {
                    pair <MMap::iterator, MMap::iterator> pa= mmap.equal_range(vec_teams[mpos].size());
                    MMap::iterator mmit;
                    for (mmit=pa.first; (*mmit).second!=mpos; ++mmit);
                    mmap.erase(mmit);
                    vec_teams[mpos].push_back(in_vec[id]);
                    mmap.insert(pair<int,int>(vec_teams[mpos].size(),mpos));
                    added = true;
                    break;
                }
            }
            // Since not able to add to existing teams
            // new team is created and added to it
            if(!added) {
                vec_teams.push_back(vector<int>());
                vec_teams[vec_teams.size() -1].push_back(in_vec[id]);
                mmap.insert(pair<int,int>(1,vec_teams.size() -1));
            }
        }
        int ans = (*(mmap.begin())).second;
        cout<<vec_teams[ans].size()<<endl;
    }
    return 0;
}

Answer 1

Separation of concerns

At the moment, all your code is in a convoluted main function handling :

• getting the input from stdin

• solving the problem

• printing the answer in stdout.

It would be better to separate the concerns. On top of making things clearer and easier to maintain, it would also make things easier to test.

Writing tests

Because you'll probably want to improve the algorithm, it can be a safe option to write tests to ensure you are aware if you break your code. Great thing is that you have test cases provided with the problem, you just need to write them as code, run them and be happy.

At this stage, my code looks like :

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <assert.h>

using namespace std;

typedef multimap<int,int> MMap;

vector<int> get_input_from_std()
{
    // contains input for each test case
    vector<int> in_vec;
    int size;
    cin>> size;
    int val;
    for(int i=0;i<size;++i) {
        cin>>val;
        in_vec.push_back(val);
    }
    return in_vec;
}

int get_min_team_size(vector<int> in_vec)
{
    if(in_vec.size()==0) {
        return 0;
    }
    sort(in_vec.begin(),in_vec.end());
    vector<vector<int> > vec_teams;
    vec_teams.push_back(vector<int>());
    // maintains ordered, key value pair of size and its position(index) in vec_teams
    MMap mmap;
    mmap.clear();
    vec_teams[0].push_back(in_vec[0]);
    mmap.insert(pair<int,int>(vec_teams[0].size(),0));

    for(int id=1; id<in_vec.size(); ++id) {
        bool added = false;
        MMap::iterator it = mmap.begin();
        //inserts the skill level to correct team
        // if not possible to add to any
        // then new team is created after the loop
        for(int i=0; i<vec_teams.size(); ++i,++it) {
            int mpos = (*it).second;
            if (vec_teams[mpos][vec_teams[mpos].size() -1 ] + 1 == in_vec[id]) {
                pair <MMap::iterator, MMap::iterator> pa= mmap.equal_range(vec_teams[mpos].size());
                MMap::iterator mmit;
                for (mmit=pa.first; (*mmit).second!=mpos; ++mmit);
                mmap.erase(mmit);
                vec_teams[mpos].push_back(in_vec[id]);
                mmap.insert(pair<int,int>(vec_teams[mpos].size(),mpos));
                added = true;
                break;
            }
        }
        // Since not able to add to existing teams
        // new team is created and added to it
        if(!added) {
            vec_teams.push_back(vector<int>());
            vec_teams[vec_teams.size() -1].push_back(in_vec[id]);
            mmap.insert(pair<int,int>(1,vec_teams.size() -1));
        }
    }
    int ans = (*(mmap.begin())).second;
    return vec_teams[ans].size();
}

/*
Using http://stackoverflow.com/questions/8906545/how-to-initialize-a-vector-in-c
*/

void unit_tests()
{
    {
        int vv[]{4, 5, 2, 3, -4, -3, -5};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 3);
    }
    {
        int vv[]{-4};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 1);
    }
    {
        int vv[]{3, 2, 3, 1};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 1);
    }
    {
        int vv[]{1, -2, -3, -4, 2, 0, -1};
        vector<int> v(begin(vv), end(vv));
        assert(get_min_team_size(v) == 7);
    }
}

void stdin_tests()
{
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t;
    cin>>t;
    for(int tcase=0; tcase<t; tcase++) {
        vector<int> in_vec = get_input_from_std();
        cout<< get_min_team_size(in_vec) <<endl;
    }
}

int main() {
    unit_tests();
    return 0;
}

Algorithms and performances

In the case of programming problems like the one you are trying to solve, the real issue is usually the complexity of your algorithm, how it behaves on large inputs.

In order to see how your code behaves on larges inputs, you have two main strategies (and you should try apply both):

• pen, paper and mathematics

• tests : great thing is that now, it is quite easy to define tests of any size you like. You just need to time your program.

For instance, you could add the following tests to your test suite :

int nb_elts = 100000;
{ // Single big team
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(i);
    assert(get_min_team_size(v) == nb_elts);
}
{ // Double big team
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
    {
        v.push_back(i);
        v.push_back(i);
    }
    assert(get_min_team_size(v) == nb_elts);
}
{ // Multiple different one-player teams
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(2 * i);
    assert(get_min_team_size(v) == 1);
}
{ // Multiple identical one-player teams
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
        v.push_back(0);
    assert(get_min_team_size(v) == 1);
}
{ // Overlapping three-player teams 
    vector<int> v;
    for (int i = 0; i < nb_elts; i++)
    {
        v.push_back(2*i);
        v.push_back(2*i+1);
        v.push_back(2*i+2);
    }
    cout << get_min_team_size(v) << endl;
    assert(get_min_team_size(v) == 3);
}

A quick look at your code tells me is probably somewhere around O(n^2) which grows "very" fast.

I have designed an algorithm which seems to be faster on the various inputs I have tried but I might have forgotten edge-cases.

In any case, the principle is the following :

• we sort the individuals by levels just like you did.

• we count of many individuals we have for each levels

• when considering a new group of individual :

  • if we have more people than the number of teams, we create as many new teams keeping track of the level of the smallest level

  • if we have more teams than the number of people, we end the formation of as many teams, starting with the longest ones (the one with the smallest starting levels).

I hope :

• I managed to make this explanation clear

• this actually works.

And here is the corresponding code :

int get_min_team_size(vector<int> levels)
{
    if (levels.size()==0)
        return 0;
    sort(levels.begin(),levels.end());

    int sol = levels.size(); // Solution will not be bigger that the size of the input
    queue<int> lowest_lvl; // Storing the (sorted) levels of the less skilled member of the teams being formed.
    int level = levels[0] - 2; // Level of the individuals being processed (the minus 2 is a trick not to have to handle the beginning in a special way).
    int nb_in_level = 0; // Number of individual being processed
    levels.push_back(levels.back() + 2); // trick not to have to handle the end in a special way
    for(int id=0; id<levels.size(); ++id)
    {
        int ind_lvl = levels[id];
        if (ind_lvl == level)
        {
            // Same level : just counting the new individual
            nb_in_level++;
        }
        else 
        {
            bool lvl_gap = ind_lvl != level + 1;

            // Different level : processing what needs to be done for previous level :
            // 1) If we haven't started enough teams, let's start them from that level
            while (lowest_lvl.size() < nb_in_level)
                lowest_lvl.push(level);

            // 2) If we have too many teams started, let's end the one starting with the longest ones
            // (they correspond to the first teams as we have them sorted by the level of the smallest individual)
            // and check their length. If we have a gap of level, we want to end them all.
            if (lvl_gap)
                nb_in_level = 0;

            while (lowest_lvl.size() > nb_in_level)
            {
                // Theoritically, lowest_lvl is sorted so only the last element is relevant but we have to unpop them anyway
                sol = min(sol, 1 + level - lowest_lvl.front());
                lowest_lvl.pop();
            }

            // 3) If there is a gap of level, we add the new beginning of team. 
            if (lvl_gap)
            {
                lowest_lvl.push(ind_lvl);
            }
            nb_in_level = 1;
            level = ind_lvl;
        }
    }
    assert(nb_in_level == 1);
    assert(lowest_lvl.size() == 1);
    cout << sol << endl;
    return sol;
}