Optimize the algorithm for choosing a football team

Question

I need to build a football team. Every player has his performance described by an integer. The greater the number, the more effective the player is. Every team should be solid. If one of the players plays much better than all others, then other team members will dislike him, and the team will not be solid. Thus, the performance of every team member should not exceed the sum of performances of any two other team members. Your task is to assemble a solid team with maximum total performance (which is the sum of performances of all players).

The first line of the input contains the number n (1 <= n <= 100000). The second line contains the performances of every of the n players. Performances are positive integers not greater than 2^31.

The output should contain two lines. The first line should contain the maximum total performance of the team you can build from given players. The second line should contain the numbers of the players (in ascending order) that you need to put to your team in order to reach this performance. The players have numbers starting from 1 to n in the same order that their performances appear in the input. If there are several ways to build the team, output any of them.

For example:

Input:

5

3 2 5 4 1

Output:

14

1 2 3 4

I have invented such algorithm:

1. Read all numbers from input.

2. Sort them in ascending by recursive qicksort.

3. Iterate through sorted vector and accumulate two sums, choosing the maximum of them and keeping indexes of the begining and the end of two optimal sequences.

Here is my code for this algorithm:

#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>     
#include <time.h>    
#include <algorithm>

using std::swap;
using std::vector;
using std::cout;
using std::cin;

typedef unsigned long ulong;
typedef unsigned long long  ullong;

template <typename T>
int random_partition(vector<T> &input, int start, int end)
{
    srand(time(NULL));
    int pivotIdx = start + rand() % (end - start + 1);
    T pivot = input[pivotIdx];
    swap(input[pivotIdx], input[end]);
    pivotIdx = end;
    int ind = start - 1;

    for (int j = start; j <= end - 1; ++j)
    {
        if (input[j] <= pivot)
        {
            ind = ind + 1;
            swap(input[ind], input[j]);
        }
    }

    swap(input[ind + 1], input[pivotIdx]);
    return ind + 1;
}

template <typename T>
void random_quick_sort(vector<T>& input, int start, int end)
{
    if (start < end) 
    {
        int mid = random_partition(input, start, end);
        random_quick_sort(input, start, mid-1);
        random_quick_sort(input, mid + 1, end);
    }
}

struct Player
{
    int number;
    ulong efficiency;
    Player(int numb, ulong ef) : number(numb), efficiency(ef) {}
};

bool operator <= (const Player& plRight, const Player& plLeft)
{
    return (plRight.efficiency <= plLeft.efficiency);
}

class Team
{
   vector<Player> players;
    vector<int> bestPlayersNumbers;
    ullong sumOfBestPlayers;    

public:
    Team() {}

    void addPlayer(Player player)
    {
        players.push_back(player);
    }

    void sortPlayersByEfficiency()
    {
        random_quick_sort(players, 0, players.size() - 1);
    }

    void choosePlayers()
    {
        sortPlayersByEfficiency();

        int subListBegin = 0;
        int prevSubListBegin = 0;
        int subListEnd = 1;
        int prevSubListEnd = 0;
        ullong currentMaxSum = 0;

        if (players.size() < 2)
        {
            currentMaxSum = players[0].efficiency;
        }
        else
        {
            currentMaxSum = players[0].efficiency + players[1].efficiency;
            prevSubListEnd = 1;
        }
        ullong prevMaxSum = currentMaxSum;

        for (int iter = 2; iter < players.size(); ++iter)
        {
            while (players[iter].efficiency - players[subListBegin].efficiency > 
                    players[subListBegin + 1].efficiency )
            {
                currentMaxSum = currentMaxSum - players[subListBegin].efficiency;
                ++subListBegin;
            }
            currentMaxSum += players[iter].efficiency;
            subListEnd = iter;

            if ( prevMaxSum <= currentMaxSum) 
            {
                prevMaxSum = currentMaxSum;
                prevSubListEnd = subListEnd;
                prevSubListBegin = subListBegin;
            }
        }

       sumOfBestPlayers = prevMaxSum;

        for (int i = prevSubListBegin; i <= prevSubListEnd; ++i)
        {
            bestPlayersNumbers.push_back(players[i].number);
        }
        random_quick_sort(bestPlayersNumbers, 0, bestPlayersNumbers.size() - 1);

    }

    void printSumAndPlayers()
    {
        printf("%ull\n", sumOfBestPlayers);
        for (int i = 0; i < bestPlayersNumbers.size(); ++i)
        {
            printf("%i ", bestPlayersNumbers[i] + 1);
        }
    }    
};

int main()
{
    clock_t begin, end;
    double time_spent;

    FILE *file;

    file = fopen("test.txt", "r");

    int playersNumber;
    Team team;
    fscanf(file, "%i", &playersNumber);

    for (int i = 0; i < playersNumber; ++i)
    {
        ulong playerEffeciency = 0;
        fscanf(file, "%ul", &playerEffeciency);

        team.addPlayer(Player(i, playerEffeciency));
    }

    begin = clock();
    team.choosePlayers();

    team.printSumAndPlayers();

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    std::cout << time_spent << std::endl;

    return 0;
}

This algorithm works correctly, but it is rather slow. I need it to work faster, but I can't work out something more effective at the moment. Can you give me some ideas how I can optimize my algorithm to make it work faster?

I will be grateful for your help.

Answer 1

Just some design things:

• You're using C libraries:

  #include <stdlib.h> // should be <cstdlib>
  #include <time.h>   // should be <ctime>
  

• I'd recommend defining Team's public members outside the class declaration.

  addPlayer() should pass by const&.

  printSumAndPlayers() should be const.

• Prefer to use std::size_type for looping through an std::vector. This should at least prevent type warnings and allow the loop to work with any vector size.

  std::vector<T>::size_type j;
  
  for (j = start; j <= end - 1; ++j) {}
  

• ind = ind + 1 can just be ind++.

• Prefer the C++ way of casting:

  time_spent = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  

• Prefer to call std::srand() in main() only once. Each time random_partition() is called, the call to std::srand() will reset the seed to 0, thereby giving you the "same" random value.

  You should also use nullptr instead if you're using C++11.