JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Re: Iterating Over All Subsets of a Set Revision History (1 edit)
 Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) 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; } } ```
 Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) 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 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++) { if (2*Integer.bitCount(i) != n) continue; //size of A and B must be n/2   long sumX = 0; long sumY = 0; for (int k = 0; k < n; k++) { //point in B if ((i&(1< 0) { sumX += x[k]; sumY += y[k]; } //point in A else { sumX -= x[k]; sumY -= y[k]; } }   double length=Math.sqrt(sumX*sumX + sumY*sumY); //vector length result = Math.min(result,length); } return result; } } ```