With the Google Code Jam 2011 less than four weeks away, it is time for some finger exercises.
Let’s start with the Minimum Scalar Product, which should only take you a few minutes.
Here’s the Java version, which will only work for the small input set. I’ll explain later.
public static int getMinimumScalarProduct2(int[] x, int[] y) {
Arrays.sort(x);
Arrays.sort(y);
int sum=0;
for (int i = 0; i < x.length; i++) {
sum += x[i] * y[x.length -1 -i];
}
return sum;
}
What we do is sort both arrays, then multiply them. One starting from the beginning, the other from the end. So our biggest numbers are multiplied with the smallest. The math is on Google's solution page, we're just looking at coding here.
This works for the small input set, but not the large one. Why?
Take a look at the Limits:
Large dataset
T = 10
100 ? n ? 800
-100000 ? xi, yi ? 100000
The result of the large dataset will not fit in an int. So we switch to BigInteger, which can hold our results.
public static BigInteger getMinimumScalarProduct(int[] x, int[] y) {
Arrays.sort(x);
Arrays.sort(y);
BigInteger sum = BigInteger.ZERO;
for (int i = 0; i < x.length; i++) {
sum = sum.add( new BigInteger(""+ x[i]).multiply(new BigInteger(""+y[x.length -1 -i])));
}
return sum;
}
Take a look in the BigInteger API doc, I'm very sure you'll need it for this years jam. I initially made the mistake of not assigning the result of sum.add() to sum.
Now, as I try to do a bit python, I will also present my python solution. Maybe Christian can spot my classic java thinking and provide a more python like version for my lines.
f = open('../resources/codejam/msp-large.in', 'r')
cases = int(f.readline())
for i in range (0, cases):
nrOfIntegers = f.readline()
xs = f.readline()
ys = f.readline()
x = [int(s) for s in xs.split()]
y = [int(s) for s in ys.split()]
x.sort()
y.sort()
sum = 0
size = len(x)
for j in range(0, size):
sum+= int(x[j])* int(y[size -1 - j])
print sum
It's the exact same idea, so no suprises here.
Happy practicing.
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014