JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set
 Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply Now let's solve VectorMatching. In this problem we are given n points and we are asked to find a vector matching that has the minimal length. The number of points is small (n=20) which allows us to iterate over all possible vector matchings. A vector matching consists of two sets of points A and B, such that the head of the i-th vector is the i-th point in A and its tail is the i-th point in B. A and B should have the same number of elements, namely n/2. Each point can be either in set A or in set B, so we have 2^n possible states. However, we only need to consider those states where the size of A is n/2. This reduces the problem to Choose(20,10) = 185756 states.Suppose the point (x1,y1) is in A and the point (x2,y2) is in B. The vector represented by these two points is (x2-x1,y2-y1). Hence if a point is in A then it contributes negatively to the vector sum; otherwise it is in B and it contributes positively. So now we can determine the vector sum (which is a vector) as we iterate through the points in A and B; its x-component will be sumX and its y-component will be sumY:```public class VectorMatching { public double minimumLength(int[] x, int[] y) { double result = Double.MAX_VALUE; int n = x.length; for (int i = 0; i < (1 << n); i++) { //size of A and B must be n/2 if (2*Integer.bitCount(i) != n) continue;   long sumX = 0; long sumY = 0; for (int k = 0; k < n; k++) { //point (x[k],y[k]) is in B if ((i&(1< 0) { sumX += x[k]; sumY += y[k]; } //point (x[k],y[k]) is in A else { sumX -= x[k]; sumY -= y[k]; } }   double length=Math.sqrt(sumX*sumX + sumY*sumY); //vector length result = Math.min(result,length); //record the minimum length } return result; } } ```
 Subject Author Date Iterating Over All Subsets of a Set dimkadimon Apr 15, 2010 at 10:02 PM EDT Re: Iterating Over All Subsets of a Set dimkadimon Apr 15, 2010 at 10:04 PM EDT Re: Iterating Over All Subsets of a Set Nickolas Jun 28, 2010 at 2:33 AM EDT Re: Iterating Over All Subsets of a Set dimkadimon Sep 6, 2010 at 2:32 AM EDT Re: Iterating Over All Subsets of a Set codersx Jan 11, 2013 at 8:43 AM EST Re: Iterating Over All Subsets of a Set Eryx Nov 4, 2010 at 5:57 PM EDT Re: Iterating Over All Subsets of a Set savon_cn Jun 20, 2012 at 11:05 AM EDT Re: Iterating Over All Subsets of a Set dimkadimon Jul 26, 2012 at 1:08 AM EDT Re: Iterating Over All Subsets of a Set holomorph Aug 8, 2012 at 1:05 PM EDT Re: Iterating Over All Subsets of a Set d@rk_sh@dow Oct 27, 2014 at 3:09 PM EDT Re: Iterating Over All Subsets of a Set dimkadimon Nov 9, 2014 at 3:15 AM EST Re: Iterating Over All Subsets of a Set hacker007 Sep 9, 2012 at 7:54 AM EDT Re: Iterating Over All Subsets of a Set MauricioC Sep 9, 2012 at 2:44 PM EDT Re: Iterating Over All Subsets of a Set puneetm Oct 9, 2012 at 9:38 PM EDT Re: Iterating Over All Subsets of a Set dimkadimon Oct 9, 2012 at 11:34 PM EDT Re: Iterating Over All Subsets of a Set stubbscroll Oct 16, 2012 at 4:44 PM EDT Re: Iterating Over All Subsets of a Set sjsupersumit Jun 5, 2014 at 8:00 AM EDT Re: Iterating Over All Subsets of a Set d000hg Jun 9, 2014 at 9:46 AM EDT Re: Iterating Over All Subsets of a Set ZuBruce Jan 19, 2016 at 2:03 PM EST Re: Iterating Over All Subsets of a Set dimkadimon Jan 21, 2016 at 6:53 AM EST
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set Previous Thread  |  Next Thread