Google Code Jam 2008 - Minimum Scalar Product

Posted on August 15, 2009


Recently, I was just trying to solve some problems from GCJ - 2008 and started off with a problem, which looked pretty easy. This problem is from the 'Round 1 A' and is called 'Minimum Scalar Product'. The problem statement is as below:

Problem
-------

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.

Input
-----

The first line of the input file contains integer number T - the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.
Output

For each test case, output a line
Case #X: Y
where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.

Limits
------

Small dataset
-------------

T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000

Large dataset
-------------

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

Sample Input
------------

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Output
------

Case #1: -25
Case #2: 6


The solution for the above problem is pretty easy, 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:



After reading the input from the file, I pass the X-Array (v1) and Y-Array (v2), to the above method, get the result and write back to the output file. Thats it! :-)

Blog Categories
Disclaimer
The views expressed on this blog are my personal views and do not reflect the views of my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.