CareerCup

This problem is posted on the website of directi

This seems like a variant of sub set problem.
I was just thinking about doing it in a brute force way. It will atleast require C(n, n/2) (Assuming n is the total number of players) calculations with each set having n/2 element.
And then checking every combination set for the sum.

Get the sum of the skillset . Divide it by 2 . Let it be n .Then solve this as a Knapsack problem .

NONE saw the requirement ***the number of player on the two teams must not differ by more than 1***
I wonder - that is the problem. None looks into requirement.
Now - folks what we used to do here?

Captain 1: I pick the best one - highest.
Captain 2: I pick the other best one - may be I loose a bit highest-1.

If we can pick the diff as small as possible at every step - then we are done.
Indeed it is a modified knapsack issue.
Though - it does not solve the purpose - none practically creates a cricket team like that.

Here is something - kick me in case case it does not work...in a bad mood today :(
And for information almost all the results you have here are dead WRONG.
Example
Sample Input 3:

10
1
1
1
1
1
1
1
1
1
9

Output 3:
5 13 *WRONG*
10 9 1 1 1 1 1 1 1 1 1
----------------------------------------
10( 0) 9( 1)
1( 2) 1( 3)
1( 4) 1( 5)
1( 6) 1( 7)
1( 8) 1( 9)
1(10)
Sum------------------
14 14
Diff is 0 at 10

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int arr[11] = {10,2,3,10,5,8,9,7,3,5,2 };

int compare(const void* a, const void *b)
{ 
	int* _a = (int*)a;
	int* _b = (int*)b;

	if ( *_a < *_b ) return 1;
	if ( *_a == *_b ) return 0;
	if ( *_a > *_b ) return -1;
	
}
void print_arr(int*a, int len )
{
	int i ;
	for (i= 0; i < len; i++)
	{
		printf("%4d",a[i]) ;
	}
	printf("\n----------------------------------------\n");
}

void MakeTeam(int* a, int len)
{
	int sum1=0, sum2=0 ;
	int i=0, diff=0 ;
	int  testDiff1, testDiff2;

	print_arr(a, len);
	//These are chosen...
	
	for ( i = 0 ; i < len - 1 ; i+=2)
	{
		testDiff1 =  a[i]  - a[i+1] + diff; //a[i] to the 1st team a[i+1] to the seccond
		testDiff2 =  a[i+1] - a[i] + diff; //a[i+1] to the 1st team a[i] to the seccond
		if ( (int)fabs(testDiff1) > (int)fabs(testDiff2) )
		{
			diff = testDiff2;
			sum1+=a[i+1];
			sum2+=a[i];
			printf("%4d(%2d)  %4d(%2d)\n",a[i+1],i+1, a[i],i); 
		}	
		else
		{
			diff = testDiff1 ;
			sum1+=a[i];
			sum2+=a[i+1];
			printf("%4d(%2d)  %4d(%2d)\n",a[i],i,a[i+1],i+1) ; 
		}
		
	}
	if ( i < len )
	{
		//One more to go...
		
		if (diff > 0 && (diff - a[i] <= diff )  ) 
		{
			sum2+=a[i];
			diff -=a[i] ;
			printf("          %4d(%2d)\n",a[i],i) ; 
		}	
		else
		{
			sum1+=a[i];
			diff+= a[i] ;
			printf("%4d(%2d)\n",a[i],i); 
		}

	}
	printf("Sum------------------\n");
	printf("%4d       %4d\n",sum1, sum2); 
	printf ( "Diff is %d at %d\n",diff,i);


}
int main(int argc, char** argv)
{
	int i = 0;
	int* a = (int*)malloc( (argc-1)*sizeof(int)) ;
	while ( i < argc -1 )
	{
		a[i] = atoi(argv[1+i] ) ;
		i++;
	}
	if ( argc == 1 )
	{
		a = arr ;
		argc = 12 ;
	}
	qsort(a, argc -1 , sizeof(int), compare );
	MakeTeam(a, argc - 1);
}

Here is how it can be done: 2 step process:
1. divide into 2 teams as : the each team chooses a member from top and then on the next chance one from bottom. So you have 2 teams with equal number of players( or the first team having one member extra); also you have ensured the first team doesn't have a constant advantage over the second in every single pick. This doesn't really solve the problem completely, but the convergence will occur faster.
2. sum the skill set of each team; make out the difference (d) swap those team members, which cause the difference to decrease. It might be possible that even this will not solve the problem entire; in which case you might want to extend the solution to exchaging two member at a time ...and then 3 members at a time .... the objective at each step is to decrease the difference in skill sets (d) ....

Here is how it can be done: 2 step process:
1. divide into 2 teams as : the each team chooses a member from top and then on the next chance one from bottom. So you have 2 teams with equal number of players( or the first team having one member extra); also you have ensured the first team doesn't have a constant advantage over the second in every single pick. This doesn't really solve the problem completely, but the convergence will occur faster.
2. sum the skill set of each team; make out the difference (d) swap those team members, which cause the difference to decrease. It might be possible that even this will not solve the problem entire; in which case you might want to extend the solution to exchaging two member at a time ...and then 3 members at a time .... the objective at each step is to decrease the difference in skill sets (d) ....

Check Tug of war problem.
Same problem