KGS math club/solution 11 2

Revision as of 11:44, 14 February 2011 by Maproomad (talk | contribs) (added credit, C code)

Given n, k, and a k-member subset K of the n-member set N, we form the (n-k)-member subset it is paired with as follows.

Assign integers modulo n to the members of N, and cyclically order its members using them. Remove from N a member of K with a non-member of K that immediately follows it; and repeat until there are no members of K left. Append what we have left to K.

Solution by iceweasel.

He also supplied this C code to compute it:

main(int a, char **v) {

 int n=atoi(v[1]), 
 ss=atoi(v[2]),
 x0=0,
 x1=0,
 m;  
 for ( m=1<<n ; m>>=1 ; (m&ss?(x1|=m):x1?(x1&=(x1-1)):(x0|=m)) );  
 for ( m=1<<n ; m>>=1 ; m&x0&&x1&&(x1&=(x0^=m,x1-1)) );   
 printf("%d\n",ss^x0^x1); 

}