Analysis: Balanced Teams by Nathan Pinsker and Brian Dean


This problem has small enough bounds (the number of possible cow teams is only 12! / (4!)^3) that we can simply generate all possible quartets of 3-cow teams, and see which one yields the best balance. One easy way to do this is with recursion: we will enumerate all possible teams by assigning each cow to a team, one at a time.

How exactly does this work? We will first assign cow number 1 to a team. Of course, cow number 1 can go onto any of the 4 teams; let's say we put her on team 1, so team 1 only has two available spots left. We then recursively generate all possible teams that cows 2-12 can go onto, given that cow 1 is on team 1 (meaning team 1 has two spots left). Once we're done with this recursive call, we try assigning cow number 1 to team 2 instead, and repeat.

Travis Hance's code is below. The method "recurse(X)" corresponds to assigning cow X+1 to a team. The code inside the "if (player == 12)" block is used to calculate how balanced the four teams are, once we're done assigning all 12 cows to teams.

#include <cstdio>
#include <algorithm>
using namespace std;

int player_skill[12];

int player_team[12];
int team_count[4];

int answer = -1;

void recurse(int player) {
	if (player == 12) {
		int team_skill[4] = {0,0,0,0};
		for (int i = 0; i < 12; i++) {
			team_skill[player_team[i]] += player_skill[i];
		}
		int S = max(max(team_skill[0], team_skill[1]),
		            max(team_skill[2], team_skill[3]));
		int s = min(min(team_skill[0], team_skill[1]),
		            min(team_skill[2], team_skill[3]));

		if (answer == -1 || S - s < answer) {
			answer = S - s;
		}
		return;
	}

	for (int team = 0; team < 4; team++) {
		if (team_count[team] < 3) {
			player_team[player] = team;
			team_count[team]++;

			recurse(player+1);

			team_count[team]--;
		}
	}
}

int main() {
	freopen("bteams.in", "r", stdin);
	freopen("bteams.out", "w", stdout);

	for (int i = 0; i < 12; i++) {
		scanf("%d", &player_skill[i]);
	}

	recurse(0);

	printf("%d\n", answer);
}

Hugh Zhang contributed a nice solution which illustrates how the C++ STL "next permutation" function automatically deals with special case where there are equal elements in the array we are permuting -- thereby reducing the running time for an exhaustive search from 12! down to something much more manageable that runs easily in time:

#include <cstdio>
#include <algorithm>
#define LARGE (1e7)
 
using namespace std;
 
int arr[12];
int order[] = {0,0,0,1,1,1,2,2,2,3,3,3};
int ans = LARGE;
int score[4];
 
int main(){
    freopen("bteams.in","r",stdin);
    freopen("bteams.out","w",stdout);
    for(int x = 0;x<12;x++){
        scanf("%d",&arr[x]);
    }
    sort(arr,arr+12);
   
    do{
        for(int x = 0;x<4;x++) score[x] = 0;
        for(int x = 0;x<12;x++) score[order[x]]+=arr[x];
        int min = LARGE;
        int max = 0;
        for(int x = 0;x<4;x++){
            if(score[x]<min) min = score[x];
            if(score[x]>max) max = score[x];
        }
        if(max-min<ans) ans = max-min;
 
 
    } while(next_permutation(order,order+12));
    printf("%d\n",ans);
 
    return 0;
}

Finally, another nice way to enumerate all possibile solutions is to simply step an integer counter X from 0 up to 2^24, and to use the bits in X to determine which cows belong to which team. We can think of the 24 bits of X as 12 blocks of 2 bits, corresponding to 12 cows that each have a team ID in the range 0..3. So by stepping through all values of X, we are also stepping through all possible team assignments for the cows (many of which will be infeasible and pruned away, since they involve more than 3 cows on a team). Since 2^24 is a bit large, we save a factor of 4 by looping only up to 2^22, by assuming without loss of generality that the first cow is always on team 0:

#include <iostream>
using namespace std;

int main(void)
{
  freopen ("bteams.in", "r", stdin);
  freopen ("bteams.out", "w", stdout);

  int height[12], count[4], total[4], m, M, best=999999999;

  for (int i=0; i<12; i++) cin >> height[i];

  for (int x=0; x<(1<<22); x++) {

    count[0] = 1; count[1] = count[2] = count[3] = 0;
    total[0] = height[11]; total[1] = total[2] = total[3] = 0;

    for (int i=0; i<11; i++) {
      int team = (x>>(2*i))&3;
      count[team]++;
      total[team] += height[i];
    }

    if (count[0]!=3 || count[1]!=3 || count[2]!=3) continue;

    m = 999999999; M = 0;
    for (int t=0; t<4; t++) { 
      if (total[t] < m) m = total[t];
      if (total[t] > M) M = total[t];
    }
    if (M-m < best) best = M-m;

  }
  cout << best << "\n";
}