Googol: Google Code Jam 2008 - Minimum Scalar Product

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

as all that you gotta do, is to multiply the largest/smallest element from X-Array to smallest/largest element in Y-Array. If you are using Java, it is probable that your solution might pass through, for small input file, but not for the large one. This is because the data in the larger input file, might cause an overflow of the 'int' value. So, care should be taken to use 'BigInteger' or 'BigDecimal', instead of primitive 'int'. Here's the bare bones Java code, for that problem:

  public BigInteger findMin(String strXArr, String strYArr) {

    String[] xArr = strXArr.split(" ");

    String[] yArr = strYArr.split(" ");

 

    BigInteger res = new BigInteger("0");

    int len = xArr.length;    

    int[] iXArr = new int[len];

    int[] iYArr = new int[len];

 

    for(int i=0;i<len;i++) {

      iXArr[i] = Integer.parseInt(xArr[i]);

      iYArr[i] = Integer.parseInt(yArr[i]);

    }

 

    Arrays.sort(iXArr);

    Arrays.sort(iYArr);

 

    for(int i=0;i<len;i++) {                  

      res = res.add((new BigInteger("" + iXArr[i])).multiply(new BigInteger("" + iYArr[len-1-i])));      

    }

 

    return res;

  }

Read full article from Googol: Google Code Jam 2008 - Minimum Scalar Product