Team Selection
Problem credits : Code chef
Difficulty : Hard
Problem Statement :
One of the cherished customs of my childhood was choosing up sides for a cricket game. We did it this way: The two bullies of our gully would appoint themselves captains of the opposing teams, and then they would take turns picking other players. On each round, a captain would choose the most capable (or, towards the end, the least inept) player from the pool of remaining candidates, until everyone present had been assigned to one side or the other. The aim of this ritual was to produce two evenly matched teams and, along the way, to remind each of us of our precise ranking in the neighbourhood pecking order.
We all believed this was the fairest process, but does it ensure the fairest selection of players with evenly matched teams? We believed so, but then there were times when, as the game progressed we realized that the other team was stronger than ours and may be an exchange of a couple of players between the teams would have made them balanced. That scope of improvement seemed to be there...
Here, we need to find a way to create two evenly balanced teams for any game(or as evenly balanced as possible considering the strength of each player). A set of players must be divided into two teams. Each player must be on one team or the other; the number of player on the two teams must not differ by more than 1; each player will have a skill-point associated with him. The total skill-points of the players on each team should be as nearly equal as possible.(The absolute difference of the sum of skill-points of players in each team should be the least).
LOGIC :
To solve this problem we can do one thing, take the elements(skill points) in an array and sort it.
You can use any sorting technique, I am using bubble sort, after sorting is done we assign skill points to each team based on the comparison of their mean of so far sum of skill points.
If the number of elements are odd we assign one value in advance to one of the team so that the remaining elements are even.
Code :
Rest of the code is self-explainatory
Full C++ implementation/Code :
int main() { int n; cout<<"Enter the number of players "; cin>>n; int SkillPoints[n]; int i;
for(i=0; i<n; i++) { cout<<"Enter the skill points for player "<<i<<" "; cin>>SkillPoints[i]; }
int team1 = 0; int team2 = 0; int team1L[(n/2)+1]; int team2L[(n/2)+1];
int temp;
int p,q; for(p=0; p<n-1; p++) { for(q=0; q<n-p-1; q++) { if(SkillPoints[q]<SkillPoints[q+1]) { temp = SkillPoints[q]; SkillPoints[q] = SkillPoints[q+1]; SkillPoints[q+1] = temp; }
} }
int point=0; int a=0,b=0; float mean1=0, mean2=0; if(n%2 !=0) { team1L[a] = SkillPoints[point]; team1 = team1 + team1L[a]; b++; point++; } if(n == 3) { while(point<n) { if(mean1 >= mean2) { team2L[a] = SkillPoints[point]; team2 = team2 + team2L[a]; a++; point++; } else { team1L[a] = SkillPoints[point]; team1 = team1 + team1L[a]; b++; point++; } } } else {
while(point<n) { if((mean1 >= mean2) && (SkillPoints[point]>=SkillPoints[point+1]) ) { team2L[a] = SkillPoints[point]; team2 = team2 + team2L[a]; a++; mean2 = team2/a; team1L[b] = SkillPoints[point+1]; team1 = team1 + team1L[b]; b++; mean1 = team1/b; point = point +2; }
else if((mean1 > mean2) && (SkillPoints[point]<SkillPoints[point+1])) { team1L[b] = SkillPoints[point]; team1 = team1 + team1L[b]; b++; mean1 = team1/b; team2L[a] = SkillPoints[point+1]; team2 = team2 + team2L[a]; a++; mean2 = team2/a; point = point +2;
}
else if((mean1 < mean2) && (SkillPoints[point]>SkillPoints[point+1])) { team1L[b] = SkillPoints[point]; team1 = team1 + team1L[b]; b++; mean1 = team1/b; team2L[a] = SkillPoints[point+1]; team2 = team2 + team2L[a]; a++; mean2 = team2/a; point = point +2; }
else if((mean1 <= mean2) && (SkillPoints[point]<=SkillPoints[point+1])) { team2L[a] = SkillPoints[point]; team2 = team2 + team2L[a]; a++; mean2 = team2/a; team1L[b] = SkillPoints[point+1]; team1 = team1 + team1L[b]; b++; mean1 = team1/b; point = point +2; }
} }
int s,d; cout<<"Team 1 : "; cout<<endl; for(s=0; s<b; s++) { cout<<team1L[s]<<" "; }
cout<<endl; cout<<"Team 2 : "; cout<<endl; for(d=0; d<a; d++) { cout<<team2L[d]<<" "; } cout<<endl;
cout<<"The total skillpoints for team 1 are "<<team1<<endl; cout<<"The total skillpoints for team 2 are "<<team2<<endl;
}
Sample INPUT/OUTPUT :
n = 3;
n = 10;
